Question

我尝试这样做：

9 ！ -5 \times 4 \times 3 \times 7 ！ ​ 4 ！ \times 2 ！ \times 3 ！

\frac{9!-5\times 4 \times 3 \times 7!}{4!\times 2!\times 3!}

得到 210

不过我编写了一个 Python 程序来验证我的答案：

import itertools
def count_ways_pigeonhole(red_balls, black_balls, boxes, max_balls_per_box):
    exists = set()
    def find_combinations(red_balls, black_balls,block):
        base = ['red' for _ in range(red_balls)] + ['black' for _ in range(black_balls)] + block
        combs = itertools.permutations(base, len(base))
        for comb in combs:
            exists.add(tuple(comb))
    find_combinations(red_balls, black_balls,['block' for _ in range(boxes - 1)])
    #validate
    validate_combinations = []
    for comb in exists:
        s = ' '.join(comb)
        s = s.split('block')
        s = [i.strip().split(' ') for i in s]
        for i in s:
            if len(i) > max_balls_per_box:
                break
        else:
            validate_combinations.append(comb)
    
    for i in range(len(validate_combinations)):
        for j in validate_combinations[:i] + validate_combinations[i+1:]:
            if validate_combinations[i] == j:
                print('error')
    for i in validate_combinations[:20]:
        print(i)
    return len(validate_combinations)


red_balls = 2
black_balls = 3 
boxes = 5
max_balls_per_box = 2



print(count_ways_pigeonhole(red_balls, black_balls, boxes, max_balls_per_box))

并得到 510。我不知道如何验证我的答案。

Answer 1

首先假设两个红球都进入同一个盒子。 $5$ 5盒子的可能选择。分配黑球的方法数就是 $x_{1} + x_{2} + x_{3} + x_{4} = 3$ x_1+x_2+x_3+x_4=3，但受以下约束 $\forall i (x_{i} \leq 2)$ \forall i~(x_i \leq 2)星条旗告诉我们 $(\binom{6}{3}) = 20$ \binom 63=20该方程的无约束解，其中 $4$ 4禁止这样做，因为他们把三个黑球都放在同一个盒子里。因此， $16$ 16考虑到红球的情况，允许分配黑球的方式。这解释了 $5 \cdot 16 = 80$ 5 \cdot 16=80組合。

现在假设红球在两个不同的盒子里。这些盒子可以在 $(\binom{5}{2}) = 10$ \binom 52=10方式。

如果两个盒子里都有一个黑球，那么 $3$ 3将剩下的黑球放入盒子的方法。

如果其中一个装有红球的盒子里也装有一个黑球，则有 $2$ 2选择该框的方法。剩余黑球的分布是 $x_{1} + x_{2} + x_{3} = 2,$ x_1+x_2+x_3=2,即 $(\binom{4}{2}) = 6.$ \binom 42=6.

如果既没有红球也没有黑球，那么黑球的分布就是 $x_{1} + x_{2} + x_{3} = 3$ x_1+x_2+x_3=3，但受以下约束 $\forall i (x_{i} \leq 2) .$ \forall i~(x_i \leq 2). 有 $(\binom{5}{2}) = 10$ \binom 52=10该方程的无约束解，其中 $3$ 3是被禁止的，因为他们把三个黑球都放在一个盒子里。因此， $7$ 7允许该方程的解。

因此，我们有 $10 (3 + 2 \cdot 6 + 7) = 220$ 10(3+2 \cdot 6+7)=220两个不同盒子中的红球的可能分布。将其添加到 $80$ 80两个红球都在同一个盒子里的解决方案，我们总共有 $300$ 300可能的解决方案。

+1（同样），因为你的答案使用了星条，而我的答案没有。在我看来，这意味着对于涉及较大数字的类似问题，问题解决者应该考虑使用你的方法作为指导，而不是我的方法。也就是说，一方面，星条将很好地概括。另一方面，在我的回答中，随着数字变大，不同满足整数分区的数量的交叉乘积将非常快速地增长。 —

Answer 2

很明显，有些盒子可以有 $0$ 0球，否则条款“最多 $2$ 2球”毫无意义。

假设盒子内的顺序无关紧要，我们可以简单地列出可能的模式，然后对它们进行排列

RR ​ 比比 ​ 乙 00 ： 5 ！ 2 ！ = 60

\boxed{RR}\boxed{BB}\boxed{B}\boxed{0}\boxed{0}: \frac{5!}{2!} = 60

