A126177 - OEIS

%I #8 Jul 23 2019 02:02:58

%S 3,9,1,27,9,81,54,2,243,270,30,729,1215,270,5,2187,5103,1890,105,6561,

%T 20412,11340,1260,14,19683,78732,61236,11340,378,59049,295245,306180,

%U 85050,5670,42,177147,1082565,1443420,561330,62370,1386,531441,3897234

%N Triangle read by rows: T(n,k) is number of hex trees with n edges and k leaves (n >= 1, 1 <= k <= 1 + floor(n/2)).

%C A hex tree is a rooted tree where each vertex has 0, 1, or 2 children and, when only one child is present, it is either a left child, or a middle child, or a right child (name due to an obvious bijection with certain tree-like polyhexes; see the Harary-Read paper).

%C Also number of hex trees with n edges and k-1 nodes of outdegree 2.

%C Row n has 1 + floor(n/2) terms.

%C Sum of terms in row n = A002212(n+1).

%C T(n,1) = 3^n (A000244).

%C T(n,2) = A027472(n+1).

%C Sum_{k=1..1+floor(n/2)} k*T(n,k) = A026375(n).

%H F. Harary and R. C. Read, <a href="https://doi.org/10.1017/S0013091500009135">The enumeration of tree-like polyhexes</a>, Proc. Edinburgh Math. Soc. (2) 17 (1970), 1-13.

%F T(n,k) = 3^(n-2k+2)*binomial(2k-2,k-1)*binomial(n,2k-2)/k. Proof: There are Catalan(k-1) full binary trees with k leaves. Each of them has 2k-2 edges. Additional n-2k+2 edges can be inserted as paths at the existing 2k-1 vertices in 3^(n-2k+2)*binomial(n,2k-2) ways.

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

%e Triangle starts:

%e     3;

%e     9,   1;

%e    27,   9;

%e    81,  54,   2;

%e   243, 270,  30;

%p T:=(n,k)->3^(n-2*k+2)*binomial(2*k-2,k-1)*binomial(n,2*k-2)/k: for n from 1 to 13 do seq(T(n,k),k=1..1+floor(n/2)) od; # yields sequence in triangular form

%Y Cf. A002212, A000244, A027472, A026375.

%K nonn,tabf

%O 1,1

%A _Emeric Deutsch_, Dec 19 2006