A008303 Triangle read by rows: T(n,k) (n >= 1, 0 <= k <= ceiling(n/2)-1) = number of permutations of [n] with k peaks.

1, 2, 4, 2, 8, 16, 16, 88, 16, 32, 416, 272, 64, 1824, 2880, 272, 128, 7680, 24576, 7936, 256, 31616, 185856, 137216, 7936, 512, 128512, 1304832, 1841152, 353792, 1024, 518656, 8728576, 21253376, 9061376, 353792, 2048, 2084864, 56520704, 222398464, 175627264, 22368256

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• tabf

Comments

From Petros Hadjicostas, Aug 06 2019: (Start)

André (1895) first defined these numbers. In his notation, T(n, k) = Q(n+1, 2*(k+1)) for n >= 1 and 0 <= k <= ceiling(n/2)-1.

His triangle is as follows (p. 148):

Q_{2,2}

Q_{3,2}

Q_{4,2} Q_{4,4}

Q_{5,2} Q_{5,4}

Q_{6,2} Q_{6,4} Q_{6,6}

Q_{7,2} Q_{7,4} Q_{7,6}

...

He has Q(n, s) = 0 when either s is odd, or n <= 1, or s > n. Also, Q_{n,2} = 2^(n-2) for n >= 2.

His recurrence is Q(n, s) = s * Q(n-1, s) + (n - s + 1) * Q(n-1, s-2) for n >= 3 and s >= 2. (Obviously, for s odd, we get Q(n, s) = 0 + 0 = 0.)

In terms of the current array, André's (1895) recurrence becomes T(n, k) = (2*k + 2) * T(n-1, k) + (n - 2*k) * T(n-1, k-1) for n >= 2 and 1 <= k <= n with T(n, 0) = 2^(n-1) for n >= 1. In this recurrence, we assume T(n, k) = 0 for k >= ceiling(n/2) or k < 0.

(End)

From Petros Hadjicostas, Aug 07 2019: (Start)

We clarify further the quantity Q(n, s) defined by André (1895). In his paper, André considers circular permutations of [n] and deals with maxima, minima, and so-called "séquences" in a permutation.

The term "séquence" in a permutation, as used by André in several of his papers in the 19th century, means a list of consecutive numbers in the permutation that go from a maximum to a minimum, or vice versa, and do not contain any interior minima or maxima. This terminology is also repeated in Ex. 13 (pp. 260-261) by Comtet (even though he refers to the corresponding indices rather than the numbers in the permutation itself).

Some authors call these so-called "séquences" (defined by André and Comtet) "alternate runs" (or just "runs"). Here we are actually dealing with "circular runs" if we read these so-called "séquences" in ascending order in one of the two directions on a circle.

Q(n, s) is the number of circular permutations of [n] (out of the (n-1)! in total) that have exactly s of these so-called "séquences" ("alternate runs").

André (1895) proves that, in a circular permutation of [n], the number of maxima equals the number of minima and that the number of his so-called "séquences" ("alternate runs") is always even (i.e., Q(n, s) = 0 for s odd).

He also shows that, if v = floor(n/2), then the only possible values for the length of a so-called "séquence" ("alternate run") in a circular permutation of [n] are 2, 4, ..., 2*v. That is why Q(n, s) = 0 when either s is odd, or n <= 1, or s > n.

Note that Sum_{t = 1..floor(n/2)} Q_{n, 2*t} = Sum_{t = 1..floor(n/2)} T(n-1, t-1) = (n-1)! = total number of circular permutations of [n].

Since T(n, k) = Q(n+1, 2*(k+1)) for n >= 1 and 0 <= k <= ceiling(n/2)-1, we conclude that the number of (linear) permutations of [n] with k peaks equals the number of circular permutations of [n+1] with exactly 2*(k+1) of these so-called "séquences" ("alternate runs").

(End)

From Petros Hadjicostas, Aug 08 2019: (Start)

The author of this array indirectly assumes that a "peak" of a (linear) permutation of [n] is an interior maximum of the permutation; i.e., we ignore maxima at the endpoints of a permutation.

Similarly, a "valley" of a (linear) permutation of [n] is an interior minimum of the permutation; i.e., we ignore minima at the endpoints of the permutation.

Since the complement of a permutation a_1 a_2 ... a_n (using one-line notation, not cycle notation) is (n+1-a_1) (n+1-a_2) ... (n+1-a_n), it follows that, for n >= 2 and 0 <= k <= ceiling(n/2) - 1, T(n, k) is also the number of (linear) permutations of [n] with exactly k valleys.

(End)

Examples

			Triangle T(n,k) (with rows n >= 1 and columns k >= 0) starts as follows:
