login
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

%I #29 Feb 26 2024 11:01:15

%S 1,2,3,2,4,10,5,30,7,6,70,56,7,140,252,30,8,252,840,330,9,420,2310,

%T 1980,143,10,660,5544,8580,2002,11,990,12012,30030,15015,728,12,1430,

%U 24024,90090,80080,12376,13,2002,45045,240240,340340,111384,3876,14,2730

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

%C Row n has ceiling(n/2) terms.

%C Row sums are the Catalan numbers (A000108).

%C T(n,1) = n;

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

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

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

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

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

%C 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]

%H J.-C. Aval, A. Boussicault, B. Delcroix-Oger, F. Hivert, et al., <a href="http://arxiv.org/abs/1511.09455">Non-ambiguous trees: new results and generalization</a>, arXiv preprint arXiv:1511.09455 [math.CO], 2015.

%H Bérénice Delcroix-Oger, Florent Hivert, Patxi Laborde-Zubieta, Jean-Christophe Aval, and Adrien Boussicault, <a href="https://hal.archives-ouvertes.fr/hal-03165269v2">Non-ambiguous trees: new results and generalisation</a>, hal-03165269v2 [cs.DM] [math.CO], 2021.

%H Tad White, <a href="https://arxiv.org/abs/2401.01462">Quota Trees</a>, arXiv:2401.01462 [math.CO], 2024. See p. 20.

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

%F 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.

%e Triangle starts:

%e 1;

%e 2;

%e 3, 2;

%e 4, 10;

%e 5, 30, 7;

%e 6, 70, 56;

%p 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;

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

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

%K nonn,tabf

%O 1,2

%A _Emeric Deutsch_, Feb 27 2007