[Math] How many 90 ball bingo cards are there

combinationscombinatoricspermutations

In the UK there are 90 bingo balls. A bingo card consists of 9 columns and 3 rows. A row contains exactly five numbers and four blanks. A column consists of one, two or three numbers and never three blanks. The columns are occupied by the number chosen from 1-9 (only nine), 10-19 (ten), 20-29 … 70-79 and importantly 80-90 (eleven). Numbers in columns are ordered from top to bottom.

How many possible unnumbered card layouts are there?

How many possible numbered cards are there?

I have started to approach this problem by first choosing the blanks for the first two rows and then attempting to work out a compensating row. This was hard.

Next I begun to understand that there were a number of equivalence classes as columns could be reordered for the purposes producing different layouts.

Next I looked into the most convoluted card which had five numbers followed by four blanks in the first row and four blanks followed five number in the second. This satisfied the "no blank column" requirement. Now the final row could be arranged however it wanted, though there was one confusing overlap to deal with.

I considered another convoluted card which had as many columns of three as possible. It turns out it's possible have a maximum of three columns of three which also gives rise to the maximum of six columns of one. It also turns out you can have a maximum of six columns of two. I think the starting point might be to determine the classes of card initially by column combinations and then permute them.

Having gotten all muddled by the layouts, I turned to the numbers. With a single number, it was one of 9, 10 or 11 depending on the column and that was easy. For the two number case, let's say with a column of ten, the first ($i$) was chosen from 9 and the next from $10-i$. It suddenly occurred to me that it was just combinations, phew. How to fit that with the whole business of column choice lost me.

It seems possible that for each possible "set" of columns, there will be a way of determining the distribution of possible first columns and adding in an appropriate factor for the number combinations.

Frankly, it's all getting bigger than my coffee table.

Any simplifications from higher maths I'm missing?

Best Answer

Let $N^{(k)}_{a,b,c}$ be the number of possible unnumbered layouts of the last $k$ columns, given that there are $a$ numbers left to assign in the first row, $b$ in the second row, and $c$ in the third row. Given the rules (at least one number per column), you have the recursion $$ \begin{eqnarray} N^{(k)}_{a,b,c}&=&N^{(k-1)}_{a-1,b-1,c-1}+N^{(k-1)}_{a-1,b-1,c}+N^{(k-1)}_{a-1,b,c-1}+N^{(k-1)}_{a,b-1,c-1} + N^{(k-1)}_{a-1,b,c}+N^{(k-1)}_{a,b-1,c}+N^{(k-1)}_{a,b,c-1}, \end{eqnarray} $$ with the boundary conditions that $N^{(0)}_{0,0,0}=1$ and $N^{(k)}_{a,b,c}=0$ unless all indices are between $0$ and $k$. You want to find $N^{(9)}_{5,5,5}$. The following Python function performs the calculation:

def N(a,b,c,k,cache={(0,0,0,0):1}):
   if min(a,b,c)<0 or max(a,b,c)>k:
     return 0
   if not cache.has_key((a,b,c,k)):
     val  = N(a-1,b-1,c-1,k-1)
     val += N(a-1,b-1,c,k-1) + N(a-1,b,c-1,k-1) + N(a,b-1,c-1,k-1)
     val += N(a-1,b,c,k-1) + N(a,b-1,c,k-1) + N(a,b,c-1,k-1)
     cache[(a,b,c,k)] = val
   return cache[(a,b,c,k)]

N(5,5,5,9)
> 735210

The result is below the upper bound of ${{9}\choose{5}}^3=126^3=2000376$ obtained by allowing all-blank columns, as it should be.

For numbered layouts, the recursion is slightly different, because the number of ways to choose the numbers depends on the column. Here, let $m_k$ be the number of allowed numbers in the $k$-th column from the end: $m_1=11$, $m_9=9$, and $m_k=10$ otherwise. In a column with no blanks, there are ${m_k}\choose{3}$ ways to choose the numbers; with one blank, ${m_k}\choose{2}$; and with two blanks, $m_k$. The recursion is therefore $$ \begin{eqnarray} M^{(k)}_{a,b,c}&=&{{m_k}\choose{3}}M^{(k-1)}_{a-1,b-1,c-1}+ {{m_k}\choose{2}}\left(M^{(k-1)}_{a-1,b-1,c}+M^{(k-1)}_{a-1,b,c-1}+M^{(k-1)}_{a,b-1,c-1}\right) \\ && + m_k\left(M^{(k-1)}_{a-1,b,c}+M^{(k-1)}_{a,b-1,c}+M^{(k-1)}_{a,b,c-1}\right). \end{eqnarray} $$ Not unexpectedly, the result here is much larger: $$ M^{(9)}_{5,5,5} = 3669688706217187500. $$ As a sanity check on this result, one might consider the average branching factor for the $15$ numbers in an average unnumbered layout: $$ \left(\frac{M^{(9)}_{5,5,5}}{N^{(9)}_{5,5,5}}\right)^{\frac{1}{15}} \approx 7.023. $$ Since in a typical row (with $m_k=10$) the possible outcomes have average branching factors ${{10}\choose{3}}^{1/3}\approx 4.93$, ${{10}\choose{2}}^{1/2}\approx 6.71$, and $10$, this seems very reasonable.

Note that we can also enumerate the possible unnumbered layouts in an entirely different way, using inclusion-exclusion. The basic idea is to count all the ways of placing $5$ numbers in each of the three rows, then remove the cases with an all-blank column, then add back in the cases with two all-blank columns, and so on: $$ \begin{eqnarray} N^{(9)}_{5,5,5} &=& {{9}\choose{5}}^3 - {{9}\choose{1}}{{8}\choose{5}}^3 + {{9}\choose{2}}{{7}\choose{5}}^3 - {{9}\choose{3}}{{6}\choose{5}}^3 + {{9}\choose{4}} \\ &=& 735210, \end{eqnarray} $$ as above. This is an elegant solution to the unnumbered case, but I do not see a way to extend it to the numbered layouts.

Related Question