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.

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, 433162, 1910706, 4474002, 6031076, 4717222, 1995181, 353792

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

Désiré André, Mémoire sur les permutations alternées, J. Math. Pur. Appl., 7 (1881), 167-184.

Désiré André, Etude sur les maxima, minima et sequences des permutations, Ann. Sci. Ecole Norm. Sup., 3, no. 1 (1884), 121-135.

Désiré André, Mémoire sur les permutations quasi-alternées, Journal de mathématiques pures et appliquées 5e série, tome 1 (1895), 315-350.

Désiré André, Mémoire sur les séquences des permutations circulaires, Bulletin de la S. M. F., tome 23 (1895), pp. 122-184.

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;
  1, 30, 118, 150, 61;
  ...

Maple

T:= proc(n, k) option remember; `if`(n<2, 0, `if`(k=1, 1,
      k*T(n-1, k) + 2*T(n-1, k-1) + (n-k)*T(n-1, k-2)))
    end:
seq(seq(T(n, k), k=1..n-1), n=2..12);  # Alois P. Heinz, Feb 08 2023

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).

A008303 gives circular version of P(n, k).

T(2n,n) gives A360426.

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