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
Examples
Triangle starts 1; 1, 2; 1, 6, 5; 1, 14, 29, 16; 1, 30, 118, 150, 61; ...
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.
Crossrefs
Programs
-
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 *)
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).
Extensions
More terms from Larry Reeves (larryr(AT)acm.org), Feb 01 2001