login
Triangle read by rows: T(n,k) = binomial(3k,k)*binomial(n+k,3k)/(2k+1) (0 <= k <= floor(n/2)).
3

%I #39 Feb 26 2024 11:01:08

%S 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,

%T 120,1386,2640,715,1,165,2772,8580,5005,273,1,220,5148,24024,25025,

%U 4368,1,286,9009,60060,100100,37128,1428,1,364,15015,137280,340340,222768

%N Triangle read by rows: T(n,k) = binomial(3k,k)*binomial(n+k,3k)/(2k+1) (0 <= k <= floor(n/2)).

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

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

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

%H Michael De Vlieger, <a href="/A108759/b108759.txt">Table of n, a(n) for n = 0..10200</a> (rows 0 <= n <= 200, flattened)

%H David Callan, <a href="https://arxiv.org/abs/math/0502532">Some Identities for the Catalan and Fine Numbers</a>, arXiv:math/0502532 [math.CO], 2005.

%H Wenqin Cao, Emma Yu Jin, and Zhicong Lin, <a href="https://doi.org/10.1016/j.dam.2019.01.035">Enumeration of inversion sequences avoiding triples of relations</a>, Discrete Applied Mathematics (2019); see also <a href="http://www.emmayujin.at/Pubs/CaoJinLin19.pdf">author's copy</a>

%H Thomas Einolf, Robert Muth, and Jeffrey Wilkinson, <a href="https://arxiv.org/abs/2107.13417">Injectively k-colored rooted forests</a>, arXiv:2107.13417 [math.CO], 2021.

%H Sergey Kitaev and Philip B. Zhang, <a href="https://arxiv.org/abs/2310.17236">Non-overlapping descents and ascents in stack-sortable permutations</a>, arXiv:2310.17236 [math.CO], 2023.

%H Heinrich Niederhausen, <a href="https://doi.org/10.37236/1649">Catalan Traffic at the Beach</a>, Electronic Journal of Combinatorics, Volume 9 (2002), #R33 (p.12).

%H Yidong Sun, <a href="https://arxiv.org/abs/0805.1279">A simple bijection between binary trees and colored ternary trees</a>, arXiv:0805.1279 [math.CO], 2008.

%H Tad White, <a href="https://arxiv.org/abs/2401.01462">Quota Trees</a>, arXiv:2401.01462 [math.CO], 2024. See p. 20.

%F T(n,k) = binomial(n+1,2k+1) * binomial(n+k,k) / (n+1).

%F Sum_{k=0..floor(n/2)} T(n,k)*2^k = A049171(n+1). - _Philippe Deléham_, Dec 08 2009

%e Table begins

%e n\k..0....1....2....3....4

%e 0 |..1

%e 1 |..1

%e 2 |..1....1

%e 3 |..1....4

%e 4 |..1...10....3

%e 5 |..1...20...21

%e 6 |..1...35...84...12

%e 7 |..1...56..252..120

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

%e The ordered trees on 3 edges with 1 node adjacent to a leaf are (drawn down from the root)

%e /\..../\....|

%e |......|..../\

%e together with the path of 3 edges; so T(3,1)=4. (Example reworked by _David Callan_, Oct 08 2005)

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

%t 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 *)

%Y Cf. A000108, A001764, A049171.

%K nonn,tabf

%O 0,6

%A _Emeric Deutsch_, Jun 24 2005