>>563
+ の個数は 最大で n-1個

+ の個数が k 個の時

n個の○
○○○…○○○
の間に + を挿入する方法は
nCk 通りだから

(nC1) + (nC2) + … + (nC(n-1))

これは
(1+p)^n - 1 -p^n
の第一項を二項定理で展開して p = 1としたもの。