Exercise** **How many shapes of `m`
by `n` row echelon forms are there?

Answer By the previous exercise,
the shapes of row echelon forms can be counted by the pivot columns, which are some numbers between 1 and `n`. For example, the row echelon form

[ | * | # | # | # | ] |

0 | 0 | * | # | ||

0 | 0 | 0 | 0 |

corresponds to the numbers {1, 3}, which means that [col 1] and [col 3] are pivot columns. Thus we
count the number of ways of choosing no more than `m` numbers from {1, 2, ..., `n`}. The total number is

`C`(`n`,0) + `C`(`n`,1) + ... + `C`(`n`, min{`m`,`n`})

where `C`(`n`,`s`) = `n`!/`s`!(`n`-`s`)!
is the number of ways of choosing `s` numbers from {1, 2, ..., `n`}.