A240885 -id:A240885 - cp's OEIS frontend

A113229 Number of permutations avoiding the consecutive pattern 3412.

1, 1, 2, 6, 23, 110, 631, 4223, 32301, 277962, 2657797, 27954521, 320752991, 3987045780, 53372351265, 765499019221, 11711207065229, 190365226548070, 3276401870322033, 59523410471007913, 1138295039078030599, 22856576346825690128, 480807130959249565541

Offset: 0

David Callan, Oct 19 2005

nonn

a(n) is the number of permutations on [n] that avoid the consecutive pattern 3412 (also number that avoid 2143).

			The 5! - a(5) = 10 permutations on [5] not counted by a(5) are 14523, 24513, 34125, 34512, 35124, 43512, 45123, 45132, 45231, 53412.

Alois P. Heinz, Table of n, a(n) for n = 0..200 (terms n = 0..60 from Ray Chandler)
A. Baxter, B. Nakamura, and D. Zeilberger. Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes
V. Dotsenko and A. Khoroshkin, Shuffle algebras, homology, and consecutive pattern avoidance, arXiv preprint arXiv:1109.2690 [math.CO], 2011.
Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns, arXiv:math/0505254 [math.CO], 2005.
Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns, Adv. in Appl. Math. 36 (2006), no. 2, 138-155.
S. Elizalde and M. Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110-125.
Steven Finch, Pattern-Avoiding Permutations [Broken link?]
Steven Finch, Pattern-Avoiding Permutations [Cached copy, with permission]

Cf. A113228, A117156, A117158, A117226, A201692, A201693.

Column k=0 of A264319.

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

b[u_, o_, t_] := b[u, o, t] = If[u+o == 0, 1, Sum[b[u-j, o+j-1, If[t>0 && j>t, t-j, 0]], {j, 1, u}] + Sum[b[u+j-1, o-j, j], {j, Range[If[t<0, 1-t, 1], o]}]]; a[n_] := b[n, 0, 0]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Mar 13 2015, after Alois P. Heinz *)

The Dotsenko et al. reference gives a g.f. There is an associated triangle of numbers c_{n,l} that should be added to the OEIS if it is not already present.

a(n) ~ c * d^n * n!, where d = 0.9561742431150784273897350385923872770208469..., c = 1.1465405299007850875068632404058971045769... . - Vaclav Kotesovec, Aug 23 2014

A052319 Number of increasing rooted trimmed trees with n nodes.

Original entry on oeis.org

1, 1, 1, 2, 7, 28, 131, 720, 4513, 31824, 249513, 2151744, 20242983, 206313024, 2264425179, 26628836352, 334022337153, 4451717814528, 62820790592913, 935750983412736, 14672143677452679, 241555066200437760

Offset: 1

Christian G. Bower, Dec 11 1999

In an increasing rooted tree, nodes are numbered and numbers increase as you move away from root.
A trimmed tree is a tree with a forbidden limb of length 2.
A tree with a forbidden limb of length k is a tree where the path from any leaf inward hits a branching node or another leaf within k steps.
Number of permutations on [n+1] beginning with 12 and avoiding a consecutive 132 pattern (n>=1). For example, a(4)=2 counts 12345, 12453. - Ralf Stephan, Apr 25 2004

Vaclav Kotesovec, Table of n, a(n) for n = 1..465
M. E. Jones and J. B. Remmel, Pattern matching in the cycle structures of permutations, Pure Math. Appl. (PU.M.A.), 22 (2011) 173-208.
S. Kitaev, Generalized pattern avoidance with additional restrictions, Sem. Lothar. Combinat. B48e (2003).
S. Kitaev and T. Mansour, Simultaneous avoidance of generalized patterns, arXiv:math/0205182 [math.CO], 2002.
Rupert Li, Vincular Pattern Avoidance on Cyclic Permutations, arXiv:2107.12353 [math.CO], 2021, p. 7.
Index entries for sequences related to rooted trees

Cf. A002955, A002988-A002992, A052318-A052329.

seq(n! * coeff(series(-log(1-sqrt(Pi/2)*erf(x/sqrt(2))), x, n+1), x, n), n=1..20) # Vaclav Kotesovec, Jan 07 2014

Rest[CoefficientList[Series[-Log[1-Sqrt[Pi/2]*Erf[x/Sqrt[2]]], {x, 0, 20}], x] * Range[0, 20]!] (* Vaclav Kotesovec, Jan 07 2014 *)

