login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A008303 Number of permutations of [n] with k peaks, triangle read by rows, T(n,k) for n >= 1 and 0 <= k <= ceiling(n/2)-1. 16
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 (list; graph; refs; listen; history; text; internal format)
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, Birkhauser, 2015, Chapter 4.

LINKS

Vincenzo Librandi and 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

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.

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, 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, Yeong-Nan Yeh, Several variants of the Dumont differential system and permutation statistics, Science China Mathematics 60 (2018).

A. Mendes and J. B. Remmel, Permutations and words counted by consecutive patterns, Adv. Appl. Math. 37(4) (2006), 443-480.

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.

Yan Zhuang, Monoid networks and counting permutations by runs, arXiv preprint arXiv:1505.02308 [math.CO], 2015.

FORMULA

From Emeric Deutsch, Jul 26 2009:

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

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;

  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)

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

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, A101280, A185896, A242783, A242784, A090672, A000182.

Sequence in context: A319030 A285335 A187619 * A229296 A232565 A058942

Adjacent sequences:  A008300 A008301 A008302 * A008304 A008305 A008306

KEYWORD

tabf,nonn

AUTHOR

N. J. A. Sloane

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 10 06:23 EDT 2020. Contains 333392 sequences. (Running on oeis4.)