[ 1]    1;
[ 2]    2;
[ 3]    4,       2;
[ 4]    8,      16;
[ 5]   16,      88,      16;
[ 6]   32,     416,     272;
[ 7]   64,    1824,    2880,     272;
[ 8]  128,    7680,   24576,    7936;
[ 9]  256,   31616,  185856,  137216,    7936;
[10]  512,  128512, 1304832, 1841152,  353792;
  A000079, A000431, A000487, A000517, A179708, ...
T(3,1) = 2 because we have 132 and 231.
From _Petros Hadjicostas_, Aug 07 2019: (Start)
In terms of André's (1895) notation (see the comments above), we have Q(4, 2) = T(3, 0) = 4 and Q(4, 4) = T(3, 1) = 2.
Out of the (4-1)! = 6 circular permutations of [4], each of the permutations 1324 and 1423 has exactly 4 so-called "séquences" ("alternate runs"), while each of the rest (1234, 1243, 1342, and 1432) has exactly 2 so-called "séquences" ("alternate runs").
In detail, we list the so-called "séquences" ("alternate runs") of the above circular permutations:
1234 --> 1234 and 41 (maximum 4 and minimum 1).
1243 --> 124 and 431 (maximum 4 and minimum 1).
1324 --> 13, 32, 24, and 41 (maxima 3, 4, and minima 1, 2).
1342 --> 134 and 421 (maximum 4 and minimum 1).
1423 --> 14, 42, 23, and 31 (maxima 3, 4 and minima 1, 2),
1432 --> 14 and 4321 (maximum 4 and minimum 1).
(End)
		

References

