login
A357812
Number of subsets of [n] in which exactly half of the elements are powers of 2.
5
1, 1, 1, 3, 4, 10, 20, 35, 70, 126, 210, 330, 495, 715, 1001, 1365, 4368, 6188, 8568, 11628, 15504, 20349, 26334, 33649, 42504, 53130, 65780, 80730, 98280, 118755, 142506, 169911, 906192, 1107568, 1344904, 1623160, 1947792, 2324784, 2760681, 3262623, 3838380
OFFSET
0,4
LINKS
FORMULA
a(n) = binomial(n,A029837(n+1)).
a(n) = binomial(n,A113473(n)) for n>0, a(0) = 1.
a(n) = Sum_{j>=0} binomial(A029837(n+1),j)*binomial(n-A029837(n+1),j).
EXAMPLE
a(6) = 20: {}, {1,3}, {1,5}, {1,6}, {2,3}, {2,5}, {2,6}, {3,4}, {4,5}, {4,6}, {1,2,3,5}, {1,2,3,6}, {1,2,5,6}, {1,3,4,5}, {1,3,4,6}, {1,4,5,6}, {2,3,4,5}, {2,3,4,6}, {2,4,5,6}, {1,2,3,4,5,6}.
MAPLE
a:= n-> binomial(n, max(0, 1+ilog[2](n))):
seq(a(n), n=0..40);
PROG
(Python)
from math import comb
def A357812(n): return comb(n, n.bit_length()) # Chai Wah Wu, Oct 14 2022
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Oct 13 2022
STATUS
approved