A327722 -id:A327722 - cp's OEIS frontend

A202213 Number of permutations of [n] avoiding the consecutive pattern 45321.

1, 1, 2, 6, 24, 119, 708, 4914, 38976, 347765, 3447712, 37598286, 447294144, 5764747515, 80011430240, 1189835682714, 18873422539776, 318085061976105, 5676223254661760, 106919460527212950, 2119973556022047744, 44136046410218669055, 962630898723772565760

Offset: 0

Ray Chandler, Dec 14 2011

nonn

a(n) is the number of permutations on [n] that avoid the consecutive pattern 45321. It is the same as the number of permutations which avoid 12354, 21345 or 54312.

Alois P. Heinz, Table of n, a(n) for n = 0..200 (terms n = 1..40 from Ray Chandler)
A. Baxter, B. Nakamura, and D. Zeilberger, Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes, 2011.
Sergi Elizalde and Marc Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110-125; see Theorem 3.2 (p. 116) with m = a = 3 and u = 0.
Eric Weisstein's World of Mathematics, Pochhammer Symbol.
Wikipedia, Falling and rising factorials.

Cf. A177523, A202214-A202236, A329070.

Column k = 0 of A264781 and row m = 2 of A327722.

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

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

From Petros Hadjicostas, Nov 02 2019: (Start)
E.g.f.: 1/W(z), where W(z) = 1 + Sum_{n >= 0} (-1)^(n+1)* z^(4*n+1)/(b(n)*(4*n+1)) with b(n) = A329070(n,4) = (4*n)!/(4^n*(1/4)_n). (Here (x)_n = x*(x + 1)*...*(x + n - 1) is the Pochhammer symbol, or rising factorial, which is denoted by (x)^n in some papers and books.)  The function W(z) satisfies the o.d.e. W^(4)(z) + z*W'(z) = 0 with W(0) = 1, W'(0) = -1, and W^(k)(0) = 0 for k = 2..3. [See Theorem 3.2 (with m = a = 3 and u = 0) in Elizalde and Noy (2003).]
a(n) = Sum_{m = 0..floor((n-1)/4)} (-4)^m * (1/4)_m * binomial(n, 4*m+1) * a(n-4*m-1) for n >= 1 with a(0) = 1. (End)

A111004 Number of permutations avoiding a consecutive 132 pattern.

Original entry on oeis.org

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)

A117226 Number of permutations of [n] avoiding the consecutive pattern 1243.

Original entry on oeis.org

1, 1, 2, 6, 23, 110, 630, 4204, 32054, 274914, 2619692, 27459344, 313990182, 3889585408, 51888955808, 741668212080, 11307669002720, 183174676857608, 3141820432768752, 56882461258572976, 1084056190235653304, 21692744773505849952, 454758269790599361968

Offset: 0

Steven Finch, Apr 26 2006

nonn

a(n) is the number of permutations on [n] that avoid the consecutive pattern 1243. It is the same as the number of permutations which avoid 3421, 4312 or 2134.

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, 2011.
Sergi Elizalde and Marc Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110-125; see p. 120.
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. Appl. Math. 36 (2006), 138-155.
Steven Finch, Pattern-Avoiding Permutations. [Archived copy]
Steven Finch, Pattern-Avoiding Permutations. [Cached copy, with permission]
Eric Weisstein's World of Mathematics, Pochhammer Symbol.
Wikipedia, Falling and rising factorials.

Cf. A113228, A113229, A117156, A117158, A176730, A201692, A201693, A231166.

Row m = 1 of A327722.

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

A[x_]:=Integrate[AiryAi[ -t],{t,0,x}]; B[x_]:=Integrate[AiryBi[ -t],{t,0,x}];
c=-3^(2/3)*Gamma[2/3]/2; d=-3^(1/6)*Gamma[2/3]/2;
a[n_]:=SeriesCoefficient[1/(c*A[x]+d*B[x]+1),{x,0,n}]*n!; Table[a[n],{n,0,10}] (* fixed by Vaclav Kotesovec, Aug 23 2014 *)
(* constant d: *) 1/x/.FindRoot[3^(2/3)*Gamma[2/3]/2 * Integrate[AiryAi[-t],{t,0,x}] + 3^(1/6)*Gamma[2/3]/2 * Integrate[AiryBi[-t],{t,0,x}]==1,{x,1},WorkingPrecision->50] (* Vaclav Kotesovec, Aug 23 2014 *)

