A202213 -id:A202213 - cp's OEIS frontend

A202236 Number of permutations avoiding the consecutive pattern 35241.

1, 2, 6, 24, 119, 708, 4916, 39008, 348202, 3453572, 37679044, 448455648, 5782307134, 80291122976, 1194530208634, 18956382485568, 319626461800751, 5706286536509228, 107533930423507736, 2133112981295131824, 44429507242283663790, 969465861672912148324

Offset: 1

Ray Chandler, Dec 15 2011

nonn

a(n) is the number of permutations on [n] that avoid the consecutive pattern 35241. It is the same as the number of permutations which avoid 14253, 31425 or 52413.

Ray Chandler, Table of n, a(n) for n = 1..40
A. Baxter, B. Nakamura, and D. Zeilberger. Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes

Cf. A177523, A202213-A202235.

A264781 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the consecutive pattern 45321; triangle T(n,k), n >= 0, 0 <= k <= max(0, floor((n-1)/4)), read by rows.

Original entry on oeis.org

1, 1, 2, 6, 24, 119, 1, 708, 12, 4914, 126, 38976, 1344, 347765, 15110, 5, 3447712, 180736, 352, 37598286, 2308548, 9966, 447294144, 31481472, 225984, 5764747515, 457520055, 4753185, 45, 80011430240, 7068885600, 97954080, 21280, 1189835682714, 115808906178

Offset: 0

Alois P. Heinz, Nov 24 2015

Consecutive patterns 12354, 21345, 54312 give the same triangle.

The attached Maple program gives a recurrence for the o.g.f. of each row in terms of u. Using that recurrence we may get any row or column from this irregular triangular array T(n,k). The recurrence follows from manipulation of the bivariate o.g.f./e.g.f. 1/W(u,z) = Sum_{n, k >= 0} T(n, k)*u^k*z^n/n!, whose reciprocal W(u,z) is the solution of the o.d.e. in Theorem 3.2 in Elizalde and Noy (2003) (with m = a = 3). - Petros Hadjicostas, Nov 05 2019

			T(5,1) = 1: 45321.
T(6,1) = 12: 156432, 256431, 356421, 453216, 456321, 463215, 546321, 563214, 564213, 564312, 564321, 645321.
T(9,2) = 5: 786549321, 796548321, 896547321, 897546321, 897645321.
Triangle T(n,k) begins:
00 :           1;
01 :           1;
02 :           2;
03 :           6;
04 :          24;
05 :         119,          1;
06 :         708,         12;
07 :        4914,        126;
08 :       38976,       1344;
09 :      347765,      15110,        5;
10 :     3447712,     180736,      352;
11 :    37598286,    2308548,     9966;
12 :   447294144,   31481472,   225984;
13 :  5764747515,  457520055,  4753185,    45;
14 : 80011430240, 7068885600, 97954080, 21280;

Alois P. Heinz, Rows n = 0..170, flattened
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.
Petros Hadjicostas, Maple program for a recurrence.

Columns k=0-1 give: A202213, A264896.
Row sums give A000142.
T(4n+1,n) gives A007696.
Cf. A002265, A007696, A062199.

b:= proc(u, o, t) option remember; `if`(u+o=0, 1, add(
       b(u+j-1, o-j, `if`(u+j-30, -1, `if`(t=-1, -2, 0)))), j=1..u)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):
seq(T(n), n=0..17);

b[u_, o_, t_] := b[u, o, t] = If[u+o == 0, 1, Sum[
     b[u+j-1, o-j, If[u+j-3 < j, 0, j]], {j, 1, o}] + Expand[
     If[t == -2, x, 1]*Sum[b[u-j, o+j-1, If[j < t || t == -2, 0,
     If[t > 0, -1, If[t == -1, -2, 0]]]], {j, 1, u}]]];
T[n_] := CoefficientList[b[n, 0, 0], x];
T /@ Range[0, 17] // Flatten (* Jean-François Alcover, Feb 19 2021, after Alois P. Heinz *)

Sum_{k > 0} k * T(n,k) = A062199(n-5) for n > 4.

A327722 Number T(m,n) of permutations of [n] avoiding the consecutive pattern 12...(m+1)(m+3)(m+2), where m, n >= 0; array read by ascending antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 2, 5, 1, 1, 2, 6, 16, 1, 1, 2, 6, 23, 63, 1, 1, 2, 6, 24, 110, 296, 1, 1, 2, 6, 24, 119, 630, 1623, 1, 1, 2, 6, 24, 120, 708, 4204, 10176, 1, 1, 2, 6, 24, 120, 719, 4914, 32054, 71793, 1, 1, 2, 6, 24, 120, 720, 5026, 38976, 274914, 562848

Offset: 0

Petros Hadjicostas, Nov 02 2019

