Number of unique sequences up to permutation

Question

If I have a set of $n$ natural numbers, how many ways are there to form sequences of length $p$ from those numbers such that the sequences are unique up to permutation.

For example, the unique sequences for $p=4, n=3$:
1111, 1112, 1113, 1122, 1123, 1133, 1222, 1223, 1233, 1333, 2222, 2223, 2233, 2333, 3333

in the $p=3, n=5$ case:
111, 112, 113, 114, 115, 122, 123, 124, 125, 133, 134, 135, 144, 145, 222, 223, 224, 225, 233, 234, 235, 244, 245, 255, 333, 334, 335, 344, 345, 355, 444, 445, 455, 555.

I now believe that whatever it is should be be given by a sum of the form $$\sum_{x_1=1}^p\dots\sum_{x_n=x_{n-1}}^p1$$ Are there easy closed forms for this sum? Is there a name for it? Any info?

Answer 1

Hint:

You have $p$ tokens to place in $n$ boxes labelled from $1$ to $n$.

Put your $p$ tokens in a row

$$\underbrace{\bullet \ldots \bullet\ldots \bullet\ldots \bullet}_\limits{p}$$

Then choose where you split this sequence - where you put the separators between boxes. $n$ boxes means $n-1$ separators. Therefore the answer is...

Answer 2

Let $S=\{1,...,n\}$.

Up to a permutation of the terms, a $p$-term sequence of elements of $S$ is completely determined by the counts $x_1,...,x_n$, where $x_i$ is the number of times the value $i$ occurs in the sequence.

Thus, the number of such sequences is the same as the number of $n$-tuples $(x_1,...,x_n)$ of nonnegative integers satisfying $$x_1 + \cdots + x_n=p$$ which, by the stars-and-bars formula is $$\binom{p+n-1}{n-1}$$

As an example, for the case $p=4,\;n=3$, the formula yields $$\binom{4+3-1}{3-1}=\binom{6}{2}=15$$ which matches your direct count.