|
Search: id:A094067
|
|
|
| A094067 |
|
Triangle read by rows: T(n,k) is the number of permutations p of [n] in which the length of the longest initial segment avoiding the 123-, the 132-, and the 321-pattern is equal to k. |
|
+0 1
|
|
| 1, 0, 2, 0, 3, 3, 0, 12, 7, 5, 0, 60, 35, 17, 8, 0, 360, 210, 102, 35, 13, 0, 2520, 1470, 714, 245, 70, 21, 0, 20160, 11760, 5712, 1960, 560, 134, 34, 0, 181440, 105840, 51408, 17640, 5040, 1206, 251, 55, 0, 1814400, 1058400, 514080, 176400, 50400, 12060
(list; table; graph; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
Row sums are the factorial numbers (A000142). Diagonal yields the Fibonacci numbers A000045.
|
|
REFERENCES
|
E. Deutsch and W. P. Johnson, Create your own permutation statistic, Math. Mag., 77, 130-134, 2004.
R. Simion and F. W. Schmidt, Restricted permutations, European J. Combin., 6, 383-406, 1985.
|
|
FORMULA
|
T(n, k)= n!*[(k+1)fibonacci(k+1)-fibonacci(k+2)]/(k+1)! for 1<=k<=n-1; T(1, 1)=1; T(n, n)=fibonacci(n+1).
|
|
EXAMPLE
|
T(4,3)=7 because the permutations 4132, 3124, 2413, 4213, 2314, and 3214 do not avoid all three patterns 123, 132, and 213, but their initial segments
of length three, namely 413, 312, 241, 421, 231, and 321, do.
1; 0,2; 0,3,3; 0,12,7,5; 0,60,35,17,8; 0,360,210,102,35,13; 0,2520,1470,714,245,70,21;
|
|
MAPLE
|
with(combinat): T:=proc(n, k) if n=1 and k=1 then 1 elif n=1 then 0 elif k=1 then 0 elif k=n then fibonacci(n+1) elif k>0 and k<n then n!*((k+1)*fibonacci(k+1)-fibonacci(k+2))/(k+1)! else 0 fi end: seq(seq(T(n, k), k=1..n), n=1..11);
|
|
CROSSREFS
|
Cf. A000142, A000045.
Sequence in context: A053727 A127952 A134409 this_sequence A094112 A105569 A068455
Adjacent sequences: A094064 A094065 A094066 this_sequence A094068 A094069 A094070
|
|
KEYWORD
|
nonn,tabl
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), May 31 2004
|
|
|
Search completed in 0.002 seconds
|