2

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.

Om Sharma
  • 335
  • 1
  • 11
  • Welcome to Stack Overflow. I suggest you take some time to debug your problem by stepping through it one line at a time. https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems and https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ have some great tips to get you started. – Code-Apprentice Jan 06 '18 at 17:20
  • Do they all have the same amount of balls in each box? – Miket25 Jan 06 '18 at 17:37
  • @Miket25 P boxes will contain same number of balls and Q boxes will contain same number of balls but it is not necessary that balls in p are equal to q. – Om Sharma Jan 06 '18 at 17:39
  • @Miket25 There can be P boxes each having 3 balls and Q boxes each having 7 balls .Also there can boxes each having 7 balls and Q boxes also having 7 balls.So balls in P and Q need not be same but balls in P each will be equal and same goes for Q. – Om Sharma Jan 06 '18 at 17:44
  • @Miket25 can the error be eliminated using inclusion-exclusion? – Om Sharma Jan 06 '18 at 17:47
  • It sounds more of using a mix of bionomials and multinoimals – Miket25 Jan 06 '18 at 19:16
  • @Miket25 do you have a solution? – Om Sharma Jan 06 '18 at 19:22
  • I don't. If your original question is seeking for a mathematical answer, I suggest your best option is asking on math stack exchange. – Miket25 Jan 06 '18 at 19:34
  • This doesn't look like python-3.x – Georgy Jan 06 '18 at 21:36
  • 1
    The print and raw_input show it to be python 2. The fact that you have your own "combinations" instead of using itertools is a huge red flag. You may be reinventing the wheel. – Kenny Ostrom Jan 06 '18 at 21:41

0 Answers0