By taking complements of permutations, we see that T(m,n) is also the number of permutations of [n] avoiding the consecutive pattern (m+3)(m+2)...(3)(1)(2). [The complement of permutation (c_1,c_2,...,c_n) of [n] is (n + 1 - c_1, n + 1 - c_2, ..., n + 1 - c_n).]
If we let S(n,k) = T(n-k, k) for n >= 0 and 0 <= k <= n, we get a triangular array shown in the Example section below.
Note that lim_{n -> oo} S(n,k) = k! = A000142(k) for k >= 0.
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 W_m(z) = 1 + Sum_{n >= 0} (-1)^(n+1)* z^((m+2)*n + 1)/(b(n, m+2)*((m + 2)*n + 1)) is infinity (for each m >= 0). Thus, the function W_m(z) (as defined by the power series) is entire.

			Array T(m, n) (with rows m >= 0 and columns n >= 0) begins as follows:
  1, 1, 2, 5, 16,  63, 296, 1623, 10176,  71793, ...
  1, 1, 2, 6, 23, 110, 630, 4204, 32054, 274914, ...
  1, 1, 2, 6, 24, 119, 708, 4914, 38976, 347765, ...
  1, 1, 2, 6, 24, 120, 719, 5026, 40152, 360864, ...
  1, 1, 2, 6, 24, 120, 720, 5039, 40304, 362664, ...
  1, 1, 2, 6, 24, 120, 720, 5040, 40319, 362862, ...
  ...
Triangular array S(n, k) = T(n-k, k) (with rows n >= 0 and columns k >= 0) begins as follows:
  1;
  1, 1;
  1, 1, 2;
  1, 1, 2, 5;
  1, 1, 2, 6, 16;
  1, 1, 2, 6, 23,  63;
  1, 1, 2, 6, 24, 110, 296;
  1, 1, 2, 6, 24, 119, 630, 1623;
  1, 1, 2, 6, 24, 120, 708, 4204, 10176;
  1, 1, 2, 6, 24, 120, 719, 4914, 32054,  71793;
  1, 1, 2, 6, 24, 120, 720, 5026, 38976, 274914, 562848;
  ...

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 u = 0 and m and a in the theorem equal to our m + 1.
Eric Weisstein's World of Mathematics, Pochhammer Symbol.
Wikipedia, Falling and rising factorials.

Rows include A111004 (m = 0, pattern 132), A117226 (m = 1, pattern 1243), A202213 (m = 2, pattern 12354).

Cf. A000142, A033312, A242569, A329070.

E.g.f for row m >= 0: 1/W_m(z), where W_m(z) = 1 + Sum_{n >= 0} (-1)^(n+1)* z^((m+2)*n + 1)/(b(n, m+2)*((m + 2)*n + 1)) with b(n, k) = A329070(n, k) = (k*n)!/(k^n * (1/k)_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_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).
T(m, n) = Sum_{s = 0..floor((n - 1)/(m + 2))} (-(m + 2))^s * (1/(m + 2))_s * binomial(n, (m + 2)*s + 1) * T(m, n - (m + 2)*s - 1) for n >= 1 with T(m, 0) = 1.
T(m, n) = n! for 0 <= n <= m + 2.
T(m, m+3) = (m + 3)! - 1 = A000142(m + 3) - 1 = A033312(m + 3) for m >= 0. [In the set of permutations of [m + 3] there is exactly one permutation that contains the pattern 12...(m+1)(m+3)(m+2).]
Conjecture: T(m, m + 4) = A242569(m + 4) = (m + 4)! - 2*(m + 4) for m >= 0.
Limit_{m -> oo} T(m, n) = n! = A000142(n) for n >= 0.

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).

A202214 Number of permutations avoiding the consecutive pattern 53421.

Original entry on oeis.org

1, 2, 6, 24, 119, 708, 4914, 38977, 347779, 3447902, 37600925, 447332398, 5765327905, 80020698913, 1189991560707, 18876181370841, 318136382176708, 5677225148401090, 106939954137362482, 2120412050923152077, 44145844897844974946, 962859209130749461268

Offset: 1

Ray Chandler, Dec 14 2011

nonn

a(n) is the number of permutations on [n] that avoid the consecutive pattern 53421. It is the same as the number of permutations which avoid 12435, 13245 or 54231.

Ray Chandler, Table of n, a(n) for n = 1..40
A. Baxter, B. Nakamura, and D. Zeilberger. Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes

Cf. A177523, A202213-A202236.

A202235 Number of permutations avoiding the consecutive pattern 32415.

Original entry on oeis.org

1, 2, 6, 24, 119, 708, 4915, 38992, 347990, 3450772, 37640794, 447908832, 5774077131, 80160465380, 1192342710241, 18917802834912, 318910800658728, 5692346715440768, 107249322475436984, 2127032690422975168, 44293813329642772714, 966307529386769800328

Offset: 1

