A215341 -id:A215341 - cp's OEIS frontend

A114997 Number of ordered trees with n edges and no unary or binary nodes.

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

Offset: 1

Nachum Dershowitz, Feb 23 2006

nonn

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

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.

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

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

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

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

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

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

Offset set to 1 by Joerg Arndt, Aug 19 2012

A215340 Expansion of series_reversion( x/(1 + sum(k>=1, x^A032766(k)) ) ) / x.

Original entry on oeis.org

1, 1, 1, 2, 6, 16, 40, 107, 307, 893, 2597, 7646, 22878, 69162, 210402, 644098, 1984598, 6149428, 19143220, 59840692, 187781992, 591343894, 1868106990, 5918537492, 18800935948, 59869902152, 191081899648, 611138052146, 1958410654202, 6287175115130, 20218209139666, 65120537016867

Offset: 0

Joerg Arndt, Aug 19 2012

Number of Dyck n-paths avoiding ascents of length == 2 mod 3, see example. - David Scambler, Apr 16 2013

This is a special case of the following: let S be a set of positive numbers, r(x) = x/(1 + sum(e in S, x^e)), and f(x)=series_reversion(r(x)) / x, then f is the g.f. for the number of Dyck words of semilength n with substrings UUU...UU only of lengths e in S (that is, all ascent lengths are in S). [Joerg Arndt, Apr 16 2013]

			The 16 Dyck words of semilength 5 without substrings UUU..UU of length 2, 5, 8, etc. (using '1' for U and '.' for D) are
01:   1.1.1.1.1.
02:   1.1.111...
03:   1.111...1.
04:   1.111..1..
05:   1.111.1...
06:   1.1111....
07:   111...1.1.
08:   111..1..1.
09:   111..1.1..
10:   111.1...1.
11:   111.1..1..
12:   111.1.1...
13:   1111....1.
14:   1111...1..
15:   1111..1...
16:   1111.1....
- _Joerg Arndt_, Apr 16 2013

Alois P. Heinz, Table of n, a(n) for n = 0..750

Cf. A215341.

b:= proc(x, y, t) option remember;
      `if`(y0 and t<>2, b(x-1, y, 0), 0)+b(x, y-1, irem(t+1, 3))))
    end:
a:= n-> b(n, n, 0):
seq(a(n), n=0..40);  # Alois P. Heinz, Apr 16 2013

b[x_, y_, t_] := b[x, y, t] = If[y0 && t != 2, b[x-1, y, 0], 0] + b[x, y-1, Mod[t+1, 3]]]]; a[n_] := b[n, n, 0]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Apr 08 2015, after Alois P. Heinz *)

N = 66;  x = 'x + O('x^N);
rf = x/(1+sum(n=1, N, ((n%3)!=2)*x^n ) );
gf = serreverse(rf)/x;
v = Vec(gf)

G.f. A(x) satisfies 0 = -x^3*A(x)^4 + (-x + 1)*A(x) - 1. [Joerg Arndt, Mar 01 2014]
Recurrence: 27*(n-1)*n*(n+1)*(2*n-5)*(4*n-11)*(4*n-7)*a(n) = 9*(n-1)*n*(4*n-11)*(96*n^3 - 456*n^2 + 616*n - 197)*a(n-1) - 3*(n-1)*(1728*n^5 - 15552*n^4 + 53164*n^3 - 85322*n^2 + 63369*n - 17010)*a(n-2) + (4*n-9)*(4*n-3)*(728*n^4 - 6188*n^3 + 19267*n^2 - 25987*n + 12810)*a(n-3) - 3*(n-3)*(2*n-3)*(3*n-10)*(3*n-8)*(4*n-7)*(4*n-3)*a(n-4). - Vaclav Kotesovec, Mar 22 2014
a(n) ~ sqrt(2*(3+r)/(3*(1-r)^3)) / (3*sqrt(Pi)*n^(3/2)*r^n), where r = 0.295932936709444136... is the root of the equation 27*(1-r)^4 = 256*r^3. - Vaclav Kotesovec, Mar 22 2014
a(n) = 1/(n + 1)*Sum_{k = 0..floor(n/3)} binomial(n + 1, n - 3*k)*binomial(n + k, n). - Peter Bala, Aug 02 2016

Modified definition to obtain offset 0 for combinatorial interpretation, Joerg Arndt, Apr 16 2013

A215342 Expansion of series reversion of x(1-x^3sum(k>=1, x^k)).

Original entry on oeis.org

