A324130 -id:A324130 - cp's OEIS frontend

A111004 Number of permutations avoiding a consecutive 132 pattern.

1, 1, 2, 5, 16, 63, 296, 1623, 10176, 71793, 562848, 4853949, 45664896, 465403791, 5108121216, 60069714207, 753492215808, 10042248398625, 141712039383552, 2110880441637045, 33097631526180864, 544903371859138335, 9398216812334008320, 169463659008217238055

Offset: 0

David Callan, Oct 01 2005

nonn

a(n) is the number of permutations on [n] that avoid the consecutive pattern 132 (pattern entries must occur consecutively in the permutation).
In the Mathematica code below, a[n, k] is the number of such permutations with first entry k and they are counted recursively by the length, say ell, of the longest increasing left factor L. (For ell >= 2 the first entry following L must be < the penultimate entry of L or else a consecutive 132 would occur.) The first sum counts ell = 1, the second ell = 2, the third ell >= 3; m is the penultimate entry of L and j is the first entry in the (reduced) subpermutation following L. Note that j is indexed from 0 to cover the case when L is the entire permutation.
Asymptotically, a(n)/n! ~ c/r^n where r = 1.2755477364172... is the unique positive root of Integrate[exp(-t^2/2), {t,0,r}] = 1 and c = exp(r^2/2)/r = 1.7685063678958....

			The first 3 entries of 2431 form a consecutive 132 pattern.
The 4!-a(4) = 8 permutations on [4] that DO contain a consecutive 132 pattern are 1243, 1324, 1423, 1432, 2143, 2431, 3142, 4132. Also, for example, 1342 contains a scattered 1-3-2 pattern but not a consecutive 132.

Ray Chandler, Table of n, a(n) for n = 0..200
A. Baxter, B. Nakamura, and D. Zeilberger. Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes
Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns, arXiv:math/0505254 [math.CO], 2005.
S. Elizalde and M. Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110-125.
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.

Cf. A049774, A197365, A324130, A324134.

Row m = 0 of A327722.

Clear[a]; a[0, 0] = a[0] = 1; a[n_, 0]/;n>=1 := 0; a[n_, k_]/;k>n := 0; a[n_, k_]/;1<=k<=n<=2 := 1; a[n_, k_]/;n>=3 := a[n, k] = Sum[a[n-1, j], {j, k-1}] + (n-k)Sum[a[n-2, j], {j, k-1}] + Sum[(n-m) Binomial[m-k-1, ell-3]a[n-ell, j], {ell, 3, n-k+1}, {m, k+ell-2, n-1}, {j, 0, m-ell+1}]; a[n_]/;n>=1 := a[n] = Sum[a[n, k], {k, n}]; Table[a[n], {n, 0, 15}]
(* or, faster *) ExpGfToList[f_, n_, x_] := CoefficientList[Normal[Series[f, {x, 0, n}]] /. x^(pwr_) -> pwr!*x^pwr, x]; ExpGfToList[1/( 1-(Pi/2)^(1/2)*Erf[z/2^(1/2)] ), 25, z]

E.g.f.: Sum_{n >= 0} a(n) x^n/n! = 1/( 1 - (Pi/2)^(1/2)*Erf(x/2^(1/2)) ).
a(n) = A197365(n,0). - Peter Bala, Oct 14 2011
From Sergei N. Gladkovskii, Nov 28 2011: (Start)
E.g.f.: A(x) = 1/( 1 - (Pi/2)^(1/2)*erf(x/2^(1/2)) ) = (1 + (x^3)/(2*(x-1)*W(0) -(x^2)))/(1 - x) with
W(k) = 2*(k^2) + (5 - 4*(x^2))*k + 3 - 2*(x^2) + 2*(x^2)*(k+1)*((2*k + 3)^2)/W(k+1) (continued fraction). (End)

A324134 Number of permutations of [n] that avoid the shuffle pattern s-k-t, where s = 12 and t = 132.

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 710, 4800, 36298, 302780, 2758618, 27246450, 289962508, 3308024082, 40278949800, 521427324542, 7152011191362, 103621538280688, 1581465201545374, 25361207137790358, 426374509273382756, 7499269147438400178, 137728268057069904088, 2636572230825216681414

Offset: 0

N. J. A. Sloane, Feb 16 2019

nonn

			From _Petros Hadjicostas_, Oct 31 2019: (Start)
In a permutation of [n] that contains the shuffle pattern s-k-t, where s = 12 and t = 132, k should be greater than the numbers in pattern s and the numbers in pattern t. (The numbers in each of the patterns s and t should be contiguous.) Clearly, for n = 0..5, all permutations of [n] avoid this shuffle pattern (since we need at least six numbers to get this pattern). Hence, a(n) = n! for n = 0..5.
For n = 6, k should be equal to 6, and for the pattern s = 12 we have the 10 choices 12, 13, 14, 15, 23, 24, 25, 34, 35, and 45. The corresponding permutations of [6] that contain this shuffle pattern are 126354, 136254, 146253, 156243, 236154, 246153, 256143, 346152, 356142, and 456132. Thus, a(6) = 6! - 10 = 710. (End)

Sergey Kitaev, Partially Ordered Generalized Patterns, Discrete Math. 298 (2005), no. 1-3, 212-229.

Cf. A000142, A111004, A324130.

Let b(n) = A111004(n) = number of permutations avoiding a consecutive 132 pattern. Then a(n) = Sum_{i = 0..n-1} binomial(n-1,i) * (a(n-1-i) + b(i) * a(n-1-i) - b(n-1-i)) for n >= 1 with a(0) = b(0) = 1. [See the recurrence for C_n on p. 220 of Kitaev (2005).] - Petros Hadjicostas, Oct 30 2019

More terms from Petros Hadjicostas, Oct 30 2019

cp's OEIS Frontend

A111004 Number of permutations avoiding a consecutive 132 pattern.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula