login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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

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.

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.

Cf. A002265, A007696, A062199.

Sequence in context: A248837 A005394 A095818 * A224316 A256195 A256196

Adjacent sequences:  A264778 A264779 A264780 * A264782 A264783 A264784

KEYWORD

nonn,tabf

AUTHOR

Alois P. Heinz, Nov 24 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 26 01:49 EDT 2021. Contains 346294 sequences. (Running on oeis4.)