login
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.
6
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,3
COMMENTS
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
LINKS
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.
FORMULA
Sum_{k > 0} k * T(n,k) = A062199(n-5) for n > 4.
EXAMPLE
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;
MAPLE
b:= proc(u, o, t) option remember; `if`(u+o=0, 1, add(
b(u+j-1, o-j, `if`(u+j-3<j, 0, j)), j=1..o)+ expand(
`if`(t=-2, x, 1)*add(b(u-j, o+j-1, `if`(j<t or t=-2, 0,
`if`(t>0, -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);
MATHEMATICA
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 *)
CROSSREFS
Columns k=0-1 give: A202213, A264896.
Row sums give A000142.
T(4n+1,n) gives A007696.
Sequence in context: A005394 A095818 A369098 * A224316 A256195 A256196
KEYWORD
nonn,tabf
AUTHOR
Alois P. Heinz, Nov 24 2015
STATUS
approved