Formula for the number of ways to choose $n$ digits from $k$ possible digits such that the selection contains no repeats under permutation

Question

An example to illustrate:

Say I have 3 digits, to be taken from the set $\{1,2,3\}$.

I want to choose from this set of digits, with repetition allowed, to make triplets.

However, no two triplets should be attainable through permutation of the triplet - e.g:

$001$ can be permuted to $010$

$201$ can be permuted to $012$

but $011$ and $001$ are "permutationally independent" (any help on the proper name for this appreciated)

In this case, the set of all possible triplets is $\{000, 001, 011, 111, 002, 022, 222, 012, 112, 122\}$, and there are $10$ possibilities.

How could I have worked out this number without manually enumerating the possibilities? And how could this be done for forming n-tuples from a set of k possible digits?

I have tagged this question with some group theory tags, as am expecting from my own thinking that the answer can probably be quite neatly given in terms of dihedral group actions and orbits, though I may be wrong.

Answer 1

You can use stars and bars (Theorem 2) to count this. For your general "$n$-tuples from a set of $k$ digits" question, it yields $\binom{n+k-1}{n-1}$. In the special case $n=k=3$, this is $\binom{5}{2}=10$, which matches your manual enumeration.

Answer 2

To elaborate more on angryavian’s answer, Your general "$n$-tuples from a set of $k$ digits" question is equivalent to choosing non-negative $x_1$ times of the digit 1, … $x_k$ of the digit k, where sum of all these $x_i$ need to be $n$. Each solution $(x_1,…x_k)$ corresponds to one type of tuples with all its permutations. Total number of tuples is thus the total number of solutions $\binom{n+k-1}{n-1}$.