login
A055585
Second column of triangle A055584.
6
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
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.
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
KEYWORD
easy,nonn
AUTHOR
Wolfdieter Lang, May 26 2000
STATUS
approved