Ray Chandler, Dec 15 2011

nonn

a(n) is the number of permutations on [n] that avoid the consecutive pattern 32415. It is the same as the number of permutations which avoid 15243, 34251 or 51423.

Ray Chandler, Table of n, a(n) for n = 1..40
A. Baxter, B. Nakamura, and D. Zeilberger. Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes

Cf. A177523, A202213-A202236.

A202215 Number of permutations avoiding the consecutive pattern 43251.

Original entry on oeis.org

1, 2, 6, 24, 119, 708, 4914, 38977, 347783, 3447982, 37602245, 447353497, 5765670515, 80026435959, 1190091483826, 18877998176267, 318170909582504, 5677911026433716, 106954187252974515, 2120720309936327198, 44152804913927293967, 963022839743497051427

Offset: 1

Ray Chandler, Dec 14 2011

nonn

a(n) is the number of permutations on [n] that avoid the consecutive pattern 43251. It is the same as the number of permutations which avoid 15234, 23415 or 51432.

Ray Chandler, Table of n, a(n) for n = 1..40
A. Baxter, B. Nakamura, and D. Zeilberger. Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes

Cf. A177523, A202213-A202236.

A202216 Number of permutations avoiding the consecutive pattern 34521.

Original entry on oeis.org

1, 2, 6, 24, 119, 708, 4914, 38976, 347775, 3447912, 37601586, 447346944, 5765604885, 80025786960, 1190085736014, 18877969022976, 318171464604945, 5677939605422880, 106955077375109430, 2120744934976978944, 44153462828412744975, 963040357207773472320

Offset: 1

Ray Chandler, Dec 14 2011

nonn

a(n) is the number of permutations on [n] that avoid the consecutive pattern 34521. It is the same as the number of permutations which avoid 12453, 31245, 35421, 54213, 12543, 32145 or 54123.

Ray Chandler, Table of n, a(n) for n = 1..40
A. Baxter, B. Nakamura, and D. Zeilberger. Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes

Cf. A177523, A202213-A202236.

A202217 Number of permutations avoiding the consecutive pattern 45132.

Original entry on oeis.org

1, 2, 6, 24, 119, 708, 4914, 38976, 347776, 3447932, 37601916, 447352224, 5765690544, 80027220448, 1190110692204, 18878422622976, 318180082610048, 5678110761876224, 106958628519952128, 2120821833862388544, 44155198873515034560, 963081167548894179456

Offset: 1

Ray Chandler, Dec 14 2011

nonn

a(n) is the number of permutations on [n] that avoid the consecutive pattern 45132. It is the same as the number of permutations which avoid 21534, 23154 or 43512.

Ray Chandler, Table of n, a(n) for n = 1..40
A. Baxter, B. Nakamura, and D. Zeilberger. Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes

Cf. A177523, A202213-A202236.

A202218 Number of permutations avoiding the consecutive pattern 32451.

Original entry on oeis.org

1, 2, 6, 24, 119, 708, 4914, 38977, 347793, 3448182, 37605545, 447406214, 5766525727, 80040747361, 1190340631290, 18882526564227, 318256944873984, 5679619717431613, 106989639176572571, 2121488012937187849, 44170136425049025574, 963430265253564585315

Offset: 1

Ray Chandler, Dec 15 2011

nonn

a(n) is the number of permutations on [n] that avoid the consecutive pattern 32451. It is the same as the number of permutations which avoid 15423, 34215 or 51243.

Ray Chandler, Table of n, a(n) for n = 1..40
A. Baxter, B. Nakamura, and D. Zeilberger. Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes

Cf. A177523, A202213-A202236.

cp's OEIS Frontend

A202236 Number of permutations avoiding the consecutive pattern 35241.

Views

Author

Keywords

Comments

Links

Crossrefs

A264781 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the consecutive pattern 45321; triangle T(n,k), n >= 0, 0 <= k <= max(0, floor((n-1)/4)), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A327722 Number T(m,n) of permutations of [n] avoiding the consecutive pattern 12...(m+1)(m+3)(m+2), where m, n >= 0; array read by ascending antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

A202214 Number of permutations avoiding the consecutive pattern 53421.

Views

Author

Keywords

Comments

Links

Crossrefs

A202235 Number of permutations avoiding the consecutive pattern 32415.

Views

Author

Keywords

Comments

Links

Crossrefs

A202215 Number of permutations avoiding the consecutive pattern 43251.

Views

Author

Keywords

Comments

Links

Crossrefs

A202216 Number of permutations avoiding the consecutive pattern 34521.

Views

Author

Keywords

Comments

Links

Crossrefs

A202217 Number of permutations avoiding the consecutive pattern 45132.

Views

Author

Keywords

Comments

Links

Crossrefs

A202218 Number of permutations avoiding the consecutive pattern 32451.

Views

Author

Keywords

Comments

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.