Conditional combinatorics (by frequency of elements)

[Lee1]

Hey guys,

I'd love to get the formula to answer the following question:

I have 50 colorless balls and 100 different paints. All balls have to be painted.
Note that the balls' order is not important and repetition is allowed (means I can paint up to 50 balls in any single color if I want).
With that in mind, there are (100+50-1)!/50!(100-1)! possible color combinations in total (1.34191072e+40) to end up with. So far, so good.

But now I want to split this amount of combinations into two different categories based on the frequency of colors appearing:

Group 1 shall include any of these combinations that contain no more than three balls of any individual color.
Group 2 shall include every combination that contains at least four balls of at least one individual color (e.g. "6 blue and 5 yellow balls + 89 differently colored balls")
--> In the end I want to be able to tell how many combinations belong to each group.

Note that only one of these cases has to be solved (whichever is easier to calculate, I bet it's the 2nd) as the other one equals the difference to the total number of combinations.

I tried hard to solve this but I failed since I've never learned how to count the number of combinations by calculation and formula rather than by simply counting them all through.

As a little help here's some data to testproof your formula (note that this data is not directly related to the task above):
If n (colors) is 5 and r (balls) is 8, then the total number of combinations is 495, while 155 belong to the first and 340 to the second group. These are the numbers you should get when using 5 and 8 as values other than 100 and 50. I got these numbers by simply counting every possible calculation (and then doublechecked that result) to have some data for verification. Any help is highly recommended, thanks in advance! =)

Best wishes,
Manuel

 

[Lee1]

No suggestions? =/

 

[MarkFL]

No suggestions? =/

Hello and welcome to MHB, Lee! :D

We ask that our users not bump a thread, as per MHB Rule #1:

No bumping. Bumping a thread is posting a reply to that thread solely to raise its profile and return it to the top of the active threads list. This is forbidden at MHB. If you want to draw attention to an unanswered thread, then post something of value such as further progress. It is also forbidden to bump one thread by drawing attention to it in a different thread.

So, if you wish to post to show what progress you have made since you first posted the thread, this is fine, but we do not want people just posting in an effort to raise the profile of the thread.

 

[Lee1]

Hey, MarkFL!

