|
| |
|
|
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, 5718929678273, 17157057470297
(list;
graph;
refs;
listen;
history;
text;
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
|
T. D. Noe, Table of n, a(n) for n = 4..400
E. Rodney Canfield and Herbert S. Wilf, Counting permutations by their runs up and down, arXiv:math/0609704 [math.CO], 2006.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Index entries for linear recurrences with constant coefficients, signature (7,-17,17,-6).
|
|
|
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).
Limit_{n->infinity} 4*a(n)/3^n = 1. - Philippe Deléham, 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 Simon Plouffe in his 1992 dissertation.] [correct up to offset]
# second Maple program:
a:= n-> (<<0|0|1|2>>. <<7|1|0|0>, <-17|0|1|0>, <17|0|0|1>, <-6|0|0|0>>^n)[1, 4]:
seq(a(n), n=4..30); # Alois P. Heinz, Aug 26 2008
|
|
|
MATHEMATICA
|
nn = 40; CoefficientList[Series[x^4*(5 - 6*x)/((1 - 3*x)*(1 - 2*x)*(1 - x)^2), {x, 0, nn}], x] (* T. D. Noe, Jun 19 2012 *)
|
|
|
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: A268244 A297632 A153077 * A327133 A267921 A241676
Adjacent sequences: A000349 A000350 A000351 * A000353 A000354 A000355
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
N. J. A. Sloane
|
|
|
EXTENSIONS
|
Edited by Emeric Deutsch, Feb 18 2004
|
|
|
STATUS
|
approved
|
| |
|
|
