5

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.

A. Sarid
  • 3,916
  • 2
  • 31
  • 56

4 Answers4

4

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
amit
  • 175,853
  • 27
  • 231
  • 333
  • This is a great explanation, and seems to work for every example I've tried. You just need to fix the typo in the final formula where it's calculating W(2) on max{N-A,0} instead of max{N-B,0}. – Brian Stephens Sep 02 '16 at 19:29
  • @BrianStephens Thanks, was doing it as you typed your comment. – amit Sep 02 '16 at 19:30
  • Thank you so much for this correct and well explained solution. I wouldn't thought of using Inclusion Exclusion. Guess I need to refresh my memory about combinatorics. – A. Sarid Sep 03 '16 at 06:36
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)

Saurav Sahu
  • 13,038
  • 6
  • 64
  • 79
-1

It should be

   ans = (A + B) - N + 1
Harbeer Kadian
  • 364
  • 2
  • 14
  • No. Take for example total of 4 fruits. and you have 10 apples and 1 orange. The total number of combinations is 2. Either 1 orange and 3 apples or 0 oranges and 4 apples. Copied comment from another answer. – Sanket Makani Sep 02 '16 at 18:25
  • Sorry My mistake. – Harbeer Kadian Sep 02 '16 at 18:31
  • I have copied the comment of author from another answer which is not satisfying the same. Your answer won't give correct input if ```A``` is 10 ```B``` is 1 and ```N``` =4...Answer should be ```ans=2```(two pairs can be generated (A,B)=(4,0) or (A,B)=(3,1)) but your formula will give ```ans=8```. – Sanket Makani Sep 02 '16 at 18:34
  • Still trying to figure out – Harbeer Kadian Sep 02 '16 at 18:58
-3

Ok, sorry, I was (way) too fast.

You know there's always at least one solution.

You have to take at least enough fruit of A so that with B, it makes N. You take at max A fruit of A. If that's bigger than N, the limit is N. So the answer should be:

min(A, N) - max(0, N-B) + 1
Nicolai Ehemann
  • 574
  • 4
  • 10
  • No. Take for example total of 4 fruits. and you have 10 apples and 1 orange. The total number of combinations is 2. Either 1 orange and 3 apples or 0 oranges and 4 apples. – A. Sarid Sep 02 '16 at 18:00
  • To explain a bit more: min(A,N) is the maximum number of A you can take. max(0, N-B) is the minimum number of A you need. The difference is hence always positive or 0 (because A + B >= N). The difference plus 1 is the thus the solution. – Nicolai Ehemann Sep 02 '16 at 18:52