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
KEYWORD
AUTHOR
EXTENSIONS
More terms from Larry Reeves (larryr(AT)acm.org), Feb 01 2001
STATUS
approved