A355519 Number of valid brackets in an n-round tournament.

1, 2, 5, 19, 123, 1457, 32924, 1452015, 126487061, 21898598245, 7558601003617, 5209629536999054, 7175576970776253311, 19758953061561609438197, 108796404018098314291373545, 1197986411771818785507163602609, 26381385902615283298043180284145933

Offset: 0

Author

John P. D'Angelo, Jul 05 2022

Keywords

• nonn

Comments

a(n) is the number of nonnegative n-tuples (x_1, ..., x_n) satisfying the inequalities x_1 <= 2^(n-1) and x_{j+1} <= min(x_j, 2^(n-j-1)) for all j.

Examples

			For n=1, we have a(n)=2, because the only 1-tuples are 0 and 1.
For n=2, we have a(2)=5, as the possible 2-tuples are (2,1), (2,0), (1,1), (1,0), (0,0).
For n=3, there are 19 possibilities: (4,2,1), (4,2,0), (4,1,1), (4,1,0), (4,0,0), (3,2,1), (3,2,0), (3,1,1), (3,1,0), (3,0,0), (2,2,1), (2,2,0), (2,1,1), (2,1,0), (2,0,0), (1,1,0), (1,0,0), (0,0,0).
		

References

• John P. D'Angelo, Counting Bracket Tournaments, to appear in Journal of Integer Sequences. [The first 26 terms appear there together with a method for computing them.]

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..82
• John P. D'Angelo and Jiri Lebl, Integer Sequences and Output Arrays, arXiv:2208.09544 [math.NT], 2022.
• John P. D'Angelo, Counting Tournament Brackets, J. Int. Seq., Vol. 25 (2022), Article 22.6.8.

Crossrefs

Cf. A000108, A107354.

Programs

Maple

b:= proc(n, i) option remember; `if`(n=0, 1,
      add(b(n-1, j), j=0..min(i, 2^(n-1))))
    end:
a:= n-> b(n, infinity):
seq(a(n), n=0..14);  # Alois P. Heinz, Jul 05 2022
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1, -add(a(j)
      *(-1)^(n-j)*binomial(1+ 2^j, n-j), j=0..n-1))
    end:
seq(a(n), n=0..23);  # Alois P. Heinz, Jul 08 2022

Mathematica

a[n_] := a[n] = If[n == 0, 1, -Sum[a[j]*(-1)^(n-j)*Binomial[1+2^j, n-j], {j, 0, n-1}]];
Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Jul 01 2025, after Alois P. Heinz *)

Python

from functools import cache
@cache
def b(n, i): return 1 if n==0 else sum(b(n-1, j) for j in range(min(i, 2**(n-1))+1))
def a(n): return b(n, float('inf'))
print([a(n) for n in range(15)]) # Michael S. Branicky, Jul 05 2022 after Alois P. Heinz

Formula

a(n) = Sum_{j=0..n-1} a(j)*(-1)^(n-j+1)*binomial(2^j+1,n-j) with a(0) = 1. - Alois P. Heinz, Jul 08 2022