相同元素分配到相同空间问题（放鸡蛋问题）详解

在高中的时候，我们接触到的排列组合问题是将相同元素放到不同空间，这个很好求。
那么相同元素分配到相同空间怎么办呢？
我在网上大概查了一下，但是也没有解释的很详细的，所以就根据已有的进行了推导，并对已有的部分资料中的错误也在此进行了更正。
接下来我将以放鸡蛋问题作为例子
设有n个鸡蛋，m个篮子，问：

• 将n个鸡蛋放到m个篮子里，允许有空篮子，有几种方法？
• 将n个鸡蛋放到m个篮子里，且不允许有空篮子，有几种方法?
  ps:n = 7,m = 3时，1，1，5；1，5，1；5，1，1被认为是同一种分法

设F(m,n)：将n个鸡蛋给m个篮子，且篮子可以为空
设T(m,n)：将n个鸡蛋给m个篮子，且篮子不可以为空

对问题2：将n个鸡蛋放到m个篮子里，且不允许有空篮子，有几种方法?

• m = n:篮子数 = 鸡蛋数时
  很明显，此时只能一个篮子里放一个鸡蛋。所以只有一种方法。
• m > n:篮子数 > 鸡蛋数时
  不可能。
• m < n:篮子数 < 鸡蛋数时
  可以先给m个篮子里装入一个鸡蛋，此时就满足了题意，没有篮子是空的。
  剩余的鸡蛋为n-m个再分到m个篮子中，此时允许有篮子分不到鸡蛋。即T(m,n) = F(m,n-m)。
  此时就转化为将n-m个鸡蛋装入m个篮子里，且允许有空篮子的问题了。

对于问题1：将n个鸡蛋放到m个篮子里，允许有空篮子，有几种方法？

方法数 = 所有篮子都不空 + 空1个篮子 + 空2个篮子 + ... +空m -1个篮子
即F(m,n) = T(m,n) + T(m-1,n) + T(m-2,n) + ... + T(1,n)，根据上面对问题2的分析我们可知：T(m,n) = F(m,n-m)，则上式变为：
F(m,n) = F(m,n-m) + F(m-1,n)这也就是我们后边要用到的递归原型。
对于递归来说，我们要考虑好它的终止条件：

• 当 m = 1即篮子数 = 1时，无论有多少的鸡蛋都只能放进这个篮子里，所以返回1；
• 当 n = 0即鸡蛋数 = 0时，无论有多少篮子，也没有鸡蛋可以放，所以返回0；
• 当 n < m 即鸡蛋数 <篮子数时，肯定会有n - m个空篮子，所以我们令m = n；

但此时我们得到的递归式还并不是我们最终需要的，在此我以F(2,2)作为例子：
F(2,2)指将两个鸡蛋放入两个篮子中，且允许有空篮子。那我们仔细想一想其实就能想出来，只有两种分配方法：1,1和2，0。
但此时若我们用上述得到的式子进行计算可得：F(2,2) = F(2,0) + F(1,2) = 1与真实答案不符，仔细观察该式，可知原因：当 m = n时，直接利用变化来的式子未考虑一个篮子放一个鸡蛋的情况，所以还要在上面得到的式子的基础上，对终止条件进行补充：

• 当 n = m时，令分配方法数 += 1。

以数的划分为例题

我用c++以上述思路来解决数的划分：
题目描述
将整数 n 分成 k 份，且每份不能为空，问有多少种不同的分法。当 n=7, k=3 时，下面三种分法被认为是相同的：1,1,5; 1,5,1; 5,1,1

输入格式
一行两个数 n, k。

输出格式
一行一个整数，即不同的分法数。
输入数据

7 3

输出数据

4

四种分法为：1,1,5；1,2,4；1,3,3；2,2,3。

思路：在这里我把数看作鸡蛋，分法看作篮子。

/**
*Filename:heli
*Author:wan
*Date:2022.1.14
*version:1.3
*Description:heli
*/
#include 
using namespace std;
int number;//分配方法数
int give_space(int m,int n){
//篮子是m,鸡蛋是n
int sum = 0;
if(m ==n){
sum += 1;
// printf("sum:%d\n",sum);
}
if(n == 0){//蛋 = 0
return 0;
}
if(m == 1||m == 0){//篮子 = 0/1
return 1;
}
if(n < m){//鸡蛋数<篮子数时，篮子 = 鸡蛋
m = n;
//此处判断很重要，否则计算时会少1
return give_space(m,n);
}
//printf("%d %d\n",m,n);
sum += give_space(m,n-m);
sum += give_space(m-1,n);
return sum;
}
int main(){
int n,k;
scanf("%d %d",&n,&k);
if(n <= k){
number = 1;
}
else{
//k = m,篮子，n是鸡蛋
number += give_space(k,n - k);
}
printf("%d",number);
return 0;
}

ps:在终止条件中，当 n < m 即鸡蛋数 <篮子数时，我们令m = n后记得把这个m,n重新传进去，否则会少考虑将每个篮子里放一个鸡蛋的情况。

最后的最后：本文基于个人理解，可能存在错误的地方，如有错误请各位大佬指出，我会尽快进行修改。
希望有帮到你呀:D