RR ​ 乙 乙 乙 0 ： 5 ！ 3 ！ = 20

\boxed{RR}\boxed{B}\boxed{B}\boxed{B}\boxed{0}: \frac{5!}{3!} = 20

R R 比比 ​ 乙 0 ： 5 ！ 2 ！ = 60

\boxed{R}\boxed{R}\boxed{BB}\boxed{B}\boxed{0}: \frac{5!}{2!} = 60

R R 乙 乙 乙 ： 5 ！ 2 ！ 3 ！ = 10

\boxed{R}\boxed{R}\boxed{B}\boxed{B}\boxed{B}: \frac{5!}{2!3!} = 10

RB ​ RB ​ 乙 00 ： 5 ！ 2 ！ 2 ！ = 30

\boxed{RB}\boxed{RB}\boxed{B}\boxed{0}\boxed{0}: \frac{5!}{2!2!} = 30

RB ​ R 比比 ​ 00 ： 5 ！ 2 ！ = 60

\boxed{RB}\boxed{R}\boxed{BB}\boxed{0}\boxed{0} : \frac{5!}{2!} = 60

RB ​ R 乙 乙 0 ： 5 ！ 2 ！ = 60

\boxed{RB}\boxed{R}\boxed{B}\boxed{B}\boxed{0}: \frac{5!}{2!} = 60

唉，这总共只 $300$ \boxed{300}

$\underline{A D D E D}$ \underline{\mathtt{ADDED}}

如果我们假设盒子内颜色的顺序很重要，那么

60 + 20 + 60 + 10 + 4 \times 30 + 2 \times 60 + 2 \times 60 = 510

60+20+60+10+4\cdot30+2\cdot60+2\cdot60 = \boxed{510}

这与您的 Python 答案相符，但我没有看到哪里指定了盒子内的顺序很重要。

Accepted Answer

编辑

首先，请查看我根据罗伯特·肖尔 (Robert Shore) 的回答留下的评论。

可能存在比我所采用的方法更优雅的方法。我认为这个问题很棘手，需要理解。

数量 $2$ ~2~（红球）可以分为

$2$ ~2~
$1 + 1.$ ~1 + 1.~

鉴于没有盒子包含超过 $2$ ~2~球，令人满意的分区 $3$ ~3~（黑球）是

$2 + 1.$ ~2 + 1.~
$1 + 1 + 1.$ ~1 + 1 + 1.~

所以，你有 $2 \times 2 = 4$ ~2 \times 2 = 4~个别案例来列举。

编辑

我的猜测是，这代表了问题作者的意图。否则，为什么要提出一个涉及如此小数字的问题，例如 $2$ ~2~和 $3 ?$ ~3~?

让 $N_{1}, N_{2}, N_{3}, N_{4}$ ~N_1, N_2, N_3, N_4~分别表示下面案例 1、案例 2、案例 3 和案例 4 中的枚举。

然后，最终的计算将是

否 1 + 否 2 + 否 3 + 否 4 。

N_1 + N_2 + N_3 + N_4.

$\underline{Case 1: 2 Red, 2 + 1 Black}$ \underline{\text{Case 1:} ~2 ~\text{Red,} ~2 + 1 ~\text{Black}}

这 $2$ ~2~红色的， $2$ ~2~黑色和 $1$ ~1~黑色可以被认为是三个独立的实体，必须被分配 $3$ ~3~不同的盒子。

由于这些实体不同，这些框的分配顺序是相关的。

所以，

否 1 = 5 ！ （ 5-3 ） ！ ​ ​ = 60。

N_1 = \frac{5!}{(5-3)!} = 60.

$\underline{Case 2: 2 Red, 1 + 1 + 1 Black}$ \underline{\text{Case 2:} ~2 ~\text{Red,} ~1 + 1 + 1 ~\text{Black}}

与案例 1 类似，您有 $4$ ~4~不同的实体。

所以，

否 2 = 5 ！ （ 5-4 ） ！ ​ ​ \times 1 3 ！ = 20。

N_2 = \frac{5!}{(5-4)!} \times \frac{1}{3!} = 20.

在上面的计算中， $\frac{1}{3!}$ ~\dfrac{1}{3!}~因素适应于将黑球分配到盒子的顺序无关紧要，因为每个盒子都恰好接收 1 个黑球。

$\underline{Case 3: 1 + 1 Red, 2 + 1 Black}$ \underline{\text{Case 3:} ~1 + 1 ~\text{Red,} ~2 + 1 ~\text{Black}}

