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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A008970 Triangle T(n,k) = P(n,k)/2, n >= 2, 1<=k<n, of one-half of number of permutations of 1..n such that the differences have k runs with the same signs. 11
1, 1, 2, 1, 6, 5, 1, 14, 29, 16, 1, 30, 118, 150, 61, 1, 62, 418, 926, 841, 272, 1, 126, 1383, 4788, 7311, 5166, 1385, 1, 254, 4407, 22548, 51663, 59982, 34649, 7936, 1, 510, 13736, 100530, 325446, 553410, 517496, 252750, 50521, 1, 1022, 42236 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

2,3

REFERENCES

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 261, #13, P_{n,k}.

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 260, Table 7.2.1.

LINKS

Vincenzo Librandi, Rows n = 2..100, flattened

M. Bona and R. Ehrenborg, A combinatorial proof of the log-concavity of the numbers of permutations with k runs, arXiv:math/9902020 [math.CO], 1999.

F. Morley, A generating function for the number of permutations with an assigned number of sequences, Bull. Amer. Math. Soc. 4 (1897), 23-28. Shows the transpose of this triangle.

FORMULA

Let P(n, k) = number of permutations of [1..n] with k "sequences". Note that A008970 gives P(n, k)/2. Then g.f.: Sum_{n, k} P(n, k)*u^k*t^n/n! = (1+u)^(-1)*((1-u)*(1-sin(v+t*cos(v))-1) where u = sin v.

P(n, 1)=2, P(n, k) = k*P(n-1, k) + 2*P(n-1, k-1) + (n-k)*P(n-1, k-2).

EXAMPLE

Triangle starts

1;

1,2;

1,6,5;

1,14,29,16;

...

MATHEMATICA

p[n_ /; n >= 2, 1] = 2; p[n_ /; n >= 2, k_] /; 1 <= k <= n := p[n, k] = k*p[n-1, k] + 2*p[n-1, k-1] + (n-k)*p[n-1, k-2]; p[n_, k_] = 0; t[n_, k_] := p[n, k]/2; A008970 = Flatten[ Table[ t[n, k], {n, 2, 11}, {k, 1, n-1}]] (* Jean-Fran├žois Alcover, Apr 03 2012, after given recurrence *)

CROSSREFS

Diagonals give A000352, A000486, A000506, A000111, A000708, A091303. A059427 gives triangle of P(n, k).

Sequence in context: A193817 A227159 A294439 * A055896 A193723 A260914

Adjacent sequences:  A008967 A008968 A008969 * A008971 A008972 A008973

KEYWORD

tabl,nonn,easy,nice

AUTHOR

N. J. A. Sloane.

EXTENSIONS

More terms from Larry Reeves (larryr(AT)acm.org), Feb 01 2001

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 February 24 11:12 EST 2018. Contains 299603 sequences. (Running on oeis4.)