A380166 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, 1 <= k <= 2^n-1.

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

Offset: 1

Author

Noah A Rosenberg, Jan 13 2025

Keywords

• nonn
• tabf

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.

Examples

			Triangle begins:
  1;
  0, 1, 2;
  0, 0, 1, 22, 102,   160,     80;
  0, 0, 0,  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.
		

Links

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

Crossrefs

Row lengths give A000325(n).

Right border gives A056972(n).

Row sums give A379758(n).

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