A $6$ digit number is set whereby every digit can be repeated without any constraints. So one can have a number between $000001$ and $999999$. (Zeros on the left are counted).
The problem: Generate all possible patterns by translating the numbers into characters.
The constraints: - Letters used are only $a,\ b,\ c,\ d,\ e,$ and $f$.
So the pattern can range between $aaaaaa$ and $abcdef$.
Characters should run systematic order
The first character is always "$a$"
So the number $454657$ is translated to $abacbd$ or $123456$ is translated to $abcdef$. ($c$ Can't exist if there is no $b$ and $d$ can't exist if there is no $b$ and $c$) What do we call these types of permutations? How is it calculated? How can I get the equation? Please help.
Let S(n, r) be the number of patterns with n characters and r distinct characters. We wish to find a explicit formula for sum of all S(n,r) for given n and varying r. Let this sum be B(n).
We first construct the recurrence relation:
S(n, r) = S(n-1, r-1) + rS(n-1, r).
This is because for a pattern with n characters and r distinct characters we can consider if the last character was distinct from all the rest or not, giving rise to the two cases.
With the equation, we note that this is exactly the recurrence relation (with same boundary conditions) as Stirling numbers of the second kind: http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind
and that the sum S(n) is given by the Bell numbers: http://en.wikipedia.org/wiki/Bell_number
Going back to the question, the answer would be B(6) = 203 (the 7th Bell number)