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

Author

Noah A Rosenberg, Feb 25 2025

Keywords

• nonn

Comments

a(n) is also the number of single-elimination sports tournament schedules possible for 2n+1 teams if matches involve three teams, arbitrarily many arenas are available, and labeled teams have been specified, but the bracket of matches has not been specified.

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.

Crossrefs

Cf. A317059 for binary rather than ternary trees, A339411 if simultaneity is disallowed.

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.