27:
336:. In a short 1889 note, Cayley extended the formula in several directions, by taking into account the degrees of the vertices. Although he referred to Borchardt's original paper, the name "Cayley's formula" became standard in the field.
316:
due to Jim Pitman counts in two different ways the number of different sequences of directed edges that can be added to an empty graph on n vertices to form from it a rooted tree; see
145:
106:
67:
249:
212:
188:
269:
317:
281:
360:. Each labelled rooted forest can be turned into a labelled tree with one extra vertex, by adding a vertex with label
313:
603:
534:
387:
493:(1860). "Über eine Interpolationsformel für eine Art Symmetrischer Functionen und über Deren Anwendung".
111:
490:
329:
72:
33:
512:
345:
221:
215:
550:
470:
289:
466:
8:
191:
20:
280:
Many proofs of Cayley's tree formula are known. One classical proof of the formula uses
197:
173:
293:
582:
565:
577:
371:
168:
546:
476:
297:
284:, a formula for the number of spanning trees in an arbitrary graph involving the
259:
301:
597:
508:
462:
255:
164:
309:
160:
333:
285:
152:
26:
386:. A bijection between rooted forests and parking functions was given by
398:
The following generalizes Cayley's formula to labelled forests: Let
344:
Cayley's formula immediately gives the number of labelled rooted
308:-node trees with two distinguished nodes and maximal directed
367:
and connecting it to all roots of the trees in the forest.
264:
30:
The complete list of all trees on 2,3,4 labeled vertices:
318:
Double counting (proof technique) § Counting trees
224:
200:
176:
114:
75:
36:
495:
Math. Abh. der
Akademie der Wissenschaften zu Berlin
419:
connected components, such that vertices 1, 2, ...,
370:
There is a close connection with rooted forests and
423:all belong to different connected components. Then
243:
206:
182:
139:
100:
61:
300:of Cayley's formula. Another bijective proof, by
595:
533:
254:The formula equivalently counts the number of
461:
304:, finds a one-to-one transformation between
16:Number of spanning trees of a complete graph
374:, since the number of parking functions on
566:"On Cayley's formula for counting forests"
581:
570:Journal of Combinatorial Theory, Series A
489:
25:
596:
563:
507:
537:(1968). "On an enumeration problem".
411:be the number of labelled forests on
328:The formula was first discovered by
339:
13:
393:
14:
615:
262:with labeled vertices (sequence
539:Journal of Combinatorial Theory
282:Kirchhoff's matrix tree theorem
557:
527:
501:
483:
455:
1:
448:
583:10.1016/0097-3165(90)90064-4
564:Takács, Lajos (March 1990).
167:. It states that for every
7:
10:
620:
332:in 1860, and proved via a
323:
140:{\displaystyle 4^{4-2}=16}
108:trees with 3 vertices and
18:
517:Quart. J. Pure Appl. Math
101:{\displaystyle 3^{3-2}=3}
62:{\displaystyle 2^{2-2}=1}
275:
19:Not to be confused with
244:{\displaystyle n^{n-2}}
330:Carl Wilhelm Borchardt
245:
208:
184:
148:
147:trees with 4 vertices.
141:
102:
69:tree with 2 vertices,
63:
535:Schützenberger, M. P.
246:
209:
185:
142:
103:
64:
29:
604:Trees (graph theory)
513:"A theorem on trees"
472:Proofs from THE BOOK
388:M. P. Schützenberger
222:
198:
174:
112:
73:
34:
479:. pp. 141–146.
467:Ziegler, Günter M.
241:
204:
180:
149:
137:
98:
59:
372:parking functions
352:vertices, namely
207:{\displaystyle n}
183:{\displaystyle n}
611:
588:
587:
585:
561:
555:
554:
531:
525:
524:
505:
499:
498:
491:Borchardt, C. W.
487:
481:
480:
459:
444:
385:
366:
359:
340:Other properties
294:Prüfer sequences
267:
250:
248:
247:
242:
240:
239:
213:
211:
210:
205:
190:, the number of
189:
187:
186:
181:
169:positive integer
157:Cayley's formula
146:
144:
143:
138:
130:
129:
107:
105:
104:
99:
91:
90:
68:
66:
65:
60:
52:
51:
21:Cayley's theorem
619:
618:
614:
613:
612:
610:
609:
608:
594:
593:
592:
591:
562:
558:
532:
528:
506:
502:
488:
484:
477:Springer-Verlag
460:
456:
451:
436:
424:
410:
396:
394:Generalizations
379:
361:
353:
342:
326:
314:double counting
298:bijective proof
278:
263:
229:
225:
223:
220:
219:
199:
196:
195:
175:
172:
171:
159:is a result in
119:
115:
113:
110:
109:
80:
76:
74:
71:
70:
41:
37:
35:
32:
31:
24:
17:
12:
11:
5:
617:
607:
606:
590:
589:
576:(2): 321–323.
556:
526:
500:
482:
463:Aigner, Martin
453:
452:
450:
447:
428:
415:vertices with
402:
395:
392:
341:
338:
325:
322:
277:
274:
260:complete graph
256:spanning trees
238:
235:
232:
228:
203:
179:
136:
133:
128:
125:
122:
118:
97:
94:
89:
86:
83:
79:
58:
55:
50:
47:
44:
40:
15:
9:
6:
4:
3:
2:
616:
605:
602:
601:
599:
584:
579:
575:
571:
567:
560:
552:
548:
544:
540:
536:
530:
522:
518:
514:
510:
504:
496:
492:
486:
478:
474:
473:
468:
464:
458:
454:
446:
443:
440:
435:
431:
427:
422:
418:
414:
409:
405:
401:
391:
389:
383:
378:cars is also
377:
373:
368:
364:
357:
351:
347:
337:
335:
331:
321:
319:
315:
312:. A proof by
311:
310:pseudoforests
307:
303:
299:
295:
291:
287:
283:
273:
271:
266:
261:
257:
252:
236:
233:
230:
226:
217:
201:
193:
177:
170:
166:
165:Arthur Cayley
162:
158:
154:
134:
131:
126:
123:
120:
116:
95:
92:
87:
84:
81:
77:
56:
53:
48:
45:
42:
38:
28:
22:
573:
569:
559:
542:
538:
529:
520:
516:
503:
494:
485:
471:
457:
441:
438:
433:
429:
425:
420:
416:
412:
407:
403:
399:
397:
381:
375:
369:
362:
355:
349:
343:
327:
305:
279:
253:
163:named after
161:graph theory
156:
150:
545:: 219–221.
334:determinant
302:André Joyal
286:determinant
153:mathematics
523:: 376–378.
509:Cayley, A.
449:References
390:in 1968.
234:−
124:−
85:−
46:−
598:Category
511:(1889).
469:(1998).
296:yield a
216:vertices
214:labeled
551:0218257
497:: 1–20.
346:forests
324:History
268:in the
265:A000272
549:
290:matrix
288:of a
276:Proof
258:of a
192:trees
384:+ 1)
358:+ 1)
270:OEIS
578:doi
365:+ 1
348:on
292:.
272:).
218:is
194:on
151:In
600::
574:53
572:.
568:.
547:MR
541:.
521:23
519:.
515:.
475:.
465:;
445:.
437:=
320:.
251:.
155:,
135:16
586:.
580::
553:.
543:4
442:n
439:k
434:k
432:,
430:n
426:T
421:k
417:k
413:n
408:k
406:,
404:n
400:T
382:n
380:(
376:n
363:n
356:n
354:(
350:n
306:n
237:2
231:n
227:n
202:n
178:n
132:=
127:2
121:4
117:4
96:3
93:=
88:2
82:3
78:3
57:1
54:=
49:2
43:2
39:2
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
