1
$\begingroup$

The answer is 7: WWW, WWB, WBW, BWW, WBB, BWB, BBW. Is there an elegant way of calculating it in a way that scales to picking M balls out of K black and N white balls?

$\endgroup$
3
$\begingroup$

There isn't really a nice expression for it, no. What you want in general is a sum of binomial coefficients $$ \sum_{i = \max(0, M-N)}^{\min(K, M)}\binom{M}{i} $$ where each term is the number of orders in which you can pick $i$ black balls and $M-i$ white balls, and the boundaries of the sum are the given by how many black balls you could possibly draw.

A sum of consecutive binomial coefficients like this has no nice closed form in general. For the three cases $\sum_{i = 0}^M$, $\sum_{i = 0}^{M/2}$ and $\sum_{i = M/2}^M$ (in other words, either there are more than enough balls of both colors, or exactly one of the colors is limited, to exactly $M/2$) there is a nice expression (it's just a power of $2$), and cases close to those can be calculated from there, but that's the only special cases that I know of.

$\endgroup$
1
  • $\begingroup$ There ir a common name to the combinatory problems with "limited replacement" depending of the objects? $\endgroup$ Jul 18 '18 at 9:51
0
$\begingroup$

$$\sum_{k=\max\{0,M-N\}}^{k=\min\{K,N\}}\dfrac{ M!}{k!(M-k)!}$$

For each $k$ balls of the color with smaller number chosen, $(M-k)$ balls of the other color is chosen. Order the balls, account for the identical objects.

$\endgroup$
2
  • $\begingroup$ Can you explain it? $\endgroup$ Jul 18 '18 at 9:40
  • 1
    $\begingroup$ @RafaelGonzalezLopez my bad just now, misread the question $\endgroup$ Jul 18 '18 at 9:46
0
$\begingroup$

The generating function for all words without restrictions is

$GF(x,y,t) = {1 \over 1 - xt - yt}$

where the coefficient of $x^ny^kt^m$ encodes the number of word of length $m$ that contain $n$ letters W and $k$ letters B.

$$\sum_{0 \leqslant n}^{N} coeff(x^n)\ \sum_{0 \leqslant k}^{K} coeff(y^k)\ \sum_{m=M}coeff(t^m) \ GF(x,y,t) $$

for the given case, this "viewport" will extract the polynomials:

$x^3+3x^2y+3xy^2+y^3$

$x^3+3x^2+3x+1$

$7$

$\endgroup$
0
$\begingroup$

Oh dear me ! here is a nice one :

We have to partition in two subsets a string of length M $x_1x_2...x_M$

then the exponential generating function is :

$$ (1 + x + {x^2 \over 2!} + \cdots + {x^K \over K!}).(1 + x + {x^2 \over 2!} + \cdots + {x^N \over N!}) $$

Just take the coefficient of $x^M \over M!$

see here How many arrangements of k items from n items when there are duplicate items

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.