問題的描述：現在有N個一模一樣的蘋果，要放在編號為1、2、3……、N的盤子裡（假設盤子足夠大，能放下所有的蘋果），問一共有多少種放法？

算法分析：

用符號F（i，j）表示i個蘋果放在j個盤子裡的放法數

如果1號盤子裡沒有蘋果，則i個蘋果要放在剩余的j-1個盤子裡

如果1號盤裡有1個蘋果，則剩余的i-1個蘋果放在剩余的j-1個盤子裡

如果1號盤裡有2個蘋果，則剩余的i-2個蘋果放在剩余的j-1個盤子裡

以此類推

如果1號盤裡有i-1個蘋果，則剩下的1個蘋果放在j-1個盤子裡

如果1號盤裡有i個蘋果，則剩下的j-1個盤子裡沒有蘋果

於是得到以下的關系式

① F（i，j）=F（i，j-1）+F（i-1，j-1）+F（i-2，j-1）+……+F（1，j-1）+F（0，j-1）

由上面的式子可以得出

② F（i-1，j）=F（i-1，j-1）+F（i-2，j-1）+……+F（1，j-1）+F（0，j-1）

回代到①可知

③ F（i，j）=F（i，j-1）+F（i-1，j）

另由定義可知，

④ F（i，1）=1

⑤ F（1，i）=i

根據式子③④⑤，推測F（i，j）的計算公式為

⑥ F（i，j）=C（i，i+j-1） 注：C（M，N）表示組合數，表示N個裡面選M的個數。組合數的計算公式這裡不描述了

下面用數學歸納法證明式子⑥的正確性

證明：

F（i，1）=C（i，i+1-1）=C（i，i）=1 式子④滿足式子⑥

F（1，i）=C（1，1+i-1）=C（1，i）=i 式子⑤滿足式子⑥

假設F（i，j-1）、F（i-1，j）滿足式子⑥

F（i，j-1）=C（i，i+j-1-1）=C（i，i+j-2）

F（i-1，j）=C（i-1，i-1+j-1）=C（i-1，i+j-2）

則由式子③可知

F（i，j）=F（i，j-1）+F（i-1，j）=C（i，i+j-2）+C（i-1，i+j-2）=C（i，i+j-1） 滿足式子⑥

由此證明式子⑥的正確性

故計算公式為

F（i，j）=C（i，i+j-1）

那麼

3個蘋果放在3個盤子裡的放法數為F（3，3）=C（3，3+3-1）=C（3，5）=10

2個蘋果放在4個盤子裡的放法數為F（2，4）=C（2，2+4-1）=C（2，5）=10

7個蘋果放在7個盤子裡的放法數為F（7，7）=C（7，7+7-1）=C（7，13）=1716

10個蘋果放在10個盤子裡的放法數為F（10，10）=C（10，10+10-1）=C（10，19）=92378

N個蘋果放在N個盤子裡的放法數為F（N，N）=C（N，2N-1）