A360426 -id:A360426 - cp's OEIS frontend

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

N. J. A. Sloane

			Triangle starts
  1;
  1,  2;
  1,  6,   5;
  1, 14,  29,  16;
  1, 30, 118, 150, 61;
  ...

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.

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.

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.

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

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

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

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

A059427 Triangle read by rows: T(n,k) is the number of permutations of [n] with k alternating runs (n>=2, k>=1).

Original entry on oeis.org

2, 2, 4, 2, 12, 10, 2, 28, 58, 32, 2, 60, 236, 300, 122, 2, 124, 836, 1852, 1682, 544, 2, 252, 2766, 9576, 14622, 10332, 2770, 2, 508, 8814, 45096, 103326, 119964, 69298, 15872, 2, 1020, 27472, 201060, 650892, 1106820, 1034992, 505500, 101042, 2, 2044

Offset: 2

N. J. A. Sloane, Jan 31 2001

The permutation 732569148 has 4 alternating runs: 732, 2569, 91 and 148.

			T(3,2) = 4 because each of the permutations 132, 312, 213, 231 has two alternating runs: (13, 32), (31, 12), (21, 13), (23, 31); each of 123 and 321 has 1 alternating run.
Triangle (with rows n >= 2 and columns k >= 1) begins as follows:
  2;
  2,   4;
  2,  12,  10;
  2,  28,  58,   32;
  2,  60, 236,  300,  122;
  2, 124, 836, 1852, 1682, 544;
  ...

L. Comtet, Advanced Combinatorics, Reidel, Dordrecht, Holland, 1974, p. 261, #13.
F. N. David and D. E. Barton, Combinatorial Chance, Hafner, NY, 1962, pp. 157-162.
F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 262, Table 7.2.1 doubled.
D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1973, Vol. 3, pp. 46 and 587-8.

T. D. Noe, Rows n = 2..50 of triangle, flattened
Désiré André, Sur les permutations alternées, J. Math. Pur. Appl., 7 (1881), 167-184.
Désiré André, Étude sur les maxima, minima et séquences 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, J. Comb. Theory, Ser. A, 90, 293-303, 2003.
E. Rodney Canfield and Herbert S. Wilf, Counting permutations by their runs up and down, arXiv:math/0609704 [math.CO], 2006.
E. R. Canfield and H. S. Wilf, Counting permutations by their alternating runs, J. Combin. Theory Ser. A 115 (2008), 213-225.
L. Carlitz, Enumeration of permutations by sequences, Fib. Quart., 16 (1978), 259-268.
L. Carlitz, The number of permutations with a given number of sequences, Fib. Quart., 18 (1980), 347-352.
C.-O. Chow and S.-M. Ma, Counting signed permutations by their alternating runs, Discrete Mathematics, Volume 323, 28 May 2014, Pages 49-57.
C.-O. Chow, S.-M. Ma, T. Mansour, and M. Shattuck, Counting permutations by cyclic peaks and valleys, Annales Mathematicae et Informaticae, (2014), Vol. 43, pp. 43-54.
Qi Fang, Ya-Nan Feng, and Shi-Mei Ma, Alternating runs of permutations and the central factorial numbers, arXiv:2202.13978 [math.CO], 2022.
Ira M. Gessel and Yan Zhuang, Counting permutations by alternating descents , arXiv:1408.1886 [math.CO], 2014.
Shi-Mei Ma, An explicit formula for the number of permutations with a given number of alternating runs, arXiv preprint arXiv:1110.6779 [math.CO], 2011 [Version 1 references the OEIS and sequence A059427; this reference was deleted in Version 2]
Shi-Mei Ma, Enumeration of permutations by number of alternating runs, arXiv:1110.5014 [math.CO], 2011-2012.
Shi-Mei Ma, Enumeration of permutations by number of alternating runs, Discrete Math., 313 (2013), 1816-1822.
S.-M. Ma, T. Mansour and D. G. L. Wang, Combinatorics of Dumont differential system on the Jacobi elliptic functions, arXiv preprint arXiv:1403.0233 [math.CO], 2014-2018.
S.-M. Ma and T. Mansour, The 1/k-Eulerian polynomials and k-Stirling permutations, arXiv preprint arXiv:1409.6525 [math.CO], 2014.
Shi-Mei Ma and Hai-Na Wang, Enumeration of a dual set of Stirling permutations by their alternating runs, arXiv:1506.08716 [math.CO], 2015.
R. P. Stanley, Longest alternating subsequences of permutations, arXiv:math/0511419 [math.CO], 2005.
R. P. Stanley, Longest alternating subsequences of permutations, Michigan Math. J. 57 (2008), 675-687.
Yan Zhuang, Monoid networks and counting permutations by runs, arXiv preprint arXiv:1505.02308 [math.CO], 2015-2016.
Y. Zhuang, Counting permutations by runs, J. Comb. Theory Ser. A 142 (2016), pp. 147-176.

Diagonals give A001250, A001758. Column k = 2 is A028399.
Cf. A008303 (circular version of this array), A008970.
T(2n,n) gives 2*A360426.

P := proc(n,k) if n<2 or k<1 or k>=n then 0 elif n=2 and k=1 then 2 else k*P(n-1,k)+2*P(n-1,k-1)+(n-k)*P(n-1,k-2) fi end: p:=(n,k)->P(n+1,k): matrix(9,9,p);

t[n_, k_] := t[n, k] = k*t[n-1, k] + 2*t[n-1, k-1] + (n-k)*t[n-1, k-2];
t[2, 1] = 2; t[n_, k_] /; n < 2 || k < 1 || k >= n = 0;
Flatten[Table[t[n, k], {n,2,11}, {k, 1, n-1}]][[1 ;; 47]]
(* Jean-François Alcover, Jun 16 2011, after recurrence *)

P(n, k) = 0 if n < 2 or k < 1 or k >= n; P(2, 1) = 2; P(n, k) = k*P(n-1, k) + 2*P(n-1, k-1) + (n-k)*P(n-1, k-2) [André]. - Emeric Deutsch, Feb 21 2004
The row generating polynomials P[n] satisfy P[n] = t*[(1 - t^2) * dP[n-1]/dt + (2 + (n-2) * t) * P[n-1]] and P[2] = 2*t.
T(n, n-1) = 2*A000111(n) = A001250(n-1).
T(n, k) = k*T(n-1, k) + 2*T(n-1, k-1) + (n-k)*T(n-1, k-2), where we set T(2, 1) = 2 and T(n, k) = 0 if n < 2 or k < 1 or k >= n.
E.g.f.: Sum_{n, k >= 0} T(n, k) * x^n * t^k/n! = 2*(1 - t^2 + t * sqrt(1-t^2) * sinh(x * sqrt(1 - t^2)))/((1 + t)^2*(1-t*cosh(x * sqrt(1 - t^2)))) - 2(1 + t*x)/(1 + t).
T(n, k) = 2*A008970(n, k).

Edited by Emeric Deutsch and Ira M. Gessel, Dec 06 2004

André reference from Philippe Deléham, Jul 26 2006

cp's OEIS Frontend

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.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions