素朴な式変形のみで結論を導出します．まず，以下の式を証明します．

• 式 $A$: $\sum_i \ {}_{n}\mathrm{C}_{i} \ x^i = (1 + x)^n$
• 式 $B$: $\sum_i \ i \ {}_{n}\mathrm{C}_{i} \ x^{i - 1} = n (1 + x)^{n - 1}$

式 $A$ については，右辺の展開を考えれば成立します．式 $A$ の両辺を $x$ で微分することで，式 $B$ の成立も示されます．

元の問題について考えます．あるカードの集合について，その集合のように取るために可能な限り早く取るようにします．すなわち，各操作では集合にあるカードについて，番号の小さい順に見ていって取れるなら取るということです．
$i$ 回目の操作で選んだカードの枚数を $V_i$ とします．ここで，$V_i$ は(広義)単調減少として構いません．もしそうでないなら，$V_i < V_{i + 1}$ なる $i$ が存在します．このとき，$i$ 回目の操作によって $i + 1$ 回目の操作で新たに選ぶことができるようになったカードは $V_i$ 枚のため，$i + 1$ 回目の操作で選んだカードのうち，$i$ 回目の操作で選ぶことのできたカードが存在します．よって上の戦略に反します．

上の議論より $i$ 回目の操作で取ることのできるカードは $i$ 回目の操作で新たに選ぶことができるようになった $V_{i - 1}$ 種類に限られます．
よって，答えとなる式は $\sum_{V} \left( V_1 + V_2 + \ldots + V_M \right) {}_{K}\mathrm{C}_{V_1} {}_{V_1}\mathrm{C}_{V_2} \ldots {}_{V_{M - 1}}\mathrm{C}_{V_M}$ です．ここで，$V$ は $K \geq V_1 \geq V_2 \geq \ldots \geq V_M \geq 0$ を動きます．
結論としては，これは $\frac{KM \left( 1 + M \right)^{K}}{2}$ となります．$M$ についての帰納法で示します．

$M = 1$ のときを考えます．これは $\sum_{V_1} V_1 \ {}_{K}\mathrm{C}_{V_1}$ です．式 $B$ よりこれは $2^{K - 1} \ K$ となり，上と一致することが示せます．

$M -1$ で成立するとして，$M$ の場合を考えます．この式を $\sum_{V} V_1 \ {}_{K}\mathrm{C}_{V_1} {}_{V_1}\mathrm{C}_{V_2} \ldots {}_{V_{M - 1}}\mathrm{C}_{V_M}$ と $\sum_{V} \left( V_2 + \ldots + V_M \right) {}_{K}\mathrm{C}_{V_1} {}_{V_1}\mathrm{C}_{V_2} \ldots {}_{V_{M - 1}}\mathrm{C}_{V_M}$ の和と捉えます．

$1$ つめの式について，$\sum_{V_1} \left( V_1 \ {}_{K}\mathrm{C}_{V_1} \sum_{V_2, V_3, \ldots, V_M} \left( {}_{V_1}\mathrm{C}_{V_2} \ldots {}_{V_{M - 1}}\mathrm{C}_{V_M} \right) \right)$ と書き直します．ここで，$\sum_{V_2, V_3, \ldots, V_M} \left( {}_{V_1}\mathrm{C}_{V_2} \ldots {}_{V_{M - 1}}\mathrm{C}_{V_M} \right) = M^{V_1}$ となります．
これは式 $A$ を繰り返し用いてもいいですし，$V$ の単調性に基づいて，$M$ 個のものに色 $1$ から色 $V_1$ のいずれかを選択するといった組み合わせ的解釈を用いても示せます．これと式 $B$ より全体では $\sum_{V_1} V_1 \ {}_{K}\mathrm{C}_{V_1} \ M^{V_1} = KM (1 + M)^{K - 1}$ を得ます．

$2$ つめの式について，$\sum_{V_1} \left( {}_{K}\mathrm{C}_{V_1} \sum_{V_2, V_3, \ldots, V_M} \left( \left( V_2 + V_3 + \ldots + V_M \right) {}_{V_1}\mathrm{C}_{V_2} \ldots {}_{V_{M - 1}}\mathrm{C}_{V_M} \right) \right)$ と書き直します．ここで，$\sum_{V_2, V_3, \ldots, V_M} \left( \left( V_2 + V_3 + \ldots + V_M \right) {}_{V_1}\mathrm{C}_{V_2} \ldots {}_{V_{M - 1}}\mathrm{C}_{V_M} \right) = \frac{V_1 \left(M - 1\right) M^{V_1}}{2}$ となります．
これは $M - 1$ で成立していることより示せます．これと式 $B$ より全体では $\frac{M-1}{2} \sum_{V_1} V_1 \ {}_{K}\mathrm{C}_{V_1} \ M^{V_1} = \frac{M - 1}{2} \left( KM (1 + M)^{K - 1} \right)$ を得ます．

これより全体では \(\left( 1 + \frac{M - 1}{2} \right) \left( KM (1 + M)^{K - 1} \right) = \frac{KM (1 + M)^K}{2}\) となり，示されました．