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$
2
  • $\begingroup$ The condition $x_0, x_1, x_2, x_3 \leq k$ is kind of unnecessary considering they're $\geq 0$. $\endgroup$
    – MT_
    Jul 27, 2016 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, 2016 at 21:34

2 Answers 2

Reset to default
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$
1
  • $\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, 2016 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$

You must log in to answer this question.

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