a(n) ~ c * d^n * n!, where d = 0.952891423325053197208702817349165942637814..., c = 1.169657787464830219717093446929792145316... . - Vaclav Kotesovec, Aug 23 2014
From Petros Hadjicostas, Nov 01 2019: (Start)
E.g.f.: 1/W(z), where W(z) := 1 + Sum_{n >= 0} (-1)^(n+1)* z^(3*n+1)/(b(n)*(3*n+1)) with b(n) = A176730(n) = (3*n)!/(3^n*(1/3)_n). (Here (x)_n = x*(x + 1)*...*(x + n - 1) is the Pochhammer symbol, or rising factorial, which is denoted by (x)^n in some papers and books.) The function W(z) satisfies the o.d.e. W'''(z) + z*W'(z) = 0 with W(0) = 1, W'(0) = -1, and W''(0) = 0. [See Theorem 4.3 (Case 1243 with u = 0) in Elizalde and Noy (2003).]
a(n) = Sum_{m = 0..floor((n-1)/3)} (-3)^m * (1/3)_m * binomial(n, 3*m+1) * a(n-3*m-1) for n >= 1 with a(0) = 1. (End)

A329070 Array read by ascending antidiagonals: T(n, k) = (kn)!/(k^n(1/k)_n) with (n >= 0 and k >= 1), where (x)_n = x(x + 1)...*(x + n - 1) is the Pochhammer symbol.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 8, 6, 1, 1, 48, 180, 24, 1, 1, 384, 12960, 8064, 120, 1, 1, 3840, 1710720, 10644480, 604800, 720, 1, 1, 46080, 359251200, 35765452800, 19813248000, 68428800, 5040, 1, 1, 645120, 109930867200, 244635697152000, 2303884477440000, 70355755008000, 10897286400, 40320, 1

Offset: 0

Petros Hadjicostas, Nov 03 2019

For information about the function W_m(z) = 1 + Sum_{n >= 0} (-1)^(n+1)* z^((m+2)*n + 1)/(T(n, m+2)*((m + 2)*n + 1)) (mentioned in the Formula section below), see Theorem 3.2 in Elizalde and Noy (2003) with u = 0 and m and a in the theorem equal to our m + 1. See also the documentation of array A327722.
By using the ratio test and the Stirling approximation to the gamma function, we may show that the radius of convergence of the power series for W_m(z) is infinity (for each m >= 0). Thus, the function W_m(z) (as defined by the above power series) is entire.
If we define S(m,s) = T(n-s, s+1) for m >= 0 and 0 <= s <= m, we get the triangular array that appears in the Example section below.

			Array T(n,k) (with rows n >= 0 and columns k >= 1) begins as follows:
  1,  1,     1,        1,           1,              1,  ...
  1,  2,     6,       24,         120,            720,  ...
  1,  8,   180,     8064,      604800,       68428800, ...
  1, 48, 12960, 10644480, 19813248000, 70355755008000, ...
  ...
Triangular array S(m,s) = T(m-s, s+1) (with rows m >= 0 and columns s >= 0):
  1;
  1,     1;
  1,     2,         1;
  1,     8,         6,           1;
  1,    48,       180,          24,           1;
  1,   384,     12960,        8064,         120,        1;
  1,  3840,   1710720,    10644480,      604800,      720,    1;
  1, 46080, 359251200, 35765452800, 19813248000, 68428800, 5040, 1;
  ...

Sergi Elizalde and Marc Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110-125; see Theorem 3.2 (p. 116).
Alison Schuetz and Gwyneth Whieldon, Polygonal Dissections and Reversions of Series, arXiv:1401.7194 [math.CO], 2014.
Eric Weisstein's World of Mathematics, Pochhammer Symbol.
Wikipedia, Falling and rising factorials.

Rows include A000012 (n = 0), A000142 (n = 1), A060593 (n = 2).
Columns include A000012 (k = 1), A000165 (k = 2), A176730 (k = 3).
Ratios T(n+1,k)/(k!*T(n,k)) include A000012 (k = 1), A000027 (k = 2), A000326 (k = 3), A100157 (k = 4), A234043 (k = 5).
Cf. A111004, A117226, A202213, A327722.

A := (n, k) -> `if`(k=0, 1, (GAMMA(1/k)*GAMMA(k*n+1))/(GAMMA(n+1/k)*k^n)):
seq(seq(A(n-k-1, k), k=1..n-1), n=0..10); # Peter Luschny, Nov 04 2019

T(0,k) = 1, T(1,k) = k!, and T(2,k) = (2*k)!/(k + 1) for k >= 1.
T(n,1) = 1, T(n,2) = (2*n)!!, and T(n,3) is related to the Airy functions (see the documentation of A176730).
T(n+1,k) = (k-1)! * binomial(k*(n+1), k-1) * T(n,k) for n >= 0 and k >= 1.
T(n+1,k)/(k! * T(n,k)) = Cat(n+1, k), where Cat(d, k) = binomial(k*d, k)/(k * (d - 1) + 1) is a Fuss-Catalan number; see Theorem 1.2 in Schuetz and Whieldon (2014).
If F(k,z) = Sum_{n >= 0} z^(k*n)/T(n,k), then F(k,z) satisfies the o.d.e. F^(k-1)(k,z) - z*F(k,z) = 0.
If W_m(z) = 1 + Sum_{n >= 0} (-1)^(n+1)* z^((m+2)*n + 1)/(T(n, m+2)*((m + 2)*n + 1)), then 1/W_m(z) is the e.g.f. of row m of A327722(m,n), which counts permutations of [n] that avoid the consecutive pattern 12...(m+1)(m+3)(m+2) (or equivalently, the consecutive pattern (m+3)(m+2)...(3)(1)(2)).
The function W_m(z) satisfies the o.d.e. W_m^(m+2)(z) + z*W_m'(z) = 0 with W_m(0) = 1, W_m'(0) = -1, and W_m^(s)(0) = 0 for s = 2..(m + 1).

cp's OEIS Frontend

A202213 Number of permutations of [n] avoiding the consecutive pattern 45321.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A111004 Number of permutations avoiding a consecutive 132 pattern.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A117226 Number of permutations of [n] avoiding the consecutive pattern 1243.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A329070 Array read by ascending antidiagonals: T(n, k) = (k*n)!/(k^n*(1/k)_n) with (n >= 0 and k >= 1), where (x)_n = x*(x + 1)*...*(x + n - 1) is the Pochhammer symbol.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A329070 Array read by ascending antidiagonals: T(n, k) = (kn)!/(k^n(1/k)_n) with (n >= 0 and k >= 1), where (x)_n = x(x + 1)...*(x + n - 1) is the Pochhammer symbol.