空室なしで６人を５部屋に割り当てる方法は何通りあるか？
# choose(n,r)は nＣrのこと

# how many ways of allocating 5 rooms to 6 people without vacancy?

# allocated to 1 room (4 vacant)
a1=choose(5,1)*1^6 # 5

# allocated to 2 rooms (3 vacant)
a2=choose(5,2)*(2^6-2) # 620

# allocated to 3 rooms (2 vacant)
a3=choose(5,3)*( 3^6-choose(3,2)*(2^6-2)-3 ) # 5400

# allocated to 4 rooms (1 vacant)
a4=choose(5,4)*( 4^6 - choose(4,3)*(3^6-choose(3,2)*(2^6-2)-3) - choose(4,2)*(2^6-2)-4 ) # 7800

5^6 - a1 - a2 - a3 - a4 # 15625-5-620-5400-7800 = 1800

で解けるには解けたけど、漸化式で解くとかエレガントな方法ってないだろうか？