黑球可以分布在 $\frac{5!}{(5 - 2)!} = 20$ ~\displaystyle \frac{5!}{(5-2)!} = 20~方式。

然后，由于收到 1 个黑球的盒子也可以收到一个红球，因此有 $4$ ~4~有箱子可以接收红球。

第二个因素是

4 ！ （ 4-2 ） ！ ​ ​ \times 1 2 ！ = 6。

\frac{4!}{(4-2)!} \times \frac{1}{2!} = 6.

所以，

否 3 = 20 \times 6 = 120。

N_3 = 20 \times 6 = 120.

$\underline{Case 4: 1 + 1 Red, 1 + 1 + 1 Black}$ \underline{\text{Case 4:} ~1 + 1 ~\text{Red,} ~1 + 1 + 1 ~\text{Black}}

与其他案例的分析类似，

否 4 = (5 2 ） \times （ 5 3 ） = 100。

N_4 = \binom{5}{2} \times \binom{5}{3} = 100.

$\underline{Final Computation}$ \underline{\text{Final Computation}}

否 1 + 否 2 + 否 3 + 否 4

N_1 + N_2 + N_3 + N_4

= 60 + 20 + 120 + 100 = 300。

= 60 + 20 + 120 + 100 = 300.

我认为它不包括 1 个盒装 1 个黑色和 1 个红色，是吗？ — 
@laoyaobainian 是的，它确实涵盖了这一点。但是，组织不是通过放入框 1、框 2 等来组织。相反，组织是通过组合令人满意的整数分区来组织 $2$ ~2~具有令人满意的整数分割 $3.$ ~3.~ 我建议你仔细阅读答案，并尝试理解我的想法。然后，如果你能发现我的想法中存在明显的缺陷，请留下另一条评论。例如，你的第一条评论太模糊了，我无法直接回复。 — 
@laoyaobainian如果你能找到所有的明确的完整分布 $5$ ~5~如果您认为我忽略了（或数了不止一次）将球放入盒子中，请准确指定完整的分布。然后，我将调查一个具体问题。 —

Answer 4

这可能不是最直接的方法，但却是一项使用生成函数的很好的练习。

让

f （ x, y) = 1 + x + y + x y + 十 2 + 是 2

f(x,y)=1+x+y+xy+x^2+y^2

是一个盒子配置的生成函数，其中指数 $x$ x表示盒子里的红球数量和 $y$ y表示盒子里的黑球数量。

因此，五个盒子中分别有 0 个、1 个或 2 个球（无论球的颜色和总数如何）的所有可能配置的生成函数为

克 （ x, y) = f （ x, y ） 5 = （ 1 + x + y + x y + 十 2 + 是 2 ） 5 。

g(x,y) = f(x,y)^5 = (1+x+y+xy+x^2+y^2)^5.

换句话说， $x^{p} y^{q}$ x^p y^q在 $g (x, y)$ g(x,y)表示 5 个盒子的配置数量，

每个盒子里的球的数量为0、1或2；
计算所有五个盒子，红球总数为 $p$ p黑球总数为 $q$ q。

然后，我们感兴趣的配置由术语表示 $x^{2} y^{3}$ x^2y^3，我们需要计算它的系数。

经过一些代数运算，我们可以证明

克 （ x, y) = \sum k = 0 5 \sum 米 = 0 钾 \sum n = 0 5 - k \sum l = 0 5 - k （ 5 钾 ） （ 钾 米 ） （ 5 - k n ） （ 5 - k 升 ） 十 n + l 是 5 + 2 米 - k - n

g(x,y)=\sum_{k=0}^5\sum_{m=0}^k\sum_{n=0}^{5-k}\sum_{l=0}^{5-k}\binom{5}{k}\binom{k}{m}\binom{5-k}{n}\binom{5-k}{l}x^{n+l}y^{5+2m-k-n}

因此，我们追求的配置数量是

