Length of this expression can take in positive integers including 0

Question

$f(x,y,z) = 5x+6y+8z$ such that $x,y,z>=0$ (numbers) , and f(x,y,z) max is 160 ,we need to find total no possible values this expression $f(x,y,z)$ takes less than than 161 with all x,y,z greater equal to zero and x+y+z max is 20 . ( I encountered this while trying to solve for total number of distinct terms in the expansion of $(1 +3x^5 +4 x^6 + 5x^8)$$^{20}$) any elegant method to get all values ? As i thought of this only when trying to solve for this binomial expansion. Or there is some different elegant method to get the total number of distinct terms ? ...

Answer 1

We want to find the number $K$ of non-zero terms of the polynomial \begin{align*} P(x)=\left(1 +3x^5 +4 x^6 + 5x^8\right)^{20}\tag{1} \end{align*} Since $\mathrm{deg}\left(P(x)\right)=160$ we know $K\leq 161$.

We observe in (1) we have to select $20$ times one of $x^0, x^5, x^6, x^8$ and so the number $K$ of non-zero terms is \begin{align*} \color{blue}{K=\left|\left\{a,b,c\geq 0\Big|a+b+c\leq 20, 5a+6b+8c\leq 160\right\}\right|}\tag{2} \end{align*}

In order to find $K$ we partition the set in (2) into disjoint subsets and determine the size of each of the subsets. We claim: The number of different non-zero terms in $P$ is \begin{align*} \color{blue}{K=154}\tag{3} \end{align*}

We want to calculate with sets and define some commonly used operations. Let $M,N$ be sets containing non-negative integers, and $t\in\mathbb{N}_0$. We define \begin{align*} M+N=\left\{x+y\Big|x\in M,y\in N\right\},\qquad tM= \left\{t x\Big|x\in M\right\} \end{align*} We also use the short-hand notation $[n]:=\{0,1,2,\ldots,n\}$.

Expressions $8c$:

We want to count the number of tripels of the form $5a+6b+8c$ and we start with the set $M_8$ of all valid multiples of $8$. We obtain

\begin{align*} M_8=\left(8\mathbb{N}_0\cap [160]\right) =\{0,8,16,24,\ldots,120,128,136,144,152,160\} \end{align*} Each of the elements $M_8$ is a valid power of an $x$-term and we have \begin{align*} \color{blue}{\left|M_8\right|=21}\tag{4} \end{align*}

Expressions $5a+8c$:

Next we consider expressions of the form $5a+8c$. Since the $\mathrm{lcm}(5,8)=40=8\cdot 5$ we have $7$ cosets of the form \begin{align*} \left(M_8+j\cdot\{5\}\right)\cap[8(20-j)+5j]\qquad\qquad 1\leq j\leq 7 \end{align*}

We obtain for $1\leq j\leq 7$: \begin{align*} \left|\left(M_8+\{5\}\right)\cap[157]\right|&=\left|\{5,13,21,\ldots,157\}\right|\,\,\,=20\\ \left|\left(M_8+2\cdot\{5\}\right)\cap[154]\right|&=\left|\{10,18,26,\ldots,154\}\right|=19\\ \left|\left(M_8+3\cdot\{5\}\right)\cap[151]\right|&=\left|\{15,23,31,\ldots,151\}\right|=18\\ \left|\left(M_8+4\cdot\{5\}\right)\cap[148]\right|&=\left|\{20,28,36,\ldots,148\}\right|=17\\ \left|\left(M_8+5\cdot\{5\}\right)\cap[145]\right|&=\left|\{25,33,41,\ldots,145\}\right|=16\\ \left|\left(M_8+6\cdot\{5\}\right)\cap[142]\right|&=\left|\{30,38,46,\ldots,142\}\right|=15\\ \left|\left(M_8+7\cdot\{5\}\right)\cap[139]\right|&=\left|\{35,43,51,\ldots,139\}\right|=14\\ \end{align*}

We sum up and get with (4) \begin{align*} \color{blue}{21+(20+19+18+17+16+15+14)=140}\tag{5} \end{align*} This way we found already pretty much of the possible non-negative integers $\leq 160$. We try to exhaust the missing valid numbers by checking:

Expressions $6b+8c$:

Since $\mathrm{lcm}(6,8)=24=4\cdot 6$ we have $3$ cosets of the form \begin{align*} \left(M_8+j\cdot\{6\}\right)\cap[8(20-j)+6j]\qquad\qquad 1\leq j\leq 3 \end{align*} In the previous step we had the convenient situation that all the sets were pairwise disjoint. This is no longer the case and we have to filter out the wanted numbers by a somewhat closer inspection.

We obtain for $1\leq j\leq 3$: \begin{align*} \left|\left(M_8+\{6\}\right)\cap[158]\right|&=\left|\{6,14,22,\color{blue}{30\ldots,142},150,158\}\right|\to 5\\ \left|\left(M_8+2\cdot\{6\}\right)\cap[156]\right|&=\left|\{12,\color{blue}{20,\ldots,148},156\}\right|\qquad\qquad\to 2\\ \left|\left(M_8+3\cdot\{6\}\right)\cap[154]\right|&=\left|\{\color{blue}{18,\ldots,154}\}\right|\qquad\qquad\qquad\quad\ \to 0\\ \end{align*}

The blue marked entries were already considered in previous steps. We sum up and get with (5) \begin{align*} \color{blue}{140+(5+2+0)=147}\tag{6} \end{align*}

Expressions $5a+6b+8c$:

We obtain for $(a,b)=(1,1)$: \begin{align*} \left|\left(M_8+\{5\}+\{6\}\right)\cap[155]\right|&=\left|\{11,19,27,\color{blue}{35\ldots,139},147,155\}\right|\to 5\\ \end{align*} We obtain for $(a,b)=(1,2)$: \begin{align*} \left|\left(M_8+\{5\}+2\cdot\{6\}\right)\cap[153]\right|&=\left|\{17,\color{blue}{25\ldots,145},153\}\right|\to 2\\ \end{align*}

The blue marked entries were already considered in previous steps. We sum up and get with (6) \begin{align*} \color{blue}{147+(5+2)=154} \end{align*}

Conclusion: The value $\color{blue}{K=154}$ is the wanted result and the seven missing values are \begin{align*} \color{blue}{1,2,3,4,7,9,159} \end{align*} None of $1,2,3,4,7,9$ can be written in the form $5a+6b+8c$. The final missing number $\color{blue}{159}$ near $160$ has representations \begin{align*} 159=152+\ \ 7&=19\cdot 8+7\\ =144+15&=\color{blue}{18}\cdot 8+\color{blue}{3}\cdot 5\\ =136+23&=\color{blue}{17}\cdot 7+\color{blue}{3}\cdot 6 +\color{blue}{1}\cdot 5 \end{align*} where each of the representations $159=5a+6b+8c$ has $a+b+c\geq21>20$.