0,2

Also T(n,k) is number of hex trees with n edges and k left edges (0<=k<=n). 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). Accordingly, one can have left, vertical, or right edges.

Also (with a different offset) T(n,k) is the number of skew Dyck paths of semilength n and having k peaks (1<=k<=n). A skew Dyck path is a path in the first quadrant which begins at the origin, ends on the x-axis, consists of steps U=(1,1)(up), D=(1,-1)(down) and L=(-1,-1)(left) so that up and left steps do not overlap. The length of the path is defined to be the number of its steps. E.g. T(3,2)=5 because we have (UD)U(UD)D, (UD)U(UD)L, U(UD)D(UD), U(UD)(UD)D and U(UD)(UD)L (the peaks are shown between parentheses).

Sum of terms in row n = A002212(n+1). T(n,1)=A001793(n); T(n,2)=A006974(n-2); sum(kT(n,k), k=0..n)=A026379(n+1).

A126216 = N * P. - Gary W. Adamson (qntmpkt(AT)yahoo.com), Nov 30 2007

E. Deutsch, E. Munarini and S. Rinaldi, Skew Dyck paths (in preparation).

F. Harary and R. C. Read, The enumeration of tree-like polyhexes, Proc. Edinburgh Math. Soc. (2) 17 (1970), 1-13.

T(n,k)=[1/(n+1)]*binomial(n+1,k)*sum(2^j*binomial(k,n-k-j)*binomial(n+1-k,j),j=n-2k..n-k) if 0<k<=n; T(n,0)=2^n. G.f.=G=G(t,z) satisfies G=1+(t+2)zG+tz^2*G^2.

The triangle P begins

1,

1,1

1,2,1

1,3,3,1,...

and T begins

1,

1,1,

1,3,1,

1,6,6,1,

1,10,20,10,1, ...

The product P*T gives

1,

2,1,

4,5,1,

8,18,9,1,

16,56,50,14,1,...

T:=proc(n, k) if k=0 then 2^n elif k<=n then binomial(n+1, k)*sum(binomial(k, n-k-j)*binomial(n+1-k, j)*2^j, j=n-2*k..n-k)/(n+1) else 0 fi end: for n from 0 to 10 do seq(T(n, k), k=0..n) od; # yields sequence in triangular form

Cf. A001263, A007318, A002212, A001793, A006974, A026379.

Cf. A128718, A026378.

Cf. A126216.

Sequence in context: A124237 A123876 A114164 this_sequence A154342 A143494 A124960

Adjacent sequences: A126179 A126180 A126181 this_sequence A126183 A126184 A126185

nonn,tabl,nice

Emeric Deutsch (deutsch(AT)duke.poly.edu), Dec 19 2006, Mar 30 2007

New definition in terms of P and N from Philippe DELEHAM, Jun 30 2007

Edited by N. J. A. Sloane (njas(AT)research.att.com), Jul 22 2007