Suppose that you’ve picked a legitimate set $A=\{a_1,a_2,a_3,a_4\}$, where $a_1<a_2<a_3<a_4$. Let $b_1=a_2-a_1$, the size of the gap between $a_1$ and $a_2$. Similarly, let $b_2=a_3-a_2$ and $b_3=a_4-a_3$. If you know the numbers $b_1,b_2$, and $b_3$, you almost know $A$. You would know $A$ if you also had $a_1$; then you could recover the whole lot:
$$\begin{align*}
a_1&=a_1\\
a_2&=a_1+b_1\\
a_3&=a_1+b_1+b_2\\
a_4&=a_1+b_1+b_2+b_3
\end{align*}$$
Now we know how to count the integer solutions to equations of the form $x_1+\ldots+x_m=n$, even subject to various conditions on the $x_k$, so it would be nice to be able to recast this problem in such terms. We’re not there yet, because $a_1+b_1+b_2+b_3$ doesn’t have to be a particular number. However, we could use another number, $b_4$, to measure the size of the gap from $a_4$ to $10$, the maximum possible value, by setting $b_4=10-a_4$. Now we know that $a_1+b_1+b_2+b_3+b_4=10$, and all four members of $A$ are recoverable from these five numbers.
Your instructor made one further small modification: instead of using $a_1$ directly, he used $a_1-1$, calling it $b_0$. You can think of $b_0$ as the gap between $1$, the lowest possible value, and the actual value of $a_1$. Notice that $b_0+b_1+b_2+b_3+b_4=(a_1-1)+b_1+b_2+b_3+b_4=10-1=9$, and that we can recover $A$ just as well from $b_0,b_1,b_2,b_3,b_4$ as from $a_1,b_1,b_2,b_3,b_4$:
$$\begin{align*}
a_1&=1+b_0\\
a_2&=1+b_0+b_1\\
a_3&=1+b_0+b_1+b_2\\
a_4&=1+b_0+b_1+b_2+b_3
\end{align*}$$
(We don’t need $b_4$ to reconstruct $A$; it’s there to make the sum a known constant.)
Thus, there is a bijection between $4$-element subsets $A$ of $\{1,\dots,10\}$ satisfying the condition that no two members are consecutive, and ordered $5$-tuples $\langle b_0,b_1,b_2,b_3,b_4\rangle$ of integers satisfying the equation $$b_0+b_1+b_2+b_3+b_4=9\tag{1}$$ together with the conditions $b_1,b_2,b_3\ge 2$ (to ensure that no two members of $A$ are consecutive), $b_0\ge 0$ (to ensure that $1$ is the smallest possible value of $a_1$), and $b_4\ge 0$ (to ensure that $10$ is the largest possible value of $a_4$.
Now the fact is that I wouldn’t use generating functions to count the number of solutions to $(1)$ subject to the given constraints. This is a bog-standard stars-and-bars problem that can be solved immediately by the technique explained in the article to which I linked. Because I think that the idea is a useful one to understand, I’ll give my own explanation here. Imagine that I have $9$ indistinguishable marbles and five boxes, labelled $B_0$ through $B_4$, and I want to count the number of distinguishable ways to put the $9$ marbles into the $5$ boxes. If you think of $b_k$ as representing the number of marbles in box $B_k$, you can see that the answer is the same as the number of solutions of $(1)$ in non-negative integers. Ah, but I’m required to have at least $2$ marbles in each of boxes $B_1,B_2$, and $B_3$. No problem: I just put $2$ marbles into each of those boxes right away, leaving myself with just $9-6=3$ marbles to distribute as I please amongst the $5$ boxes. (By the way, this shows that the number of solutions of $(1)$ that meet the stated conditions is the same as the number of solutions of $$b_0+b_1+b_2+b_3+b_4=3\tag{2}$$ in non-negative integers.) From here on I’ll simply ignore the $6$ required marbles and look at the number of ways of distributing the other three.
Draw a schematic of the boxes: instead of drawing the boxes themselves, draw the boundaries between them, representing them by vertical bars, $|$: $$|\;|\;|\;|\;.$$ The spaces between the bars, before the first bar, and after the last bar represent the five boxes. If I represent the marbles by $o$’s, I can symbolize the arrangement with two marbles in the first box and one in the third by $$oo||o||\;.$$ Each possible distribution of the three marbles corresponds to a unique string of three $o$’s and four $|$’s, and each string of three $o$’s and four $|$’s corresponds to a unique distribution of the three marbles. Thus, the number of solutions to $(2)$ in non-negative integers, and hence the number of solutions to $(1)$ that meet the extra conditions, is simply the number of strings of four $|$’s and three $o$’s. This is just the number of ways of choosing which $3$ of the $7$ positions in the string are to be $o$’s, so it’s $\binom73$. (Or, if you prefer, it’s the number of ways of choosing which $4$ of the $7$ position in the string are to be $|$’s, which is $\binom74$; of course these are the same.)
If you use generating functions directly on $(1)$, it works like this. The possible values for $b_0$ and $b_4$ are $0,1,\dots$, while those for $b_1,b_2$, and $b_3$ are $2,3,\dots$. These are the exponents on the terms of $\sum\limits_{n\ge 0}x^n$ and $\sum\limits_{n\ge 2}x^n$, respectively. We know that formally $$\sum_{n\ge 0}x^n=\frac1{1-x}\;,$$ so $$\sum_{n\ge 2}x^n=x^2\sum_{n\ge 0}x^n=\frac{x^2}{1-x}\;.$$ Let $$g(x)=\left(\sum_{n\ge 0}x^n\right)^2\left(\sum_{n\ge 2}x^n\right)^3=\frac{x^6}{(1-x)^5}\;;$$ this is the desired generating function.
To see what this means, imagine multiplying out the summations:
$$(1+x+x^2+x^3+\ldots)^2(x^2+x^3+x^4+\ldots)^3=x^6(1+x+x^2+x^3+\ldots)^5\;.$$
When you’ve collected terms, the coefficient of $x^9$ will be the number of products that produced $x^9$: $x^6\cdot x^0\cdot x^0\cdot x^0\cdot x^0\cdot x^3$, $x^6\cdot x\cdot x^0\cdot x^0\cdot x^2\cdot x^0$, etc. Each of these corresponds to one solution of $(1)$. For instance, the two that I just listed correspond to $$0+2+2+2+3=9$$ and $$1+2+2+4+0=9\;,$$ respectively. Thus, the answer to the question is simply the coefficient of $x^9$ in $$g(x)=\frac{x^6}{(1-x)^5}\;.$$ This is the coefficient of $x^3$ in $$\frac1{(1-x)^5}=(1+x+x^2+x^3+\ldots)^5\;,$$ which is the same as the coefficient of $x^3$ in $$(1+x+x^2+x^3)^5\;,$$ since the higher powers of $x$ can’t contribute to an $x^3$ term. You can go ahead and work out this coefficient by direct calculation, though it’s a bit tedious.
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$ :
- If it start with $1$ , then we must find the number of digits of lenght $3$ , it can be found by E.G.F such that $$3!\times [x^3]\bigg(1+\frac{x^1}{1!}+\frac{x^2}{2!}\bigg)^3 \bigg(1+\frac{x^1}{1!}\bigg)$$
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.
Best Answer
If it is NOT TRUE that all members of a set of numbers are $\ge15$, that's equivalent to saying at least one of them is less than $15$, not that all of them are less than $15$.