login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A121685 Triangle read by rows: T(n,k) is the number of binary trees having n edges and k branches (1<=k<=n). A binary tree is a rooted tree in which each vertex has at most two children and each child of a vertex is designated as its left or right child. 1

%I #2 Mar 30 2012 17:36:10

%S 2,4,1,8,4,2,16,12,12,2,32,32,48,16,4,64,80,160,80,40,5,128,192,480,

%T 320,240,60,10,256,448,1344,1120,1120,420,140,14,512,1024,3584,3584,

%U 4480,2240,1120,224,28,1024,2304,9216,10752,16128,10080,6720,2016,504,42

%N Triangle read by rows: T(n,k) is the number of binary trees having n edges and k branches (1<=k<=n). A binary tree is a rooted tree in which each vertex has at most two children and each child of a vertex is designated as its left or right child.

%C The row sums are the Catalan numbers (A000108). T(n,1)=2^n = A000079(n). T(n,n)=A089408(n+1). Sum(k*T(n,k),k=1..n)=A121686(n).

%F T(n,k)=2^(n-k)*c(k/2)*binomial(n-1,k-1) if k is even and 2^(n-k+1)*c((k-1)/2)*binomial(n-1,k-1) if k is odd, where c(m)=binomial(2m,m)/(m+1) are the Catalan numbers (A000108). G.f.=(1-2z+2tz)(1-2z-sqrt[(1-2z)^2-4t^2*z^2])/(2t^2*z^2) - 1.

%e Triangle starts:

%e 2;

%e 4,1;

%e 8,4,2;

%e 16,12,12,2;

%e 32,32,48,16,4;

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

%Y Cf. A000108, A000079, A089408, A121686.

%K nonn,tabl

%O 1,1

%A _Emeric Deutsch_, Aug 15 2006

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 11:14 EDT 2024. Contains 371278 sequences. (Running on oeis4.)