题的描述：现在有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）
本文转自万仓一黍博客园博客，原文链接：http://www.cnblogs.com/grenet/archive/2012/11/19/2777200.html，如需转载请自行联系原作者
