2
$\begingroup$

There are $n$ objects and two buckets $B_1$ and $B_2$. The problem is as follows:

Some of these objects must be placed in the two buckets, according to the following rules:

  1. Number of objects in $B_1$ must be equal to the number of objects in $B_2$. This number can be $0$.
  2. There are $a$ objects among these $n$ objects that can only be placed in $B_1$.
  3. Similarly, there are $b$ objects among these $n$ objects that can only be placed in $B_2$. The rest of the $y=n-a-b$ objects can be placed in either bucket.

How many ways are there to place some of the objects in the buckets?

My Attempt:

$$\sum_{i=0}^{min(a+y,\;b+y)}{a+y \choose i}{b+y \choose i}$$

But I need to subtract from this, the ways in which the same object from the $y$-collection is put in both $B_1$ and $B_2$.

My Second Attempt:

$$\sum_{\substack{i+k_1=j+k_2\\k_1+k_2\le y}}{a \choose i}{y \choose k_1}{b \choose j}{y-k_1 \choose k_2}$$

This will give the exact answer. But, I don't know how to simplify this summation.

$\endgroup$
5
  • $\begingroup$ Please show what you have attempted and explain where you are stuck. $\endgroup$ Commented Nov 3, 2018 at 9:22
  • $\begingroup$ @N.F.Taussig Added some work. $\endgroup$
    – Truth-seek
    Commented Nov 4, 2018 at 16:23
  • $\begingroup$ I think this is the problem math.stackexchange.com/questions/2982821/… in disguise. $\endgroup$ Commented Nov 7, 2018 at 14:10
  • $\begingroup$ Based on the work so far, I assumed the objects are meant to be distinguishable, whereas in the linked question they are indistinguishable, This would affect the result, of course. $\endgroup$
    – David K
    Commented Nov 7, 2018 at 15:16
  • $\begingroup$ @DavidK No the objects are indistinguishable. So, indeed the questions are the same. But, I didn't find any answers, I could use, there as well. $\endgroup$
    – Truth-seek
    Commented Nov 7, 2018 at 15:35

1 Answer 1

2
$\begingroup$

I originally assumed the objects were all distinguishable, since otherwise the idea of counting $\binom ai$ way of using $i$ of the $a$ objects makes no sense.

Given that the objects actually are indistinguishable (except possibly for the classification into three types of objects), this question really is equivalent to Number of ways to fill a bag using red, blue and white balls.

In that question, the white balls (corresponding to the $y$ objects) that are grouped with the red balls (corresponding to the $a$ objects) are painted red, leading to two answers depending on whether we consider a white ball painted red to be distinguishable from a ball that was red beforehand.

In this question, no change is made to the $y$ objects (other than placing some of them in buckets), so if we use some intrinsic property of each object to determine which bucket an object can go into, we should be able to distinguish objects in the first bucket according to whether they were among the original $a$ objects or $y$ objects, and the answer https://math.stackexchange.com/a/2982836 applies.

On the other hand, if we simply have $a + b + y$ identical objects in three separate piles, and the restrictions on which bucket we can put an object into are determined solely by the pile the object came from, then the answer https://math.stackexchange.com/a/2982921 applies. (Once the object is in a bucket we can no longer tell which pile it came from, just as that answer assumes we cannot tell whether a red ball was originally white.)


Here's my original answer, no longer actually applicable to this particular question.

Let's try this for $a = b = 1,$ $y = 2.$ The condition $i+k_1=j+k_2,\ k_1+k_2<y$ says that we cannot place both of the $y$ objects in the buckets, which rules out some obviously correct arrangements, so I suppose it was really meant to be $i+k_1=j+k_2,\ k_1+k_2 \leq y.$ And of course let's not forget we also have to watch the limits of $i$ and $j$: $i \leq a,\ j\leq b.$

The summation over $i+k_1=j+k_2,\ k_1+k_2 \leq y,\ i \leq a,\ j\leq b$ ranges over the following sets of indices:

