# Number of subsets size N.

So I have a problem where I have a set of ordered objects size N. For example,

A = {1, 2, 3, 4, 5}


How do I find how many ordered subsets there are of A that are size N? For instance, for N = 2, there are four total subsets of size N.

{1, 1}, {1, 2}, {2, 1}, {2, 2}


But when you make the subsets ordered, there are now only three subsets.

{1, 1}, {1, 2}, {2, 2}


For N = 3, there are 27 possible subsets, but 10 ordered subsets. For N = 4, there are 256 possible subsets, but only 34 unique ones. We can see the for a set size N, there are N^N subsets of the set size N. What is the pattern for the number of ordered subsets there are of size N, where the original set is size N?

• Hint: Stars and bars, let $x_1$ be the number of times $1$ appears, $x_2$ the number of times $2$ appears etc... We have $x_1+x_2+\dots+x_N=N$ with each $x_i$ a non-negative integer. – JMoravitz Feb 27 '17 at 19:45
• What you refer to as subsets of size $N$ seem actually to be multisets. – hardmath Feb 27 '17 at 19:47

Viewing this as a problem of stars and bars there are $N$ distinct boxes and $N$ identical balls.
$\binom{2+2-1}{2}=\binom{3}{2}=3$
$\binom{3+3-1}{3}=\binom{5}{3}=10$
$\binom{4+4-1}{4}=\binom{7}{4}=\color{red}{35}$ (you must have missed one when you were counting by hand, remember counting by hand is usually a terrible idea)
In general there are $\binom{2N-1}{N}$ objects that you describe.
I say "objects" because what you describe are not technically sets, subsets, or ordered sets. A more correct phrase would be ordered multisets, but I would prefer to just call them "monotonic increasing sequences of length $N$ (with each entry taken from $\{1,2,\dots,N\}$)"