A264781 - OEIS

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.

%I #36 May 20 2023 23:17:05

%S 1,1,2,6,24,119,1,708,12,4914,126,38976,1344,347765,15110,5,3447712,

%T 180736,352,37598286,2308548,9966,447294144,31481472,225984,

%U 5764747515,457520055,4753185,45,80011430240,7068885600,97954080,21280,1189835682714,115808906178

%N 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.

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

%C 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

%H Alois P. Heinz, <a href="/A264781/b264781.txt">Rows n = 0..170, flattened</a>

%H A. Baxter, B. Nakamura, and D. Zeilberger, <a href="http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/auto.html">Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes</a>, 2011.

%H Sergi Elizalde and Marc Noy, <a href="https://doi.org/10.1016/S0196-8858(02)00527-4 ">Consecutive patterns in permutations</a>, Adv. Appl. Math. 30 (2003), 110-125; see Theorem 3.2 (p. 116) with m = a = 3.

%H Petros Hadjicostas, <a href="/A264781/a264781_1.txt">Maple program for a recurrence</a>.

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

%e T(5,1) = 1: 45321.

%e T(6,1) = 12: 156432, 256431, 356421, 453216, 456321, 463215, 546321, 563214, 564213, 564312, 564321, 645321.

%e T(9,2) = 5: 786549321, 796548321, 896547321, 897546321, 897645321.

%e Triangle T(n,k) begins:

%e 00 : 1;

%e 01 : 1;

%e 02 : 2;

%e 03 : 6;

%e 04 : 24;

%e 05 : 119, 1;

%e 06 : 708, 12;

%e 07 : 4914, 126;

%e 08 : 38976, 1344;

%e 09 : 347765, 15110, 5;

%e 10 : 3447712, 180736, 352;

%e 11 : 37598286, 2308548, 9966;

%e 12 : 447294144, 31481472, 225984;

%e 13 : 5764747515, 457520055, 4753185, 45;

%e 14 : 80011430240, 7068885600, 97954080, 21280;

%p b:= proc(u, o, t) option remember; `if`(u+o=0, 1, add(

%p b(u+j-1, o-j, `if`(u+j-3<j, 0, j)), j=1..o)+ expand(

%p `if`(t=-2, x, 1)*add(b(u-j, o+j-1, `if`(j<t or t=-2, 0,

%p `if`(t>0, -1, `if`(t=-1, -2, 0)))), j=1..u)))

%p end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):

%p seq(T(n), n=0..17);

%t b[u_, o_, t_] := b[u, o, t] = If[u+o == 0, 1, Sum[

%t b[u+j-1, o-j, If[u+j-3 < j, 0, j]], {j, 1, o}] + Expand[

%t If[t == -2, x, 1]*Sum[b[u-j, o+j-1, If[j < t || t == -2, 0,

%t If[t > 0, -1, If[t == -1, -2, 0]]]], {j, 1, u}]]];

%t T[n_] := CoefficientList[b[n, 0, 0], x];

%t T /@ Range[0, 17] // Flatten (* _Jean-François Alcover_, Feb 19 2021, after _Alois P. Heinz_ *)

%Y Columns k=0-1 give: A202213, A264896.

%Y Row sums give A000142.

%Y T(4n+1,n) gives A007696.

%Y Cf. A002265, A007696, A062199.

%K nonn,tabf

%O 0,3

%A _Alois P. Heinz_, Nov 24 2015