You have 4 letters abcd.
How many 4-letter strings can you write with them?
Assumptions:
– the order is not important (aaab, abaa, baaa are same, counts 1)
– you can use same letter more than once (aaaa, aabb, etc.)
I don't want to find solution with brute force, but with some meaningful calculation.
Best Answer
As Gerry Myerson pointed out, what you are asking is equivalent to asking how many solutions there are to the equation $$x_1 + x_2 + x_3 + x_4 = 4$$ in the non-negative integers, where $x_1$ represents the number of $a$'s in the string, $x_2$ represents the number of $b$'s, $x_3$ represents the number of $c$'s, and $x_4$ represents the number of $d$'s. The number of solutions of this equation is the number of ways we can insert three addition signs in a list of four ones. For instance, $$1 1 + + 1 + 1$$ corresponds to the solution $x_1 = 2$, $x_2 = 0$, $x_3 = 1$, and $x_4 = 1$, while $$+ 1 + 1 + 1 1$$ corresponds to the solution $x_1 = 0$, $x_2 = 1$, $x_3 = 1$, and $x_4 = 2$. The number of solutions is thus the number of ways of selecting three addition signs from $4 + 3 = 7$ symbols, which is $$\binom{4 + 3}{3} = 35$$ Using similar reasoning, you can show that the number of solutions of the equation $$x_1 + x_2 + \cdots + x_k = n$$ in the non-negative integers is $$\binom{n + k - 1}{k - 1}$$