# inclusion-exclusion principle working

We have $n$ non-negative integers $a_1, a_2, \dots, a_n$. We will call a sequence of indexes $i_1, i_2, \dots, i_k$ such that $1\le i_1 < i_2 < \dots< i_k\le n$ a group of size $k$.

How many groups exists such that

$$a_{i_1}\mathbin{\&} a_{i_2}\mathbin{\&}\ldots\mathbin{\&} a_{i_k} = 0\;,$$

where $1\le k\le n$.

Operation $x\mathbin{\&} y$ denotes bitwise AND operation of two numbers.

Approach:

Use inclusion-exclusion principle in this problem.

Let $f(x)$ be the count of numbers $i$ where $A_i\mathbin{\&}x = x$.

Let $g(x)$ be the number of $1$s in the binary respresentation of $x$. Then the answer is equal to

$$(-1)^{g(x)}\cdot 2^{f(x)}$$

But I could not understand the correctness and working intuition of this.

For calculating f(x) if Number are in range 0 to 10^6 so bit required to represent them is 20.

 for(int i=0;i<20;i++) {
for(int j=0;j<(1<<20);j++) {
if(0 == (j & (1<<i))) {
f[j | (1<<i)] += f[j];
}
}
}


0 1 2 3

• Since $A_i$ is undefined, in the definition of $f(x)$ should it be $a_k\mathbin{\&}x=x$ instead of $A_i\mathbin{\&}x=x$? The expression $(-1)^{g(x)}\cdot2^{f(x)}$ is meaningless until you tell us what $x$ is, and I suspect that you’ve left out a summation sign. Finally, by my count the correct answer for $0,1,2,3$ is $9$, not $10$: there are $2^3=8$ groups that include $0$, and the only other solution is $1\mathbin{\&}2=0$. – Brian M. Scott Jul 24 '15 at 9:45
• summation should be there my mistake !!!! But answer is 10 8 group with zero  one group with 1 and 2 and finally  1 and 2 and 3 – Sunny Jul 24 '15 at 9:56
• I haven’t quite figured out what’s going on. It would help if you could say what values of $x$ the summation is taken over. – Brian M. Scott Jul 24 '15 at 10:02