A126179 - OEIS

%I #24 Sep 19 2024 04:17:38

%S 3,9,1,27,6,3,81,27,27,2,243,108,162,24,6,729,405,810,180,90,5,2187,

%T 1458,3645,1080,810,90,15,6561,5103,15309,5670,5670,945,315,14,19683,

%U 17496,61236,27216,34020,7560,3780,336,42,59049,59049,236196,122472

%N Triangle read by rows: T(n,k) is number of hex trees with n edges and k branches (1 <= k <= n).

%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 median child, or a right child (name due to an obvious bijection with certain tree-like polyhexes; see the Harary-Read reference).

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

%H J. Riordan, <a href="http://dx.doi.org/10.1016/S0097-3165(75)80010-0">Enumeration of plane trees by branches and endpoints</a>, J. Comb. Theory (A) 19, 1975, 214-222.

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

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

%F T(2n,2n) = c(n); T(2n+1,2n+1) = 3*c(n), where c(n) = binomial(2n,n)/(n+1) is a Catalan number (A000108).

%F Sum_{k=1..n} k*T(n,k) = A126180(n).

%F T(n,k) = 3^(n-k+1)*binomial(n-1,k-1)*c((k-1)/2) if k is odd; T(n,k) = 3^(n-k)*binomial(n-1,k-1)*c(k/2) if k is even; c(m) = binomial(2m,m)/(m+1) is a Catalan number.

%F G.f.: ((1-3z+3tz)/(1-3z))*C(t^2*z^2/(1-3z)^2)-1, where C(z) = (1-sqrt(1-4z))/(2z) is the Catalan function.

%F G.f.: (1-3z+3tz)*(1-3z-sqrt((1-3z)^2-4t^2*z^2))/(2t^2*z^2)-1;

%e Triangle starts:

%e     3;

%e     9,   1;

%e    27,   6,   3;

%e    81,  27,  27,   2;

%e   243, 108, 162,  24,   6;

%p c:=n->binomial(2*n,n)/(n+1): T:=proc(n,k) if k mod 2 = 0 then 3^(n-k)*binomial(n-1,k-1)*c(k/2) else 3^(n-k+1)*binomial(n-1,k-1)*c((k-1)/2) fi end: for n from 1 to 11 do seq(T(n,k),k=1..n) od; # yields sequence in triangular form

%t n = 20; g[t_, z_] = (1 - 3z + 3t*z)* ((1 - 3z - Sqrt[(1 - 3z)^2 - 4t^2*z^2])/(2t^2*z^2)) - 1; Flatten[ Rest[ CoefficientList[#, t]] & /@ Rest[ CoefficientList[ Series[g[t, z], {z, 0, n}], z]]] (* _Jean-François Alcover_, Jul 22 2011, after g.f. *)

%Y Cf. A000108, A000244, A002212, A126180.

%K nonn,tabl

%O 1,1

%A _Emeric Deutsch_, Dec 19 2006