A145878 Triangle read by rows: T(n,k) is the number of permutations of [n] having k strong fixed points (0 <= k <= n).
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, 3676, 1031, 249, 62, 15, 6, 0, 1, 30677, 7590, 1603, 344, 80, 18, 7, 0, 1, 285335, 63006, 11751, 2214, 445, 99, 21, 8, 0, 1, 2928846, 583160, 97056, 16168, 2865, 552, 119, 24
Offset: 0
Examples
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). Triangle starts: 1; 0, 1; 1, 0, 1; 3, 2, 0, 1; 14, 6, 3, 0, 1; 77, 29, 9, 4, 0, 1;
References
- Stanley, R. P., Enumerative Combinatorics, Volume 1 (1986), p. 49.
Links
- Nathaniel Johnston, Table of n, a(n) for n = 0..5050
- Theresa Baren, Michael Cory, Mia Friedberg, Peter Gardner, James Hammer, Joshua Harrington, Daniel McGinnis, Riley Waechter, Tony W. H. Wong, On the Domination Number of Permutation Graphs and an Application to Strong Fixed Points, arXiv:1810.03409 [math.CO], 2018.
- Todd Feil, Gary Kennedy and David Callan, Problem E3467, Amer. Math. Monthly, 100 (1993), 800-801.
- FindStat - Combinatorial Statistic Finder, The number of strong fixed points
- V. Strehl, The average number of splitters in a random permutation [Unpublished; included here with the author's permission.]
Programs
-
Maple
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 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): 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 -
Mathematica
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 *)
Formula
T(n,0) = A052186(n).
Sum_{k=1..n} T(n,k) = A006932(n).
Sum_{k=0..n} k*T(n,k) = A003149(n-1).
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
G.f.: 1/(1-(I(x)- x + y*x)) where I(x) is o.g.f. for A003319. - Geoffrey Critzer, Apr 27 2012
From Daniel A. McGinnis, Oct 15 2018: (Start)
T(n,k) = Sum_{i=1..n-k+1} T(n-i,k-1)*T(i-1,0).
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).
See the link by Theresa Baren, et al. (End)
Comments