A380166 Irregular triangle read by rows: T(n,k) is the number of sequences in which the games of a fully symmetric single-elimination tournament with 2^n teams can be played if arbitrarily many arenas are available and the number of distinct times at which games are played is k, n <= k <= 2^n-1.

1, 1, 2, 1, 22, 102, 160, 80, 1, 672, 45914, 973300, 9396760, 49410424, 155188488, 304369008, 376231680, 284951040, 120806400, 21964800, 1, 458324, 2493351562, 1695612148252, 328854102958150, 26894789756402464, 1153061834890296576, 29635726970329429536

Offset

1,3

Comments

T(n,k) is also the number of tie-permitting labeled histories for a fully symmetric labeled topology with 2^n leaves and exactly k times at which events take place.

Links

Table of n, a(n) for n=1..28.

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

Formula

T(1,1) = 1 and for n > 1 and n <= k <= 2^n - 1, T(n,k) = Sum_{c=max(n-1,k-2^(n-1))..min(2^(n-1)-1,k-1)) Sum_{d=max(n-1,k-c-1)..min(2^(n-1)-1,k-1) ((k-1)! / ((k-1-d)! * (k-1-c)! * (c+d-(k-1))!)) * T(n-1,c) * T(n-1,d).

Example

Triangle begins:
  1;
  1,   2;
  1,  22,   102,    160,      80;
  1, 672, 45914, 973300, 9396760, 49410424, 155188488, 304369008, 376231680, 284951040, 120806400, 21964800;
  ...
For n = 2 and a tournament with 2^2 = 4 teams and structure ((A,B),(C,D)), game (A,B) can be played before or after game (C,D); the championship game occurs later, producing T(2,3) = 2. Alternatively, game (A,B) can be played simultaneously with (C,D), with the championship game occurring later, producing T(2,2) = 1.

Crossrefs

Row lengths give A000325(n).

Right border gives A056972(n).

Row sums give A379758(n).

Sequence in context: A330354 A200859 A127607 * A255861 A059360 A368016

Adjacent sequences: A380163 A380164 A380165 * A380169 A380170 A380171

Keyword

nonn,tabf

Author

Noah A Rosenberg, Jan 13 2025

Status

approved