No.473

$a+b+ab = (a+1)(b+1)-1$ となる. これを $S$ の各要素に再帰的に適用すると, 選ぶ要素の順序によらず最後は $X = (s_1+1)(s_2+1) \cdots (s_N+1)-1$ に収束する.

よって $X+1$ を $N$ 個の $2$ 以上の数の積に分解する組み合わせの数を求める問題となる.

”$x$ を $n$ 個の $m$ 以上の数の積に分解する組み合わせの個数” を返す関数を作って中で再帰を回せばこのような組み合わせの数を求めることができる.