1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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\;.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.