Unique $k$ tuples from a population of $n$ types

Question

(The inspiration of the problem is here.)

Suppose there are $n$ types of, say, marbles $1,\ldots,n$. How many unique $k$-tuples are there? For convenience, let $S(n,k)$ be the answer.

Ordering within a tuple doesn't matter. For example, with $k=3$ and $n=3$, we have $S(3,3)=10$: $$ (1,1,1)\\ (1,1,2),\quad(1,1,3),\\ (1,2,2),\quad(1,2,3),\quad(1,3,3),\\ (2,2,2),\quad(2,2,3),\quad(2,3,3),\quad(3,3,3). $$ (Here, $(1,1,2)$, for example, denotes a tuple consisting of two marbles of type 1 and one marble of type 2.)

Maybe we can do induction on $k$ for any fixed $n$?

Answer 1

This is a stars and bars problem. We can express it as the number of ways to place $k$ indistinguishable balls in $n$ buckets. For example, if $n=4$ and $k=3$ then putting $2$ ball ins bucket $1$ and 1 in bucket $4$ corresponds to the tuple $(1,1,4).$

The number of ways to do this is well-known to be $${n+k-1\choose n-1}$$

Answer 2

It's not a closed form expression or a generalization but an idea:

When we have $k$-tuples, let us find the partitions of $k$. For example, for $k = 3$, we have

• $3$
• $2+1$
• $1+1+1$

Now let each number in summation represent the "# of repeated marbles". For example we include $(1,1,1)$ to the partition $3$ while $(1,1,2)$ and $(1,2,2)$ should be included to $2+1$. Then for $n = 3$, $k = 3$ case, we have in total

$$\binom{3}{1}+\binom{3}{1}\binom{2}{1}+\binom{3}{3} = 10$$

tuples where $\binom{3}{1}$ is the number of ways of choosing the elements of partition $3$, $\binom{3}{1}\binom{2}{1}$ is number of ways of choosing the two times repeated element (for example, for $(1,1,2)$ it is $1$) and one non-repeated element (it is $2$ in the same example) of partition $2+1$ and $\binom{3}{3}$ is number of ways of choosing $3$ different elements of partition $1+1+1$.