OFFSET
1,2
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)
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.
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)
EXAMPLE
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;
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)
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 *)
PROG
(C++)
#include <vector>
#include <iostream>
using namespace std;
int peaks(const vector<int> & perm) {
int pks=0;
for(int i=1 ; i < perm.size()-1; i++)
if ( perm[i]>perm[i+1] && perm[i]> perm[i-1] ) pks++;
return pks ;
}
int main(int argc, char *argv[]) {
int n=1;
if ( argc > 1 ) n=atoi(argv[1]);
int nmax = n+12;
if ( argc > 2 ) nmax=atoi(argv[2]);
for (; n < nmax ; n++) {
const int kmax = (n+1)/2;
vector<int> Tnk(kmax);
vector<int> perm(n);
for(int i=0 ; i < n ; i++) perm[i]=i+1;
int pks = peaks(perm);
Tnk[pks]++;
while ( next_permutation(perm.begin(), perm.end()) ) {
pks = peaks(perm);
Tnk[pks]++;
}
for (int i=0; i < Tnk.size(); i++) cout << Tnk[i] << ", " ;
}
}
/* R. J. Mathar, Jun 26 2007 */
(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 */
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
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
STATUS
approved