A378855 Triangle read by rows: T(n,k) is the number of sequences in which the games of a single-elimination tournament with n teams can be played if arbitrarily many arenas are available, the tournament bracket is chosen to the bracket with the largest such number of sequences, and the number of distinct times at which games are played is k, log_2(n) <= k <= n-1.

1, 0, 1, 0, 1, 2, 0, 0, 2, 3, 0, 0, 2, 9, 8, 0, 0, 1, 12, 30, 20, 0, 0, 1, 22, 102, 160, 80, 0, 0, 0, 10, 114, 380, 485, 210, 0, 0, 0, 10, 198, 1100, 2495, 2478, 896, 0, 0, 0, 5, 204, 1930, 7260, 12810, 10640, 3360, 0, 0, 0, 5, 344, 4890, 27110, 72702

Offset: 2

Author

Noah A Rosenberg, Feb 10 2025

Keywords

• nonn
• tabl

Comments

T(n,k) is also the number of tie-permitting labeled histories for a labeled topology with n leaves and exactly k times at which events take place, when the labeled topology is chosen to be the labeled topology with the largest number of tie-permitting labeled histories across all labeled topologies with n leaves.

The first row has n=2. Terms for n=2 to 8 appear in Tables 2 and 3 of King & Rosenberg (2023); terms for n=9 to 16 are supplied by Emily H. Dickey.

Examples

			Triangle begins:
  1;
  0, 1;
  0, 1, 2;
  0, 0, 2,  3;
  0, 0, 2,  9,   8;
  0, 0, 1, 12,  30,    20;
  0, 0, 1, 22, 102,   160,     80;
  0, 0, 0, 10, 114,   380,    485,     210;
  0, 0, 0, 10, 198,  1100,   2495,    2478,      896;
  0, 0, 0,  5, 204,  1930,   7260,   12810,    10640,      3360;
  0, 0, 0,  5, 344,  4890,  27110,   72702,   101024,     70080,     19200;
  0, 0, 0,  2, 278,  6360,  53000,  211365,   451164,    529116,    321600,     79200;
		

Links

• Matthew C. King and Noah A. Rosenberg, A mathematical connection between single-elimination sports tournaments and evolutionary trees, Math. Mag. 96 (2023), 484-497.

Crossrefs

Row sums are A380767.

Cf. A380166 for the triangle if n is a power of 2.

Entries T(n,n-1) follow A056971.

Formula

The maximum is computed over unlabeled binary rooted trees T with n leaves (trees in the set enumerated by A001190) of the quantity computed for tree T in eq. 3 of King & Rosenberg (2023). This maximum gives the row sum, tabulated in A380767. For the tree that generates the maximum, the row entries are computed as the specific terms described in Theorem 3 of King & Rosenberg (2023) (and summed in eq. 3).