A000303 -id:A000303 - cp's OEIS frontend

A049774 Number of permutations of n elements not containing the consecutive pattern 123.

1, 1, 2, 5, 17, 70, 349, 2017, 13358, 99377, 822041, 7477162, 74207209, 797771521, 9236662346, 114579019469, 1516103040833, 21314681315998, 317288088082405, 4985505271920097, 82459612672301846, 1432064398910663705, 26054771465540507273, 495583804405888997218

Offset: 0

Tuwani A. Tshifhumulo (tat(AT)caddy.univen.ac.za)

Permutations on n letters without double falls. A permutation w has a double fall at k if w(k) > w(k+1) > w(k+2) and has an initial fall if w(1) > w(2).
Hankel transform is A055209. - Paul Barry, Jan 12 2009
Increasing colored 1-2 trees of order n with choice of two colors for the right branches of the vertices of outdegree 2 except those vertices on the path from the root to the leftmost leaf. - Wenjin Woan, May 21 2011

			Permutations without double increase and without pattern 123:
a(3) = 5: 132, 213, 231, 312, 321.
a(4) = 17: 1324, 1423, 1432, 2143, 2314, 2413, 2431, 3142, 3214, 3241, 3412, 3421, 4132, 4213, 4231, 4312, 4321.

F. N. David and D. E. Barton, Combinatorial Chance, Hafner, New York, 1962, pp. 156-157.
I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983, (5.2.17).

Alois P. Heinz, Table of n, a(n) for n = 0..464 (first 201 terms from Ray Chandler)
Martin Aigner, Catalan and other numbers: a recurrent theme, in Algebraic Combinatorics and Computer Science, a Tribute to Gian-Carlo Rota, pp.347-390, Springer, 2001.
Juan S. Auli, Pattern Avoidance in Inversion Sequences, Ph. D. thesis, Dartmouth College, ProQuest Dissertations Publishing (2020), 27964164.
Juan S. Auli, Sergi Elizalde, Consecutive Patterns in Inversion Sequences, arXiv:1904.02694 [math.CO], 2019. See Table 1.
Paul Barry, Constructing Exponential Riordan Arrays from Their A and Z Sequences, Journal of Integer Sequences, 17 (2014), #14.2.6.
Paul Barry, On a transformation of Riordan moment sequences, arXiv:1802.03443 [math.CO], 2018.
Nicolas Basset, Counting and generating permutations using timed languages, HAL Id: hal-00820373, 2013.
A. Baxter, B. Nakamura, and D. Zeilberger. Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes; Local copy [Pdf file only, no active links].
S. Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns arXiv:math/0505254 [math.CO], 2015.
S. Elizalde and M. Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110-123.
Steven Finch, Pattern-Avoiding Permutations [Archived version]
Steven Finch, Pattern-Avoiding Permutations [Cached copy, with permission]
Ira M. Gessel and Yan Zhuang, Counting permutations by alternating descents , arXiv:1408.1886 [math.CO], 2014. See Eq. (3). - _N. J. A. Sloane_, Aug 11 2014
Kaarel Hänni, Asymptotics of descent functions, arXiv:2011.14360 [math.CO], Nov 29 2020, p. 14.
Mingjia Yang and Doron Zeilberger, Increasing Consecutive Patterns in Words, arXiv:1805.06077 [math.CO], 2018.
Christopher Zhu, Enumerating Permutations and Rim Hooks Characterized by Double Descent Sets, arXiv:1910.12818 [math.CO], 2019.

Cf. A065429, A080635, A111004, A117158, A177523, A177533.
Column k=0 of A162975.
Column k=3 of A242784.
Equals 1 + A000303. - Greg Dresden, Feb 22 2020

b:= proc(u, o, t) option remember;
     `if`(u+o=0, 1, add(b(u-j, o+j-1, 0), j=1..u)+
     `if`(t=1, 0,   add(b(u+j-1, o-j, 1), j=1..o)))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..23);  # Alois P. Heinz, Nov 04 2021

Table[Simplify[ n! SeriesCoefficient[ Series[ Sqrt[3] Exp[x/2]/(Sqrt[3] Cos[Sqrt[3]/2 x] - Sin[Sqrt[3]/2 x]), {x, 0, n}], n] ], {n, 0, 40}]
(* Second program: *)
b[u_, o_, t_, k_] := b[u, o, t, k] = If[t == k, (u + o)!, If[Max[t, u] + o < k, 0, Sum[b[u + j - 1, o - j, t + 1, k], {j, 1, o}] + Sum[b[u - j, o + j - 1, 1, k], {j, 1, u}]]];
a[n_] := b[0, n, 0, 2] - b[0, n, 0, 3] + 1;
a /@ Range[0, 40] (* Jean-François Alcover, Nov 09 2020, after Alois P. Heinz in A000303 *)

