将第 2 步中按第二个 111 的位置 k+1k+1k+1 得到的计数求和，长度为 (n+1)(n+1)(n+1) 且含有 r+1r+1r+1 个数字 1 的每个字符串都会恰好被计数一次，因此总数为 (n+1r+1)\binom{n+1}{r+1}(r+1n+1)。另一方面，逐项看这个和，由于 (k1)=k\binom{k}{1}=k(1k)=k，它正是第 1 步中的 ∑kk(n−kr−1)\sum_k k\binom{n-k}{r-1}∑kk(r−1n−k)。