A056856 Triangle of numbers related to rooted trees and unrooted planar trees.

1, 1, 2, 2, 9, 9, 6, 44, 96, 64, 24, 250, 875, 1250, 625, 120, 1644, 8100, 18360, 19440, 7776, 720, 12348, 79576, 252105, 420175, 352947, 117649, 5040, 104544, 840448, 3465728, 8028160, 10551296, 7340032, 2097152

Offset: 1

Author

F. Chapoton, Aug 31 2000

Keywords

• nonn
• tabl
• easy

Comments

The rows sum to A006963: (2*n - 1)!/n!.

The main diagonal is A000169: n^(n-1).

The left column is A000142: (n - 1)!.

The alternating sum in row n is (-1)^(n-1)*(n - 1)!

If Y := X * (1 - X)^(z-1), then (1 - z*X)^(-1) = 1 + Sum_{n>=1} Y^n/(n-1)! * (Sum_{k=1..n} (-1)^(n-k) * z^k * T(n, k)). Note that if Y = y^(z-1) and X = x^(z-1) then y = x - x^z, dy/dx = 1 - z*x^(z-1) = 1 - z*X, and dx/dy = (1 - z*X)^(-1). Also x = y + x^z = y + y^z + z*y^(2*z-1) + ... = y * (1 + Sum_{n>=1} Y^n/(n-1)! * (1+(z-1)*n)^(-1) * (Sum_{k=1..n} (-1)^(n-k) * z^k * T(n, k))). - Michael Somos, Aug 01 2019

Examples

			Triangle begins:
{1},
{1, 2},
{2, 9, 9},
{6, 44, 96, 64},
{24, 250, 875, 1250, 625},
...
		

References

• R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, Reading, MA, 2nd ed. 1998.

Crossrefs

Cf. A006963, A000142, A000169, A203904.

Programs

Maple

seq(seq(coeff(product(n*x + k, k = 1..n-1), x, i), i = 0..n-1), n = 1..8); # Peter Bala, Nov 08 2015

Mathematica

T[n_, m_] := (n^(m-1)*Binomial[n-1, m-1]*Sum[((-1)^(n-m-k)*Binomial[n+k-1, k]*StirlingS2[n-m+k, k]*Binomial[2*n-m, n-m-k])/Binomial[n-m+k, k], {k, 0, n-m}]); Table[T[n, m], {n, 1, 8}, {m, 1, n}] // Flatten (* Jean-François Alcover, Feb 23 2017, after Vladimir Kruchinin *)
T[ n_, k_] := If[ n < 1 || k < 1, 0, Coefficient[ (-1)^(n - k) Binomial[n z, n] (n - 1)!, z, k]]; (* Michael Somos, Aug 01 2019 *)

Maxima

T(n,m):=(n^(m-1)*binomial(n-1,m-1)*sum(((-1)^(n-m-k)*binomial(n+k-1,k)*stirling2(n-m+k,k)*binomial(2*n-m,n-m-k))/binomial(n-m+k,k),k,0,n-m)); /* Vladimir Kruchinin, Apr 05 2016 */

PARI

{T(n, k) = if( n < 1 || k < 1, 0, polcoeff( (-1)^(n-k) * binomial(n*x, n)*(n-1)!, k))}; /* Michael Somos, Aug 01 2019 */

Formula

Formula for row n: Sum_{k = 0..n-1} T(n,k)*y^k = Product_{k = 1..n-1} (k + n*y)

E.g.f.: A(x,t) = Sum_{n >= 1} 1/(n*t)*binomial(n*t + n - 1, n)*x^n = log(B_(t+1)(x)), where B_t(x) = Sum_{n >= 0} 1/(n*t + 1)*binomial(n*t + 1, n)*x^n is Lambert's generalized binomial series - see Graham et al., Section 5.4. - Peter Bala, Nov 08 2015

T(n,m) = n^(m-1)*binomial(n-1,m-1)*Sum_{k=0..n-m} ((-1)^(n-m-k)*binomial(n+k-1,k)*stirling2(n-m+k,k)*binomial(2*n-m,n-m-k))/binomial(n-m+k,k). - Vladimir Kruchinin, Apr 05 2016

Conjecture: T(n,k) = A130534(n,k)* n^(k-1). - R. J. Mathar, Mar 31 2023

Extensions

a(29)-a(36) from Peter Bala, Nov 08 2015