How many 90 ball bingo cards are there?

Question

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?

Answer 1

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.

Answer 2

I would start by listing the ${9 \choose 5} = 126 $ row layouts between blanks and numbers. Then three loops over those 126 is a total of $126^3=2,000,376$ to find all the legal patterns of blanks. For each legal pattern, you can calculate the number of ways to fill it with numbers, for example if there are three numbers in the first column, there are ${9 \choose 3}=84$ ways to fill in those numbers. It shouldn't take a computer long, but I don't know an approach that will work by hand.

Answer 3

Much less elegantly than mjqxxxx, I arrived at the count of unnumbered cards by listing them.

Consider each column to have a defining number between 0 (no numbers) and 7 (all three). Subject to the limitation that each row has five numbers and no column has none, they extend from {7,6,6,6,6,1,1,1,1} to {1,1,2,2,4,4,7,7,7}, with a total of 735,210, the same result as above.

My answer for the numbered cards is a little different, though. For the first pattern, there are (in Excel-speak),

=PRODUCT(COMBIN({9,10,10,10,10,10,10,10,11}, {3,2,2,2,2,1,1,1,1})) = 3,788,977,500,000 possibilities.

Summing that result for each row, I get 3,669,688,706,215,250,000 for the count of numbered cards, which agrees to the first 14 digits with the prior result.

But I'm an Excel guy, not a mathematician.

EDIT: And the difference is the result of running out of precision in a Double, sorry.

Answer 4

Unless I've missed something rather obvious, working out the number and actual valid layouts of blanks is rather easy using perl. Not a mathematical solution I know, but someone might be interested.

Consider a line which is 9 boxes long and set blanks as zeros and a box with a number in it as a 1 and think of this as a 9 bit number. This number is valid so long at it has 5 bits set to '1'. So 4 blanks followed by 5 numbers is 000011111 or 31 in decimal and at the other end it's 111110000 or 496 decimal. A simple bit of perl code will show you all the possibilities for one line:-

sub size3 {
my $x = shift;
unpack '%32b*', pack 'I', $x;
}

$count=0;
for($row=0;$row<512;$row++){
   if (size3($row) == 5 ){
      $array[$count]=$row;
      $count++;
      print "$row\n";
   }
}

The size3 subroutine just counts the number of bits set to '1' in the number. I found this sometime ago on the internet but can not remember the original author for which I apologise.

So we now need to loop though all the possibilities 3 times (one per row) to get all the possible combinations (including invalid ones).

for ($item=0;$item<$count;$item++){
   for ($item2=0;$item2<$count;$item2++){
      for ($item3=0;$item3<$count;$item3++){

However this ignores the requirement not to have any blank cols. i.e. cols which have 3 blank boxes.

By masking off each bit of each row starting with the most or least significant we just count the number of bits set to '1' for each bit position in each row.

$val1=size3($array[$item] & 0b100000000) + size3($array[$item2] & 0b100000000) + size3($array[$item3] & 0b100000000);

and repeat for each of the other 8 bit locations:

     $val2=size3($array[$item] & 0b010000000) + size3($array[$item2] & 0b010000000) + size3($array[$item3] & 0b010000000);
     $val3=size3($array[$item] & 0b001000000) + size3($array[$item2] & 0b001000000) + size3($array[$item3] & 0b001000000);
     $val4=size3($array[$item] & 0b000100000) + size3($array[$item2] & 0b000100000) + size3($array[$item3] & 0b000100000);
     $val5=size3($array[$item] & 0b000010000) + size3($array[$item2] & 0b000010000) + size3($array[$item3] & 0b000010000);
     $val6=size3($array[$item] & 0b000001000) + size3($array[$item2] & 0b000001000) + size3($array[$item3] & 0b000001000);
     $val7=size3($array[$item] & 0b000000100) + size3($array[$item2] & 0b000000100) + size3($array[$item3] & 0b000000100);
     $val8=size3($array[$item] & 0b000000010) + size3($array[$item2] & 0b000000010) + size3($array[$item3] & 0b000000010);
     $val9=size3($array[$item] & 0b000000001) + size3($array[$item2] & 0b000000001) + size3($array[$item3] & 0b000000001);

The three rows are then valid only if all these values ($val1 through $val9) are greater than zero.

The full code (not optimal or using strict syntax, I know!) is :-

#!/usr/bin/perl
my @array;

sub size3 {
my $x = shift;
unpack '%32b*', pack 'I', $x;
}

$count=0;
for($row=0;$row<512;$row++){
   if (size3($row) == 5 ){
      $array[$count]=$row;
      $count++;
   }
}

$count2=0;
for ($item=0;$item<$count;$item++){
   for ($item2=0;$item2<$count;$item2++){
      for ($item3=0;$item3<$count;$item3++){
         $val1=size3($array[$item] & 0b100000000) + size3($array[$item2] & 0b100000000) + size3($array[$item3] & 0b100000000);
         $val2=size3($array[$item] & 0b010000000) + size3($array[$item2] & 0b010000000) + size3($array[$item3] & 0b010000000);
         $val3=size3($array[$item] & 0b001000000) + size3($array[$item2] & 0b001000000) + size3($array[$item3] & 0b001000000);
         $val4=size3($array[$item] & 0b000100000) + size3($array[$item2] & 0b000100000) + size3($array[$item3] & 0b000100000);
         $val5=size3($array[$item] & 0b000010000) + size3($array[$item2] & 0b000010000) + size3($array[$item3] & 0b000010000);
         $val6=size3($array[$item] & 0b000001000) + size3($array[$item2] & 0b000001000) + size3($array[$item3] & 0b000001000);
         $val7=size3($array[$item] & 0b000000100) + size3($array[$item2] & 0b000000100) + size3($array[$item3] & 0b000000100);
         $val8=size3($array[$item] & 0b000000010) + size3($array[$item2] & 0b000000010) + size3($array[$item3] & 0b000000010);
         $val9=size3($array[$item] & 0b000000001) + size3($array[$item2] & 0b000000001) + size3($array[$item3] & 0b000000001);
         if ( ($val1 >0 ) && ($val2 >0 ) && ($val3 >0 ) && ($val4 >0 ) && ($val5 >0 ) && ($val6 >0 ) && ($val7 >0 ) && ($val8 >0 ) && ($val9 >0 ) ) {
             printf("%09b\n%09b\n%09b\n ---------\n", $array[$item],$array[$item2],$array[$item3]);
            $count2++;
         }
      }
   }
}
print "$count2\n";

Which prints out each solution and the total count of solutions which is 735210.

The start (or end, depending how you look at it) of the sequence is:-

000011111
000011111
111100001
---------
000011111
000011111
111100010
---------
000011111
000011111
111100100
---------

I doubt that you'll ever see these layouts in use in real life, so there must be a rule missing concerning valid layouts not presented here.

Now it's a rather trivial task to sequence through the actual number groups 1-9 10-19 20-29 30-39 40-49 50-59 60-69 70-79 80-90 in numerical order through the respective cols where the bit is set to '1' each time in order to not only count the solutions but display them as well.

I won't present that here as my main point is that by modelling the layout problem as three sets of binary numbers and the rules as simple counts of the number of bits set to '1' in both rows and cols simplifies the problem programatically.

I've written this at gone 2am so there might be a few mistakes in here but the method is sound.