|
%I #220 Jan 25 2024 11:49:55
%S 1,2,4,2,8,16,16,88,16,32,416,272,64,1824,2880,272,128,7680,24576,
%T 7936,256,31616,185856,137216,7936,512,128512,1304832,1841152,353792,
%U 1024,518656,8728576,21253376,9061376,353792,2048,2084864,56520704,222398464,175627264,22368256
%N Triangle read by rows: T(n,k) (n >= 1, 0 <= k <= ceiling(n/2)-1) = number of permutations of [n] with k peaks.
%C From _Petros Hadjicostas_, Aug 06 2019: (Start)
%C 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.
%C His triangle is as follows (p. 148):
%C Q_{2,2}
%C Q_{3,2}
%C Q_{4,2} Q_{4,4}
%C Q_{5,2} Q_{5,4}
%C Q_{6,2} Q_{6,4} Q_{6,6}
%C Q_{7,2} Q_{7,4} Q_{7,6}
%C ...
%C 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.
%C 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.)
%C 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.
%C (End)
%C From _Petros Hadjicostas_, Aug 07 2019: (Start)
%C 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.
%C 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).
%C 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.
%C 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").
%C 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).
%C 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.
%C 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].
%C 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").
%C (End)
%C From _Petros Hadjicostas_, Aug 08 2019: (Start)
%C 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.
%C 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.
%C 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.
%C (End)
%D 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]
%D Florence Nightingale David, Maurice George Kendall, and D. E. Barton, Symmetric Functions and Allied Tables, Cambridge, 1966, p. 261, Table 7.3.
%D 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
%D T. K. Petersen, Eulerian Numbers, Birkhäuser, 2015, Chapter 4.
%H Alois P. Heinz, <a href="/A008303/b008303.txt">Rows n = 1..200, flattened</a> (first 30 rows from Vincenzo Librandi)
%H Max A. Alekseyev, <a href="https://arxiv.org/abs/1205.4581">On the number of permutations with bounded run lengths</a>, arXiv preprint arXiv:1205.4581 [math.CO], 2012-2013. - From _N. J. A. Sloane_, Oct 23 2012
%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 T. Austin, R. Fagen, T. Lehrer, and W. Penney, <a href="https://projecteuclid.org/euclid.aoms/1177706893">The distribution of the number of locally maximal elements in a random sample</a>, Ann. Math. Statist. 28 (1957), 786-790. - _Ira M. Gessel_, Aug 06 2014
%H S. Billey, K. Burdzy, and B. E. Sagan, <a href="http://arxiv.org/abs/1209.0693">Permutations with given peak set</a>, arXiv: 1209.0693 [math.CO], 2012.
%H S. Billey, K. Burdzy, and B. E. Sagan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Billey/billey2.html">Permutations with given peak set</a>, J. Int. Seq. 16 (2013), #13.6.1.
%H C.-O. Chow and S.-M. Ma, <a href="https://doi.org/10.1016/j.disc.2014.01.015 ">Counting signed permutations by their alternating runs</a>, Discrete Mathematics, 323 (2014), 49-57.
%H C.-O. Chow, S.-M. Ma, T. Mansour, and M. Shattuck, <a href="http://ami.ektf.hu/uploads/papers/finalpdf/AMI_43_from43to54.pdf">Counting permutations by cyclic peaks and valleys</a>, Annales Mathematicae et Informaticae 43 (2014), 43-54.
%H Kieran Clenaghan, <a href="https://arxiv.org/abs/1812.05878">In Praise of Sequence (Co-)Algebra and its implementation in Haskell</a>, arXiv:1812.05878 [math.CO], 2019. See page 36.
%H Colin Defant, <a href="https://arxiv.org/abs/2004.11367">Troupes, Cumulants, and Stack-Sorting</a>, arXiv:2004.11367 [math.CO], 2020.
%H Ming-Jian Ding and Bao-Xuan Zhu, <a href="https://doi.org/10.1016/j.aam.2023.102591">Some results related to Hurwitz stability of combinatorial polynomials</a>, Advances in Applied Mathematics, Volume 152, (2024), 102591. See p. 13.
%H S. Elizalde and M. Noy, <a href="https://doi.org/10.1016/S0196-8858(02)00527-4 ">Consecutive patterns in permutations</a>, Adv. Appl. Math. 30 (2003), 110-125; see Section 5.
%H R. C. Entringer, <a href="https://projecteuclid.org/euclid.dmj/1077378476">Enumeration of permutations of (1,...,n) by number of maxima</a>, Duke Math. J. 36 (1969), 575-579. - Ira M. Gessel, Oct 23 2013
%H C. J. Fewster and D. Siemssen, <a href="http://arxiv.org/abs/1403.1723">Enumerating Permutations by their Run Structure</a>, arXiv preprint arXiv:1403.1723 [math.CO], 2014.
%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/StatisticsDatabase/St000023">The number of inner peaks of a permutation</a>, <a href="http://www.findstat.org/StatisticsDatabase/St000092">The number of peaks of a permutation</a>, <a href="http://www.findstat.org/StatisticsDatabase/St000099">The number of valleys of a permutation</a>.
%H W. O. Kermack and A. G. McKendrick, <a href="https://doi.org/10.1017/S0370164600013821">Some distributions associated with a randomly arranged set of numbers</a>, Proc. Royal Soc. of Edinburgh 67 (1937), 332-376.
%H W. O. Kermack and A. G. McKendrick, <a href="http://www.jstor.org/stable/3607448">Some properties of points arranged on a Möbius surface</a>, Mathematical Gazette 22 (1938), 66-72.
%H Shi-Mei Ma, <a href="http://arxiv.org/abs/1106.5781">Derivative polynomials and permutations by numbers of interior peaks and left peaks</a>, arXiv preprint arXiv:1106.5781 [math.CO], 2011.
%H Shi-Mei Ma, <a href="https://doi.org/10.1016/j.disc.2013.05.010">Enumeration of permutations by number of alternating runs</a>, Discrete Math., 313 (2013), 1816-1822.
%H S.-M. Ma, T. Mansour, and D. G. L. Wang, <a href="http://arxiv.org/abs/1403.0233">Combinatorics of Dumont differential system on the Jacobi elliptic functions</a>, arXiv preprint arXiv:1403.0233 [math.CO], 2014.
%H Shi-Mei Ma, Toufik Mansour, David G.L. Wang, and Yeong-Nan Yeh, <a href="https://www.math.sinica.edu.tw/www/file_upload/mayeh/2018SCM-2016-0688.pdf">Several variants of the Dumont differential system and permutation statistics</a>, Science China Mathematics 60 (2018).
%H Shi-Mei Ma, Jun Ma, Jean Yeh, and Yeong-Nan Yeh, <a href="https://arxiv.org/abs/2001.07833">The 1/k-Eulerian polynomials of type B</a>, arXiv:2001.07833 [math.CO], 2020.
%H A. Mendes and J. B. Remmel, <a href="https://doi.org/10.1016/j.aam.2005.09.005 ">Permutations and words counted by consecutive patterns</a>, Adv. Appl. Math. 37(4) (2006), 443-480.
%H Tom Roberts and Thomas Prellberg, <a href="https://arxiv.org/abs/2401.12201">Improving Convergence of Generalised Rosenbluth Sampling for Branched Polymer Models by Uniform Sampling</a>, arXiv:2401.12201 [cond-mat.stat-mech], 2024. See p. 14.
%H Louis W. Shapiro, Wen-Jin Woan, and Seyoum Getu, <a href="https://doi.org/10.1137/0604046">Runs, slides and moments</a>, SIAM J. Algebraic and Discrete Methods 4 (1983), 459-466; see p. 461.
%H Bao-Xuan Zhu, <a href="https://arxiv.org/abs/2007.14924">Stieltjes moment properties and continued fractions from combinatorial triangles</a>, arXiv:2007.14924 [math.CO], 2020, see p. 27.
%H Yan Zhuang, <a href="http://arxiv.org/abs/1505.02308">Monoid networks and counting permutations by runs</a>, arXiv preprint arXiv:1505.02308 [math.CO], 2015.
%H Yan Zhuang, <a href="https://doi.org/10.1016/j.jcta.2016.04.002">Counting permutations by runs</a>, J. Comb. Theory Ser. A 142 (2016), pp. 147-176.
%F From _Emeric Deutsch_, Jul 26 2009: (Start)
%F 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). -
%F Sum_{k>=0} k*T(n,k) = n!*(n-2)/3 = A090672(n-1).
%F Row n has ceiling(n/2) terms. (End)
%F 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
%F From _Jinyuan Wang_, Dec 28 2020: (Start)
%F 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.
%F T(2*k-1, k) = A000182(k). (End)
%e Triangle T(n,k) (with rows n >= 1 and columns k >= 0) starts as follows:
%e [ 1] 1;
%e [ 2] 2;
%e [ 3] 4, 2;
%e [ 4] 8, 16;
%e [ 5] 16, 88, 16;
%e [ 6] 32, 416, 272;
%e [ 7] 64, 1824, 2880, 272;
%e [ 8] 128, 7680, 24576, 7936;
%e [ 9] 256, 31616, 185856, 137216, 7936;
%e [10] 512, 128512, 1304832, 1841152, 353792;
%e A000079, A000431, A000487, A000517, A179708, ...
%e T(3,1) = 2 because we have 132 and 231.
%e From _Petros Hadjicostas_, Aug 07 2019: (Start)
%e 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.
%e 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").
%e In detail, we list the so-called "séquences" ("alternate runs") of the above circular permutations:
%e 1234 --> 1234 and 41 (maximum 4 and minimum 1).
%e 1243 --> 124 and 431 (maximum 4 and minimum 1).
%e 1324 --> 13, 32, 24, and 41 (maxima 3, 4, and minima 1, 2).
%e 1342 --> 134 and 421 (maximum 4 and minimum 1).
%e 1423 --> 14, 42, 23, and 31 (maxima 3, 4 and minima 1, 2),
%e 1432 --> 14 and 4321 (maximum 4 and minimum 1).
%e (End)
%p # The Maple program yields (by straightforward counting) the generating polynomial of the row n specified in the program.
%p 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
%p # Second Maple program:
%p 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
%p # Third Maple program:
%p b:= proc(u, o, t) option remember; expand(`if`(u+o=0, 1,
%p add(b(u-j, o+j-1, 0)*x^t, j=1..u)+
%p add(b(u+j-1, o-j, 1), j=1..o)))
%p end:
%p T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):
%p seq(T(n), n=1..15); # _Alois P. Heinz_, May 22 2014
%p # Recurrence of D. André (1895).
%p T := proc(n, k) option remember;
%p if n < 1 or 2*k > (n-1) then return 0 fi;
%p if k = 0 then return 2^(n-1) fi;
%p (2*k + 2)*T(n-1, k) + (n - 2*k)*T(n-1, k-1) end:
%p seq(seq(T(n, k), k=0..(n-1)/2), n=1..12); # _Peter Luschny_, Aug 06 2019
%t From Luc Roy, Jul 08 2010: (Start)
%t It appears that one-half of the sequence A008303 can be obtained with this Mathematica program:
%t Expand[CoefficientList[Simplify[InverseSeries[Integrate[
%t Series[(1 + m Sinh[x]^2)^(-1), {x, 0, 15}, {m, 0, 15}], x]]], x]
%t Denominator[CoefficientList[Series[Exp[x], {x, 0, 15}], x]]]
%t (* Mathematica Output of Luc Roy's program *)
%t {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}
%t (End)
%t (* Another Mathematica program *)
%t m = 14; a = 1 + Sqrt[1 - t]; b = 1 - Sqrt[1 - t];
%t g[z_] = (E^(b*z) - E^(a*z))/(b*E^(a*z) - a*E^(b*z));
%t gser = Series[g[z], {z, 0, m}];
%t Do[p[n]=n!*Coefficient[gser, z, n]//Simplify, {n, 0, m}];
%t Flatten[ Table[ Coefficient[p[n], t, j], {n, 0, m}, {j, 0, Ceiling[n/2] - 1}]]
%t (* _Jean-François Alcover_, May 27 2011, after _Emeric Deutsch_ *)
%t (* To get the triangle from _Jean-François Alcover_'s Mathematica program *)
%t FormTable[Table[Coefficient[p[n], t, j], {n, 0, m}, {j, 0, Ceiling[n/2] - 1}]]
%t (* _Petros Hadjicostas_, Aug 06 2019 *)
%t gf := Sqrt[x - 1] Cot[y Sqrt[x - 1]] - 1; ser := Series[1/gf, {y, 0, 16}];
%t cy[n_] := n! Coefficient[ser, y, n]; row[n_] := CoefficientList[cy[n], x];
%t Table[row[n], {n, 1, 12}] // Flatten (* _Peter Luschny_, Aug 06 2019 *)
%o (C++)
%o #include <vector>
%o #include <iostream>
%o using namespace std;
%o int peaks(const vector<int> & perm) {
%o int pks=0;
%o for(int i=1 ; i < perm.size()-1; i++)
%o if ( perm[i]>perm[i+1] && perm[i]> perm[i-1] ) pks++;
%o return pks ;
%o }
%o int main(int argc, char *argv[]) {
%o int n=1;
%o if ( argc > 1 ) n=atoi(argv[1]);
%o int nmax = n+12;
%o if ( argc > 2 ) nmax=atoi(argv[2]);
%o for (; n < nmax ; n++) {
%o const int kmax = (n+1)/2;
%o vector<int> Tnk(kmax);
%o vector<int> perm(n);
%o for(int i=0 ; i < n ; i++) perm[i]=i+1;
%o int pks = peaks(perm);
%o Tnk[pks]++;
%o while ( next_permutation(perm.begin(), perm.end()) ) {
%o pks = peaks(perm);
%o Tnk[pks]++;
%o }
%o for (int i=0; i < Tnk.size(); i++) cout << Tnk[i] << ", " ;
%o }
%o }
%o /* _R. J. Mathar_, Jun 26 2007 */
%o (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 */
%Y From _Emeric Deutsch_, Jul 26 2009: (Start)
%Y Sum of entries in row n is n! = A000142(n).
%Y T(n,0) = 2^(n-1) = A000079(n-1).
%Y T(n,1) = A000431(n).
%Y T(n,2) = A000487(n).
%Y T(n,3) = A000517(n).
%Y T(2n, n-1) = T(2n+1, n) = A000182(n+1) (the tangent numbers). (End)
%Y Columns k = 0-6 give: A011782, A000431, A000487, A000517, A179708, A179709, A179710.
%Y Cf. A000111, A000182, A090672, A101280, A185896, A242783, A242784.
%K nonn,tabf
%O 1,2
%A _N. J. A. Sloane_
%E Additional comments from _Emeric Deutsch_, May 08 2004
%E More terms from _R. J. Mathar_ and _Vladeta Jovovic_, Jun 26 2007
%E Corrected by _Emeric Deutsch_, Jul 26 2009
%E Edited definition - _N. J. A. Sloane_, May 25 2023
|
