OFFSET
0,6
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.
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.
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.
EXAMPLE
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;
...
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Petros Hadjicostas, Nov 02 2019
STATUS
approved