0,6

Row n has 1+floor(n/2) terms. Row sums are the Catalan numbers (A000108). T(2n,n)=binomial(3n,n)/(2n+1) (A001764).

Triangle read by rows: number of ordered trees counted by number of interior vertices adjacent to a leaf. T(n,k) = number of ordered trees on n edges (A000108) containing k nodes adjacent to a leaf, where a node is a non-leaf non-root vertex. - David Callan (callan(AT)stat.wisc.edu), Jul 25 2005

T(n,k) counts full binary trees on 2n edges by the value k of the following statistic X. Delete all right edges leaving the left edges in place. This partitions the left edges into line segments of lengths say ell(1),ell(2),...,ell(t), with Sum[ell(i),i=1..t] = n. Then X = Sum[Floor(ell(i)/2),i=1..t]. This result is implicit in the Sun reference. Also, there is a standard bijection from full binary trees on 2n edges to Dyck paths of length 2n: draw tree up from root; walk clockwise around the tree starting at the root; process in turn each edge *that has not previously been traversed*: a left edge becomes an upstep and a right edge becomes a downstep. Translated to Dyck paths using this walkaround bijection, the statistic X becomes the sum, taken over all the ascents A, of Floor(Length(A)/2). (An ascent is a maximal sequence of contiguous upsteps. Its length is the number of upsteps in it). - David Callan (callan(AT)stat.wisc.edu), Jul 22 2008

H. Niederhausen, Catalan traffic at the beach, The Electronic Journal of Combinatorics, 9 (2002), #R33 (p.12).

David Callan, Some Identities for the Catalan and Fine Numbers

Yidong Sun, A simple bijection between binary trees and colored ternary trees.

T(n, k) = binom[n+1, 2k+1]binom[n+k, k]/(n+1).

Table begins

\ k..0....1....2....3....4

n\

0 |..1

1 |..1

2 |..1....1

3 |..1....4

4 |..1...10....3

5 |..1...20...21

6 |..1...35...84...12

7 |..1...56..252..120

8 |..1...84..630..660...55

The ordered trees on 3 edges with 1 node adjacent to a leaf are (drawn down

from the root)

/\..../\....|

|......|..../\

together with the path of 3 edges; so T(3,1)=4. (Example reworked by David Callan (callan(AT)stat.wisc.edu), Oct 08 2005)

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

Adjacent sequences: A108756 A108757 A108758 this_sequence A108760 A108761 A108762

Sequence in context: A138775 A121529 A006370 this_sequence A158824 A039806 A030320

nonn,tabf

Emeric Deutsch (deutsch(AT)duke.poly.edu), Jun 24 2005