|
|
A145878
|
|
Triangle read by rows: T(n,k) is the number of permutations of [n] having k strong fixed points (0 <= k <= n).
|
|
5
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,7
|
|
COMMENTS
|
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.
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
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
|
|
REFERENCES
|
Stanley, R. P., Enumerative Combinatorics, Volume 1 (1986), p. 49.
|
|
LINKS
|
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.
|
|
FORMULA
|
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
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)
|
|
EXAMPLE
|
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;
|
|
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 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|