login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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.
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.]
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)
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
Row sums gives A000142.
Sequence in context: A270741 A212220 A193233 * A195662 A340860 A112606
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Oct 29 2008
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:56 EDT 2024. Contains 370952 sequences. (Running on oeis4.)