• Florence Nightingale David and D. E. Barton, Combinatorial Chance, Charles Griffin, 1962; see Table 10.6, p. 163. [They use the notation T_{N,t^*}^{**}, where N is the length of the permutation and t^* is the number of peaks in the permutation. They also give André's recurrence. So, here n = N and k = t^*. - Petros Hadjicostas, Aug 09 2019]
• Florence Nightingale David, Maurice George Kendall, and D. E. Barton, Symmetric Functions and Allied Tables, Cambridge, 1966, p. 261, Table 7.3.
• I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983, Ex. 3.3.46. - Emeric Deutsch, Jul 26 2009
• T. K. Petersen, Eulerian Numbers, Birkhäuser, 2015, Chapter 4.

Links

• Alois P. Heinz, Rows n = 1..200, flattened (first 30 rows from Vincenzo Librandi)
• Max A. Alekseyev, On the number of permutations with bounded run lengths, arXiv preprint arXiv:1205.4581 [math.CO], 2012-2013. - From _N. J. A. Sloane_, Oct 23 2012
• Désiré André, Mémoire sur les séquences des permutations circulaires, Bulletin de la S. M. F., tome 23 (1895), pp. 122-184.
• T. Austin, R. Fagen, T. Lehrer, and W. Penney, The distribution of the number of locally maximal elements in a random sample, Ann. Math. Statist. 28 (1957), 786-790. - _Ira M. Gessel_, Aug 06 2014
• Jean-Luc Baril and José L. Ramírez, Some distributions in increasing and flattened permutations, arXiv:2410.15434 [math.CO], 2024. See p. 3.
• S. Billey, K. Burdzy, and B. E. Sagan, Permutations with given peak set, arXiv: 1209.0693 [math.CO], 2012.
• S. Billey, K. Burdzy, and B. E. Sagan, Permutations with given peak set, J. Int. Seq. 16 (2013), #13.6.1.
• C.-O. Chow and S.-M. Ma, Counting signed permutations by their alternating runs, Discrete Mathematics, 323 (2014), 49-57.
• C.-O. Chow, S.-M. Ma, T. Mansour, and M. Shattuck, Counting permutations by cyclic peaks and valleys, Annales Mathematicae et Informaticae 43 (2014), 43-54.
• Kieran Clenaghan, In Praise of Sequence (Co-)Algebra and its implementation in Haskell, arXiv:1812.05878 [math.CO], 2019. See page 36.
• Colin Defant, Troupes, Cumulants, and Stack-Sorting, arXiv:2004.11367 [math.CO], 2020.
• Ming-Jian Ding and Bao-Xuan Zhu, Some results related to Hurwitz stability of combinatorial polynomials, Advances in Applied Mathematics, Volume 152, (2024), 102591. See p. 13.
• S. Elizalde and M. Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110-125; see Section 5.
• R. C. Entringer, Enumeration of permutations of (1,...,n) by number of maxima, Duke Math. J. 36 (1969), 575-579. - Ira M. Gessel, Oct 23 2013
• C. J. Fewster and D. Siemssen, Enumerating Permutations by their Run Structure, arXiv preprint arXiv:1403.1723 [math.CO], 2014.
• FindStat - Combinatorial Statistic Finder, The number of inner peaks of a permutation, The number of peaks of a permutation, The number of valleys of a permutation.
• W. O. Kermack and A. G. McKendrick, Some distributions associated with a randomly arranged set of numbers, Proc. Royal Soc. of Edinburgh 67 (1937), 332-376.
• W. O. Kermack and A. G. McKendrick, Some properties of points arranged on a Möbius surface, Mathematical Gazette 22 (1938), 66-72.
• Shi-Mei Ma, Derivative polynomials and permutations by numbers of interior peaks and left peaks, arXiv preprint arXiv:1106.5781 [math.CO], 2011.
• 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.
• Shi-Mei Ma, Toufik Mansour, David G.L. Wang, and Yeong-Nan Yeh, Several variants of the Dumont differential system and permutation statistics, Science China Mathematics 60 (2018).
• Shi-Mei Ma, Jun Ma, Jean Yeh, and Yeong-Nan Yeh, The 1/k-Eulerian polynomials of type B, arXiv:2001.07833 [math.CO], 2020.
• A. Mendes and J. B. Remmel, Permutations and words counted by consecutive patterns, Adv. Appl. Math. 37(4) (2006), 443-480.
• Tom Roberts and Thomas Prellberg, Improving Convergence of Generalised Rosenbluth Sampling for Branched Polymer Models by Uniform Sampling, arXiv:2401.12201 [cond-mat.stat-mech], 2024. See p. 14.
• Louis W. Shapiro, Wen-Jin Woan, and Seyoum Getu, Runs, slides and moments, SIAM J. Algebraic and Discrete Methods 4 (1983), 459-466; see p. 461.
• Bao-Xuan Zhu, Stieltjes moment properties and continued fractions from combinatorial triangles, arXiv:2007.14924 [math.CO], 2020, see p. 27.
• Yan Zhuang, Monoid networks and counting permutations by runs, arXiv preprint arXiv:1505.02308 [math.CO], 2015.
• Yan Zhuang, Counting permutations by runs, J. Comb. Theory Ser. A 142 (2016), pp. 147-176.

Crossrefs

From Emeric Deutsch, Jul 26 2009: (Start)

Sum of entries in row n is n! = A000142(n).

T(n,0) = 2^(n-1) = A000079(n-1).

T(n,1) = A000431(n).

T(n,2) = A000487(n).

T(n,3) = A000517(n).

T(2n, n-1) = T(2n+1, n) = A000182(n+1) (the tangent numbers). (End)

Columns k = 0-6 give: A011782, A000431, A000487, A000517, A179708, A179709, A179710.

Cf. A000111, A000182, A090672, A101280, A185896, A242783, A242784.

Programs

Maple

# The Maple program yields (by straightforward counting) the generating polynomial of the row n specified in the program.
n := 8: with(combinat): P := permute(n): st := proc (p) local ct, j: ct := 0: for j from 2 to nops(p)-1 do if p[j-1] < p[j] and p[j+1] < p[j] then ct := ct+1 else end if end do: ct end proc: sort(add(t^st(P[j]), j = 1 .. factorial(n))); # Emeric Deutsch, Jul 26 2009
# Second Maple program:
a := 1+sqrt(1-t): b := 1-sqrt(1-t): G := (exp(b*z)-exp(a*z))/(b*exp(a*z)-a*exp(b*z)): Gser := simplify(series(G, z = 0, 15)): for n to 12 do P[n] := sort(expand(factorial(n)*coeff(Gser, z, n))) end do: for n to 12 do seq(coeff(P[n], t, j), j = 0 .. ceil((1/2)*n)-1) end do; # yields sequence in triangular form - Emeric Deutsch, Jul 26 2009
# Third Maple program:
b:= proc(u, o, t) option remember; expand(`if`(u+o=0, 1,
      add(b(u-j, o+j-1, 0)*x^t, j=1..u)+
      add(b(u+j-1, o-j, 1), j=1..o)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):
seq(T(n), n=1..15);  # Alois P. Heinz, May 22 2014
# Recurrence of D. André (1895).
T := proc(n, k) option remember;
if n < 1 or 2*k > (n-1) then return 0 fi;
if k = 0 then return 2^(n-1) fi;
(2*k + 2)*T(n-1, k) + (n - 2*k)*T(n-1, k-1) end:
seq(seq(T(n, k), k=0..(n-1)/2), n=1..12); # Peter Luschny, Aug 06 2019

Mathematica

From Luc Roy, Jul 08 2010: (Start)
It appears that one-half of the sequence A008303 can be obtained with this Mathematica program:
Expand[CoefficientList[Simplify[InverseSeries[Integrate[
Series[(1 + m Sinh[x]^2)^(-1), {x, 0, 15}, {m, 0, 15}], x]]], x]
Denominator[CoefficientList[Series[Exp[x], {x, 0, 15}], x]]]
(* Mathematica Output of Luc Roy's program *)
{0, 1, 0, 2 m, 0, 8 m + 16 m^2, 0, 32 m + 416 m^2 + 272 m^3, 0, 128 m + 7680 m^2 + 24576 m^3 + 7936 m^4, 0, 512 m + 128512 m^2 + 1304832 m^3 + 1841152 m^4 + 353792 m^5, 0, 2048 m + 2084864 m^2 + 56520704 m^3 + 222398464 m^4 + 175627264 m^5 + 22368256 m^6, 0, 8192 m + 33497088 m^2 + 2230947840 m^3 + 20261765120 m^4 + 41731645440 m^5 + 21016670208 m^6 + 1903757312 m^7}
(End)
(* Another Mathematica program *)
m = 14; a = 1 + Sqrt[1 - t]; b = 1 - Sqrt[1 - t];
g[z_] = (E^(b*z) - E^(a*z))/(b*E^(a*z) - a*E^(b*z));
gser = Series[g[z], {z, 0, m}];
Do[p[n]=n!*Coefficient[gser, z, n]//Simplify, {n, 0, m}];
Flatten[ Table[ Coefficient[p[n], t, j], {n, 0, m}, {j, 0, Ceiling[n/2] - 1}]]
(* Jean-François Alcover, May 27 2011, after Emeric Deutsch *)
(* To get the triangle from Jean-François Alcover's Mathematica program *)
FormTable[Table[Coefficient[p[n], t, j], {n, 0, m}, {j, 0, Ceiling[n/2] - 1}]]
(* Petros Hadjicostas, Aug 06 2019 *)
gf := Sqrt[x - 1] Cot[y Sqrt[x - 1]] - 1; ser := Series[1/gf, {y, 0, 16}];
cy[n_] := n! Coefficient[ser, y, n]; row[n_] := CoefficientList[cy[n], x];
Table[row[n], {n, 1, 12}] // Flatten (* Peter Luschny, Aug 06 2019 *)

PARI

{T(n, k) = if(n<1, 0, my(z = sqrt(1 - y + y*O(y^(n\2)))); n!*polcoef(polcoef(z/(z - tanh(x*z)), n, x), k))}; /* Michael Somos, May 24 2023 */

Formula

From Emeric Deutsch, Jul 26 2009: (Start)

E.g.f.: G(t,z)=[exp(bz)-exp(az)]/[b*exp(az)-a*exp(bz)], where a+b=2 and ab=t, i.e., a=1+sqrt(1-t), b=1-sqrt(1-t) (see the Goulden-Jackson reference). -

Sum_{k>=0} k*T(n,k) = n!*(n-2)/3 = A090672(n-1).

Row n has ceiling(n/2) terms. (End)

E.g.f.: tan(t*sqrt(x-1))/(sqrt(x-1)-tan(t*sqrt(x-1))) = Sum_{n>=0} P(n,x)*t^n/n! = t + 2*t^2/2! + (4+2*x)*t^3/3! + (8+16*x)*t^4/4! + .... The row generating polynomials P(n,x) satisfy x^(n-1)*P(n,1+1/x^2) = R(n-1,x), where R(n,x) are the row polynomials of A185896. A000670(n) = (3/2)^(n-1)*P(n,8/9). - Peter Bala, Oct 14 2011

From Jinyuan Wang, Dec 28 2020: (Start)

T(n, k) = (n - 2*k + 2)*T(n-1, k-1) + 2*k*T(n-1, k) for n > 1 and k > 1; T(n, 1) = 2^(n - 1); T(1, k) = 0 for k > 1.

T(2*k-1, k) = A000182(k). (End)

From Ammar Khatab, Aug 17 2024: (Start)

T(2*n,k) = 4^(n-k+1)* Sum_{p=0..k} (-1)^p * (2*p+2*n-2*k-1)/(p+2*n-2*k-1) binomial(p+2*n-2*k-1,p) (A008292(2*n,k-p+1)+A008292(2*n,2*n+p-k) ) for n>0.

T(2*n+1,k) = 4^(n-k)* Sum_{p=0..k} (-1)^p * (p+n-k)/(p+2*n-2*k) binomial(p+2*n-2*k,p) (A008292(2*n+1,k-p+1)+A008292(2*n,2*n+p-k+1) ) for k<>n. (End)

Extensions

Additional comments from Emeric Deutsch, May 08 2004

More terms from R. J. Mathar and Vladeta Jovovic, Jun 26 2007

Corrected by Emeric Deutsch, Jul 26 2009

Edited definition - N. J. A. Sloane, May 25 2023