|
| |
|
|
A145878
|
|
Triangle read by rows: T(n,k) is the number of permutations of [n] having k strong fixed points (0<=k<=n). 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.
|
|
4
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 0,7
|
|
|
COMMENTS
| Row sums are the factorials (A000142).
T(n,0)=A052186(n).
Sum(T(n,k),k=1..n)=A006932(n).
Sum(k*T(n,k),k=0..n)=A003149(n-1).
Conjectures: 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.
The first Maple program, in the present form, yields row 7 of the triangle. Row n (0<=n<=10) is obtained by changing the value of n at the beginning of the program.
|
|
|
REFERENCES
| Stanley, R. P., Enumerative Combinatorics, Volume 1 (1986), p. 49.
Problem E3467, Amer. Math. Monthly, 100 (1993), 800-801.
|
|
|
LINKS
| Nathaniel Johnston, Table of n, a(n) for n = 0..5050
V. Strehl, The average number of splitters in a random permutation [Unpublished; included here with the author's permission.]
|
|
|
FORMULA
| 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). [From Paul Barry (pbarry(AT)wit.ie), Dec 09 2009]
|
|
|
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
|
|
|
CROSSREFS
| Cf. A000142, A052861, A006932, A003149.
Sequence in context: A118972 A171224 A193233 * A195662 A112606 A108512
Adjacent sequences: A145875 A145876 A145877 * A145879 A145880 A145881
|
|
|
KEYWORD
| nonn,tabl
|
|
|
AUTHOR
| Emeric Deutsch (deutsch(AT)duke.poly.edu), Oct 29 2008
|
| |
|
|