\begin{gather} i = j = k_1 = k_2 = 0;\\ i = j = 0,\ k_1 = k_2 = 1;\\ i = 0,\ j = 1,\ k_1 = 1,\ k_2 = 0;\\ i = 1,\ j = 0,\ k_1 = 0,\ k_2 = 1;\\ i = j = 1,\ k_1 = k_2 = 0;\\ i = j = k_1 = k_2 = 1. \end{gather}

Adding up the resulting terms, for example ${a \choose i}{y \choose k_1}{b \choose j}{y \choose k_2} = {1 \choose 0}{2 \choose 0}{1 \choose 0}{2 \choose 0} = 1\cdot 1\cdot 1\cdot 1,$ we have \begin{multline} (1\cdot 1\cdot 1\cdot 1) + (1\cdot 2\cdot 1\cdot 2) + (1\cdot 2\cdot 1\cdot 1)\\ + (1\cdot 1\cdot 1\cdot 2) + (1\cdot 1\cdot 1\cdot 1) + (1\cdot 2\cdot 1\cdot 2)\\ = 1 + 4 + 2 + 2 + 1 + 4 = 14. \end{multline} But if we label the objects $A$, $B,$ $Y_1,$ and $Y_2,$ the possible arrangments in the buckets are \begin{gather} \emptyset,\ \emptyset; \\ \{Y_1\},\ \{Y_2\}; \\ \{Y_2\},\ \{Y_1\}; \\ \{Y_1\},\ \{B\}; \\ \{Y_2\},\ \{B\}; \\ \{A\},\ \{Y_1\}; \\ \{A\},\ \{Y_2\}; \\ \{A\},\ \{B\}; \\ \{A,Y_1\},\ \{B,Y_2\}; \\ \{A,Y_2\},\ \{B,Y_1\}. \end{gather}

There are only $10$ ways to place the objects. So the formula counted too many.

If we use the condition $i+k_1=j+k_2,k_1+k_2<y$ after all, then both of the terms with $k_1 = k_2 = 1$ are eliminated, and we count $1 + 2 + 2 + 1 = 6$ ways, which is too few.

Here's what went wrong: when multiplying ${y \choose k_1}$ and ${y \choose k_2}$ you assume that in the case $k_1=k_2=1$ you can combine any of the two subsets enumerated by ${y \choose k_1},$ including (for example) $\{Y_1\},$ with any of the two subsets enumerated by ${y \choose k_2}$, including $\{Y_1\}$; but of course it is not possible to put $\{Y_1\}$ simultaneously in both buckets.

I think what you want here is not the binomial coefficients ${y \choose k_1}$ and ${y \choose k_2}$ but rather the multinomial coefficient $$\binom{y}{k_1\quad k_2\quad y - k_1 - k_2} = \frac{y!}{k_1! k_2! (y - k_1 - k_2)!},$$ which is the number of ways to partition $y$ objects into a tuple of three subsets: one subset to put in the first box, one subset to put in the second box, and a third subset to leave out of both boxes.

Note that you can get the same result by changing ${y \choose k_2}$ to ${y - k_1 \choose k_2}$, because $$\binom{y}{k_1\quad k_2\quad y - k_1 - k_2} = \binom{y}{k_1}\binom{y - k_1}{k_2},$$ but I think the multinomial coefficient is clearer and needs less computation.


Note that in any permissible configuration using $i$ objects from the $a$ objects and $j$ from the $b$ objects, the smallest possible value of $k_1$ is either $j - i$ or $0,$ whichever is larger, the largest possible value of $k_1$ is $\lfloor \frac12(y + j - i)\rfloor$ and $k_2 = i + k_1 - j.$ We can then write the summation as $$ \sum_{i = 0}^{\min\{a,b+y\}} \sum_{y = 0}^{\min\{b,i+y\}} \sum_{k = \max\{0,j-i\}}^{\lfloor \frac12(y + j - i)\rfloor} \binom ai \binom bj \binom{y}{k\quad i - j + k \quad y - i + j - 2k}. $$

I do not have any ideas for simplifying the sum beyond this; it may just be a matter of working out the sum term by term.

$\endgroup$
1
  • $\begingroup$ Thnx. Can you help me with computing the summation also. $\endgroup$
    – Truth-seek
    Commented Nov 7, 2018 at 14:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .