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. :)