1, 0, 0, 0, 1, 1, 1, 1, 6, 12, 19, 27, 71, 166, 329, 579, 1222, 2756, 5921, 11754, 24179, 52372, 114031, 239726, 502269, 1074961, 2333143, 5017552, 10714567, 23006558, 49861081, 108122488, 233691980, 505329915, 1097463037, 2389325284, 5199960642, 11314793335, 24663217250, 53864633059

Offset: 1

Joerg Arndt, Aug 19 2012

nonn

Dissections (using non-intersecting diagonals) of a convex (n+1)-gon into k-gons where k>=6. [Joerg Arndt, Feb 15 2014]

			Use the Lang and the Abramowitz and Stegun links in A111785. In the A-S list of partitions of the integer n on page 831 null all partitions containing 1, 2, or 3. These correspond to the null coefficients of x^2, x^3, and x^4 in the series to be reverted and to 3-, 4-, and 5-gons not being allowed in the dissections. a(9)=6 corresponds to the A-S partitions (n=8,m=1, partition 1)=8 and (8,2,4)=4^2, and these in turn correspond to one undissected 10-gon + five ways to divide a 10-gon into two 6-gons. a(10)=12 corresponds to (9,1,1)=9 and (9,2,4)=4,5, corresponding to one undissected 11-gon + the eleven ways to divide an 11-gon into a 6-gon and 7-gon. - _Tom Copeland_, Feb 15 2014

Vaclav Kotesovec, Table of n, a(n) for n = 1..250
Alison Schuetz, Gwyneth Whieldon, Polygonal Dissections and Reversions of Series, arXiv:1401.7194 [math.CO]
D. Birmajer, J. B. Gil, M. D. Weiner, Colored partitions of a convex polygon by noncrossing diagonals, arXiv preprint arXiv:1503.05242 [math.CO], 2015.

Cf. A001003 (rev. of x*(1-1*sum(k>=1,x^k)) ), A046736 (rev. of x*(1-x*sum(k>=1,x^k)) ), A054514 (rev. of x*(1-x^2*sum(k>=1,x^k)) ).

Cf. A000108 (rev. of x/(1+1*sum(k>=1,x^k)) ), A005043 (rev. of x/(1+x*sum(k>=1,x^k)) ), A114997 (rev. of x/(1+x^2*sum(k>=1,x^k)) ), A215341 (rev. of x/(1+x^3*sum(k>=1,x^k)) ).

nmax=20; aa=ConstantArray[0,nmax]; aa[[1]]=0; Do[AGF=1+Sum[aa[[n]]*x^n,{n,1,j-1}]+koef*x^j; sol=Solve[Coefficient[1-(1+x)*AGF+x*AGF^2 +x^4*AGF^5,x,j]==0,koef][[1]]; aa[[j]]=koef/.sol[[1]],{j,2,nmax}]; Flatten[{1,aa}] (* Vaclav Kotesovec, Mar 23 2014 *)

N=66; Vec(serreverse(x*(1-x^3*sum(k=1,N,x^k))+O(x^N)))

Recurrence: 283*(n-3)*(n-2)*(n-1)*n*(14438110231*n^6 - 346214993274*n^5 + 3438949212625*n^4 - 18105364836570*n^3 + 53265099505324*n^2 - 82987438028496*n + 53465930027280)*a(n) = (n-3)*(n-2)*(n-1)*(5399853226394*n^7 - 137584187324067*n^6 + 1483504918415939*n^5 - 8763694066910355*n^4 + 30585682233578711*n^3 - 62946796681030518*n^2 + 70573456271906136*n - 33158656683118080)*a(n-1) - (n-3)*(n-2)*(534210078547*n^8 - 14946795065326*n^7 + 180235890644998*n^6 - 1221993860476624*n^5 + 5087726442447403*n^4 - 13295664719568394*n^3 + 21246368278875372*n^2 - 18919520411340456*n + 7154560952974080)*a(n-2) - 5*(n-4)*(n-3)*(28876220462*n^8 - 793496758165*n^7 + 9354947999333*n^6 - 61627542806839*n^5 + 247116200695877*n^4 - 613894185501244*n^3 + 913857055091496*n^2 - 732955177968120*n + 234541607788800)*a(n-3) + 5*(9947857949159*n^10 - 357916425755694*n^9 + 5753280746412201*n^8 - 54388490463504720*n^7 + 334719732595671573*n^6 - 1400557913088383070*n^5 + 4032929135663406319*n^4 - 7886242788829977540*n^3 + 10015113186875731788*n^2 - 7452248915385205056*n + 2464721951024954880)*a(n-4) - 8*(n-5)*(2*n - 9)*(4*n - 21)*(4*n - 19)*(14438110231*n^6 - 259586331888*n^5 + 1924445899720*n^4 - 7522955714190*n^3 + 16337121992089*n^2 - 18661982982042*n + 8745398997120)*a(n-5). - Vaclav Kotesovec, Mar 22 2014
a(n) ~ s*sqrt((3*r*s+r-4)/(5*(3*r*s-2*r-2))) / (2*sqrt(Pi) * n^(3/2) * r^(n-1)), where s = 1.1954869989505368389... is the root of the equation 64 - 897*s + 2460*s^2 - 2787*s^3 + 1442*s^4 - 283*s^5 = 0, and r = (4*s-5)/(s*(3*s-4)) = 0.441061092405258554919... - Vaclav Kotesovec, Mar 23 2014
G.f. A(x) for offset 0 satisfies 1-(1+x)*A(x) + x*A(x)^2 + x^4*A(x)^5 = 0. - Vaclav Kotesovec, Mar 23 2014

