%I #15 Feb 26 2025 09:51:30

%S 1,1,10,420,43960,9347800,3513910400,2131249120000,1952028782704000,

%T 2568150610833808000,4666919676058159520000,

%U 11351087418588355518080000,36008099327884173922432000000,145785514242304854141480256000000,739598808823839440680777500928000000,4627885522642342503645368137231360000000

%N Number of labeled histories for rooted ternary trees with 2n+1 leaves if simultaneous trifurcations are allowed.

%C 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.

%H Emily H. Dickey and Noah A. Rosenberg, <a href="https://doi.org/10.1098/rstb.2023.0307">Labelled histories with multifurcation and simultaneity</a>, Phil. Trans. R. Soc. B 380 (2025), 20230307.

%F 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.

%e 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.

%p a:= proc(n) option remember; `if`(n=0, 1, add((2*n+1)!/

%p (i!*6^i*(2*n+1-3*i)!)*a(n-i), i=1..(2*n+1)/3))

%p end:

%p seq(a(n), n=0..15); # _Alois P. Heinz_, Feb 25 2025

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

%K nonn,new

%O 0,3

%A _Noah A Rosenberg_, Feb 25 2025