|
%I #38 Feb 09 2023 09:50:34
%S 1,1,2,1,6,5,1,14,29,16,1,30,118,150,61,1,62,418,926,841,272,1,126,
%T 1383,4788,7311,5166,1385,1,254,4407,22548,51663,59982,34649,7936,1,
%U 510,13736,100530,325446,553410,517496,252750,50521,1,1022,42236,433162,1910706,4474002,6031076,4717222,1995181,353792
%N 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.
%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 261, #13, P_{n,k}.
%D F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 260, Table 7.2.1.
%H Vincenzo Librandi, <a href="/A008970/b008970.txt">Rows n = 2..100, flattened</a>
%H Désiré André, <a href="http://sites.mathdoc.fr/JMPA/PDF/JMPA_1881_3_7_A10_0.pdf">Mémoire sur les permutations alternées</a>, J. Math. Pur. Appl., 7 (1881), 167-184.
%H Désiré André, <a href="https://doi.org/10.24033/asens.235">Etude sur les maxima, minima et sequences des permutations</a>, Ann. Sci. Ecole Norm. Sup., 3, no. 1 (1884), 121-135.
%H Désiré André, <a href="http://sites.mathdoc.fr/JMPA/PDF/JMPA_1895_5_1_A7_0.pdf">Mémoire sur les permutations quasi-alternées</a>, Journal de mathématiques pures et appliquées 5e série, tome 1 (1895), 315-350.
%H Désiré André, <a href="https://doi.org/10.24033/bsmf.519">Mémoire sur les séquences des permutations circulaires</a>, Bulletin de la S. M. F., tome 23 (1895), pp. 122-184.
%H M. Bona and R. Ehrenborg, <a href="https://arxiv.org/abs/math/9902020">A combinatorial proof of the log-concavity of the numbers of permutations with k runs</a>, arXiv:math/9902020 [math.CO], 1999.
%H F. Morley, <a href="http://dx.doi.org/10.1090/S0002-9904-1897-00451-7">A generating function for the number of permutations with an assigned number of sequences</a>, Bull. Amer. Math. Soc. 4 (1897), 23-28. Shows the transpose of this triangle.
%F 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).
%F 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).
%e Triangle starts
%e 1;
%e 1, 2;
%e 1, 6, 5;
%e 1, 14, 29, 16;
%e 1, 30, 118, 150, 61;
%e ...
%p T:= proc(n, k) option remember; `if`(n<2, 0, `if`(k=1, 1,
%p k*T(n-1, k) + 2*T(n-1, k-1) + (n-k)*T(n-1, k-2)))
%p end:
%p seq(seq(T(n,k), k=1..n-1), n=2..12); # _Alois P. Heinz_, Feb 08 2023
%t 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 *)
%Y Diagonals give A000352, A000486, A000506, A000111, A000708, A091303.
%Y A059427 gives triangle of P(n, k).
%Y A008303 gives circular version of P(n, k).
%Y T(2n,n) gives A360426.
%K tabl,nonn,easy,nice
%O 2,3
%A _N. J. A. Sloane_
%E More terms from Larry Reeves (larryr(AT)acm.org), Feb 01 2001
|
