Let $A$ be the set of all natural numbers whose digits are in the multiset $\{1^2,2^2,3^2,4^2\}$ (each digit can appear at most twice). Let $B$ be the set of all the $4$ digit numbers from $A$. Compute $\sum_{n\in B}n.$
Just in case, I found the generating function for the $4-$ combinations of $\{1,2,3,4\}$ with the given restriction and $|B|$:
$\begin{aligned}f(x)&=(1+x+x^2)^4\\&=\left(\frac{1-x^3}{1-x}\right)^4\\&=(1-x^3)^4(1-x)^{-4}=(1-4x^3+6x^6-4x^9+x^{12})\sum_{k=0}^\infty\binom{-4}k(-x)^k\\&=(1-4x^3+6x^6-4x^9+x^{12})\sum_{k=0}^\infty\binom{k+3}kx^k\end{aligned}$
We need the coefficient $\langle x^4\rangle$ next to $x^4$:
$|B|=\langle x^4\rangle=\binom{4+3}4-4\binom{1+3}1=19.$
I don't think this helps, though.
I've seen a somewhat related answer by Marc van Leeuwen and thought about imitating it, but I would either have to apply the following approach to every single $4$ permutation of$\{1,2,3,4\}$ with the given restriction or consider the sequence $(a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8)=(1,1,2,2,3,3,4,4)$ and look at the first $4$ digits in each permutation, but I quit from the latter as I would overcount even more possibilities because some of the arrangements might appear in the other half of the each sequence I get.
In the linked answer, the number formed from a sequence obtained by a permutation of the initial sequence $(a_1,\ldots,a_6)$ is written in the form $$\sum_{i=0}^5a_{\sigma(i)}10^{i}$$ hence the sum is $$\sum_{\sigma\in S_6}\sum_{i=0}^5a_{\sigma(i)}10^i,$$ but repetitions lead to some numbers being counted as many times as is the product of factoriels of multiplicities od the digits, which is $12$, so the sum is rewriten as $$\sum_{i=0}^510^i\cdot\sum_{\sigma\in S_6}a_{\sigma(i)}=11111\sum_{\sigma\in S_6}a_{\sigma(i)}=12s$$ and further $$\sum_{\sigma\in S_6}a_{\sigma(i)}=\sum_{k=1}^6a_{\color{red}{k}}\sum_{\sigma\in S_6}[\sigma(i)=\color{red}{k}]=\sum_{k=1}^6a_k\cdot\space |S_5|.$$
Then, it can easily be computed. However, I got lost in my task. How should I approach this problem?
Best Answer
For these types of questions , you must use exponential generating functions instead of ordinary generating functions , because the order of numbers does matter.It is said that "each digit can appear at most twice" , so we can write the exponential generating function form of each digits such that $$\bigg(1+\frac{x^1}{1!}+\frac{x^2}{2!}\bigg)$$
About E.G.F
There are $4$ distinct digits , so we must find the coefficient of $[x^4]$ in the expansion of $$\bigg(1+\frac{x^1}{1!}+\frac{x^2}{2!}\bigg)^4$$
and multiply $[x^4]$ by $4!$ , or just find the coefficient of $\frac{x^4}{4!}$.
If you want to find the number of digits of length $n$ , then find the coefficient of $[x^n]$ in the expansion of $$\bigg(1+\frac{x^1}{1!}+\frac{x^2}{2!}\bigg)^4$$
and multiply $[x^n]$ by $n!$ , or just find the coefficient of $\frac{x^n}{n!}$
CALCULATION OF EXPANSION
So , answer is $$4! \times \frac{17}{2} =204$$
According to link , the number of $5$ digits numbers consisting of the given set and obey the restriction is equal to $$5! \times 5 = 600$$
Do you get the idea ?
Now , It is time to find the summation. By using the logic of E.G.F . Lets find the number of digits of lenght $4$ and starting with $1$ :
CALCULATION OF EXPANSION
So , it is $3! \times (17/2)=51$ , we can take it as $1000 \times 51 =51,000$ to find the summations .$51$ is also valid for when it start with $2$ , $3$ or $4$. Then ,
For starting with $2$ : $2 \times 51 \times 1000=102,000$
For starting with $3$ : $3 \times 51 \times 1000=163,000$
For starting with $4$ : $4 \times 51 \times 1000=204,000$
Then , the summation of the digits of thousands is equal to $51,000+102,000+163,000+204,000 =520,000$
Can you calculate the rest ? You will just find for hundredss , tens and ones digits
I think you stuck in finding the number of possible digits , the rest is classical basic summation problem.