Write $31$ as the sum of $4$ different numbers from $1$ to $18$

Question

No. of ways of selecting $4$ different numbers from the set $A=\{1, 2, 3, 4, \ldots, 18\}$ whose sum is $31$.

I know combinations with multinomial theorem but here how to eliminate the ways when $2$ or $3$ numbers are repeated?

Answer 1

$$x_1+x_2+x_3+x_4=31 \quad \& \quad x_1, x_2, x_3, x_4 \in A$$ $\implies$ No. of ways $=$ coefficient of $t^{31}$ in $(t+t^2+t^3+\ldots+t^{18})^4$ which equals $\binom {30} 3 - 4\binom {12} 9$ (By Multinomial Theorem).

Here, $\binom {30} 3 - 4\binom {12} 9$ contains selected no.s that can be repeated and are also permuted. I want only selected non repeated for $x_1+x_2+x_3+x_4=31$.

$1$) When any $2$ numbers are repeated (includes the case when $3$ are repeated)

Say, $2x+y+z=31$

$Y+z$ can be $\{29, 27, 25, 23, \ldots, 3\}$. Then, (coefficient of $t^{29}$ +coefficient of $t^{27}$ +coefficient of $t^{25}$ +$\ldots$ +coefficient of $t^3$) in $(t+t^2+t^3+\ldots+t^{18})^2 = 150$ (By Multinomial theorem). But in those $150$, $y$ and $z$ will swap, so $150/2=75$.

$2$) $2x+2y=31$ is not possible

$3$) When any $3$ numbers are repeated, say, $3x+y=31$

$Y=\{1,4,7,10,13,16\}$, i.e., $6$. So $75-6=69$ have only $2$no.s repeated & $6$ have $3$ no.s repeated.

$4$) Clearly, $4x=31$ is not possible.

Now, equating permutations:

$\implies \binom {30} 3 -4\binom {12} 9 = 4!$ (No. of selections with distinct no.s non repeating, i.e., the required answer) $+(69 \binom42 (2!))$ [selecting $2$no.s from $x_1, x_2, x_3, x_4$ when only $2$ no.s are repeated and $2!$ when remaining $2$ are interchanged] $+(6 \binom41 )$ [when any $3$ are repeating]

$\implies \binom {30} 3 -4\binom {12} 9 = 4!$ (Required Answer) $+(69 \binom42 (2!))+24$

Therefore: $\implies$ Required answer ${}= 97$.

Explanation to the very first step:

Co-efficient of t^31 in (t+t^2+t^3+..+t^18)^4 i,e t^4((t^18)-1)^4/(t-1))^4 = t^4((t^18)-1)^4(1-t)^(-4) (By the sum of gp) t^4(t^72-4t^54+6t^36-4t^18+1)(1-t)^(-4)

Now, (1-t)^(-4)=1+(4C1)t+(5C2)t^2+(6C3)t^3+ ... (By negative index)

Therefore, Co-efficient of t^31 = Co-efficient of t^27 in (1-t)^(-4) - 4(Co-efficient of t^9 in (1-t)^(-4)) = ((4+27-1)C(27)) - 4((4+9-1)C(9))= (30C3) - 4(12C9).