# Count the number of ways of putting balls into bins

In this task you are given an odd number of white balls and the same number of black balls. The task is to count all the ways of putting the balls into bins so that in each bin there is an odd number of each color.

For example, say we have 3 white balls. The different ways are:

(wwwbbb)
(wb)(wb)(wb)


for the two different possibilities.

If we have 5 white balls the different ways are:

(wwwwwbbbbb)
(wwwbbb)(wb)(wb)
(wwwb)(wbbb)(wb)
(wb)(wb)(wb)(wb)(wb)


You can take the input, which is a single integer, in any way you like. The output is just a single integer.

Your code must be fast enough so that you have seen it complete for 11 white balls.

You can use any language or library that you like.

• Please clarify, can our output be just the number of different ways? That is, a single number as output?
– orlp
Apr 14, 2018 at 19:10
• I assume this is from math.stackexchange.com/questions/2736933/… You should cite it @Lembik
– qwr
Apr 14, 2018 at 19:21
• I think you should take out the speed criterion or make it more specific. "Fast enough" is too vague. Apr 14, 2018 at 19:56
• You know that PPCG users are crazy enough that they would rather spending money on using a supercomputer to compute it for 11 than taking 1 more byte? So why wasting their money? :) Apr 15, 2018 at 2:48
• (remark: It's possible to calculate P function efficiently with a complicated formula. It may be possible to calculate this function too, with a suitable formula.) Apr 18, 2018 at 15:00

# Python 3, 108 bytes

C=lambda l,r,o=():((l,r)>=o)*l*r%2+sum(C(l-x,r-y,(x,y))for x in range(1,l,2)for y in range(1,r,2)if(x,y)>=o)


Recursively enumerates all sets, making sure to not get duplicates by always generating the sets in order. Reasonably fast when memoized using C = functoools.lru_cache(None)(C), but this is not necessary for n = 11.

Call C(num_white, num_black) to get your result. First couple of n:

1: 1
3: 2
5: 4
7: 12
9: 32
11: 85
13: 217
15: 539
17: 1316
19: 3146
21: 7374


To generate the results:

def odd_parts(l, r, o=()):
if l % 2 == r % 2 == 1 and (l, r) >= o:
yield [(l, r)]

for nl in range(1, l, 2):
for nr in range(1, r, 2):
if (nl, nr) < o: continue
for t in odd_parts(l - nl, r - nr, (nl, nr)):
yield [(nl, nr)] + t


E.g. for (7, 7):

[(7, 7)]
[(1, 1), (1, 1), (5, 5)]
[(1, 1), (1, 1), (1, 1), (1, 1), (3, 3)]
[(1, 1), (1, 1), (1, 1), (1, 1), (1, 1), (1, 1), (1, 1)]
[(1, 1), (1, 1), (1, 1), (1, 3), (3, 1)]
[(1, 1), (1, 3), (5, 3)]
[(1, 1), (1, 5), (5, 1)]
[(1, 1), (3, 1), (3, 5)]
[(1, 1), (3, 3), (3, 3)]
[(1, 3), (1, 3), (5, 1)]
[(1, 3), (3, 1), (3, 3)]
[(1, 5), (3, 1), (3, 1)]

• Very nice indeed.
– user9206
Apr 14, 2018 at 22:49

# Pari/GP, 81 bytes

p=polcoeff;f(n)=p(p(prod(i=1,n,prod(j=1,n,1+(valuation(i/j,2)==0)*x^i*y^j)),n),n)


For more efficiency, replace 1+ with 1+O(x^(n+1))+O(y^(n+1))+ (the first O term alone already helps a lot).

Try it online! (earlier 86 byte version with a pair of unneeded parens and without the p= abbreviation)

### Old version, 90 bytes

f(n)=polcoeff(polcoeff(taylor(1/prod(i=0,n,prod(j=0,n,1-x^(2*i+1)*y^(2*j+1))),x,n+1),n),n)


Computing f(11) needs a bigger stack size, the error message will tell you how to increase it. It's more efficient (but less golfy) to replace the two n that appear as second arguments to prod with (n-1)/2.

• Works up to 13 for me!
– user9206
Apr 15, 2018 at 20:04
• I guess that is with the version using (n-1)/2? Apr 15, 2018 at 20:37
• Yes, good point.
– user9206
Apr 15, 2018 at 21:07
• Out of interest, do you think it's possible to compute f(500)?
– user9206
Apr 16, 2018 at 15:16
• It takes a few minutes to compute f(500)=214621724504756565823588442604868476223315183681404 Apr 17, 2018 at 0:15

# Python 3, 180 172 bytes

def f(n):
r=range;N=n+1;a=[N*for _ in r(N)];R=r(1,N,2);a=1
for i in R:
for j in R:
for k in r(N-i):
for l in r(N-j):a[k+i][l+j]+=a[k][l]
return a[n][n]


Try it online!

Straightforward implementation of the generating function. Long but (somewhat) efficient. O(n4) time, O(n2) memory.

The resulting array a contains all results of all sizes up to n, although only a[n][n] is returned.

• What does your code calculate for even n, out of interest? As in a.
– user9206
Apr 15, 2018 at 19:37
• This is the fastest solution so far too!
– user9206
Apr 15, 2018 at 20:15
• @Lembik a = Number of ways to put 4 white balls and 4 black balls into bins, each bin has an odd number of white balls and an odd number of black balls. Exacly as in the defintion. Apr 16, 2018 at 2:09

# Python 2, 168 181 bytes

from itertools import*
r,p=range,product
def f(n):
a,R=eval([*n]*n),r(1,n,2);a=1
for i,j in p(R,R):
for k,l in p(r(n-i),r(n-j)):a[k+i][l+j]+=a[k][l]
return a[-1][-1]


Try it online!

• This is a snippet (assumes n contains the input) You should either add def f(n): or n=input() (to make it a function/full program resp.) Apr 18, 2018 at 14:31
• And... this is Python 2, you can use a tab instead of two spaces. Saves a byte. The a can be eval([*n]*n) (where  stands for repr`). Apr 18, 2018 at 14:32