# Inclusion Exclusion Principle Applied to $\binom{n}k$

Derive an identity for $\binom{n}k$ via inclusion-exclusion by counting the $k$-multisets of $[n]$ in which each element of $[n]$ appears at most once. Use $P_i =$ "element $i$ appears more than once in the multiset" as the $i$-th property, for $1<i<n$.

Here's how I approached it:

Let the universe $U=$ all $k$-sized multisets of $n = \left(\!\left(n\atop k\right)\!\right)$. We want only those multisets where the property $P_i$ is not satisfied, so find $N_{=}(\varnothing)$.

I'm just not putting together how to ACTUALLY find/count this.

For each $i\in[n]$ the number of $k$-multisets with property $P_i$ is $\left(\!\left(n\atop{k-2}\right)\!\right)$: you set aside two $i$’s and choose a $(k-2)$-multiset from $[n]$. More generally, for any $S\subseteq[n]$ the number of multisets having $P_i$ for each $i\in S$ is $$\left(\!\!\left(n\atop{k-2|S|}\right)\!\!\right)\;.$$

Since $[n]$ has $\binom{n}m$ subsets of size $m$, the number of $k$-multisets with none of the properties is

$$\sum_{m\ge 0}(-1)^m\binom{n}m\left(\!\!\left(n\atop{k-2m}\right)\!\!\right)=\left(\!\!\left(n\atop k\right)\!\!\right)-n\left(\!\!\left(n\atop{k-2}\right)\!\!\right)+\binom{n}2\left(\!\!\left(n\atop{k-4}\right)\!\!\right)-+\ldots\;.\tag{1}$$

On the other hand, a $k$-multiset with none of the properties is just a $k$-subset, so $(1)$ is equal to $\binom{n}k$. Finally, we know that

$$\left(\!\!\left(n\atop k\right)\!\!\right)=\binom{n+k-1}k\;,$$

so

$$\binom{n}k=\sum_{m\ge 0}(-1)^m\binom{n}m\binom{n+k-2m-1}{k-2m}\;.$$

For example,

$$\binom42=\sum_{m\ge 0}(-1)^m\binom4m\binom{5-2m}{2-2m}=\binom40\binom52-\binom41\binom30=10-4=6\;.$$