|
| |
|
|
A114997
|
|
Number of ordered trees with n edges and no unary or binary nodes.
|
|
6
|
|
|
|
0, 0, 1, 1, 1, 4, 8, 13, 31, 71, 144, 318, 729, 1611, 3604, 8249, 18803, 42907, 98858, 228474, 528735, 1228800, 2865180, 6693712, 15676941, 36807239, 86584783, 204060509, 481823778, 1139565120, 2699329341, 6403500057, 15211830451, 36183117255, 86171536894, 205459894230, 490417795075
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,6
|
|
|
COMMENTS
|
Also counts sequences of n natural numbers, excluding 1 and 2, such that the sum of every prefix is no more than its length.
a(n) is the number of Dyck paths of semilength n with all ascents of length >= 3. For example, a(6) = 4 counts U^6.D^6, U^3.D.U^3.D^5, U^3.D^2.U^3.D^4, U^3.D^3.U^3.D^3 where ^ denotes repetition and a dot denotes concatenation. - David Callan, Dec 08 2021
|
|
|
LINKS
|
Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Andrei Asinowski, Axel Bacher, Cyril Banderier, Bernhard Gittenberger, Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata, Laboratoire d'Informatique de Paris Nord (LIPN 2019).
Nachum Dershowitz and Shmuel Zaks, More patterns in trees: Up and down, young and old, odd and even, SIAM J. Discrete Mathematics, 23 (2009), 447-465.
|
|
|
FORMULA
|
a(n) = Sum_{(n+3)/2 <= k <= n} (1/(n+1) * binomial(n+1, k) * binomial(2*k-n-3, n-k)).
If A(x) is the g.f. for the sequence with a(0)=1, then x^3*A^3+x*A^2-(1 + x)*A+1 = 0. - Emeric Deutsch, Jan 13 2015
Let A(x) be the g.f. for the sequence with a(0)=1, then x*A(x) is the reversion of x/(1+x^2*sum(k>=1,x^k)). - Joerg Arndt, Aug 19 2012 (proved by Emeric Deutsch, Jan 13 2015)
Recurrence: (n+1)*(n+2)*(28*n^2 - 38*n - 15)*a(n) = -4*(n+1)*(14*n^3 - 12*n^2 + 7*n - 15)*a(n-1) + (n-2)*(140*n^3 + 90*n^2 - 221*n + 45)*a(n-2) + 6*(n-2)*(28*n^3 - 24*n^2 - 75*n + 95)*a(n-3) + 23*(n-3)*(n-2)*(28*n^2 + 18*n - 25)*a(n-4). - Vaclav Kotesovec, Mar 22 2014
a(n) ~ c / (n^(3/2) * r^n), where r = (4*sqrt(2) - 3 + 23*sqrt((344*sqrt(2))/529 - 235/529))/46 = 0.402505948621022106992... is the root of the equation 23*r^4+6*r^3+5*r^2-2*r-1 = 0 and c = sqrt((280 + 133*sqrt(2) - 25*sqrt(14*(11 + 8*sqrt(2)))) / (7*Pi))/4 = 0.273007516... - Vaclav Kotesovec, Mar 22 2014, updated Jan 14 2015
|
|
|
MAPLE
|
eq := x^3*A^3+x*A^2-(1+x)*A+1 = 0: A := RootOf(eq, A): Aser := series(A, x = 0, 40): seq(coeff(Aser, x, n), n = 1 .. 38); # Emeric Deutsch, Jan 13 2015
|
|
|
MATHEMATICA
|
Table[Sum[1/(n+1)*Binomial[n+1, k]*Binomial[2*k-n-3, n-k], {k, Ceiling[(n+3)/2], n}], {n, 1, 20}] (* Vaclav Kotesovec, Mar 22 2014 *)
|
|
|
PROG
|
(PARI) a(n)=sum(k=ceil((n+3)/2), n, (1/(n+1) * binomial(n+1, k) * binomial(2*k-n-3, n-k)) ); \\ Joerg Arndt, Aug 19 2012
(PARI) N=66; gf=serreverse(x/(1+x^2*sum(k=1, N, x^k))+O(x^N)) / x;
/* = 1 + x^3 + x^4 + x^5 + 4*x^6 + 8*x^7 + 13*x^8 + 31*x^9 + ... */
v114997=Vec(gf) /* = [1, 0, 0, 1, 1, 1, 4, 8, 13, 31, ...] */ \\ Joerg Arndt, Aug 19 2012
|
|
|
CROSSREFS
|
Cf. A000108 (rev. of x/(1+1*sum(k>=1,x^k)) ), A005043 (rev. of x/(1+x*sum(k>=1,x^k)), A215341 (rev. of x/(1+x^3*sum(k>=1,x^k)) ).
Sequence in context: A080003 A033016 A027008 * A146919 A312221 A312222
Adjacent sequences: A114994 A114995 A114996 * A114998 A114999 A115000
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
Nachum Dershowitz, Feb 23 2006
|
|
|
EXTENSIONS
|
Offset set to 1 by Joerg Arndt, Aug 19 2012
|
|
|
STATUS
|
approved
|
| |
|
|
