A055585 Second column of triangle A055584.

1, 6, 25, 88, 280, 832, 2352, 6400, 16896, 43520, 109824, 272384, 665600, 1605632, 3829760, 9043968, 21168128, 49152000, 113311744, 259522560, 590872576, 1337982976, 3014656000, 6761218048, 15099494400, 33587986432, 74440507392

Offset

0,2

Comments

Number of 132-avoiding permutations of [n+5] containing exactly three 123 patterns. - Emeric Deutsch, Jul 13 2001

If X_1,X_2,...,X_n are 2-blocks of a (2n+2)-set X then, for n>=1, a(n-1) is the number of (n+3)-subsets of X intersecting each X_i, (i=1,2,...,n). - Milan Janjic, Nov 18 2007

Convolution of A001792 with itself. - Philippe Deléham, Feb 21 2013

Links

Table of n, a(n) for n=0..26.

Milan Janjic, Two Enumerative Functions

M. Janjic, On a class of polynomials with integer coefficients, JIS 11 (2008) 08.5.2

Pudwell, Lara; Scholten, Connor; Schrock, Tyler; Serrato, Alexa Noncontiguous pattern containment in binary trees, ISRN Comb. 2014, Article ID 316535, 8 p. (2014), Section 5.2.

A. Robertson, H. S. Wilf and D. Zeilberger, Permutation patterns and continued fractions, Electr. J. Combin. 6, 1999, #R38.

Index entries for linear recurrences with constant coefficients, signature (8,-24,32,-16).

Formula

G.f.: (1-x)^2/(1-2*x)^4.

a(n) = A055584(n+1, 1). a(n) = sum(a(j), j=0..n-1)+A001793(n+1), n >= 1.

a(n) = 2^(n-3)(n+1)(n+3)(n+8)/3.

Preceded by 0, this is the binomial transform of the tetrahedral numbers A000292. - Carl Najafi, Sep 08 2011

E.g.f.: (1/6)*(2*x^3 + 15*x^2 + 24*x + 6)*exp(2*x). - G. C. Greubel, Aug 22 2015

Example

a(1)=6 because 432516,432561,435126,452136,532146 and 632145 are the only 132-avoiding permutations of 123456, containing exactly three increasing subsequences of length 3.

Mathematica

Table[(1/3)*2^(n-3)*(n+1)*(n+3)*(n+8), {n, 0, 50}] (* G. C. Greubel, Aug 22 2015 *)
LinearRecurrence[{8, -24, 32, -16}, {1, 6, 25, 88}, 30] (* Harvey P. Dale, Nov 03 2017 *)

Prog

(PARI) Vec(((1-x)^2)/(1-2*x)^4 + O(x^30)) \\ Michel Marcus, Aug 22 2015

Crossrefs

Cf. A055584, partial sums of A049612, n >= 1.

Sequence in context: A233698 A230723 A220275 * A099625 A209243 A143628

Adjacent sequences: A055582 A055583 A055584 * A055586 A055587 A055588

Keyword

easy,nonn

Author

Wolfdieter Lang, May 26 2000

Status

approved