# Tough combinatorics problem

We have an urn containing $n_a$ tiles labelled "A", $n_b$ ones labelled "B", and $n_c$ tiles labelled "C". We also have a string of letters consisting of $s_a$ occurrences of the letter "A", $s_b$ occurrences of the letter "B" and $s_c$ occurrences of the letter "C". If I draw $j$ tiles at random from the urn, what is the probability that I will be able to match exactly $k$ of them with letters from our string? Also what's the probability that I will be able to match at least $k$ of them with letters from our string?

Edit: When I say "match", I mean that if 3 "A" tiles and 2 "B" tiles are drawn from the urn, and the string contains 1 "A" and 3 "B"s, then I will have matched 1 "A" and 2 "B"s, i.e. I will have matched 3 (=1+2) tiles.

• I need the solution for a project. I've been 16 years out of University and have forgotten how to deal with this. I'm curious first of all whether it's possible to find a solution that is relatively fast to compute on a computer. Also I would be grateful for a few pointers that could point me towards the solution, if one is too tired to write it out explicitly. – alex k Jul 14 '14 at 23:32
• Would you specify what 'match exactly $k$ of them with letters from our string' mean? Suppose we have $a+b+c=j$ where $a$ things of type $A$, $b$ things of type $B$ and $c$ things of type $C$. Then, is $k=a\cdot s_a+b\cdot s_b+c\cdot s_c$ ? – talegari Jul 15 '14 at 5:47
• I'm not sure I understand the question. Could you explain what you mean? – Oria Gruber Jul 15 '14 at 6:07
• @talegari I edited my question to explain what I mean by "match". In your example, k = min(a, $s_a$) + min(b, $s_b$) + min(c, $s_c$) – alex k Jul 15 '14 at 10:18
• I think there is no other way than listing the combinations for the condition and applying the formula for hypergeometric distribution. – gar Jul 15 '14 at 17:12

Here is an outline -- we count the number of possibilities of getting exactly $k$ matches. Suppose we choose $0\le m_a\le n_a$ of type A, $0\le m_b\le n_b$ of type B and $0 \le m_c \le n_c$ of type C where $m_a+m_b+m_c=j$. We say "A overflows" if $m_a>s_a$. We break into four cases:

• None of A, B, C overflow

This is true only if $j=k$. This is given by the coefficient of $x^j$ in the expression $(1+x+\dots +x^{s_a})(1+x+\dots +x^{s_b})(1+x+\dots +x^{s_c})$

• Exactly one them overflows.

Lets suppose that A overflows. If $n_a-s_a\ge j-k$, the coefficient of $x^{k-s_a}$ in the expression $(1+x+\dots +x^{s_b})(1+x+\dots +x^{s_c})$ counts it. We can find similar expressions for B and C.

• Exactly two of them overflow.

Lets suppose that A and B overflow. If $(n_a-s_a)+(n_b-s_b)\ge j-k$ and $0\le k-(s_a+s_b)\le s_c$, we look at the coefficient of $x^{j-k}$ in $(1+x+\dots +x^{n_a-s_a})(1+x+\dots +x^{n_b-s_b})$. We can find similar expressions when A does not overflow and B does not overflow.

• All of them overflow.

Then, $k\ge (s_a+1)+(s_b+1)+(s_c+1)$. This is given by the coefficient of $x^{j-k}$ in $(1+x+\dots +x^{n_a-s_a})(1+x+\dots +x^{n_b-s_b})(1+x+\dots +x^{n_c-s_c})$