Oops, I'm sorry. Won't happen again. I just start to get a bit frustrated as I don't think my problem is overly difficult for a common statistician (which I'm not) yet this is my 4th board to ask this question (whereas I have to admit that I wasn't too clear about what exactly I wanted on the first two boards).

I didn't actually do anything further since I posted this thread since I've failed over and over again trying to solve my problem. So my last hope was to explain the problem as clear as possible one last time and find a kind person to have a look.
Meanwhile I would already be pleased if a mathematician could at least tell me whether this is way harder than it looks so I'd know to give up.

The trouble I have is that in school when it came to combinatorics I learned to count/semi-calculate the number of combinations in easy exercises only. "How many 4-digit lock combinations contain a 7" and so on. Things like that where you don't need to have a specific formula but would rather start counting all the cases individual you can think of "by hand".

Now in this case the answer is in the 10^somethings so I simply cannot start to count these cases. I have to do the math - which I never learnt. And I think I did also never learn about having more "options" than actual slots to put them into which is the case in my task.

I tried anyway so here's what I did but please keep in mind that this solution is definitely wrong:

First of all I thought the 2nd case (see 1st post) would be easier to calculate (not sure of it though) as you could easily come up with the criteria of having one four-of-a-kind (which ensures you only get the combinations for the 2nd case) plus 46 other balls which could have any of the 100 colors. So this would mean we have (100 + 46 - 1)!/(46 (100 - 1)!) different combinations (because order doesn't matter). But of course we could have hundred different four-of-a-kinds to start with and therefore have to multiplicate those with (100 + 46 - 1)!/(46 (100 - 1)!) which would result in 100 * (100 + 46 - 1)!/(46 (100 - 1)!).

But doing so, I count many combinations multiple times in different orders. Like for example, if my red four-of-a-kind somewhere has four green balls: RRRR-[...]-GGGG, then this would be the same as having four red balls hidden somewhere within the 46 balls of my green four-of-a-kind case: GGGG-[...]-RRRR (only if the [...]-part stays the same, of course). By increasing the amount of k from 50 up to something like 500, this would strongly increase the number of combinations counted multiple times this way. I was unable to remove this doubles from my term however.

I did then start to draw out more simple cases and colored excel tabs in color patterns for several evenings just to get an idea about how it might be done and also to get some definite fix numbers for hand-counted solutions that I could check my formulas with. It helped me to further enhance the formula but since I'm sure I took the wrong turn way back at the beginning I see no need to post it here.

In another board someone even wrote me a small tool to bruteforce other results but this works very slow and on really low numbers only. I hope for a very simple looking solution like you take something over something else and that's already it so you can easily calculate within the millions. I just don't know how to do it in the correct way.

My plan is to further increase n or k to several thousands (resulting in extremely large numbers, I know) and furthermore, to add some specific modulations to this formula.

I need/want this formula for personal use only and to share it on a blog. Which I'd like to start any day soon. =)

So if anybody feels like he can do that, your help is very welcome! If you wish, I'll add your name and link to the blog entry once it's done.

Thank you,

Manuel from Germany

 

[awkward]

Hi Manuel,

I'll give two solutions: one using generating functions (my favorite) and another using Inclusion / Exclusion. To generalize, let's say there are b balls and c colors. We want to count the number of ways to paint the balls using no more than 3 of the c colors, where $c \ge 3$. The ordering of the balls is not significant, only the total number of balls of each color. So what we want is the number of integer solutions of
$$x_1 + x_2 + x_3 + \dots + x_c = b \qquad \qquad (*)$$
subject to $0 \le x_i \le 3$ for $i = 1, 2, 3, \dots , c$. Let's say the number of solutions is $a_b$.

​First solution: Define $f(x) = \sum_{i=0}^{\infty} a_i x^i$. Then it's "easy to see" that
$$f(x) = (1 + x + x^2 + x^3)^c$$
Now we just apply a little algebra, using the binomial theorem (including the binomial theorem for negative exponents):
$$f(x) = \left( \frac{1-x^4}{1-x} \right)^c = (1-x^4)^c (1-x)^{-c} = \sum_{i=0}^c (-1)^i \binom{c}{i} x^{4i} \cdot \sum_{j=0}^{\infty} \binom{c+j-1}{j} x^j$$
The coefficient of $x^b$ in this product corresponds to the factors where $4i + j = b$, i.e. $j = b-4i$. So
$$a_b = \sum_{i = 0}^{\lfloor b/4 \rfloor} (-1)^i \binom{c}{i} \binom{c + b - 4i -1}{b-4i}$$

Second solution: If we remove the constraints $x_i \le 3$, the number of solutions of (*) in non-negative integers is
$$N = \binom{c+b-1}{b}$$
Let's say a solution has "Property i" if $x_i > 3$, so we would like to count the number of solutions which have none of the properties, $N_0$. Let $S_j$ be the number of solutions with $j$ of the properties, for $j = 1, 2, \dots , c$. We'll start by computing the number of solutions with Property 1, i.e. $x_1 > 3$. Define $y_1 = x_1 - 4$, so $y_1 \ge 0$. Then (*) becomes
$$y_1 + x_2 + x_3 + \dots + x_c = b -4$$
which has $\binom{c + b - 4 - 1}{b-4}$ solutions. More generally, in computing $S_1$, there are $\binom{c}{1}$ ways to choose $i$, and for each choice of $i$ there are $\binom{c + b - 4 - 1}{b-4}$ solutions. So
$$S_1 = \binom{c}{1} \binom{c + b - 4 - 1}{b-4}$$
Similarly, in computing $S_j$, there are $\binom{c}{j}$ ways to choose the variables which violate the constraints, and for each combination of violating variables there are $\binom{c + b -4j -1}{b-4j}$ solutions. So
$$S_j = \binom{c}{j} \binom{c + b -4j -1}{b-4j}$$ for $j = 1, 2, 3, \dots , \lfloor b/4 \rfloor$, and $S_j = 0$ for $j > \lfloor b/4 \rfloor$.
Finally, by the Principle of Inclusion / Exclusion,
$$ N_0 = N - S_1 + S_2 - S_3 + ... + (-1)^{\lfloor b/4 \rfloor} S_{\lfloor b/4 \rfloor}$$
This is the same formula we obtained using generating functions, although written differently.

 

[Lee1]

Hallo awkward and a big THANK YOU!

I was absolutely thrilled over your detailed yet well-structured post that must have cost you a huge effort!

All the more I feel sorry to say: I'm not entirely sure but I fear you solved a different problem than the one I requested (with me having part of the fault for not being able to specify the problem any further).

I think what you calculated is the number of possible combinations to use only a small subset of colors (c) from a much bigger set of colors, did you? For example: We have 50 colorless balls and 100 colors, so how many combinations contain no more than c of these colors?

My request was (or should have been) the following: We have 50 colorless balls and 100 colors, so how many combinations contain no single color on more than three balls at a time? For example: There are three yellow-colored balls and 47 all in different colors then it's a "good combination". But if there are four yellow-colored balls" and anything else then it's a "bad combination" we don't want.
Further examples:
Blue-Blue-Blue-Green-Green-Green-Red-Red-Red-Black-Black-Black-Pink-Orange-... is fine as it contains no color more than three times.
Pink-Pink-Pink-Pink-Pink-Brown-Brown-Brown-Brown-Brown-Brown-Red-Yellow-Blue-... is not as it contains 5x Pink and 6x Brown which both violate the rule of having no more than 3 of a kind.

I strongly hope I did only misinterpret your calculation but I failed to get my test result of 155 (--> start post) so far and got further confused by your sentence "We want to count the number of ways to paint the balls using no more than 3 of the c colors".

I'm truly sorry if it was my bad description that caused this possible mistake.In the case that no such mistake has happened at all, I would request some further help as I can't manage to receive my "155" by using your formula. I used the S₁= one. Putting in the numbers from my first post (c = 5, b = 8), I receive the following:

S₁ = {5 \1 } {5 + 8 - 4 - 1 \8 - 4 } = {5 \1 } {8 \4 } = 350 \ne 155

Did I do anything wrong here?

 

[awkward]

Manuel,

I think you may be misinterpreting some mathematical notation. The notation $\binom{n}{m}$ means the number of ways to pick m objects from a set of n objects, which is
$$\frac{n!}{m! (n-m)!}$$

I think if you work out your example of 8 balls and 5 colors, you will find the formula given above does result in 155.

$$\binom{5}{0} \binom{5+8-1}{8} - \binom{5}{1} \binom{5+4-1}{4} + \binom{5}{2} \binom{5 + 0 -1}{0} = 1 \times 495 - 5 \times 70 + 10 \times 1 = 155$$

 

[Lee1]

Hi, awkward,

you're right, thanks! I feel relieved that the misunderstanding was on my side.
Now that I see how it is done I can finally start calculating and then start my blog entry. If you're interested in what it is even used for, here is a small offtopic explanation:

Spoiler

Magic cards. I want to write a blog entry on the math and complexity behind deck building with currently more than 14,000 cards available. The "three of a kind" refers to the "four of a kind" rule in deck building. I just changed it to 3 for various reasons.
Since I place high value on "doing it right" and also being the perfectionist I am I wanted to get my numbers correct. It may seem "over the top" for the actual use but the math behind this could also be used in some calculator in the future even though I first want to use it for illustration purposes only.
Magic the Gathering is a very mathematical and statistical card game and so some interested players are always looking for more tools to calculate stuff. Even if it doesn't help too much in the actual game it is still pretty impressive or interesting to count and calculate certain things.
I myself am very interested in math, however I'm an amateur. I wish I could've done all this by myself but I soon noticed this would exceed my skills. Having seen your terms now I have to say I was correct about this.
I did lots of research but couldn't find anything that would've helped me with my question. I wondered how this was possible as the general idea behind this formula isn't overly complex or abstract. Some people must have done this before. Yet I didn't even know what to look for.

You helped me quite a lot but may I ask you for two further modifications of the formula?

1) We have c colors. Let c be 100 again. Out of these 100 colors there are u colors that can only appear once (on one single ball) other than the rest of the colors that can appear on up to three balls each. Let u be 3.
Please note: The identity of each color (whether it belongs to u or c) is fix. So let's say red, blue and green balls can only appear once each. The other 97 colors can each appear up to three times. This is set. There is no switching around. I do not need to know the number of combinations for any possible u/c-distribution (like if brown belonged to u and so on). So it's actually more like a "97 + 3" colors thing while each group has its own rules.

2) Same as 1) but instead of u which reduces the number down to 1 we use q which increases the number to b (number of balls). Let q be 3. This means 97 colors can only appear zero times, once, twice or as a three of a kind whereas q (three) colors can appear multiple times up to the number of balls (like 50 pink balls out of a total of 50 balls in an extreme case).
Please note: Same as above.

If you're willing to help me one last time, I want to thank you in advance - and even more for everything you've done for me so far! I absolutely appreciate your kind help and time you invested for me on this matter! You may feel hugged if you want to. Thank you so much!

Manuel