2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – JMoravitz Feb 27 '17 at 19:45
  • $\begingroup$ What you refer to as subsets of size $N$ seem actually to be multisets. $\endgroup$ – hardmath Feb 27 '17 at 19:47
1
$\begingroup$

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\}$)"

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.