How many ways to construct an increasing list given $N^2$ cards There are $N$ people and $N^2$ cards. They are divided into $N$ cards with the number 1, $N$ with the number 2, $N$ with the number 3, and so on. Each person will choose one card and give it back afterwards. How many ways to make a line with $N$ cards such that they are sorted in increasing order For example: 4 will give 35 ways. (1,2,3,4, 2,2,2,4 , 3,4,4,4, ...etc)
The answer I found is $\binom{N + N - 1}{N} \to \binom{2N - 1}{N}$. However, I cannot see the logic behind it?
 A: Since each numbered card is returned after selection, you essentially have an unlimited number of each of  $1,2,3...N$ cards at your disposal.
To keep count of how many times each card has been used, put a counter ("ball") in $N$ numbered bins.
The stars and bars formula gives
$\binom{N+N-1}{N-1} = \binom{N+N-1}{N} = \binom{2N-1}{N}$
A: As others have pointed out, this is a classic stars and bars. However, let's put some combinatorial proof flavor to this.
Imagine you have decks of $1$s, $2$s, ... , $N$s lining up in front of you. At first you pick up the $1$s deck. You need to do one of the following actions; draw a card from the deck in your hand and put it in the line or put the deck in your hand away and pick up the next card deck. By the end of this activity you'd have drawn $N$ cards (thus forming the line you want) and you'd have put $N-1$ decks away and have the $N$s deck in your hand. Notice that you have performed a total of $2N-1$ actions, $N$ of which are drawing cards. Is the number of possible way to do this $\binom{2N-1}{N}$?
