|
| |
|
|
A061356
|
|
Triangle T(n,k) = labeled trees on n nodes with maximal node degree k (0 < k < n).
|
|
4
| |
|
|
1, 2, 1, 9, 6, 1, 64, 48, 12, 1, 625, 500, 150, 20, 1, 7776, 6480, 2160, 360, 30, 1, 117649, 100842, 36015, 6860, 735, 42, 1, 2097152, 1835008, 688128, 143360, 17920, 1344, 56, 1, 43046721, 38263752, 14880348, 3306744, 459270, 40824, 2268, 72, 1
(list; table; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 2,2
|
|
|
COMMENTS
| This is a formula from Theorem F, vol. I, p. 81 (French edition) used in proving Theorem D.
If we let N = n+1, binomial(N-2, k-1)*(N-1)^(N-k-1) = binomial(n-1, k-1)*n^(n-k), so this sequence with offset 1,1 also gives the number of rooted forests of k trees over [n]. - Washington G. Bomfim (webonfim(AT)bol.com.br), Jan 09 2008
Let S(n,k) be the signed triangle, S(n,k) = (-1)^(n-k)T(n,k), which starts 1, -2, 1, 9, -6, 1,..., then the inverse of S is the triangle of idempotent numbers A059298. [From Peter Luschny (peter(AT)luschny.de), Mar 13 2009]
With offset 1 also number of labeled multigraphs of k components, n nodes, and no cycles except one loop in each component. See link below to have a picture showing the bijection between rooted forests and multigraphs of this kind. (Note that there are no labels in the picture, but the bijection remains true if we label the nodes.) [From W. Bomfim (webonfim(AT)bol.com.br), Sep 04 2010]
With offset 1, T(n,k) is the number of forests of rooted trees on n nodes with exactly k (rooted) trees. - Geoffrey Critzer, Feb 10 2012
|
|
|
REFERENCES
| L. Comtet, Analyse Combinatoire, P.U.F., Paris 1970. Volume 1, p 81.
L. Comtet, Advanced Combinatorics, Reidel, 1974.
J. W. Moon, Another proof of Cayley's formula for counting trees, A.M.M., 70 (1963) p846-7.
|
|
|
LINKS
| Jim Pitman, Coalescent Random Forests .
J. Zeng, A Ramanujan sequence that refines the Cayley formula for trees, Ramanujan J., 3(1999) 1, 45-54.
W. Bomfim, Bijection between rooted forests and multigraphs without cycles except one loop in each connected component. [From W. Bomfim (webonfim(AT)bol.com.br), Sep 04 2010]
|
|
|
FORMULA
| T(n, k) = binomial(n-2, k-1)*(n-1)^(n-k-1).
E.g.f.: (-LambertW(-y)/y)^(x+1)/(1+LambertW(-y)) (from Vladeta Jovovic (vladeta(AT)eunet.rs))
|
|
|
EXAMPLE
| 1
2 1
9 6 1
64 48 12 1
625 500 150 20 1
7776 6480 2160 360 30 1
|
|
|
MATHEMATICA
| nn = 7; t = Sum[n^(n - 1) x^n/n!, {n, 1, nn}]; f[list_] := Select[list, # > 0 &]; Map[f, Drop[Range[0, nn]! CoefficientList[Series[Exp[y t], {x, 0, nn}], {x, y}], 1]] // Flatten (* Geoffrey Critzer, Feb 10 2012 *)
|
|
|
CROSSREFS
| Columns are A000169, A053506, A053507, A053508, A053509. First diagonal is A002378. Sum of lines gives A000272.
Sequence in context: A155545 A141618 A061691 * A141028 A201685 A120671
Adjacent sequences: A061353 A061354 A061355 * A061357 A061358 A061359
|
|
|
KEYWORD
| easy,nonn,tabl,changed
|
|
|
AUTHOR
| Olivier Gerard (olivier.gerard(AT)gmail.com), Jun 07 2001
|
| |
|
|
