login
A108263
Triangle read by rows: T(n,k) is the number of short bushes with n edges and k branchnodes (i.e., nodes of outdegree at least two). A short bush is an ordered tree with no nodes of outdegree 1.
10
1, 0, 0, 1, 0, 1, 0, 1, 2, 0, 1, 5, 0, 1, 9, 5, 0, 1, 14, 21, 0, 1, 20, 56, 14, 0, 1, 27, 120, 84, 0, 1, 35, 225, 300, 42, 0, 1, 44, 385, 825, 330, 0, 1, 54, 616, 1925, 1485, 132, 0, 1, 65, 936, 4004, 5005, 1287, 0, 1, 77, 1365, 7644, 14014, 7007, 429, 0, 1, 90, 1925, 13650, 34398
OFFSET
0,9
COMMENTS
Row n has 1+floor(n/2) terms. Row sums are the Riordan numbers (A005043). Column 3 yields A033275; column 4 yields A033276.
Related to the number of certain non-crossing partitions for the root system A_n. Cf. p. 12, Athanasiadis and Savvidou. Diagonals are A033282/A086810. Also see A132081 and A100754.- Tom Copeland, Oct 19 2014
LINKS
Indranil Ghosh, Rows 0..100, flattened
C. Athanasiadis and C. Savvidou, The local h-vector of the cluster subdivision of a simplex, arXiv preprint arXiv:1204.0362, 2012
F. R. Bernhart, Catalan, Motzkin and Riordan numbers, Discr. Math., 204 (1999) 73-112.
Robert Coquereaux and Jean-Bernard Zuber, Counting partitions by genus. II. A compendium of results, arXiv:2305.01100 [math.CO], 2023. See p. 10.
FORMULA
G.f. G=G(t, z) satisfies z*(1+t*z)*G^2 - (1+z)*G + 1 = 0.
T(n, k) = A086810(n-k, k). - Philippe Deléham, May 30 2005
EXAMPLE
T(6,3)=5 because the only short bushes with 6 edges and 3 branchnodes are the five full binary trees with 6 edges.
Triangle begins:
1;
0;
0,1;
0,1;
0,1,2;
0,1,5;
0,1,9,5
MAPLE
G:=(1+z-sqrt((1-z)^2-4*t*z^2))/2/z/(1+t*z): Gser:=simplify(series(G, z=0, 18)): P[0]:=1: for n from 1 to 16 do P[n]:=coeff(Gser, z^n) od: for n from 0 to 16 do seq(coeff(t*P[n], t^k), k=1..1+floor(n/2)) od; # yields sequence in triangular form
A108263 := (n, k) -> binomial(n-k-1, n-2*k)*binomial(n, k)/(n-k+1);
seq(print(seq(A108263(n, k), k=0..ceil((n-1)/2))), n=0..8); # Peter Luschny, Sep 25 2014
MATHEMATICA
T[n_, k_]:=Binomial[n-k-1, n-2k]*Binomial[n, k]/(n-k+1); Flatten[Table[T[n, k], {n, 0, 11}, {k, 0, Ceiling[(n-1)/2]}]] (* Indranil Ghosh, Feb 20 2017 *)
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, May 29 2005
STATUS
approved