|
Search: id:A116701
|
|
|
| A116701 |
|
Number of permutations of length n which avoid the patterns 132, 4321. |
|
+0
1
|
|
| 1, 2, 5, 13, 31, 66, 127, 225, 373, 586, 881, 1277, 1795, 2458, 3291, 4321, 5577, 7090, 8893, 11021, 13511, 16402, 19735, 23553, 27901, 32826, 38377, 44605, 51563, 59306, 67891, 77377, 87825, 99298, 111861, 125581, 140527, 156770, 174383, 193441
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
Also, number of permutations of length n which avoid the patterns 312, 1234, 4312; or avoid the patterns 132, 1324, 4321, etc.
|
|
LINKS
|
Lara Pudwell, Systematic Studies in Pattern Avoidance, 2005.
|
|
FORMULA
|
G.f.: A(x) = -{x(x^4-2x^3+5x^2-3x+1)}/{(x-1)^5}
a(n) = (n^4 - 4n^3 + 11n^2 - 8n + 12)/12. - Franklin T. Adams-Watters, Sep 16 2006
Binomial transform of [1, 1, 2, 3, 2, 0, 0, 0,...]. - Gary W. Adamson (qntmpkt(AT)yahoo.com), Oct 23 2007
Equals A001263 * [1, 1, 1, 0, 0, 0,...], where A001263 = the Narayana triangle. - Gary W. Adamson (qntmpkt(AT)yahoo.com), Nov 19 2007
|
|
EXAMPLE
|
a(4)=13 because we have 11 permutations of [4] that do not avoid the patterns 132 and 4321; namely: 1324,1342,1432,4132,1423,3142,2431,2413,2143,1243, and 4321.
|
|
MAPLE
|
G:=(x*(x^4-2*x^3+5*x^2-3*x+1))/(1-x)^5: Gser:=series(G, x=0, 48): seq(coeff(Gser, x, n), n=1..45); - Emeric Deutsch (deutsch(AT)duke.poly.edu), Jul 29 2006
|
|
CROSSREFS
|
Cf. A001263.
Sequence in context: A077278 A073683 A098501 this_sequence A068739 A063636 A076501
Adjacent sequences: A116698 A116699 A116700 this_sequence A116702 A116703 A116704
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
Lara Pudwell (lpudwell(AT)math.rutgers.edu), Feb 26 2006
|
|
EXTENSIONS
|
Entry revised by njas, Jul 25 2006
More terms from Emeric Deutsch (deutsch(AT)duke.poly.edu), Jul 29 2006
|
|
|
Search completed in 0.002 seconds
|
