A355519 - OEIS

%I #43 Sep 09 2022 22:35:54

%S 1,2,5,19,123,1457,32924,1452015,126487061,21898598245,7558601003617,

%T 5209629536999054,7175576970776253311,19758953061561609438197,

%U 108796404018098314291373545,1197986411771818785507163602609,26381385902615283298043180284145933

%N Number of valid brackets in an n-round tournament.

%C 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.

%D 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.]

%H Alois P. Heinz, <a href="/A355519/b355519.txt">Table of n, a(n) for n = 0..82</a>

%H John P. D'Angelo and Jiri Lebl, <a href="https://arxiv.org/abs/2208.09544">Integer Sequences and Output Arrays</a>, arXiv:2208.09544 [math.NT], 2022.

%H John P. D'Angelo, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL25/Dangelo/dan3.html">Counting Tournament Brackets</a>, J. Int. Seq., Vol. 25 (2022), Article 22.6.8.

%F 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

%e For n=1, we have a(n)=2, because the only 1-tuples are 0 and 1.

%e For n=2, we have a(2)=5, as the possible 2-tuples are (2,1), (2,0), (1,1), (1,0), (0,0).

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

%p b:= proc(n, i) option remember; `if`(n=0, 1,

%p       add(b(n-1, j), j=0..min(i, 2^(n-1))))

%p     end:

%p a:= n-> b(n, infinity):

%p seq(a(n), n=0..14);  # _Alois P. Heinz_, Jul 05 2022

%p # second Maple program:

%p a:= proc(n) option remember; `if`(n=0, 1, -add(a(j)

%p       *(-1)^(n-j)*binomial(1+ 2^j, n-j), j=0..n-1))

%p     end:

%p seq(a(n), n=0..23);  # _Alois P. Heinz_, Jul 08 2022

%o (Python)

%o from functools import cache

%o @cache

%o 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))

%o def a(n): return b(n, float('inf'))

%o print([a(n) for n in range(15)]) # _Michael S. Branicky_, Jul 05 2022 after _Alois P. Heinz_

%Y Cf. A000108, A107354.

%K nonn

%O 0,2

%A _John P. D'Angelo_, Jul 05 2022