2
$\begingroup$

I am looking to find the number of multisets with restrictions on the number of specific elements. This isn't for homework, it is a work related problem.

My set of items is {A, a, B, b}. I want to get the number of multisets with at least 3 B/b, where there is at least one of each B/b. For multisets order does not matter, and duplicates are allowed.

To get the total number of multisets with cardinality $k$, from my set of cardinality n = 4, I have been using, $$\frac{(n + k - 1)!}{(k!(n-1)!}$$However I want to count the number of multisets with at least 3 B or b, and a minimum of 1 each.

For $k = 3$ there are two solutions, $\{B, B, b\}$ and $\{B, b, b\}$. These two sets represent the minimum requirements to pass.

Then for any $k$, I was thinking the number of multisets to be $$2 * (\frac{(4 + (k-3) - 1)!}{((k-3)!(n-1)!})$$

My reasoning was that the possible valid sets are $\{B, B, b, x_3, x_4, ... x_k\}$ and $\{B, b, b, x_3, x_4, ... x_k\}$, where $\{x_3, x_4, ..., x_k\}$ is any multiset from {A, a, B, b} with cardinality $k - 3$.

The problem I ran into is that this method counts some sets multiple times. For example, if k = 4, the valid sets are $\{B, B, b, x_3\}$ and $\{B, b, b, y_3\}$, where $x_3$ and $y_3$ are any item in $\{A, a, B, b\}$. For $x_3 = b$ and $y_3 = B$, I am counting the set $\{B, B, b, b\}$ twice. I tried predicting the number of duplicate counts and subtracting that, but could not find an answer.

If I assign each element in my set $\{x_0 = A, x_1 = a, x_2 = B, x_3 = b\}$, another way to phrase the problem is to find the number of solutions to,

$$ x_0 + x_1 + x_2 + x_3 = k $$ where, $$k >= x_0, x_1, x_2, x_3 >= 0$$ $$k >= x_2 + x_3 >= 3$$ $$x_2 >= 1$$ $$x_3 >= 1 $$

EDIT

Thanks for the help guys. I have changed the requirement of 3 'B/b' elements to $minB$ 'B/b' elements. So for a multiset of size D with $minB$ required 'B\b' elements, $\{B, b, x_3, x_4, ... x_D\}$ is a valid multiset if $\{x_3, x_4, ... x_D\}$ has minB-2 'B/b' elements. Based off of these comments I came up with,

$$ numValid(D, minB) = \sum_{nb = minB - 2}^{D-2} [(nb + 1) * (D - nb - 1)] $$

The first term inside the sum $(nb + 1)$ is the number of multisets of size $minB - 2$ chosen from $\{B, b\}$. The second term is the number of multisets of size $D - 2 - nb$ chosen from $\{A, a\}$. Then summing $nb$ from $ minB - 2$ to $D - 2$, we get the number of multisets of the form $\{B, b, x_3, x_4, ... x_D\}$, where $\{x_3, x_4, ... x_D\}$ has at least $(minB - 2)$ 'B/b' elements.

Is this correct? Thanks again. :)

$\endgroup$
  • $\begingroup$ The condition $x_0, x_1, x_2, x_3 \leq k$ is kind of unnecessary considering they're $\geq 0$. $\endgroup$ – MCT Jul 27 '16 at 21:32
  • $\begingroup$ The number of non-negative integer solutions to $\begin{cases} x_1+x_2+\dots+x_r=k\\ 0\leq x_i\end{cases}$ is $\binom{k+r-1}{r-1}$ (seen by stars and bars). Via a suitable change of variables, you may have lower limits for some (or all) of the variables individually to be increased. To induce the condition that $x_2+x_3\geq 3$ (or similar), I would personally remove the outcomes which violate the condition while maintaining all other conditions. I.e. remove the outcomes where $x_2=1$ and $x_3=1$. This becomes tedious as you implement multiple simultaneous similar conditions. $\endgroup$ – JMoravitz Jul 27 '16 at 21:34
0
$\begingroup$

First take one obligatory b and one B, and forget about them. They'll always be there.

Then you're looking for multisets of size $k-2$ that contain at least one b or B. We can get those by counting all multisets of size $k-2$ and then subtract the $k-1$ ones that consist only of A and a.

By stars-and-bars there are $\binom{k-2+3}{3}$ multisets with or without bees, so your final count is $$ \binom{k+1}{3} - (k-1) = \frac{k^3-k}6 - k + 1$$

$\endgroup$
  • $\begingroup$ Thanks for your help! I modified the requirements to work for $n$ B/b's instead of 3. I appended my solution to my original question. Is it correct? $\endgroup$ – Daniel Cole Jul 29 '16 at 14:59
0
$\begingroup$

First, substitute $x_2 \mapsto x_2' + 1, x_3 \mapsto x_3' + 1$. Then this formulation is equivalent to

$$x_0 + x_1 + x_2' + x_3' = k-2$$

with the variables $\geq 0$. The total number of solutions is then ${k+1 \choose 3}$ by standard methods. The one case which doesn't work are those where $x_2' = x_3' = 0$. Can you take it from here?

$\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.