A197365 -id:A197365 - 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)

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

A263886 Number of permutations of [n] containing exactly two occurrences of the consecutive pattern 132.

Original entry on oeis.org

3, 56, 753, 9024, 104814, 1228608, 14824314, 185991936, 2438459325, 33476112000, 481470208575, 7252002478080, 114295913943660, 1882806417303552, 32377593994012260, 580478495476948992, 10835925949596420135, 210343353555466229760, 4240673559279540077085

Offset: 5

Alois P. Heinz, Oct 28 2015

nonn

			a(5) = 3: 13254, 14253, 15243.
a(6) = 56: 124365, 125364, 126354, ..., 613254, 614253, 615243.
a(7) = 753: 1235476, 1236475, 1237465, ..., 7613254, 7614253, 7615243.
a(8) = 9024: 12346587, 12347586, 12348576, ..., 87613254, 87614253, 87615243.

Alois P. Heinz, Table of n, a(n) for n = 5..200

Column k=2 of A197365.

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

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

A263887 Number of permutations of [n] containing exactly three occurrences of the consecutive pattern 132.

Original entry on oeis.org

15, 576, 13572, 259968, 4532034, 75929856, 1259571660, 21052915200, 358291184565, 6248298977280, 112089186363960, 2073140406374400, 39582481045276260, 780630651563728896, 15904712294529556680, 334724021030855393280, 7274246960518735730715

Offset: 7

Alois P. Heinz, Oct 28 2015

nonn

			a(7) = 15: 1325476, 1326475, 1327465, 1425376, 1426375, 1427365, 1524376, 1526374, 1527364, 1624375, 1625374, 1627354, 1724365, 1725364, 1726354.
a(8) = 576: 12436587, 12437586, 12438576, ..., 81724365, 81725364, 81726354.
a(9) = 13572: 123547698, 123548697, 123549687, ..., 981724365, 981725364, 981726354.

Alois P. Heinz, Table of n, a(n) for n = 7..200

Column k=3 of A197365.

b:= proc(u, o, t) option remember; series(`if`(u+o=0, 1,
      add(b(u-j, o+j-1, 0)*`if`(j<=t, x, 1), j=1..u)+
      add(b(u+j-1, o-j, j-1), j=1..o)), x, 4)
    end:
a:= n-> coeff(b(n, 0$2), x, 3):
seq(a(n), n=7..30);

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

A263888 Number of permutations of [n] containing exactly four occurrences of the consecutive pattern 132.

Original entry on oeis.org

105, 7968, 306729, 8862336, 221041785, 5090751360, 112456455285, 2438635714560, 52685573396310, 1145097655557120, 25201633254603750, 564111809386352640, 12881077471698335550, 300654388617807974400, 7182803417002318476630, 175794354355113443819520

Offset: 9

Alois P. Heinz, Oct 28 2015

nonn

			a(9) = 105: 132547698, 132548697, 132549687, ..., 192835476, 192836475, 192837465.

Alois P. Heinz, Table of n, a(n) for n = 9..100

Column k=4 of A197365.

b:= proc(u, o, t) option remember; series(`if`(u+o=0, 1,
      add(b(u-j, o+j-1, 0)*`if`(j<=t, x, 1), j=1..u)+
      add(b(u+j-1, o-j, j-1), j=1..o)), x, 5)
    end:
a:= n-> coeff(b(n, 0$2), x, 4):
seq(a(n), n=9..35);

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

A263889 Number of permutations of [n] containing exactly five occurrences of the consecutive pattern 132.

Original entry on oeis.org

945, 140160, 8451954, 354288384, 12220104063, 375886190592, 10790720535960, 297346489233408, 8010916259737230, 213667262746914816, 5691371451612082740, 152338392950319636480, 4115775817227930936570, 112602904310385883054080, 3126998971137511212293880

Offset: 11

Alois P. Heinz, Oct 28 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 11..100

Column k=5 of A197365.

b:= proc(u, o, t) option remember; series(`if`(u+o=0, 1,
      add(b(u-j, o+j-1, 0)*`if`(j<=t, x, 1), j=1..u)+
      add(b(u+j-1, o-j, j-1), j=1..o)), x, 6)
    end:
