所有组合用于从给定的橙子和苹果创建水果篮

Question

假设你有A橘子和B苹果.你想要创造一篮子N水果.您可以制作的苹果和橙子组合的总数是多少？
假设A+B >= N.

例如:
我有6个橘子和6个苹果,我想创造一个总共9个水果的篮子.
所以我有4种不同的组合:

3 apples 6 oranges
4 apples 5 oranges
5 apples 4 oranges
6 apples 3 oranges

我想创建一个简单(高效)的算法来计算这个数字.
是否有任何数学/组合方式来计算O(1)中的这个数字？我找不到一个正确的公式.

Answer 1

这个答案将展示如何获得正确的封闭公式的通用方法，而不是给出“这里，它有效”的公式。

要获得接近的公式，请使用星形和条形公式以及包含排除来找到方程的解数：

x1 + x2 = n
s.t.
(1) 0 <= x1 <= A
(2) 0 <= x2 <= B

表示：

W(0) = #solutions to the problem regardless of restrictions
W(1) = #solutions to the problem with (1) is NOT correct (x1 > A)
W(2) = #solutions to the problem with (2) is NOT correct (x2 > B)
W(1,2) = #solutions to the problem with both (1,2) NOT correct (x1 > A and X2 > B)

根据包含排除原理，我们上面形式化的问题的答案是：

E = W(0) - (W(1) + W(2)) + W(1,2)

剩下的就是给 提供公式W(...)，为此我们将使用星形和条形。

使用无限制的方程以及条形和星形的定理 2：

W(0) = Choose(N + 2 - 1, 2 - 1) = Choose(N + 1, 1) = N + 1 

为了计算 W(1) 和 W(2)，我们强制x1/x2为A+1或B+1，然后照常进行，得到方程：

x1 + x2 = N - A - 1
x1 + x2 = N - B - 1

解的数量为（再次使用定理 2）：

W(1) = Choose(N - A - 1 + 2 - 1, 1) = Chose(N-A,1) = max{N-A,0}
W(2) = (similarly) = max{N-B,0}

对于 W(1,2)，我们设置两者并继续得到：

W(1,2) = Choose(N - A - 1 - B -1 + 2 - 1) = Choose(N-A-B-1,1) = max{N-A-B-1,0}

将所有内容加在一起得出最终公式：

E = W(0) - (W(1) + W(2)) + W(1,2) = 
  = N + 1 - max{N-A,0} - max{N-B,0} + max{N-A-B-1,0}

在你的例子中是：

E = 9 + 1 - 3 - 3 + 0 = 4