請教Partition的數學問題

Question

Let f(n,k) represent the number of partition of a set S with n elements into k cell ( k = 1 ,2 ,... ,n )
Find a recursion formula for f(n,k)


可以的話請詳述過程
謝謝

Answer 1

1. 假設每個cell不一定放元素進去
總共有k個cell, n個元素放進k個cell, 可分為兩類
(1)第一個cell沒有元素, 則n個元素放進k-1個cell=> f(n, k-1)
(2)第一個cell有元素,則另k-1個cell的元素和<= n-1個
即x2+x3+...+xk-1 <= n-1
=>x2+x3+...+xk-1+U = n-1 (其中U表承接 x2+x3+...+xk-1與n-1之差額)
則k個cell分配n-1個元素=>f(n-1,k)
故 f(n,k) = f(n,k-1) + f(n-1,k)
初值條件: f(n, 1)=1, f(1, n)=n
註: f(n,k)=C(n+k-1, n)
2. 假設k個cell都要有元素, 則將上小題求出之f(n,k)公式之n改為n-k即可(因每個cell先分配一個元素, 剩n-k個,再分配至k個cell)
Ans: C(n-1, n-k)