login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A055314 Triangle T(n,k) read by rows: number of labeled trees with n nodes and k leaves, n >= 2, 2 <= k <= n. 17
1, 3, 0, 12, 4, 0, 60, 60, 5, 0, 360, 720, 210, 6, 0, 2520, 8400, 5250, 630, 7, 0, 20160, 100800, 109200, 30240, 1736, 8, 0, 181440, 1270080, 2116800, 1058400, 151704, 4536, 9, 0, 1814400, 16934400, 40219200, 31752000, 8573040, 695520, 11430, 10 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

2,2

REFERENCES

Moon, J. W. Various proofs of Cayley's formula for counting trees. 1967 A seminar on Graph Theory pp. 70--78 Holt, Rinehart and Winston, New York; MR0214515 (35 #5365). - From N. J. A. Sloane, Jun 07 2012

Renyi, Alfred. Some remarks on the theory of trees. Magyar Tud. Akad. Mat. Kutató Int. Közl. 4 1959 73--85. MR0115938 (22 #6735). - From N. J. A. Sloane, Jun 07 2012

D. Stanton and D. White, Constructive Combinatorics, Springer, 1986; see p. 67.

LINKS

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened

A. M. Hamel, Priority queue sorting and labeled trees, Annals Combin., 7 (2003), 49-54.

F. Harary, A. Mowshowitz and J. Riordan, Labeled trees with unlabeled end-points, J. Combin. Theory, 6 (1969), 60-64. - From N. J. A. Sloane, Jun 07 2012

Vites Longani, A formula for the number of labelled trees, Comp. Math. Appl. 56 (2008) 2786-2788. - R. J. Mathar, Nov 30 2008

John Riordan, The enumeration of labeled trees by degrees, Bull. Amer. Math. Soc. 72 1966 110--112. MR0186583 (32 #4042). - From N. J. A. Sloane, Jun 07 2012

Index entries for sequences related to trees

FORMULA

E.g.f.: A(x, y)=(1-x+x*y)*B(x, y)-B(x, y)^2/2. B(x, y): e.g.f. of A055302.

T(n, k) = binomial(n+1, k)*Sum( binomial(n+1-k, i)*(-1)^(n+1-k-i)*i^(n-1), i=0..n+1-k).

T(n, k) = (n!/k!)*Stirling2(n-2, n-k). - Vladeta Jovovic, Jan 28 2004

EXAMPLE

1;

3,0;

12,4,0;

60,60,5,0;

360,720,210,6,0;

2520,8400,5250,630,7,0;

...

MAPLE

T := (n, k) -> binomial(n+1, k)*add( binomial(n+1-k, i)*(-1)^(n+1-k-i)*i^(n-1), i=0..n+1-k);

# The following version gives the triangle for any n>=1, k>=1, based on the Harary et al. (1969) paper - N. J. A. Sloane, Jun 07 2012

with(combinat);

R:=proc(n, k)

if n=1 then if k=1 then RETURN(1) else RETURN(0); fi

    elif (n=2 and k=2) then RETURN(1)

    elif (n=2 and k>2) then RETURN(0)

    else stirling2(n-2, n-k)*n!/k!;

    fi;

end;

MATHEMATICA

Table[Table[Binomial[n, k] Sum[(-1)^j Binomial[n-k, j] (n-k-j)^(n-2), {j, 0, n-k}], {k, 2, n-1}], {n, 2, 10}]//Grid (* Geoffrey Critzer, Nov 12 2011 *)

Table[(n!/k!)*StirlingS2[n - 2, n - k], {n, 2, 7}, {k, 2, n}]//Flatten (* G. C. Greubel, May 17 2017 *)

PROG

(Maxima) A055314(n, k) := block(

        n!/k!*stirling2(n-2, n-k)

)$

for n : 2 thru 10 do

        for k : 2 thru n do

                print(A055314(n, k), " ") ; /* R. J. Mathar, Mar 06 2012 */

(PARI) for(n=2, 20, for(k=2, n, print1((n!/k!)*stirling(n-2, n-k, 2), ", "))) \\ G. C. Greubel, May 17 2017 *)

CROSSREFS

Cf. A000272.

Row sums give A000272. Columns 2 through 12: A001710, A055315-A055324.

Sequence in context: A132221 A140093 A194093 * A110890 A249010 A071534

Adjacent sequences:  A055311 A055312 A055313 * A055315 A055316 A055317

KEYWORD

nonn,tabl

AUTHOR

Christian G. Bower, May 11 2000

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified October 23 20:10 EDT 2017. Contains 293813 sequences.