No.140

まず, $x$ 組の夫婦が夫婦は別の車に分かれないとして $y$ グループに分かれる組み合わせ $S(x, y)$ を考える. これは第2種スターリング数であり, パスカルの三角形と似た形で計算できる.

続いて, $i$ 組の夫婦のうち, $j$ 組の夫婦が夫婦同乗し, 残りが夫婦別々の車に乗る形で $k$ グループに分かれる組み合わせの数 $C(i, j, k)$ は,

$$C(i, j, k) = {}_iC_j \cdot S(j, k) \cdot (k(k-1))^{i-j}$$

となる.あとは

$$\sum_{\substack{k \leq j \leq N \\ 1 \leq k \leq N}} C(N, j, k)$$

を計算すればいい. ${}_nC_r$ の計算にはパスカルの三角形を使う.