|
|
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)).
|
|
0
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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(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
|
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
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|