A365702 G.f. satisfies A(x) = 1 + x^5A(x)^5 / (1 - xA(x)).

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 6, 12, 19, 27, 36, 81, 177, 341, 592, 951, 1726, 3417, 6766, 12812, 22951, 41531, 78222, 151291, 291957, 550015, 1024683, 1924543, 3671017, 7063893, 13532120, 25730347, 48840523, 93154161, 178806493, 343926597, 660308308, 1265195467

Offset: 0

Seiichi Manyama, Sep 16 2023

nonn

Cf. A212364, A365698, A365699, A365700, A365701.

Cf. A000108, A005043, A114997, A215341.

a(n) = sum(k=0, n\5, binomial(n-4*k-1, n-5*k)*binomial(n+1, k))/(n+1);

a(n) = (1/(n+1)) * Sum_{k=0..floor(n/5)} binomial(n-4*k-1,n-5*k) * binomial(n+1,k).

A365730 G.f. satisfies A(x) = 1 + x^4A(x)^4(1 + x*A(x)).

Original entry on oeis.org

1, 0, 0, 0, 1, 1, 0, 0, 4, 9, 5, 0, 22, 78, 91, 35, 140, 680, 1224, 969, 1254, 5985, 14630, 17710, 17710, 55660, 164450, 269100, 299520, 593775, 1805076, 3681405, 4951692, 7594752, 20173560, 47303520, 76404460, 110676324, 239784864, 589602585, 1106339923

Offset: 0

Seiichi Manyama, Sep 17 2023

nonn

Cf. A365727, A365728, A365729, A365731.
Cf. A001005, A001006, A365724.
Cf. A215341.

a(n) = sum(k=0, n\4, binomial(k, n-4*k)*binomial(n+1, k))/(n+1);

a(n) = (1/(n+1)) * Sum_{k=0..floor(n/4)} binomial(k,n-4*k) * binomial(n+1,k).

A366054 Expansion of (1/x) * Series_Reversion( x*(1-x)^2/(1-x+x^4) ).

Original entry on oeis.org

1, 1, 2, 5, 15, 49, 168, 594, 2149, 7919, 29627, 112254, 429884, 1661308, 6470678, 25375070, 100106145, 397018815, 1582005849, 6330533220, 25428891084, 102497788194, 414445390730, 1680617637425, 6833083703094, 27849689394894, 113762630541908

Offset: 0

Seiichi Manyama, Sep 27 2023

nonn

Cf. A215341, A366055, A366056.

a(n) = sum(k=0, n\4, binomial(n+1, k)*binomial(2*n-3*k, n-4*k))/(n+1);

a(n) = (1/(n+1)) * Sum_{k=0..floor(n/4)} binomial(n+1,k) * binomial(2*n-3*k,n-4*k).

A366055 Expansion of (1/x) * Series_Reversion( x*(1-x)^3/(1-x+x^4) ).

Original entry on oeis.org

1, 2, 7, 30, 144, 741, 3996, 22287, 127494, 743919, 4410255, 26489073, 160843708, 985729010, 6089215057, 37875775533, 237021929322, 1491204370335, 9426547131330, 59843910602283, 381378377720469, 2438954925930558, 15646857920046108

Offset: 0

Seiichi Manyama, Sep 27 2023

nonn

Cf. A215341, A366054, A366056.

a(n) = sum(k=0, n\4, binomial(n+1, k)*binomial(3*n-3*k+1, n-4*k))/(n+1);

a(n) = (1/(n+1)) * Sum_{k=0..floor(n/4)} binomial(n+1,k) * binomial(3*n-3*k+1,n-4*k).

A366056 Expansion of (1/x) * Series_Reversion( x*(1-x)^4/(1-x+x^4) ).

Original entry on oeis.org

