There are N distinct boxes of balls in total. There are P boxes each containing A number of balls and remaining Q boxes contains B number of balls each.
Given a number X, what are the total the number of ways in which you can pick at least X balls from the boxes.
P+Q = N
Example: Number of P boxes=2
which contain 2 balls each, Number of Q boxes=1
which contain 2 balls. X=3(Given)
where x=minimum number of balls to be picked
So, P+Q=3 (total number of boxes)
Combinations for the number of ways to pick atleast x i.e. 3 balls would be:
combinations of 3:(111),(210),(120),(021),(012),(201),(102)
combinations of 4:(220)(202)(022)(211)(121)(112)
combinations of 5:(212)(122)(221)
combinations of 6: (222)
total Combinations: 17
My Approach:
I have used "Stars and Bars Approach":
To calculate combinations of 6: x+y+z=6 which is converted into (2-x)+(2-y)+(2-z)=6 giving out x+y+z=0.
So, the combination of 6 becomes Binomial(2C2)=1
Similarly, Combinations of 5 becomes Binomial(3C2)=3
Combinations of 4= Binomial(4C2)=6
Combinations of 3= Binomial(5C2)=10
1+3+6+10=20
but the answer should be 1+3+6+7=17
Edge case has appeared on calculating the combinations of 3. How should I tackle this problem?
global total_combinations
total_combinations=0
from math import factorial
def combinations(a):
global total_combinations
bars=numberofAs+numberofBs-1
stars=a
total_combinations+=factorial(stars+bars)/(factorial(bars)*factorial(stars))
numberofAs,numberofBs,numberofballsinA,numberofballsinB=map(int,raw_input().split())
x=int(raw_input())
operational_array=[]
for i in range(numberofAs):
operational_array.append(numberofballsinA)
for i in range(numberofBs):
operational_array.append(numberofballsinB)
max_x=sum(operational_array) #calculate combinations from x to max_x
k=max_x
for i in range(max_x,x-1,-1):
k=max_x-i
combinations(k)
print total_combinations
PS:I found this question online but it seems interesting to me.