E.g.f.: A(x) = 1/B(-x) where B'(x) is e.g.f. of A006882 and B(0) = 1.
E.g.f.: A(x) satisfies A'(x) = exp(A(x)-x^2/2).
E.g.f.: exp(-x^2/2)/(1-int[0..x, exp(-x^2/2)]). - Ralf Stephan, Apr 25 2004
E.g.f.: -log(1-sqrt(Pi/2)*erf(x/sqrt(2))). - Vaclav Kotesovec, Jan 07 2014
Limit n->infinity (a(n)/n!)^(1/n) = 1/(sqrt(2)*InverseErf(sqrt(2/Pi))) = 1/A240885 = 0.7839769312035474991... - Vaclav Kotesovec, Jan 07 2014
a(n) ~ (n-1)! / (sqrt(2)*InverseErf(sqrt(2/Pi)))^n. - Vaclav Kotesovec, Aug 22 2014

Formula updated by Christian G. Bower, Mar 06 2001

A200404 Number of permutations of [n] avoiding the pattern 143-2.

Original entry on oeis.org

1, 2, 6, 23, 107, 582, 3622, 25369, 197523, 1692535, 15829557, 160463512, 1752529064, 20516018396, 256273980368, 3402364791737, 47841014687039, 710242228143271, 11101522062378069, 182234745428876525, 3134424458578405569, 56371116965252450338

Offset: 1

N. J. A. Sloane, Nov 17 2011

nonn

Vaclav Kotesovec, Table of n, a(n) for n = 1..465
Juan S. Auli, Pattern Avoidance in Inversion Sequences, Ph. D. thesis, Dartmouth College, ProQuest Dissertations Publishing (2020), 27964164.
Juan S. Auli and Sergi Elizalde, Consecutive Patterns in Inversion Sequences, arXiv:1904.02694 [math.CO], 2019. See Table 1.
Andrew M. Baxter and Lara K. Pudwell, Enumeration schemes for vincular patterns, arXiv preprint arXiv:1108.2642 [math.CO], 2011-2012.
Yan Wang, Qi Fang, Shishuo Fu, Sergey Kitaev, and Haijun Li, Consecutive and quasi-consecutive patterns: des-Wilf classifications and generating functions, arXiv:2502.10128 [math.CO], 2025. See p. 9.

i120[1] = 1; i120[2] = 2; i120[n_] := i120[n] = Sum[s120[n, k], {k, 0, n - 1}]; s120[n_, k_] := s120[n, k] = i120[n - 1] - Sum[(n - 2 - j)*s120[n - 2, j], {j, k + 1, n - 2}]; Table[i120[m], {m, 1, 25}] (* Vaclav Kotesovec, Oct 17 2019 *)

a(n) ~ c * d^n * n! * n^alfa, where d = 1/A240885 = 1/(sqrt(2) * InverseErf(sqrt(2/Pi))), alfa = 0.96094544076267076286993824810734... and c = 0.5103992709959036090170192609... - Vaclav Kotesovec, Oct 17 2019

a(11)-a(15) from Lars Blomberg, Apr 16 2018

a(16)-a(22) from Vaclav Kotesovec, Oct 17 2019

A113226 Number of permutations of [n] avoiding the pattern 12-34.

Original entry on oeis.org

1, 1, 2, 6, 23, 107, 585, 3669, 25932, 203768, 1761109, 16595757, 169287873, 1857903529, 21823488238, 273130320026, 3627845694283, 50962676849199, 754814462534449, 11754778469338581, 191998054346198680

Offset: 0

David Callan, Oct 19 2005

nonn

a(n) is the number of permutations on [n] that avoid the vincular pattern 12-34 (also the number that avoid 43-21).
a(n) is also the number of permutations on [n] that avoid the vincular pattern 12-43 (or 21-34 or 34-21 or 43-12) or 21-43 (or 34-12). - David Bevan, Nov 15 2023
a(n) is also the number of {3,2+2}-free naturally labeled posets. - David Bevan, Nov 15 2023

			523146 contains 2346 as a 12-34 pattern because the 23 and 46 are adjacent in the permutation and the reduced form of 2346 is 1234.

David Bevan, Table of n, a(n) for n = 0..471
A. M. Baxter, Algorithms for Permutation Statistics, Ph. D. Dissertation, Rutgers University, May 2011.
Andrew M. Baxter and Lara K. Pudwell, Enumeration schemes for dashed patterns, arXiv preprint arXiv:1108.2642 [math.CO], 2011.
David Bevan, Gi-Sang Cheon and Sergey Kitaev, On naturally labelled posets and permutations avoiding 12-34, arXiv:2311.08023 [math.CO], 2023.
Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns, arXiv:math/0505254 [math.CO], 2005.
Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns, Adv. in Appl. Math. 36 (2006), no. 2, 138-155.
Steven Finch, Pattern-Avoiding Permutations [Broken link?]
Steven Finch, Pattern-Avoiding Permutations [Cached copy, with permission]

Cf. A135922 (3-free naturally labeled posets).

