A000352 One half of the number of permutations of [n] such that the differences have three runs with the same signs.
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
Offset: 4
Keywords
Examples
a(4)=5 because the permutations of [4] with three sign runs are 1324, 1423, 2143, 2314, 2413 and their reversals.
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).
Programs
-
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 *) -
PARI
a(n) = (3^n-4*2^n-2*n+11)/4;
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
Extensions
Edited by Emeric Deutsch, Feb 18 2004