$$\left(\!\!\binom{n}{k}\!\!\right)= \displaystyle\sum_{j=0}^k \binom{n}{j}\left(\!\!\binom{j}{k-j}\!\!\right)$$
Let $X$ be a set of $k$ element multi set of an n-element set.
Let $P$ be a set of $j$ element subset of an n-element set for $0 \leq j\leq k$.
Let $Q$ be a set of $k-j$ element multi set of a j-element set for $0 \leq j\leq k$.
Let $Y$ be a set of ordered pairs $(p, q), p\in P, q\in Q, |p| + |q| = k $
My idea is to define a function $f$ from $X$ to $Y$ that splits $x\in X$ into set $a$ and $b$ where $a$ contains the distinct element of $x$ and $b$ contains everything else. And the inverse $g$ will simply be the union of two given sets.
But I've noticed some problems when trying to do this.
e.g suppose you have $n = 5, k = 4, x = \left\{{1, 2, 1, 1}\right\}$.
Then $a = \left\{{1, 2}\right\}, b = \left\{{1, 1}\right\}$
But what if in the inverse function you are given $p = \left\{{2}\right\}, q = \left\{{1, 1, 1}\right\}$ Then both ordered pairs get mapped to the same things. I have also noticed that some $f(x)$ are not in $Y$. So I'm trying to find the way to map those "extra pairs" with it but I'm kinda stuck, so help pls?
The lefthand side counts the number of $k$-element multisets formed from an $n$-element set. I claim that each term of the righthand side counts the number of such multisets having exactly $j$ distinct elements. Summing $j$ from $1$ to $k$ gives the desired result. (The $j=0$ term evaluates to $0$ in the identity, so it could be omitted.)
As for my claim, let $j$ be fixed. Begin constructing the multiset by adding $j$ distinct elements in $\binom{n}{j}$ ways. Complete the multiset by multichoosing the remaining $k-j$ additional elements only from among the $j$ previously chosen, so that we are left with a multiset containing precisely $j$ distinct elements. The latter step can be completed in $\displaystyle\left(\!\!\binom{j}{k-j}\!\!\right)$ ways, giving $\displaystyle\binom{n}{j}\left(\!\!\binom{j}{k-j}\!\!\right)$ total multisets with exactly $j$ distinct elements.