cp's OEIS Frontend

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

%I A355519 #48 Jul 01 2025 08:48:46
%S A355519 1,2,5,19,123,1457,32924,1452015,126487061,21898598245,7558601003617,
%T A355519 5209629536999054,7175576970776253311,19758953061561609438197,
%U A355519 108796404018098314291373545,1197986411771818785507163602609,26381385902615283298043180284145933
%N A355519 Number of valid brackets in an n-round tournament.
%C A355519 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 A355519 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 A355519 Alois P. Heinz, <a href="/A355519/b355519.txt">Table of n, a(n) for n = 0..82</a>
%H A355519 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 A355519 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 A355519 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 A355519 For n=1, we have a(n)=2, because the only 1-tuples are 0 and 1.
%e A355519 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 A355519 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 A355519 b:= proc(n, i) option remember; `if`(n=0, 1,
%p A355519       add(b(n-1, j), j=0..min(i, 2^(n-1))))
%p A355519     end:
%p A355519 a:= n-> b(n, infinity):
%p A355519 seq(a(n), n=0..14);  # _Alois P. Heinz_, Jul 05 2022
%p A355519 # second Maple program:
%p A355519 a:= proc(n) option remember; `if`(n=0, 1, -add(a(j)
%p A355519       *(-1)^(n-j)*binomial(1+ 2^j, n-j), j=0..n-1))
%p A355519     end:
%p A355519 seq(a(n), n=0..23);  # _Alois P. Heinz_, Jul 08 2022
%t A355519 a[n_] := a[n] = If[n == 0, 1, -Sum[a[j]*(-1)^(n-j)*Binomial[1+2^j, n-j], {j, 0, n-1}]];
%t A355519 Table[a[n], {n, 0, 23}] (* _Jean-François Alcover_, Jul 01 2025, after _Alois P. Heinz_ *)
%o A355519 (Python)
%o A355519 from functools import cache
%o A355519 @cache
%o A355519 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 A355519 def a(n): return b(n, float('inf'))
%o A355519 print([a(n) for n in range(15)]) # _Michael S. Branicky_, Jul 05 2022 after _Alois P. Heinz_
%Y A355519 Cf. A000108, A107354.
%K A355519 nonn
%O A355519 0,2
%A A355519 _John P. D'Angelo_, Jul 05 2022