Matrix Combination

Question

Given numbers from 1 to n.How many ways we can arrange those numbers into rows and columns so that:

• The number of columns in the row i + 1 is not greater than the number of columns in the row i.
• For every cell, number(i, j) (a cell at row i, column j) is smaller than number(i - 1, j) and number(i, j - 1).
• There's no empty cell between two cells that contain a number.

For example: n = 3 the output should be 4:

1. |3|2|1| 

2. |3|
   |2| 
   |1|

3. |3|2|
   |1|

4. |3|1|
   |2|

For n = 4, the output should be 10:

1. |4|3|2|1|   2. |4|3|2|     3. |4|3|1|      4. |4|3|     5. |4|3|
                  |1|            |2|             |2|          |2|1|
                                                 |1|

6. |4|         7. |4|2|       8. |4|1|        9. |4|2|1|   10. |4|2|
   |3|            |3|            |3|             |3|           |3|1|
   |2|            |1|            |2|
   |1|

My approach is to write those numbers in descending order and consider it as the first row.Then I take 1 number from the first row, start from the 1st column, at put that number in the second row. After that I take 2 numbers from the first row, start from the second column, and put to the second column and so on.But it doesn't work.Please help me to find a recursive way to solve this problem, or a formula to calculate it.

Answer 1

These are equivalent to standard Young tableaux, and if you have n numbers, the number of ways to lay out the number by your rules is defined by a recurrence relation:

a(n) = a(n-1) + (n-1)a(n-2)

with base conditions a(0) = 1 and a(1) = 1.

So, for 3 numbers, as you have:

a(3) = a(2) + 2a(1) = 2 + 2 = 4

For 4 numbers, you get:

a(4) = a(3) + 3a(2) = 4 + 4 * 2 = 10.

You can find a description of standard Young tableau and the recurrence relation to generate them on Wolfram's mathworld at:

http://mathworld.wolfram.com/YoungTableau.html

This question is a duplicate of this question:

Number of Standard Young Tableaux of $n$ cells