Count the number of ways of putting balls into bins
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)]
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
.
Python 3, 180 172 bytes
def f(n):
r=range;N=n+1;a=[N*[0]for _ in r(N)];R=r(1,N,2);a[0][0]=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.