a:= n-> coeff(b(n, 0$2), x, 5):
seq(a(n), n=11..35);

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

A263890 Number of permutations of [n] containing exactly six occurrences of the consecutive pattern 132.

Original entry on oeis.org

10395, 3012480, 277327917, 16406489088, 763149164940, 30667267344384, 1122292869796980, 38645459934584832, 1279503424901535750, 41344577034084495360, 1317786118947932739210, 41752272883943166935040, 1322547105675938413149900, 42063243395064705257472000

Offset: 13

Alois P. Heinz, Oct 28 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 13..100

Column k=6 of A197365.

b:= proc(u, o, t) option remember; series(`if`(u+o=0, 1,
      add(b(u-j, o+j-1, 0)*`if`(j<=t, x, 1), j=1..u)+
      add(b(u+j-1, o-j, j-1), j=1..o)), x, 7)
    end:
a:= n-> coeff(b(n, 0$2), x, 6):
seq(a(n), n=13..35);

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

A263891 Number of permutations of [n] containing exactly seven occurrences of the consecutive pattern 132.

Original entry on oeis.org

135135, 76769280, 10623587400, 869421477888, 53506915544340, 2760751748210688, 126815221020754440, 5382400437244477440, 216344464203055466790, 8377766827724961054720, 316434243063274830653400, 11764325342293663024742400, 433465553417224967969040900

Offset: 15

Alois P. Heinz, Oct 28 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 15..100

Column k=7 of A197365.

b:= proc(u, o, t) option remember; series(`if`(u+o=0, 1,
      add(b(u-j, o+j-1, 0)*`if`(j<=t, x, 1), j=1..u)+
      add(b(u+j-1, o-j, j-1), j=1..o)), x, 8)
    end:
a:= n-> coeff(b(n, 0$2), x, 7):
seq(a(n), n=15..35);

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

A263892 Number of permutations of [n] containing exactly eight occurrences of the consecutive pattern 132.

Original entry on oeis.org

2027025, 2266145280, 467264653965, 52135907088384, 4183054629844995, 273302114875729920, 15559739185621805235, 804731991294567628800, 38866311953961514404975, 1787021214083758837555200, 79318135487882387789779275, 3434027248121360673543782400

Offset: 17

Alois P. Heinz, Oct 28 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 17..100

Column k=8 of A197365.

b:= proc(u, o, t) option remember; series(`if`(u+o=0, 1,
      add(b(u-j, o+j-1, 0)*`if`(j<=t, x, 1), j=1..u)+
      add(b(u+j-1, o-j, j-1), j=1..o)), x, 9)
    end:
a:= n-> coeff(b(n, 0$2), x, 8):
seq(a(n), n=17..35);

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

A263893 Number of permutations of [n] containing exactly nine occurrences of the consecutive pattern 132.

Original entry on oeis.org

34459425, 76077066240, 23268095463150, 3502499376844800, 362160710593122645, 29628651314310266880, 2068889029242559281900, 129136429755219072614400, 7428565762326237479436675, 402305799817247440225075200, 20831246409166627215418935750

Offset: 19

Alois P. Heinz, Oct 28 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 19..100

Column k=9 of A197365.

b:= proc(u, o, t) option remember; series(`if`(u+o=0, 1,
      add(b(u-j, o+j-1, 0)*`if`(j<=t, x, 1), j=1..u)+
      add(b(u+j-1, o-j, j-1), j=1..o)), x, 10)
    end:
a:= n-> coeff(b(n, 0$2), x, 9):
seq(a(n), n=19..35);

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

cp's OEIS Frontend

A111004 Number of permutations avoiding a consecutive 132 pattern.

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

A263886 Number of permutations of [n] containing exactly two occurrences of the consecutive pattern 132.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A263887 Number of permutations of [n] containing exactly three occurrences of the consecutive pattern 132.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A263888 Number of permutations of [n] containing exactly four occurrences of the consecutive pattern 132.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A263889 Number of permutations of [n] containing exactly five occurrences of the consecutive pattern 132.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

A263890 Number of permutations of [n] containing exactly six occurrences of the consecutive pattern 132.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

A263891 Number of permutations of [n] containing exactly seven occurrences of the consecutive pattern 132.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula