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,3

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

References

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

Links

Table of n, a(n) for n=1..36.

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

Example

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

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

Prog

(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 */

Crossrefs

Cf. A006963, A000142, A000169, A203904.

Sequence in context: A346918 A203904 A104681 * A133920 A229594 A059199

Adjacent sequences: A056853 A056854 A056855 * A056857 A056858 A056859

Keyword

nonn,tabl,easy

Author

F. Chapoton, Aug 31 2000

Extensions

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

Status

approved