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,6

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.

Links

Table of n, a(n) for n=2..64.

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

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).

Example

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;

Crossrefs

Row sums are A380767.

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

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

Sequence in context: A091008 A111006 A046742 * A263138 A274637 A178516

Adjacent sequences: A378852 A378853 A378854 * A378856 A378857 A378858

Keyword

nonn,tabl,new

Author

Noah A Rosenberg, Feb 10 2025

Status

approved