Clear[u, v, w]; w[0] = w[1] = 1; w[n_] /; n >= 2 := w[n] = u[n] + v[n];
v[n_] /; n >= 2 := v[n] = Sum[v[n, a], {a, 2, n}]; v[1, 1] = 1;
v[n_, a_] /; 2 <= a <= n :=
v[n, a] = Sum[u[n - 1, b], {b, a - 1}] + Sum[v[n - 1, b], {b, 2, a - 1}];
u[1] = 1; u[n_] /; n >= 2 := u[n] = Sum[u[n, a], {a, n - 1}]; u[1, 1] = 1;
u[n_, a_] /; a == n := 0; u[n_, a_] /; 1 <= a < n := u[n, a, n];
u[1, 1, k_] := 1; u[2, 1, k_] := 1; u[n_, a_, k_] /; a >= n := 0;
u[n_, a_, k_] /; 1 <= a < n && n >= 3 :=
u[n, a, k] = Sum[u[n, a, k, b], {b, a + 1, n}];
u[n_, a_, k_, b_] /; 1 <= a < b <= n && k >= b + 2 := u[n, a, b + 1, b];
u[n_, a_, k_, b_] /; 1 <= a < n && b == n && k == n + 1 := u[n, a, n, n];
u[n_, a_, k_, b_] /; 1 == a < b == n && k == 2 := 1;
u[n_, a_, k_, b_] /; 1 <= a < b <= n && k <= b :=
u[n, a, k, b] =
  Sum[Binomial[b - k - If[k <= a, 1, 0], j1] Binomial[
     k - 1 - If[a < k, 1, 0] - c, j2]*
    u[n - 2 - j1 - j2, c, k - If[a < k, 1, 0] - j2], {c,
    k - 1 - If[a < k, 1, 0]}, {j1, 0, b - k - If[k <= a, 1, 0]}, {j2, 0,
    k - 1 - If[a < k, 1, 0] - c}];
u[n_, a_, k_, b_] /; 1 <= a < b < n && k == b + 1 && {a, b} == {1, 2} := 1;
u[n_, a_, k_, b_] /; 1 <= a < b < n && k == b + 1 && {a, b} != {1, 2} :=
u[n, a, k, b] =
  Sum[Binomial[n - b, i] Binomial[b - 2 - c, j] u[n - 2 - i - j, c,
     b - 1 - j], {c, b - 2}, {i, 0, n - b}, {j, 0, b - 2 - c}]; Table[
w[n], {n, 0, 15}]

In the recurrence coded in Mathematica below, w[n] = # (12-34)-avoiding permutations on [n]; v[n, a] is the number that start with a descent and have first entry a; u[n, a, k, b] is the number that start with an ascent and that have (i) first entry a, (ii) other than a, all ascent initiators

A263885 Number of permutations of [n] containing exactly one occurrence of the consecutive pattern 132.

Original entry on oeis.org

1, 8, 54, 368, 2649, 20544, 172596, 1569408, 15398829, 162412416, 1834081890, 22093090560, 282889238253, 3837991053312, 55010010678120, 830731742908416, 13185328329110745, 219457733809563648, 3822426663111579150, 69538569862816419840, 1318999546575572747265

Offset: 3

Alois P. Heinz, Oct 28 2015

nonn

			a(3) = 1: 132.
a(4) = 8: 1243, 1324, 1423, 1432, 2143, 2431, 3142, 4132.
a(5) = 54: 12354, 12435, 12534, ..., 52431, 53142, 54132.
a(6) = 368: 123465, 123546, 123645, ..., 652431, 653142, 654132.
a(7) = 2649: 1234576, 1234657, 1234756, ..., 7652431, 7653142, 7654132.

Alois P. Heinz, Table of n, a(n) for n = 3..200
Eric Weisstein's World of Mathematics, Inverse Erf

Column k=1 of A197365.

b:= proc(u, o, t, c) option remember; `if`(u+o=0, c, add(
      b(u-j, o+j-1, 0, c+`if`(j<=t, 1, 0)), j=`if`(c=1, t, 0)
      +1..u) +add(b(u+j-1, o-j, j-1, c), j=1..o))
    end:
a:= n-> b(n, 0$3):
seq(a(n), n=3..30);

Drop[Coefficient[CoefficientList[Series[1/(1 - (Sqrt[Pi/2]*Erfi[(Sqrt[u-1]*x) / Sqrt[2]])/Sqrt[u-1]), {x, 0, 25}], x] * Range[0, 25]!, u], 3] (* Vaclav Kotesovec, Oct 29 2015 *)

a(n) = A197365(n,1).

a(n) ~ c * d^n * n! * n, where d = 1/A240885 = 1/(sqrt(2) * InverseErf(sqrt(2/Pi))) = 0.78397693120354749... and c = 0.679554202696108785... . - Vaclav Kotesovec, Oct 29 2015

