A059968 Number of 10-ary trees.

1, 1, 10, 145, 2470, 46060, 910252, 18730855, 397089550, 8612835715, 190223180840, 4263421511271, 96723482198980, 2216905597676000, 51256802757808320, 1194060413809070710, 27999654303202465310, 660370070571422998410, 15654733143626084944150

Offset: 0

Author

Claude Lenormand (claude.lenormand(AT)free.fr), Mar 05 2001

Keywords

• nonn
• easy

Comments

From Wolfdieter Lang, Feb 06 2020: (Start)

Ninth column of triangle A062993 (without leading zeros). A Pfaff-Fuss or 10-Raney sequence.

a(n), n>=1, enumerates 10-ary trees (rooted, ordered, incomplete) with n vertices (including the root).

See Graham et al., Hilton and Pedersen, Hoggat and Bicknell, Frey and Sellers references given in A062993. (End)

This is instance k = 10 of the generalized Catalan family {C(k, n)}A130564%20-%20_Wolfdieter%20Lang">{n>=0} given in a comment of A130564 - _Wolfdieter Lang, Feb 05 2024

Examples

			There are a(2)=10 10-ary trees (vertex degree <=10 and 10 possible branchings) with 2 vertices (one of them the root). Adding one more branch (one more vertex) to these 10 trees yields 10*10+binomial(10,2)=145=a(3) such trees. - _Wolfdieter Lang_, Sep 14 2007.
		

References

• G. Pólya and G. Szegő, Problems and Theorems in Analysis, Springer-Verlag, Heidelberg, New York, 2 vols., 1972, Vol. 1, problem 211, p. 146 with solution on p. 348.

Links

• S. Heubach, N. Y. Li and T. Mansour, Staircase tilings and k-Catalan structures, Discrete Math., 308 (2008), 5954-5964.

Crossrefs

Related algebraic sequences concerning trees: strictly k-ary trees (A000108: s=x+s^2, A001263: s=(x, y)+(x, s)+(s, y)+(s, s))), (A001764: s=x+s^3), (A002293: s=x+s^4), (A002294: s=x+s^5), (A002295: s=x+s^6), (A002296: s=x+s^7), (A007556: s=x+s^8), at most k-ary trees (A001006: s=x+xs+xs^2), (A036765-A036769, s=x+xs^2....+xs^k, k=3, 4, 5, 6, 7).

Pfaff-Fuss A062993 column members: A000108, A001764, A002293, A002294, A002295, A002296, A007556, A062994, A230388.

Cf. A130564.

Programs

Maple

seq(binomial(10*k+1, k)/(9*k+1), k=0..30);
n:=30:G:=series(RootOf(g = 1+x*g^10, g), x=0, n+1):seq(coeff(G, x, k), k=0..n); # Robert FERREOL, Apr 01 2015

Mathematica

a[n_] := Binomial[10n, n]/(9n+1);
a /@ Range[0, 25] (* Jean-François Alcover, Jan 17 2020 *)

Formula

G.f. A(x) satisfies: A = x + A^10.

a(n) = binomial(k*n, n)/((k-1)*n+1), for k=10.

Recurrence: a(0) = 1; a(n) = Sum_{i1+i2+..i10=n-1} a(i1)*a(i2)*...*a(i10) for n>=1. - Robert FERREOL, Apr 01 2015

From Wolfdieter Lang, Feb 06 2020: (Start)

a(n) = A062993(n+8, 8). [Corrected by Robert FERREOL, Apr 01 2015]

G.f.: RootOf((_Z^10)*x-_Z+1) (Maple notation, from ECS, see links for A007556).

G.f.: hypergeometric([1, 2, 3, 4, 5, 6, 7, 8, 9]/10, [2, 3, 4, 5, 6, 7, 8, 10]/9, (10^10/9^9)*x),

E.g.f.: hypergeometric([1, 2, 3, 4, 5, 6, 7, 8, 9]/10, [2, 3, 4, 5, 6, 7, 8, 9, 10]/9, (10^10/9^9)*x).

For other family members see the crossreferences.

(End)

D-finite with recurrence 81*n*(9*n-7)*(9*n-5)*(3*n-1)*(9*n-1)*(9*n+1)*(3*n-2)*(9*n-4)*(9*n-2)*a(n) -800*(10*n-9)*(5*n-4)*(10*n-7)*(5*n-3)*(2*n-1)*(5*n-2)*(10*n-3)*(5*n-1)*(10*n-1)*a(n-1)=0. - R. J. Mathar, Mar 21 2022

a(n) ~ (10^10/9^9)^n*sqrt(10/(2*Pi*(9*n)^3)). - Robert A. Russell, Jul 15 2024

G.f. A(x) satisfies A(x) = 1/A(-x*A(x)^19). - Seiichi Manyama, Jun 16 2025

Extensions

More terms from James Sellers, Mar 15 2001

a(0)=1 inserted by Alois P. Heinz, Jan 17 2020

A062744 merged into this sequence by Wolfdieter Lang, Feb 06 2020