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.

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

Author

Emeric Deutsch, May 29 2005

Keywords

• nonn
• tabf

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

Examples

			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
		

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.

Crossrefs

Cf. A005043, A033275, A033276.

Columns: A000007, A000012, A000096, A033275, A033276, A033277, A033278, A033279; A005043 (row sums), A033282, A086810

Programs

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

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