A127157 Triangle read by rows: T(n,k) is the number of ordered trees with n edges and 2k nodes of odd degree (not outdegree; 1 <= k <= ceiling(n/2)).

1, 2, 3, 2, 4, 10, 5, 30, 7, 6, 70, 56, 7, 140, 252, 30, 8, 252, 840, 330, 9, 420, 2310, 1980, 143, 10, 660, 5544, 8580, 2002, 11, 990, 12012, 30030, 15015, 728, 12, 1430, 24024, 90090, 80080, 12376, 13, 2002, 45045, 240240, 340340, 111384, 3876, 14, 2730

Offset

1,2

Comments

Row n has ceiling(n/2) terms.

Row sums are the Catalan numbers (A000108).

T(n,1) = n;

T(n,2) = 2*binomial(n+1, 4) = 2*A000332(n+1);

T(n,3) = 7*binomial(n+2, 7) = 7*A000580(n+2);

T(n,4) = 30*binomial(n+3, 10) = 30*A001287(n+3);

T(n,5) = 143*binomial(n+4, 13) = 143*A010966(n+4);

T(2n-1,n) = A006013(n-1).

T(n,k) is the number of ordered trees (A000108) with n edges, exactly k of whose vertices possess at least one leaf child. [David Callan, Aug 22 2014]

Links

Table of n, a(n) for n=1..51.

J.-C. Aval, A. Boussicault, B. Delcroix-Oger, F. Hivert, et al., Non-ambiguous trees: new results and generalization, arXiv preprint arXiv:1511.09455 [math.CO], 2015.

Bérénice Delcroix-Oger, Florent Hivert, Patxi Laborde-Zubieta, Jean-Christophe Aval, and Adrien Boussicault, Non-ambiguous trees: new results and generalisation, hal-03165269v2 [cs.DM] [math.CO], 2021.

Tad White, Quota Trees, arXiv:2401.01462 [math.CO], 2024. See p. 20.

Formula

T(n,k) = 2*binomial(3k-1,2k)*binomial(n-1+k,3k-2)/(3k-1) (formula obtained only by inspection).

G.f.: G-1, where G=G(t,z) satisfies z^2*G^3 - z(z+2)G^2 + (1+2z)*G - t^2*z - 1 = 0.

Example

Triangle starts:
  1;
  2;
  3,  2;
  4, 10;
  5, 30,  7;
  6, 70, 56;

Maple

T:=(n, k)->2*binomial(3*k-1, 2*k)*binomial(n-1+k, 3*k-2)/(3*k-1): for n from 1 to 15 do seq(T(n, k), k=1..ceil(n/2)) od;

Mathematica

m = 14(*rows*); G = 0; Do[G = Series[(1 + t^2 z - G^3 z^2 + G^2 z (2+z))/ (1+2z), {t, 0, m}, {z, 0, m}] // Normal // Expand, m]; Rest[ CoefficientList[#, t^2]]& /@ Rest[CoefficientList[G-1, z] ] // Flatten (* Jean-François Alcover, Jan 23 2019 *)

Crossrefs

Cf. A000108, A000332, A000580, A001287, A010966, A006013.

Sequence in context: A304489 A034800 A082771 * A236406 A247497 A202714

Adjacent sequences: A127154 A127155 A127156 * A127158 A127159 A127160

Keyword

nonn,tabf

Author

Emeric Deutsch, Feb 27 2007

Status

approved