E.g.f.: 1/Sum_{i>=0} (x^(3*i)/(3*i)! - x^(3*i+1)/(3*i+1)!). [Corrected g.f. --> e.g.f. by Vaclav Kotesovec, Feb 15 2015]
Equivalently, e.g.f.: exp(x/2) * r / sin(r*x + (2/3)*Pi) where r = sqrt(3)/2. This has simple poles at (3*m+1)*x0 where x0 = Pi/sqrt(6.75) = 1.2092 approximately and m is an arbitrary integer. This yields the asymptotic expansion a(n)/n! ~ x0^(-n-1) * Sum((-1)^m * E^(3*m+1) / (3*m+1)^(n+1)) where E = exp(x0/2) = 1.8305+ and m ranges over all integers. - Noam D. Elkies, Nov 15 2001
E.g.f.: sqrt(3)*exp(x/2)/(sqrt(3)*cos(x*sqrt(3)/2) - sin(x*sqrt(3)/2) ); a(n+1) = Sum_{k=0..n} binomial(n, k)*a(k)*b(n-k) where b(n) = number of n-permutations without double falls and without initial falls. - Emanuele Munarini, Feb 28 2003
O.g.f.: A(x) = 1/(1 - x - x^2/(1 - 2*x - 4*x^2/(1 - 3*x - 9*x^2/(1 - ... - n*x - n^2*x^2/(1 - ...))))) (continued fraction). - Paul D. Hanna, Jan 17 2006
a(n) = leftmost column term of M^n*V, where M = an infinite tridiagonal matrix with (1,2,3,...) in the super, sub, and main diagonals and the rest zeros. V = the vector [1,0,0,0,...]. - Gary W. Adamson, Jun 16 2011
E.g.f.: A(x)=1/Q(0); Q(k)=1-x/((3*k+1)-(x^2)*(3*k+1)/((x^2)-3*(3*k+2)*(k+1)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, Nov 25 2011
a(n) ~ n! * exp(Pi/(3*sqrt(3))) * (3*sqrt(3)/(2*Pi))^(n+1). - Vaclav Kotesovec, Jul 28 2013
E.g.f.: T(0)/(1-x), where T(k) = 1 - x^2*(k+1)^2/( x^2*(k+1)^2 - (1-x-x*k)*(1-2*x-x*k)/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Oct 17 2013

Corrected and extended by Vladeta Jovovic, Apr 14 2001

A008304 Triangle read by rows: T(n,k) (n>=1; 1<=k<=n) is the number of permutations of [n] in which the longest increasing run has length k.

Original entry on oeis.org

1, 1, 1, 1, 4, 1, 1, 16, 6, 1, 1, 69, 41, 8, 1, 1, 348, 293, 67, 10, 1, 1, 2016, 2309, 602, 99, 12, 1, 1, 13357, 19975, 5811, 1024, 137, 14, 1, 1, 99376, 189524, 60875, 11304, 1602, 181, 16, 1, 1, 822040, 1960041, 690729, 133669, 19710, 2360, 231, 18, 1, 1, 7477161

Offset: 1

N. J. A. Sloane

Row n has n terms.

			Triangle T(n,k) begins:
  1;
  1,   1;
  1,   4,   1;
  1,  16,   6,  1;
  1,  69,  41,  8,  1;
  1, 348, 293, 67, 10,  1;
  ...
T(3,2) = 4 because we have (13)2, 2(13), (23)1, 3(12), where the parentheses surround runs of length 2.

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

Alois P. Heinz, Rows n = 1..141, flattened
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. W. Wilson, Extended tables for A008304 and A064315

Row sums give A000142. Sum_{k=1..n} k*T(n,k) = A064314(n). Cf. A064315.
Columns k=1-10 give: A000012, A000303, A000402, A000434, A000456, A000467, A230055, A230234, A230235, A230236.
T(2n+j,n+j) for j=0-10 gives: A230341, A230251, A230342, A230343, A230344, A230345, A230346, A230347, A230348, A230349, A230350.

b:= proc(u, o, t, k) option remember; `if`(t=k, (u+o)!,
      `if`(max(t, u)+o b(0, n, 0, k) -b(0, n, 0, k+1):
seq(seq(T(n,k), k=1..n), n=1..15);  # Alois P. Heinz, Oct 16 2013

b[u_, o_, t_, k_] := b[u, o, t, k] = If[t == k, (u + o)!, If[Max[t, u]+o < k, 0, Sum[b[u+j-1, o-j, t+1, k], {j, 1, o}] + Sum[b[u-j, o+j-1, 1, k], {j, 1, u}]]]; T[n_, k_] := b[0, n, 0, k] - b[0, n, 0, k+1]; Table[Table[T[n, k], {k, 1, n}], {n, 1, 15}] // Flatten (* Jean-François Alcover, Jan 10 2014, translated from Alois P. Heinz's Maple code *)
(*additional code*)
nn=12;a[r_]:=Apply[Plus,Table[Normal[Series[y x^(r+1)/(1-Sum[y x^i,{i,1,r}]),{x,0,nn}]][[n]]/(n+r)!,{n,1,nn-r}]]/.y->-1;Map[Select[#,#>0&]&,Transpose[Prepend[Table[Drop[Range[0,nn]! CoefficientList[Series[1/(1-x-a[n+1])-1/(1-x-a[n]),{x,0,nn}],x],1],{n,1,8}],Table[1,{nn}]]]]//Grid (* Geoffrey Critzer, Feb 25 2014 *)

E.g.f. of column k: 1/Sum_{n>=0} ((k+1)*n+1-x)*x^((k+1)*n)/((k+1)*n+1)! - 1/Sum_{n>=0} (k*n+1-x)*x^(k*n)/(k*n+1)!. - Alois P. Heinz, Oct 13 2013

T(n,k) = A122843(n,k) for k > n/2. - Alois P. Heinz, Oct 17 2013

More terms from David W. Wilson, Sep 07 2001

Better description from Emeric Deutsch, May 08 2004

A000402 Number of permutations of [n] in which the longest increasing run has length 3.

Original entry on oeis.org

0, 0, 1, 6, 41, 293, 2309, 19975, 189524, 1960041, 21993884, 266361634, 3465832370, 48245601976, 715756932697, 11277786883720, 188135296651083, 3313338641692957, 61444453534759589, 1196988740015236617, 24442368179977776766, 522124104504306695929

Offset: 1

N. J. A. Sloane

nonn

			a(4)=6 because we have (124)3, (134)2, (234)1, 4(123), 3(124) and 2(134), where the parentheses surround increasing runs of length 3.

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 261, Table 7.4.1. (Values for n>=16 are incorrect.)
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..452 (first 100 terms from Max Alekseyev)
Max A. Alekseyev, On the number of permutations with bounded runs length, arXiv preprint arXiv:1205.4581 [math.CO], 2012-2013. - From _N. J. A. Sloane_, Oct 23 2012

Column 3 of A008304. Other columns: A000303, A000434, A000456, A000467.

Cf. A001250, A001251, A001252, A001253, A010026, A211318.

b[u_, o_, t_, k_] := b[u, o, t, k] = If[t == k, (u + o)!, If[Max[t, u] + o < k, 0, Sum[b[u + j - 1, o - j, t + 1, k], {j, 1, o}] + Sum[b[u - j, o + j - 1, 1, k], {j, 1, u}]]];
T[n_, k_] := b[0, n, 0, k] - b[0, n, 0, k + 1];
a[n_] := T[n, 3];
Array[a, 30] (* Jean-François Alcover, Jul 19 2018, after Alois P. Heinz *)

Better description from Emeric Deutsch, May 08 2004

Terms a(16), a(17) are corrected and further terms added by Max Alekseyev, May 20 2012

A000434 Number of permutations of [n] in which the longest increasing run has length 4.

Original entry on oeis.org

0, 0, 0, 1, 8, 67, 602, 5811, 60875, 690729, 8457285, 111323149, 1569068565, 23592426102, 377105857043, 6387313185576, 114303481217657, 2155348564847332, 42719058006864690, 887953677898186108, 19316200230609433690, 438920223893512987430

Offset: 1

N. J. A. Sloane

nonn

			a(5)=8 because we have (1235)4, (1245)3, (1345)2, (2345)1, 5(1234), 4(1235), 3(1245) and 2(1345), where the parentheses surround increasing runs of length 4.

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 261. (Values for n>=16 are incorrect.)
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..450 (first 100 terms from Max Alekseyev)
Max A. Alekseyev, On the number of permutations with bounded runs length, arXiv preprint arXiv:1205.4581 [math.CO], 2012-2013. - From _N. J. A. Sloane_, Oct 23 2012

Column 4 of A008304. Other columns: A000303, A000402, A000456, A000467.

Cf. A001250, A001251, A001252, A001253, A010026, A211318.

b[u_, o_, t_, k_] := b[u, o, t, k] = If[t == k, (u + o)!, If[Max[t, u] + o < k, 0, Sum[b[u + j - 1, o - j, t + 1, k], {j, 1, o}] + Sum[b[u - j, o + j - 1, 1, k], {j, 1, u}]]];
T[n_, k_] := b[0, n, 0, k] - b[0, n, 0, k + 1];
a[n_] := T[n, 4];
Array[a, 30] (* Jean-François Alcover, Jul 19 2018, after Alois P. Heinz *)

Better description from Emeric Deutsch, May 08 2004

Terms a(16)-a(18) corrected and further terms added by Max Alekseyev, May 20 2012

A000456 Number of permutations of [n] in which the longest increasing run has length 5.

Original entry on oeis.org

0, 0, 0, 0, 1, 10, 99, 1024, 11304, 133669, 1695429, 23023811, 333840443, 5153118154, 84426592621, 1463941342191, 26793750988542, 516319125748337, 10451197169218523, 221738082618710329, 4921234092461339819, 114041894068935641488

Offset: 1

N. J. A. Sloane

nonn

			a(6)=10 because we have (12346)5, (12356)4, (12456)3, (13456)2, (23456)1, 6(12345), 5(12346), 4(12356), 3(12456) and 2(13456), where the parentheses surround increasing runs of length 5.

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 261.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..450 (first 100 terms from Max Alekseyev)
Max A. Alekseyev, On the number of permutations with bounded run lengths, arXiv preprint arXiv:1205.4581 [math.CO], 2012-2013.

Column 5 of A008304. Other columns: A000303, A000402, A000434, A000467.

Cf. A001250, A001251, A001252, A001253, A010026, A211318.

b[u_, o_, t_, k_] := b[u, o, t, k] = If[t == k, (u + o)!, If[Max[t, u] + o < k, 0, Sum[b[u + j - 1, o - j, t + 1, k], {j, 1, o}] + Sum[b[u - j, o + j - 1, 1, k], {j, 1, u}]]]; T[n_, k_] := b[0, n, 0, k] - b[0, n, 0, k + 1]; a[n_] := T[n, 5]; Array[a, 25] (* Jean-François Alcover, Feb 08 2016, after Alois P. Heinz in A008304 *)

Better description from Emeric Deutsch, May 08 2004

Edited and extended by Max Alekseyev, May 20 2012

A000467 Number of permutations of [n] in which the longest increasing run has length 6.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 12, 137, 1602, 19710, 257400, 3574957, 52785901, 827242933, 13730434111, 240806565782, 4452251786946, 86585391630673, 1767406549387381, 37790452850585180, 844817788372455779, 19711244788916894489, 479203883157602851294

Offset: 1

N. J. A. Sloane

nonn

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 261.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..450 (first 100 terms from Max Alekseyev)
Max A. Alekseyev, On the number of permutations with bounded run lengths, arXiv preprint arXiv:1205.4581 [math.CO], 2012.

Column 6 of A008304. Other columns: A000303, A000402, A000434, A000456.

Cf. A001250, A001251, A001252, A001253, A010026, A211318.

b[u_, o_, t_, k_] := b[u, o, t, k] = If[t == k, (u + o)!, If[Max[t, u] + o < k, 0, Sum[b[u + j - 1, o - j, t + 1, k], {j, 1, o}] + Sum[b[u - j, o + j - 1, 1, k], {j, 1, u}]]]; T[n_, k_] := b[0, n, 0, k] - b[0, n, 0, k + 1]; a[n_] := T[n, 6]; Array[a, 23] (* Jean-François Alcover, Feb 08 2016, after Alois P. Heinz in A008304 *)

Edited and extended by Max Alekseyev, May 20 2012

cp's OEIS Frontend

A049774 Number of permutations of n elements not containing the consecutive pattern 123.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A008304 Triangle read by rows: T(n,k) (n>=1; 1<=k<=n) is the number of permutations of [n] in which the longest increasing run has length k.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A000402 Number of permutations of [n] in which the longest increasing run has length 3.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

Extensions

A000434 Number of permutations of [n] in which the longest increasing run has length 4.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

Extensions

A000456 Number of permutations of [n] in which the longest increasing run has length 5.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

Extensions

A000467 Number of permutations of [n] in which the longest increasing run has length 6.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Extensions