1, 3, 15, 91, 613, 4408, 33143, 257400, 2048825, 16625940, 137033316, 1144010387, 9653706723, 82208879366, 705587243802, 6097408839400, 53007770199641, 463269048213536, 4067950092964440, 35871913838983980, 317533385082542404, 2820492099258807887

Offset: 0

Seiichi Manyama, Sep 27 2023

nonn

Cf. A215341, A366054, A366055.

a(n) = sum(k=0, n\4, binomial(n+1, k)*binomial(4*n-3*k+2, n-4*k))/(n+1);

a(n) = (1/(n+1)) * Sum_{k=0..floor(n/4)} binomial(n+1,k) * binomial(4*n-3*k+2,n-4*k).

A365696 G.f. satisfies A(x) = 1 + x^4A(x)^2 / (1 - xA(x)).

Original entry on oeis.org

1, 0, 0, 0, 1, 1, 1, 1, 3, 6, 10, 15, 26, 49, 92, 165, 294, 535, 994, 1852, 3437, 6379, 11905, 22344, 42058, 79260, 149601, 283038, 536806, 1020066, 1941317, 3699922, 7062308, 13500402, 25842489, 49528164, 95031920, 182545222, 351023451, 675678911, 1301838177

Offset: 0

Seiichi Manyama, Sep 16 2023

nonn

Cf. A023427, A215341, A215342, A357308, A365697.

Cf. A112805.

CoefficientList[Series[(1 + x - Sqrt[1 - 2*x + x^2 - 4*x^4])/(2*x*(1 + x^3)), {x, 0, 40}], x] (* Vaclav Kotesovec, Sep 26 2023 *)

a(n) = sum(k=0, n\4, binomial(n-3*k-1, n-4*k)*binomial(n-2*k+1, k)/(n-2*k+1));

a(n) = Sum_{k=0..floor(n/4)} binomial(n-3*k-1,n-4*k) * binomial(n-2*k+1,k) / (n-2*k+1).
From Vaclav Kotesovec, Sep 26 2023: (Start)
G.f.: (1 + x - sqrt(1 - 2*x + x^2 - 4*x^4)) / (2*x*(1 + x^3)).
a(n) ~ 2^(n + 3/2) / (sqrt(Pi) * 3^(3/2) * n^(3/2)). (End)

A365697 G.f. satisfies A(x) = 1 + x^4A(x)^3 / (1 - xA(x)).

Original entry on oeis.org

1, 0, 0, 0, 1, 1, 1, 1, 4, 8, 13, 19, 38, 79, 153, 273, 509, 999, 1979, 3818, 7331, 14279, 28189, 55599, 109275, 215165, 426093, 846638, 1683215, 3348212, 6673679, 13333171, 26679522, 53437369, 107151335, 215154204, 432586412, 870678377, 1754094266

Offset: 0

Seiichi Manyama, Sep 16 2023

nonn

Cf. A023427, A215341, A215342, A357308, A365696.

Cf. A365245.

a(n) = sum(k=0, n\4, binomial(n-3*k-1, n-4*k)*binomial(n-k+1, k)/(n-k+1));

a(n) = Sum_{k=0..floor(n/4)} binomial(n-3*k-1,n-4*k) * binomial(n-k+1,k) / (n-k+1).

cp's OEIS Frontend

A114997 Number of ordered trees with n edges and no unary or binary nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A215340 Expansion of series_reversion( x/(1 + sum(k>=1, x^A032766(k)) ) ) / x.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A215342 Expansion of series reversion of x*(1-x^3*sum(k>=1, x^k)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A365702 G.f. satisfies A(x) = 1 + x^5*A(x)^5 / (1 - x*A(x)).

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

A365730 G.f. satisfies A(x) = 1 + x^4*A(x)^4*(1 + x*A(x)).

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

A366054 Expansion of (1/x) * Series_Reversion( x*(1-x)^2/(1-x+x^4) ).

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

A366055 Expansion of (1/x) * Series_Reversion( x*(1-x)^3/(1-x+x^4) ).

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

A366056 Expansion of (1/x) * Series_Reversion( x*(1-x)^4/(1-x+x^4) ).

Views

Author

Keywords

Crossrefs

Programs

PARI

A215342 Expansion of series reversion of x(1-x^3sum(k>=1, x^k)).

A365702 G.f. satisfies A(x) = 1 + x^5A(x)^5 / (1 - xA(x)).

A365730 G.f. satisfies A(x) = 1 + x^4A(x)^4(1 + x*A(x)).

A365696 G.f. satisfies A(x) = 1 + x^4A(x)^2 / (1 - xA(x)).

A365697 G.f. satisfies A(x) = 1 + x^4A(x)^3 / (1 - xA(x)).