Lesson 1

• How many non-negative integer solutions are there to the equation \(x_{1}+x_{2}+\dotsb+x_{n}=k\)?


• How many ways are there to distribute \(k\) identical coins to \(n\) distinct people?

Of course, this is the same problem: \(x_{i}\) is simply the number of coins we give to the \(i\)-th person. Such methods are called combinations with repetitions: we again want to choose \(k\) elements from an \(n\)-element set, but now the selected elements can repeat. The order still doesn't matter. In other words, now we want to choose not a \(k\)-set, but a \(k\)-multiset. That is, to define such a combination, for each element \(1 \le i \le n\), we need to specify how many times we take it: \(\sum_{i=1}^{n}x_{i}=k\).

from itertools import combinations_with_replacement

for c in combinations_with_replacement('abc', 5):
    print(*c, sep='')

aaaaa
aaaab
aaaac
aaabb
aaabc
aaacc
aabbb
aabbc
aabcc
aaccc
abbbb
abbbc
abbcc
abccc
acccc
bbbbb
bbbbc
bbbcc
bbccc
bcccc
ccccc