相同元素分配到相同空间问题(放鸡蛋问题)详解(Detailed explanation of the problem of assigning the same elements to the same space (egg laying problem))

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

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

“`cpp/***Filename:heli*Author:wan*Date:2022.1.14*version:1.3*Description:heli*/#include <bits/stdc++.h>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

————————

In high school, the arrangement and combination problem we came across was to put the same elements in different spaces, which was easy to find** So what if the same elements are allocated to the same space** I checked it on the Internet, but I didn’t explain it in detail, so I deduced it according to the existing data, and corrected the errors in some of the existing data here. Next, I will take the * * put eggs * * problem as an example. There are ` n ‘eggs and ` m’ baskets. Ask: * put n eggs in M baskets and * * allow * * to have empty baskets. How many methods* Put n eggs into m baskets, and * * is not allowed * * to have empty baskets. How many methods are there* PS: 1, 1, 5 when n = 7 and M = 3; 1,5,1; 5, 1 and 1 are considered to be the same division*

Set ` f (m, n) `: give n eggs to m baskets, and the basket can be empty set ` t (m, n) `: give n eggs to m baskets, and the basket can not be empty ## right question 2: put n eggs into m baskets, and empty baskets are not allowed. How many methods? *` M = n `: it is obvious when the number of baskets = the number of eggs. At this time, only one egg can be placed in one basket. So there’s only one way. *` m > N `: number of Baskets & gt; It is impossible to count eggs. *` m < N `: number of Baskets & lt; When counting eggs, you can first put an egg in’m ‘baskets. At this time, you meet the meaning of the question. No basket is empty. The remaining eggs are ‘N-M’ and then divided into’m ‘baskets. At this time, it is allowed that there are baskets without eggs. That is ` t (m, n) = f (m, n-m) `* At this point, it turns into the problem of putting ‘N-M’ eggs into’m ‘baskets and allowing empty baskets*

##For question 1: how many methods are there to put n eggs into m baskets and allow empty baskets? Number of methods = all baskets are not empty + 1 basket + 2 baskets ++ Empty m – 1 basket, that is ` ` f (m, n) = t (m, n) + T (m-1, n) + T (m-2, n) ++ T (1, n) `, according to the above analysis of problem 2, we know that: t (m, n) = f (m, n-m), then the above formula becomes: ` ` f (m, n) = f (m, n-m) + F (m-1, n) ` ` This is the * * recursive * * prototype we will use later. For recursion, we should consider its * * termination condition * *: * when m = 1, that is, the number of baskets = 1, no matter how many eggs can only be put into this basket, so 1 is returned* When n = 0, that is, the number of eggs = 0, no matter how many baskets there are, there are no eggs to put, so it returns 0* When n & lt; M is the number of eggs & lt; When the number of baskets, there must be n – M empty baskets, so we make m = n;

**But at this time, the recursive formula we get is not what we finally need * *. Here I take F (2,2) as an example: ` f (2,2) ‘refers to putting two eggs into two baskets and allowing empty baskets. If we think about it carefully, we can actually figure out that there are only two allocation methods: 1,1 and 2,0. But at this time, if we use the above formula to calculate, we can get that: ` f (2,2) = f (2,0) + F (1,2) = 1 ‘is inconsistent with the real answer. After careful observation of the formula, we can see the reason: * * when m = n, the formula directly using the change does not consider the situation of putting one egg in one basket * *, so we need to supplement the * * termination condition * * on the basis of the formula obtained above: * when n = m, Let ` number of allocation methods + = 1 ‘.

##Taking the division of numbers as an example, I use C + + to solve the division of numbers with the above ideas: the problem description divides the integer n into k parts, and each part cannot be empty. How many different divisions are there. When n = 7 and K = 3, the following three methods are considered to be the same: 1,1,5; 1,5,1; 5,1,1

Enter two numbers n, K in one line.

The output format is an integer per line, that is, different division numbers. input data

“`7 3 ` ` output data ` ` 4 ` ` four classification methods are: 1,1,5; 1,2,4; 1,3,3; 2,2,3。

Idea: Here I regard number as an egg and division as a basket.

“`cpp/***Filename:heli*Author:wan*Date:2022.1.14*version:1.3*Description:heli*/#include < bits/stdc++. h> using namespace std; int number;// Number of allocation methods int give_ Space (int m, int n) {/ / basket is m, egg is n, int sum = 0; if (M = = n) {sum + = 1; / / printf (“sum:% d \ n”, sum);} If (n = = 0) {/ / egg = 0 return 0;} If (M = = 1|m = = 0) {/ / basket = 0 / 1 return 1;} If (n & lt; m) {/ / number of eggs & lt; number of baskets, basket = egg, M = n; / / judgment here is very important, otherwise 1 return give_space (m, n) will be lost during calculation;}// 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, basket, n is egg number + = give_space (k, N – K);} printf(“%d”,number); return 0; }“`* PS: in the termination condition, when n & lt; M is the number of eggs & lt; When counting the baskets, we should remember to re pass this m and N after making M = n, otherwise we will less consider putting one egg in each basket*

Finally: Based on personal understanding, there may be errors in this paper. If there are errors, please point out them and I will modify them as soon as possible. Hope to help you: D