login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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; 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.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montré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).

Lim_{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]

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); # 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: A268929 A268244 A153077 * A267921 A241676 A217325

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 24 21:52 EDT 2017. Contains 283999 sequences.