This is called an extended multiplication table since it contains a "traditional" multiplication table inside it. The 12-extended table below contains a traditional 3x3 multiplication table.

It turns out that 1 appears in an extended table once, and prime numbers appear exactly twice (once in the first column, and once in the first row). In general, for a natural number n, how many times does n appear in the n-extended table?

Before looking at that question, you might want to think about finding easier ways to draw the tables. Drawing out these tables by hand can be tedious - a simple program or spreadsheet might be easier. You can use Fathom, for example, to create the table data and draw it in the collections display. Create a slider m and the attributes listed in the table below (click on the image to see a larger version).

Modify the collection display attributes to draw the tables in the collection box. By adding lots of cases and using the slider m to filter out the ones you don't need, you can vary the size of the table easily.

Interestingly, the answer to the question "how many times does n appear in the n-extended table?" is the same as the answer to the question posed in a previous post about factor lattices.

# of occurrances of n in the n-extended table = # of nodes in the factor lattice Fn

You can also recast both of these questions (how many occurances of n in the n-extended table, and how many nodesin the Fn factor lattice) as a combinatorial "balls in urns" problem.

Consider a set of colored balls where there are m different colours, where there are ki balls of color i, where i ranges from 1 to m. This would give a total number of balls equal to k1+k2+...+km. Suppose you were to distribute these balls in two urns. How many different distributions would there be? Using some counting techniques, you will find that the answer is (k1+1)*(k2+1)*...*(km+1).

How is this connected to the other problems? Consider the prime factorization of the number. For each prime, choose a colour, and for each occurance of the prime in the factorization, add a new ball of that color. For example for 12 = 3*3*2, choose two colours - say blue=3 and red=2. Since 3 occurs twice and 2 occurs once, there should be two blue balls and one red ball. Now consider distributing these balls in two urns. It turns out that you get (2+1)*(1+1) = 6 possibilities. This is the same number of times 12 occurs in the 12-extended table, and the same number of nodes in the 12-factor lattice. The image below shows the 12-extended table, the 12-factor lattice, and the "ball and urn problem" for the numer 12.

For a number n with the prime factorization:

The answer to all three questions is given by:

## No comments:

## Post a Comment