login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A008303 Triangle read by rows: T(n,k) (n>=1; 0<=k<=ceiling(n/2)-1) is the number of permutations of [n] with k peaks. 12
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, 4096, 8361984, 357888000, 2174832640, 2868264960, 795300864, 22368256, 8192, 33497088, 2230947840, 20261765120, 41731645440, 21016670208, 1903757312 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Row n has ceiling(n/2) terms.

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).

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

(End)

REFERENCES

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

C.-O. Chow and S.-M. Ma, Counting signed permutations by their alternating runs, Discrete Mathematics, Volume 323, 28 May 2014, Pages 49-57.

Chow, C. O., Ma, S. M., Mansour, T., & Shattuck, M. (2014). Counting permutations by cyclic peaks and valleys, Annales Mathematicae et Informaticae (Vol. 43, pp. 43-54).

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 261, Table 7.3.

S. Elizalde and M. Noy, Consecutive patterns in permutations (Section 5), Adv. Appl. Math. 30 (2003) 110-125.

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

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

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.

Shi-Mei Ma, Enumeration of permutations by number of alternating runs, Discrete Math., 313 (2013), 1816-1822.

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

T. K. Petersen, Eulerian Numbers, Birkhauser, 2015, chapter 4.

Louis W. Shapiro, Wen-Jin Woan and Seyoum Getu, "Runs, slides and moments", SIAM J. Algebraic and Discrete Methods 4 (1983), 461.

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

S. Billey, K. Burdzy and B. E. Sagan, Permutations with given peak set, arXiv preprint arXiv:1209.0693 [math.CO], 2012 and J. Int. Seq. 16 (2013) #13.6.1

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 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.

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.

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

FORMULA

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). - Emeric Deutsch, Jul 26 2009

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

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]]]

{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)

1;

2;

4,     2;

8,    16;

16,   88,   16;

32,  416,  272;

64, 1824, 2880, 272; ...

T(3,1) = 2 because we have 132 and 231.

MAPLE

From Emeric Deutsch, Jul 26 2009: 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

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

MATHEMATICA

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

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

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

Cf. A000111, A101280.

Cf. A090672, A000182. - Emeric Deutsch, Jul 26 2009

Cf. A185896, A242783, A242784.

Sequence in context: A120434 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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 16 09:54 EDT 2018. Contains 313791 sequences. (Running on oeis4.)