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!)
A108759 Triangle read by rows: T(n,k) = binomial(3k,k)*binomial(n+k,3k)/(2k+1) (0 <= k <= floor(n/2)). 3
1, 1, 1, 1, 1, 4, 1, 10, 3, 1, 20, 21, 1, 35, 84, 12, 1, 56, 252, 120, 1, 84, 630, 660, 55, 1, 120, 1386, 2640, 715, 1, 165, 2772, 8580, 5005, 273, 1, 220, 5148, 24024, 25025, 4368, 1, 286, 9009, 60060, 100100, 37128, 1428, 1, 364, 15015, 137280, 340340, 222768 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,6
COMMENTS
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, 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_{i=1..t} ell(i) = n. Then X = Sum_{i=1..t} floor(ell(i)/2). 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, Jul 22 2008
LINKS
Michael De Vlieger, Table of n, a(n) for n = 0..10200 (rows 0 <= n <= 200, flattened)
David Callan, Some Identities for the Catalan and Fine Numbers, arXiv:math/0502532 [math.CO], 2005.
Wenqin Cao, Emma Yu Jin, and Zhicong Lin, Enumeration of inversion sequences avoiding triples of relations, Discrete Applied Mathematics (2019); see also author's copy
Thomas Einolf, Robert Muth, and Jeffrey Wilkinson, Injectively k-colored rooted forests, arXiv:2107.13417 [math.CO], 2021.
Sergey Kitaev and Philip B. Zhang, Non-overlapping descents and ascents in stack-sortable permutations, arXiv:2310.17236 [math.CO], 2023.
Heinrich Niederhausen, Catalan Traffic at the Beach, Electronic Journal of Combinatorics, Volume 9 (2002), #R33 (p.12).
Yidong Sun, A simple bijection between binary trees and colored ternary trees, arXiv:0805.1279 [math.CO], 2008.
Tad White, Quota Trees, arXiv:2401.01462 [math.CO], 2024. See p. 20.
FORMULA
T(n,k) = binomial(n+1,2k+1) * binomial(n+k,k) / (n+1).
Sum_{k=0..floor(n/2)} T(n,k)*2^k = A049171(n+1). - Philippe Deléham, Dec 08 2009
EXAMPLE
Table begins
n\k..0....1....2....3....4
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, Oct 08 2005)
MAPLE
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
MATHEMATICA
Flatten[Table[Binomial[3k, k] Binomial[n+k, 3k]/(2k+1), {n, 0, 20}, {k, 0, Floor[n/2]}]] (* Harvey P. Dale, May 08 2012 *)
CROSSREFS
Sequence in context: A347115 A006370 A262370 * A158824 A348074 A334161
KEYWORD
nonn,tabf,changed
AUTHOR
Emeric Deutsch, Jun 24 2005
STATUS
approved

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 2 05:08 EST 2024. Contains 370460 sequences. (Running on oeis4.)