|
%I #64 Dec 14 2018 20:47:24
%S 1,0,1,1,0,1,3,2,0,1,14,6,3,0,1,77,29,9,4,0,1,497,160,45,12,5,0,1,
%T 3676,1031,249,62,15,6,0,1,30677,7590,1603,344,80,18,7,0,1,285335,
%U 63006,11751,2214,445,99,21,8,0,1,2928846,583160,97056,16168,2865,552,119,24
%N Triangle read by rows: T(n,k) is the number of permutations of [n] having k strong fixed points (0 <= k <= n).
%C A permutation p of {1,2,...,n} is said to have j as a strong fixed point (splitter) if p(k) < j for k < j and p(k) > j for k > j.
%C T(n,k) is also the number of permutation graphs on n vertices with exactly k distinct dominating sets of size one. See the link by Theresa Baren, et al. -_Daniel A. McGinnis_, Oct 16 2018
%C The values T(k+r,k) are given as a polynomial expression in k when r is fixed, and the polynomial expressions can be calculated recursively. See the link by Theresa Baren, et al. -_Daniel A. McGinnis_, Oct 19 2018
%D Stanley, R. P., Enumerative Combinatorics, Volume 1 (1986), p. 49.
%H Nathaniel Johnston, <a href="/A145878/b145878.txt">Table of n, a(n) for n = 0..5050</a>
%H Theresa Baren, Michael Cory, Mia Friedberg, Peter Gardner, James Hammer, Joshua Harrington, Daniel McGinnis, Riley Waechter, Tony W. H. Wong, <a href="https://arxiv.org/abs/1810.03409">On the Domination Number of Permutation Graphs and an Application to Strong Fixed Points</a>, arXiv:1810.03409 [math.CO], 2018.
%H Todd Feil, Gary Kennedy and David Callan, <a href="http://www.jstor.org/stable/2324797">Problem E3467</a>, Amer. Math. Monthly, 100 (1993), 800-801.
%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/StatisticsDatabase/St000221/">The number of strong fixed points</a>
%H V. Strehl, <a href="/A003149/a003149.pdf">The average number of splitters in a random permutation</a> [Unpublished; included here with the author's permission.]
%F T(n,0) = A052186(n).
%F Sum_{k=1..n} T(n,k) = A006932(n).
%F Sum_{k=0..n} k*T(n,k) = A003149(n-1).
%F G.f.: 1/(1-xy-x^2/(1-3x-4x^2/(1-5x-9x^2/(1-7x-16x^2/(1-9x-25x^2/(1-... (continued fraction). - _Paul Barry_, Dec 09 2009
%F G.f.: 1/(1-(I(x)- x + y*x)) where I(x) is o.g.f. for A003319. - _Geoffrey Critzer_, Apr 27 2012
%F From _Daniel A. McGinnis_, Oct 15 2018: (Start)
%F T(n,k) = Sum_{i=1..n-k+1} T(n-i,k-1)*T(i-1,0).
%F T(3+k,k)=3k+3, T(4+k,k)=(k+1)(k+28)/2, T(5+k,k)=(k+1)(3k+77), T(6+k,k)=(k+1)(k^2+110k+2982)/6, T(7+k,k)=(k+1)(3k^2+235k+7352)/2 (previous conjectures).
%F See the link by Theresa Baren, et al. (End)
%e T(5,3) = 4 because we have 1'2'3'54, 1'2'435', 1'324'5' and 213'4'5' (the strong fixed points are marked).
%e Triangle starts:
%e 1;
%e 0, 1;
%e 1, 0, 1;
%e 3, 2, 0, 1;
%e 14, 6, 3, 0, 1;
%e 77, 29, 9, 4, 0, 1;
%p n:=7: sfix:=proc(p) local ct,i: ct:= 0: for i to nops(p) do if p[i]=i and `subset`({seq(p[j],j=1..i-1)},{seq(k,k=1..i-1)})=true then ct:=ct+1 else end if end do: ct end proc: with(combinat): P:=permute(n): s:=[seq(sfix(P[j]),j= 1..factorial(n))]: for i from 0 to n do a[i]:=0 end do: for j to factorial(n) do if s[j]=0 then a[0]:=a[0]+1 elif s[j]=1 then a[1]:=a[1]+1 elif s[j]=2 then a[2]:=a[2]+1 elif s[j]=3 then a[3]:=a[3]+1 elif s[j]=4 then a[4]:=a[4]+1 elif s[j]=5 then a[5]:=a[5]+1 elif s[j]=6 then a[6]:=a[6]+1 elif s[j]=7 then a[7]:= a[7]+1 elif s[j]=8 then a[8]:=a[8]+1 elif s[j]=9 then a[9]:=a[9]+1 elif s[j]= 10 then a[10]:=a[10]+1 end if end do: seq(a[k],k=0..n); # yields row m of the triangle, where m is the value of n specified at the beginning of the program
%p n:=7: G:=1:for r from n to 2 by -1 do G:=1-(2*r-1)*z-(r^2*z^2)/G:od:G:=1/(1-t*z-z^2/G):
%p Gser := simplify(series(G, z = 0, n+1)): for m from 0 to n do seq(coeff(coeff(Gser, z, m), t, k), k = 0 .. m) end do; # based on P. Barry's g.f.; yields sequence in triangular form
%t nn=10;p=Sum[n!x^n,{n,0,nn}];i=1-1/p;CoefficientList[Series[1/(1-(i-x+y x)),{x,0,nn}],{x,y}]//Grid (* _Geoffrey Critzer_, Apr 27 2012 *)
%Y Row sums gives A000142.
%Y Cf. A052861, A006932, A003149.
%K nonn,tabl
%O 0,7
%A _Emeric Deutsch_, Oct 29 2008
|
