|
| |
|
|
A000352
|
|
One half of the number of permutations of [n] such that the differences have three runs with the same signs.
(Formerly M3954 N1629)
|
|
4
| |
|
|
5, 29, 118, 418, 1383, 4407, 13736, 42236, 128761, 390385, 1179354, 3554454, 10696139, 32153963, 96592972, 290041072, 870647517, 2612991141, 7841070590, 23527406090, 70590606895, 211788597919, 635399348208, 1906265153508
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 4,1
|
|
|
REFERENCES
| L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 260, #13
F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 260.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
| E. Rodney Canfield and Herbert S. Wilf, Counting permutations by their runs up and down
S. Plouffe, Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
S. Plouffe, 1031 Generating Functions and Conjectures, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
|
|
|
FORMULA
| a(n) = (3^n-4*2^n-2*n+11)/4, n>=4. - Tim Monahan, Jul 14 2011
G.f.: x^4*(5-6*x)/((1-3*x)*(1-2*x)*(1-x)^2).
4*a(n)/3^n -> 1 as n -> infinity . - DELEHAM Philippe, Feb 22 2004
|
|
|
EXAMPLE
| a(4)=5 because the permutations of [4] with three sign runs are 1324, 1423, 2143, 2314, 2413 and their reversals.
|
|
|
MAPLE
| A000352:=-(-5+6*z)/(3*z-1)/(2*z-1)/(z-1)**2; [Conjectured by S. Plouffe in his 1992 dissertation.] [correct up to offset]
a:= n-> (Matrix([[0, 0, 1, 2]]). Matrix(4, (i, j)-> if (i=j-1) then 1 elif j=1 then [7, -17, 17, -6][i] else 0 fi)^n)[1, 4]; seq (a(n), n=4..27); [From Alois P. Heinz, Aug 26 2008]
|
|
|
PROG
| (PARI) a(n) = (3^n-4*2^n-2*n+11)/4;
|
|
|
CROSSREFS
| a(n)=T(n, 3), where T(n, k) is the array defined in A008970. Cf. A000486, A000506.
Sequence in context: A085151 A119494 A153077 * A034332 A146053 A163082
Adjacent sequences: A000349 A000350 A000351 * A000353 A000354 A000355
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| Edited by Emeric Deutsch (deutsch(AT)duke.poly.edu), Feb 18 2004
|
| |
|
|
