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

Author

Wolfdieter Lang, May 26 2000

Keywords

• easy
• nonn

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

Examples

			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.
		

Links

• 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).

Crossrefs

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

Programs

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 *)

PARI

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

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