A381486 Number of labeled histories for rooted ternary trees with 2n+1 leaves if simultaneous trifurcations are allowed.
1, 1, 10, 420, 43960, 9347800, 3513910400, 2131249120000, 1952028782704000, 2568150610833808000, 4666919676058159520000, 11351087418588355518080000, 36008099327884173922432000000, 145785514242304854141480256000000, 739598808823839440680777500928000000, 4627885522642342503645368137231360000000
Offset: 0
Keywords
Examples
Consider 7 named players in a sport in which players compete 3 at a time (e.g. the television gameshow "Jeopardy!"). The number of ways a single-elimination tournament can be arranged, if simultaneous matches can take place, is a(3)=420. Three of these 420 are: (1) A, B, and C play; the winner plays against D and E; the winner plays against F and G. (2) D, E, and F play; the winner plays against A and B; the winner plays against C and G. (3) A, B, and C play simultaneous with D, E, and F; the winners of these matches play against G.
Links
- Emily H. Dickey and Noah A. Rosenberg, Labelled histories with multifurcation and simultaneity, Phil. Trans. R. Soc. B 380 (2025), 20230307.
Programs
-
Maple
a:= proc(n) option remember; `if`(n=0, 1, add((2*n+1)!/ (i!*6^i*(2*n+1-3*i)!)*a(n-i), i=1..(2*n+1)/3)) end: seq(a(n), n=0..15); # Alois P. Heinz, Feb 25 2025
Formula
a(n) = Y(2n+1), where Y(n) = Sum_{i=1..floor(n/3)} (n!/(i!*6^i*(n-3*i)!))*Y(n-2*i), with Y(1)=1.
Comments