OFFSET
0,2
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.
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.
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
EXAMPLE
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).
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
PROG
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
John P. D'Angelo, Jul 05 2022
STATUS
approved