All combination for creating a fruit basket from given oranges and apples

Question

Say you are given A oranges and B apples. You want to create a basket of total N fruits. What is the total number of combination of apples and oranges you can make?
Assuming A+B >= N.

Example:
I have 6 oranges and 6 apples and I want to create a basket with total 9 fruits.
So I have 4 different combinations:

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

I want to create a simple (and efficient) algorithm to calculate this number.
Is there any mathematical / combinatoric way to calculate this number in O(1)? I couldn't find a correct formula for this.

Answer 1

This answer will show a generic way how to get to the correct closed formula, rather than give "here, it works" formula.

To get to a close formula, using the Stars and Bars formula and Inclusion Exclusion, you want to find the number of solutions to the equation:

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

Denote:

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)

From inclusion exclusion principle, the answer to the problem we formalized above is:

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

All is left is to give formulas to W(...), and for this we will use the Stars and Bars.

Using the equations without constraits and Theorem 2 of bars and stars:

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

To calculate W(1) and W(2), we force x1/x2 to be A+1 or B+1, and then go as usual, and get the equations:

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

and the number of solutions are (again using theorem 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}

For W(1,2) we set both and go on and get:

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

Summing it all together to the final formula:

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}

Which in your example is:

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

Answer 2

Lets say A_max is the maximum of number of A that can be included in the combination, and A_min be the least number of A that must be included in any combination. Then there will be two conditions that must be satisified:

1. A_max + B_min = N
2. A_min + B_max = N

Since we know A_max(which is min(NumOfA, N)), B_min can be found easily from first equation. Similarly one can find A_min from second equation. Consequently, the list of combinations would be:

A_max + B_min

(A_max-1) + (B_min+1)

(A_max-2) + (B_min+2)

...

(A_min) + (B_max)

So the count of such combinations would be (A_max - A_min + 1) or (B_max - B_min + 1)