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.

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

Author

Petros Hadjicostas, Nov 02 2019

Keywords

• nonn
• tabl

Comments

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.

Examples

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

Links

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

Crossrefs

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

Cf. A000142, A033312, A242569, A329070.

Formula

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.