否 = \sum (5 钾 ） （ 钾 米 ） （ 5 - k n ） （ 5 - k 升 ）

N=\sum\binom{5}{k}\binom{k}{m}\binom{5-k}{n}\binom{5-k}{l}

总和是所有 $k, m, n, l$ k,m,n,l使得

$n + l = 2$ n+l=2
$5 + 2 m - k - n = 3 ⟹ k + n - 2 m = 2$ 5+2m-k-n=3 \implies k+n-2m=2
$0 \leq k \leq 5$ 0 \le k \le 5
$0 \leq m \leq k$ 0 \le m \le k
$0 \leq n \leq 5 - k$ 0\le n\le 5-k
$0 \leq l \leq 5 - k$ 0\le l\le 5-k。

因此（括号下面的四元组是 $(k, m, n, l)$ (k,m,n,l)）

否 = （ 5 2 ） （ 2 0 ） （ 3 0 ） （ 3 2 ）                      （ 2，0，0，2 ） ​ ​ ​ ​ ​ ​ + （ 5 1 ） （ 1 0 ） （ 4 1 ） （ 4 1 ）                      （ 1，0，1，1 ） ​ ​ ​ ​ ​ ​ + （ 5 3 ） （ 3 1 ） （ 2 1 ） （ 2 1 ）                      （ 3，1，1，1 ） ​ ​ ​ ​ ​ ​ + （ 5 0 ） （ 0 0 ） （ 5 2 ） （ 5 0 ）                      （ 0，0，2，0 ） ​ ​ ​ ​ ​ ​ + （ 5 2 ） （ 2 1 ） （ 3 2 ） （ 3 0 ）                      （ 2，1，2，0 ） ​ ​ ​ ​ ​ ​ = 10 \times 1 \times 1 \times 3 + 5 \times 1 \times 4 \times 4 + 10 \times 3 \times 2 \times 2 + 1 \times 1 \times 10 \times 1 + 10 \times 2 \times 3 \times 1 = 30 + 80 + 120 + 10 + 60 = 300。

\begin{align}
N &= \underbrace{\binom{5}{2}\binom{2}{0}\binom{3}{0}\binom{3}{2}}_{(2,0,0,2)} + \underbrace{\binom{5}{1}\binom{1}{0}\binom{4}{1}\binom{4}{1}}_{(1,0,1,1)}
+ \underbrace{\binom{5}{3}\binom{3}{1}\binom{2}{1}\binom{2}{1}}_{(3,1,1,1)} \\
&\qquad+ \underbrace{\binom{5}{0}\binom{0}{0}\binom{5}{2}\binom{5}{0}}_{(0,0,2,0)}
+ \underbrace{\binom{5}{2}\binom{2}{1}\binom{3}{2}\binom{3}{0}}_{(2,1,2,0)} \\
&= 10\cdot 1 \cdot 1 \cdot 3 + 5\cdot 1 \cdot 4 \cdot 4 + 10\cdot 3 \cdot 2 \cdot 2 + 1\cdot 1 \cdot 10 \cdot 1 + 10\cdot 2 \cdot 3 \cdot 1 \\
&= 30 + 80 + 120 + 10 + 60 \\
&= 300.
\end{align}

Answer 5

谢谢大家，并且有更正的验证码：

import itertools
def count_ways_pigeonhole(red_balls, black_balls, boxes, max_balls_per_box):
    exists = set()
    def find_combinations(red_balls, black_balls,block):
        base = ['red' for _ in range(red_balls)] + ['black' for _ in range(black_balls)] + block
        combs = itertools.permutations(base, len(base))
        for comb in combs:
            exists.add(tuple(comb))
    find_combinations(red_balls, black_balls,['block' for _ in range(boxes - 1)])
    #validate
    validate_combinations = []
    for comb in exists:
        s = ' '.join(comb)
        s = s.split('block')
        s = [i.strip().split(' ') for i in s]
        for i in s:
            if len(i) > max_balls_per_box:
                break
        else:
            tmp =[sorted(i) for i in s]
            if tmp not in validate_combinations:
                validate_combinations.append(tmp)
    
    for i in range(len(validate_combinations)):
        for j in validate_combinations[:i] + validate_combinations[i+1:]:
            if validate_combinations[i] == j:
                print('error')
    for i in validate_combinations[:20]:
        print(i)
    return len(validate_combinations)


red_balls = 2
black_balls = 3 
boxes = 5
max_balls_per_box = 2



print(count_ways_pigeonhole(red_balls, black_balls, boxes, max_balls_per_box))
```

组合学 – 5 个不同的盒子里有 2 个相同的红球和 3 个相同的黑球，每个盒子最多有 2 个球，求组合数。 – 数学

5 个回答
5

组合学 – 5 个不同的盒子里有 2 个相同的红球和 3 个相同的黑球，每个盒子最多有 2 个球，求组合数。 – 数学

5 个回答 5

5 个回答
5