Exercise 2156Combinatorics › Inclusion-exclusionOlympiadAdded 3 Nov 2026

Exactly $k$ properties

#IE#exactly k#sieve

Statement

State the formula for the number of elements having exactly $k$ of $n$ properties.

Hint

Use higher-order IE with binomial weights.

Show solutionHide solution

Formula. Let $N_j=\sum_{|I|=j}|A_I|$ . Then the number of elements with exactly $k$ properties is
$E_k=\sum_{j=k}^n(-1)^{j-k}\binom{j}{k}N_j.$

Special cases. $E_0=\sum_j(-1)^jN_j$ (no property); $E_1=N_1-2N_2+3N_3-\cdots$ .

Conclusion. The exact-count sieve formula.