\(n \geq 3\) なので途中寄り道をしてたどり着くこともできるので, ちょうど \(k\) 回というのは各部屋の人は \(1\) 回のみの移動で, 合計で \(k\) 回以下の移動を行うということにしても題意は変わらない. このとき, 部屋 \(i\) の人が移動するとして, 移動先を \(j\) とすると部屋 \(j\) の人は移動しても意味がない. 部屋 \(i\) の人が直接部屋 \(j\) の人が移動する先に行けばいいだけである.

移動回数を \(i \ (i \leq k)\) とすると, 移動する人の組み合わせは \(\combi{n}{i}\) である. 移動先の組み合わせは \(n-i\) 個の部屋に \(i\) 人を割り当てる組み合わせの数なので, \(\combi{n-1}{i}\) となる. 当然ながら \(i \geq n\) については考えなくてもいい.

よって答えは

\[\sum_{i=0}^{\min \{k, n-1\}} \combi{n}{i} \times \combi{n-1}{i}\]

となる. ただし, \(k=1\) のときは \(0\) 回移動ができないので \(\sum\) の下は \(i=1\) となる.