|
Search: id:A001100
|
|
|
| A001100 |
|
Triangle read by rows: T(n,k) = number of permutations of length n with exactly k rising or falling successions, for n >= 1, 0 <= k <= n-1. |
|
+0
9
|
|
| 1, 0, 2, 0, 4, 2, 2, 10, 10, 2, 14, 40, 48, 16, 2, 90, 230, 256, 120, 22, 2, 646, 1580, 1670, 888, 226, 28, 2, 5242, 12434, 12846, 7198, 2198, 366, 34, 2, 47622, 110320, 112820, 64968, 22120, 4448, 540, 40, 2, 479306, 1090270, 1108612, 650644, 236968, 54304, 7900, 748
(list; table; graph; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
Number of permutations of 12...n such that exactly k of the following occur: 12, 23, ..., (n-1)n, 21, 32, ..., n(n-1).
|
|
REFERENCES
|
F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 263.
J. Riordan, A recurrence for permutations without rising or falling successions. Ann. Math. Statist. 36 (1965), 708-710.
David Sankoff and Lani Haque, Power Boosts for Cluster Tests, in Comparative Genomics, Lecture Notes in Computer Science, Volume 3678/2005, Springer-Verlag. [Added by N. J. A. Sloane, Jul 09 2009]
|
|
FORMULA
|
Let T{n, k} = number of permutations of 12...n with exactly k rising or falling successions. Let S[n](t) = Sum_{k >= 0} T{n, k}*t^k. Then S[0] = 1; S[1] = 1; S[2] = 2*t; S[3] = 4*t+2*t^2; for n >= 4, S[n] = (n+1-t)*S[n-1] - (1-t)*(n-2+3*t)*S[n-2] - (1-t)^2*(n-5+t)*S[n-3] + (1-t)^3*(n-3)*S[n-4].
|
|
EXAMPLE
|
1; 0,2; 0,4,2; 2,10,10,2; 14,40,48,16,2; ...
|
|
CROSSREFS
|
Diagonals give A002464, A086852, A086853, A086854, A086955.
Triangle in A086856 multiplied by 2. Cf. A010028.
Adjacent sequences: A001097 A001098 A001099 this_sequence A001101 A001102 A001103
Sequence in context: A037035 A159984 A112824 this_sequence A136265 A066910 A094405
|
|
KEYWORD
|
tabl,nonn
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com), Aug 19 2003
|
|
|
Search completed in 0.002 seconds
|
