Combinations of N letters from an alphabet of N different letters

877 Views Asked by At

I'm trying to determine the number of combinations of $N$ letters from an alphabet of $N$. For instance for $N = 2$, with alphabet $(A, B)$, I can obtain $AA$, $AB$ and $BB$, $BA$ and $AB$ are the same combination so they only count for one. For $N = 3$, with alphabet $(A, B, C)$, the result I obtain is $10$. I have a procedure starting from the number of partitions I can get for $N$, summing the combinations $C(N,e)$ where $e$ is the number of elements in the partition, and multiplying each combination by the factorial of the different arrangements in the partition. However, I can't find a more general formula, if there is any.


EDIT: To further illustrate, here is the case for N = 3. The three letters are taken out of the set $(A,B,C)$, which gives the following combinations: $AAA$, $BBB$, $CCC$, $AAB$, $AAC$, $BBA$, $BBC$, $CCA$, $CCB$, $ABC$.

1

There are 1 best solutions below

5
On BEST ANSWER

It seems to me that you're looking for combinations with repetition:

$$\left(\binom{n}{k} \right) = \binom{n-1+k}{k} \ .$$

Edit: In general, this formula allows somebody to compute the number of ways that we can place $n$ objects in $k$ places, where repetition is allowed and, thus $k$ does not have to be less than $n$ as in the usual combinations.

In this specific question, we would have:

$$\left(\binom{N}{N} \right) = \binom{N-1+N}{N} = \frac{(2N-1)!}{N!(N-1)!} \ .$$

For $n=1,2,3,4,5\ldots$ we have as result $1,3,10,35,126\ldots$, which is OEIS sequence A088218 (similar to OEIS sequence A001700).