|
| |
|
|
A078481
|
|
Number of irreducible stack sortable permutations of degree n.
|
|
3
| |
|
|
0, 1, 1, 3, 7, 19, 53, 153, 453, 1367, 4191, 13015, 40857, 129441, 413337, 1328971, 4298727, 13978971, 45673981, 149867513, 493638797, 1631616239, 5410015615, 17990076527, 59981630321, 200476419713, 671564145137, 2254338511507, 7582179238151, 25547868961315
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,4
|
|
|
COMMENTS
| Also number of Dyck paths of semilength n with no UDUD. Example: a(3)=3 because the only Dyck paths of semilength 3 with no UDUD in them are: UDUUDD, UUDDUD and UUUDDD (the nonqualifying ones being UUDUDD and UDUDUD). - Emeric Deutsch (deutsch(AT)duke.poly.edu), Jan 27 2003
Contribution from Paul Barry (pbarry(AT)wit.ie), Jan 29 2009: (Start)
The sequence 1,1,1,3,7,19,... has general term sum{k=0..n, C(n+k,2k)*(-1)^(n-k)*A006318(k)} and g.f. given by
1/(1+x-2x/(1+x-x/(1+x-2x/(1+x-x/(1+x-2x/(1+x-x/(1-..... (continued fraction). (End)
|
|
|
REFERENCES
| A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
M. D. Atkinson and T. Stitt, Restricted permutations and the wreath product, Discrete Math., 259 (2002), 19-36.
Toufik Mansour, Statistics on Dyck Paths, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.5.
|
|
|
FORMULA
| G.f.: (1 - x - x^2 - (1 - 2*x - 5*x^2 - 2*x^3 + x^4)^(1/2)) / (2*x + 2*x^2) = -1 + 2*(1 + x) / (1 + x + x^2 + sqrt((1 - x + x^2)^2 - 8*x^2)).
G.f. A(x) satisfies A(x) = x + (x + x^2) * (A(x) + A(x)^2). - Michael Somos, Sep 08 2005
Given g.f. A(x), then series reversion of B(x) = x + x*A(x) is -B(-x). - Michael Somos, Sep 08 2005
Given g.f. A(x), then B(x) = x + x*A(x) satisfies 0 = f(x, B(x)) where f(u, v) = u^2*(v + v^2) + u*(1 + v + v^2) - v. - Michael Somos, Sep 08 2005
Given g.f. A(x), then B(x) = x + x*A(x) satisfies B(x) = x + C(x*B(x)) where C(x) is g.f. of A006318 with offset 1. - Michael Somos, Sep 08 2005
|
|
|
EXAMPLE
| x + x^2 + 3*x^3 + 7*x^4 + 19*x^5 + 53*x^6 + 153*x^7 + 453*x^8 + 1367*x^9 + ...
|
|
|
PROG
| (PARI) {a(n) = if( n<1, 0, polcoeff( -1 + 2*(1 + x) / (1 + x + x^2 + sqrt((1 - x + x^2)^2 - 8*x^2 + x*O(x^n))), n))} /* Michael Somos, Sep 08 2005 */
|
|
|
CROSSREFS
| Sequence in context: A026299 A183117 A183124 * A183122 A104522 A175533
Adjacent sequences: A078478 A078479 A078480 * A078482 A078483 A078484
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com), Jan 04 2003
|
| |
|
|
