Number of Possible Tables

99 Views Asked by At

A table of size $10$ x $5$ is defined with the following constraints.

  1. A table entry must contain exactly one of these five alphabets $\{a,b,c,d,e\}$.
  2. Each alphabet must appear exactly once in each row.
  3. Each alphabet must appear exactly twice in each column.

Question: What are the number of possible tables?

Following is an example of such a table: $$a \quad b \quad c \quad d \quad e $$ $$a \quad b \quad c \quad e \quad d $$ $$b \quad c \quad d \quad a \quad e $$ $$b \quad c \quad d \quad e \quad a $$ $$c \quad d \quad e \quad a \quad b $$ $$c \quad d \quad e \quad b \quad a $$ $$d \quad e \quad a \quad c \quad b $$ $$d \quad e \quad a \quad b \quad c $$ $$e \quad a \quad b \quad d \quad c $$ $$e \quad a \quad b \quad c \quad d $$

I came across this subproblem while programming a question. Any ideas/hints are much appreciated. Thanks!

1

There are 1 best solutions below

5
On

With the extra restriction that all rows need to be distinct, I calculated the total number of tables to be $40182486220800 \approx 4\cdot10^{13}$.

For this I wrote a program which enumerates all tables in 'canonical form': the first row is $abcde$ and the rows are in lexicographic ordering (implying the first column is $aabbccddee$). This lead to $922768$ tables. Now for each canonical table we can generate $5!\cdot9!$ distinct tables by first permuting the columns, and then permuting all non-first rows. On the other hand, the reversal of this process assigns exactly one canonical table to each table. Therefore the total number of tables is $922768 \cdot 5! \cdot 9!$.

I made a similar calculation on the number of canonical tables, allowing equal rows. I adjusted the number of distinct permutations of the rows according to the amount of equal rows in the current table. If I made no mistakes, this gives $41376005798400 \approx 4.1\cdot10^{13}$ distinct tables.