This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A008303 #233 Oct 26 2024 10:47:41 %S A008303 1,2,4,2,8,16,16,88,16,32,416,272,64,1824,2880,272,128,7680,24576, %T A008303 7936,256,31616,185856,137216,7936,512,128512,1304832,1841152,353792, %U A008303 1024,518656,8728576,21253376,9061376,353792,2048,2084864,56520704,222398464,175627264,22368256 %N A008303 Triangle read by rows: T(n,k) (n >= 1, 0 <= k <= ceiling(n/2)-1) = number of permutations of [n] with k peaks. %C A008303 From _Petros Hadjicostas_, Aug 06 2019: (Start) %C A008303 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 A008303 His triangle is as follows (p. 148): %C A008303 Q_{2,2} %C A008303 Q_{3,2} %C A008303 Q_{4,2} Q_{4,4} %C A008303 Q_{5,2} Q_{5,4} %C A008303 Q_{6,2} Q_{6,4} Q_{6,6} %C A008303 Q_{7,2} Q_{7,4} Q_{7,6} %C A008303 ... %C A008303 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 A008303 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 A008303 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 A008303 (End) %C A008303 From _Petros Hadjicostas_, Aug 07 2019: (Start) %C A008303 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 A008303 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 A008303 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 A008303 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 A008303 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 A008303 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 A008303 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 A008303 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 A008303 (End) %C A008303 From _Petros Hadjicostas_, Aug 08 2019: (Start) %C A008303 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 A008303 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 A008303 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 A008303 (End) %D A008303 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 A008303 Florence Nightingale David, Maurice George Kendall, and D. E. Barton, Symmetric Functions and Allied Tables, Cambridge, 1966, p. 261, Table 7.3. %D A008303 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 A008303 T. K. Petersen, Eulerian Numbers, Birkhäuser, 2015, Chapter 4. %H A008303 Alois P. Heinz, <a href="/A008303/b008303.txt">Rows n = 1..200, flattened</a> (first 30 rows from Vincenzo Librandi) %H A008303 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 A008303 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 A008303 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 A008303 Jean-Luc Baril and José L. Ramírez, <a href="https://arxiv.org/abs/2410.15434">Some distributions in increasing and flattened permutations</a>, arXiv:2410.15434 [math.CO], 2024. See p. 3. %H A008303 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 A008303 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 A008303 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 A008303 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 A008303 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 A008303 Colin Defant, <a href="https://arxiv.org/abs/2004.11367">Troupes, Cumulants, and Stack-Sorting</a>, arXiv:2004.11367 [math.CO], 2020. %H A008303 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 A008303 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 A008303 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 A008303 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 A008303 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 A008303 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 A008303 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 A008303 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 A008303 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 A008303 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 A008303 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 A008303 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 A008303 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 A008303 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 A008303 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 A008303 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 A008303 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 A008303 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 A008303 From _Emeric Deutsch_, Jul 26 2009: (Start) %F A008303 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 A008303 Sum_{k>=0} k*T(n,k) = n!*(n-2)/3 = A090672(n-1). %F A008303 Row n has ceiling(n/2) terms. (End) %F A008303 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 A008303 From _Jinyuan Wang_, Dec 28 2020: (Start) %F A008303 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 A008303 T(2*k-1, k) = A000182(k). (End) %F A008303 From _Ammar Khatab_, Aug 17 2024: (Start) %F A008303 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. %F A008303 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) %e A008303 Triangle T(n,k) (with rows n >= 1 and columns k >= 0) starts as follows: %e A008303 [ 1] 1; %e A008303 [ 2] 2; %e A008303 [ 3] 4, 2; %e A008303 [ 4] 8, 16; %e A008303 [ 5] 16, 88, 16; %e A008303 [ 6] 32, 416, 272; %e A008303 [ 7] 64, 1824, 2880, 272; %e A008303 [ 8] 128, 7680, 24576, 7936; %e A008303 [ 9] 256, 31616, 185856, 137216, 7936; %e A008303 [10] 512, 128512, 1304832, 1841152, 353792; %e A008303 A000079, A000431, A000487, A000517, A179708, ... %e A008303 T(3,1) = 2 because we have 132 and 231. %e A008303 From _Petros Hadjicostas_, Aug 07 2019: (Start) %e A008303 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 A008303 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 A008303 In detail, we list the so-called "séquences" ("alternate runs") of the above circular permutations: %e A008303 1234 --> 1234 and 41 (maximum 4 and minimum 1). %e A008303 1243 --> 124 and 431 (maximum 4 and minimum 1). %e A008303 1324 --> 13, 32, 24, and 41 (maxima 3, 4, and minima 1, 2). %e A008303 1342 --> 134 and 421 (maximum 4 and minimum 1). %e A008303 1423 --> 14, 42, 23, and 31 (maxima 3, 4 and minima 1, 2), %e A008303 1432 --> 14 and 4321 (maximum 4 and minimum 1). %e A008303 (End) %p A008303 # The Maple program yields (by straightforward counting) the generating polynomial of the row n specified in the program. %p A008303 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 A008303 # Second Maple program: %p A008303 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 A008303 # Third Maple program: %p A008303 b:= proc(u, o, t) option remember; expand(`if`(u+o=0, 1, %p A008303 add(b(u-j, o+j-1, 0)*x^t, j=1..u)+ %p A008303 add(b(u+j-1, o-j, 1), j=1..o))) %p A008303 end: %p A008303 T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)): %p A008303 seq(T(n), n=1..15); # _Alois P. Heinz_, May 22 2014 %p A008303 # Recurrence of D. André (1895). %p A008303 T := proc(n, k) option remember; %p A008303 if n < 1 or 2*k > (n-1) then return 0 fi; %p A008303 if k = 0 then return 2^(n-1) fi; %p A008303 (2*k + 2)*T(n-1, k) + (n - 2*k)*T(n-1, k-1) end: %p A008303 seq(seq(T(n, k), k=0..(n-1)/2), n=1..12); # _Peter Luschny_, Aug 06 2019 %t A008303 From Luc Roy, Jul 08 2010: (Start) %t A008303 It appears that one-half of the sequence A008303 can be obtained with this Mathematica program: %t A008303 Expand[CoefficientList[Simplify[InverseSeries[Integrate[ %t A008303 Series[(1 + m Sinh[x]^2)^(-1), {x, 0, 15}, {m, 0, 15}], x]]], x] %t A008303 Denominator[CoefficientList[Series[Exp[x], {x, 0, 15}], x]]] %t A008303 (* Mathematica Output of Luc Roy's program *) %t A008303 {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 A008303 (End) %t A008303 (* Another Mathematica program *) %t A008303 m = 14; a = 1 + Sqrt[1 - t]; b = 1 - Sqrt[1 - t]; %t A008303 g[z_] = (E^(b*z) - E^(a*z))/(b*E^(a*z) - a*E^(b*z)); %t A008303 gser = Series[g[z], {z, 0, m}]; %t A008303 Do[p[n]=n!*Coefficient[gser, z, n]//Simplify, {n, 0, m}]; %t A008303 Flatten[ Table[ Coefficient[p[n], t, j], {n, 0, m}, {j, 0, Ceiling[n/2] - 1}]] %t A008303 (* _Jean-François Alcover_, May 27 2011, after _Emeric Deutsch_ *) %t A008303 (* To get the triangle from _Jean-François Alcover_'s Mathematica program *) %t A008303 FormTable[Table[Coefficient[p[n], t, j], {n, 0, m}, {j, 0, Ceiling[n/2] - 1}]] %t A008303 (* _Petros Hadjicostas_, Aug 06 2019 *) %t A008303 gf := Sqrt[x - 1] Cot[y Sqrt[x - 1]] - 1; ser := Series[1/gf, {y, 0, 16}]; %t A008303 cy[n_] := n! Coefficient[ser, y, n]; row[n_] := CoefficientList[cy[n], x]; %t A008303 Table[row[n], {n, 1, 12}] // Flatten (* _Peter Luschny_, Aug 06 2019 *) %o A008303 (C++) %o A008303 #include <vector> %o A008303 #include <iostream> %o A008303 using namespace std; %o A008303 int peaks(const vector<int> & perm) { %o A008303 int pks=0; %o A008303 for(int i=1 ; i < perm.size()-1; i++) %o A008303 if ( perm[i]>perm[i+1] && perm[i]> perm[i-1] ) pks++; %o A008303 return pks ; %o A008303 } %o A008303 int main(int argc, char *argv[]) { %o A008303 int n=1; %o A008303 if ( argc > 1 ) n=atoi(argv[1]); %o A008303 int nmax = n+12; %o A008303 if ( argc > 2 ) nmax=atoi(argv[2]); %o A008303 for (; n < nmax ; n++) { %o A008303 const int kmax = (n+1)/2; %o A008303 vector<int> Tnk(kmax); %o A008303 vector<int> perm(n); %o A008303 for(int i=0 ; i < n ; i++) perm[i]=i+1; %o A008303 int pks = peaks(perm); %o A008303 Tnk[pks]++; %o A008303 while ( next_permutation(perm.begin(), perm.end()) ) { %o A008303 pks = peaks(perm); %o A008303 Tnk[pks]++; %o A008303 } %o A008303 for (int i=0; i < Tnk.size(); i++) cout << Tnk[i] << ", " ; %o A008303 } %o A008303 } %o A008303 /* _R. J. Mathar_, Jun 26 2007 */ %o A008303 (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 A008303 From _Emeric Deutsch_, Jul 26 2009: (Start) %Y A008303 Sum of entries in row n is n! = A000142(n). %Y A008303 T(n,0) = 2^(n-1) = A000079(n-1). %Y A008303 T(n,1) = A000431(n). %Y A008303 T(n,2) = A000487(n). %Y A008303 T(n,3) = A000517(n). %Y A008303 T(2n, n-1) = T(2n+1, n) = A000182(n+1) (the tangent numbers). (End) %Y A008303 Columns k = 0-6 give: A011782, A000431, A000487, A000517, A179708, A179709, A179710. %Y A008303 Cf. A000111, A000182, A090672, A101280, A185896, A242783, A242784. %K A008303 nonn,tabf %O A008303 1,2 %A A008303 _N. J. A. Sloane_ %E A008303 Additional comments from _Emeric Deutsch_, May 08 2004 %E A008303 More terms from _R. J. Mathar_ and _Vladeta Jovovic_, Jun 26 2007 %E A008303 Corrected by _Emeric Deutsch_, Jul 26 2009 %E A008303 Edited definition - _N. J. A. Sloane_, May 25 2023