A357812 Number of subsets of [n] in which exactly half of the elements are powers of 2.

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

Author

Alois P. Heinz, Oct 13 2022

Keywords

• nonn

Examples

			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}.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..10000

Crossrefs

Cf. A000079, A029837, A037031, A102366, A113473, A180272, A357927.

Programs

Maple

a:= n-> binomial(n, max(0, 1+ilog[2](n))):
seq(a(n), n=0..40);

Python

from math import comb
def A357812(n): return comb(n,n.bit_length()) # Chai Wah Wu, Oct 14 2022

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