A011104 Decimal expansion of 5th root of 19.

Original entry on oeis.org

1, 8, 0, 1, 9, 8, 3, 1, 2, 7, 3, 1, 7, 1, 4, 2, 3, 0, 5, 1, 8, 2, 5, 5, 3, 9, 5, 2, 9, 6, 1, 8, 9, 0, 2, 5, 8, 9, 4, 3, 7, 0, 9, 7, 0, 2, 2, 8, 0, 0, 5, 3, 2, 6, 8, 0, 3, 7, 2, 5, 2, 0, 3, 0, 4, 2, 9, 4, 0, 7, 6, 2, 3, 5, 6, 3, 0, 6, 7, 0, 2, 6, 6, 8, 8, 0, 4, 4, 2, 5, 7, 5, 4, 4, 4, 8, 3, 8, 8

Offset: 1

N. J. A. Sloane

			1.80198312731714230518255395...

Ivan Panchenko, Table of n, a(n) for n = 1..1000
Steven Finch, Pattern-Avoiding Permutations [Broken link?]
Steven Finch, Pattern-Avoiding Permutations [Cached copy, with permission]

Root(19,5); // Vincenzo Librandi, Feb 20 2015

RealDigits[19^(1/5), 10, 100][[1]] (* Alonso del Arte, Feb 19 2015 *)

sqrtn(19,5) \\ Charles R Greathouse IV, Apr 16 2014

A328500 Number of inversion sequences of length n avoiding the consecutive pattern 102.

Original entry on oeis.org

1, 1, 2, 6, 22, 96, 492, 2902, 19350, 143918, 1181540, 10614698, 103589738, 1091367634, 12346368424, 149276823258, 1921099070062, 26220186000950, 378308908684300, 5753387612678314, 91988260677198002, 1542570178562361018, 27072325866355742048

Offset: 0

Vaclav Kotesovec and Juan S. Auli, Oct 17 2019

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..250
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 3.

Cf. A049774, A071075, A200404.

b:= proc(n, j, t) option remember; `if`(n=0, 1, add(
      `if`(i<=j or i>=t, b(n-1, i, j), 0), i=1..n))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..25);  # Alois P. Heinz, Oct 18 2019

b[n_, j_, t_] := b[n, j, t] = If[n == 0, 1, Sum[If[i <= j || i >= t, b[n - 1, i, j], 0], {i, 1, n}]];
a[n_] := b[n, 0, 0];
a /@ Range[0, 25] (* Jean-François Alcover, Mar 01 2020, after Alois P. Heinz *)

a(n) ~ n! * c * d^n * n^alfa, where d = 1/A240885 = 1/(sqrt(2) * InverseErf(sqrt(2/Pi))), alfa = 0.294868853646259565..., c = 2.22826071050847602... - Vaclav Kotesovec, Oct 19 2019

A328501 Number of inversion sequences of length n avoiding the consecutive pattern 201.

Original entry on oeis.org

1, 1, 2, 6, 24, 118, 684, 4548, 34036, 282696, 2577936, 25589100, 274539856, 3164909164, 39006958856, 511759353776, 7120140764224, 104703385864788, 1622530610142744, 26425922582118000, 451264786489454168, 8062192403534869432, 150395837509736576208

Offset: 0

Vaclav Kotesovec and Juan S. Auli, Oct 17 2019

nonn

Vaclav Kotesovec, Table of n, a(n) for n = 0..465
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 3.

Cf. A049774, A071075, A200404.

a(n) ~ n! * c * d^n * n^alfa, where d = 1/A240885 = 1/(sqrt(2) * InverseErf(sqrt(2/Pi))) = 0.783976931203547499124248654869812535747328200022..., alfa = 1.9218908815253415257398764962146978742409244378248756048362586275529..., c = 0.05831456121798260255226478044037424484656774525125436523149657... - Vaclav Kotesovec, Oct 18 2019

Previous Showing 11-18 of 18 results.

cp's OEIS Frontend

A113229 Number of permutations avoiding the consecutive pattern 3412.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A052319 Number of increasing rooted trimmed trees with n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A200404 Number of permutations of [n] avoiding the pattern 143-2.

Views

Author

Keywords

Links

Programs

Mathematica

Formula

Extensions

A113226 Number of permutations of [n] avoiding the pattern 12-34.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A263885 Number of permutations of [n] containing exactly one occurrence of the consecutive pattern 132.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A011104 Decimal expansion of 5th root of 19.

Views

Author

Keywords

Examples

Links

Programs

Magma

Mathematica

PARI

A328500 Number of inversion sequences of length n avoiding the consecutive pattern 102.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A328501 Number of inversion sequences of length n avoiding the consecutive pattern 201.

Views

Author

Keywords