Connection between words and sets of solutions to integral equations

23 Views Asked by At

Consider any nonnegative integral solution $x_1, x_2,\ldots, x_n$ of the equation $x_1 + x_2 + \ldots + x_n = m.$ For each $i = 1,2,\ldots,n$, let $y_i = x_1 + x_2 + \ldots + x_i$. Then $0 \le y_1 \le y_2 \le \ldots \le y_n = m$. Conversely, suppose $(y_1, y_2, \ldots, y_n)$ is any $n$-tuple of nonnegative integers such that $0 \le y_1 \le y_2 \le \ldots \le y_n = m$, and let $x_1 = y_1$, and $x_i = y_i - y_{i- 1}$ for all integers $i = 1,2,\ldots,n.$ Then $x_1 + x_2 + \ldots + x_n = y_1 + (y_2 - y_1) + (y_3 -y_2) + \ldots + (y_n - y_{n -1}) = y_n= m$, and so $x_1 + x_2 + \ldots + x_n = m.$ $\color{red}{\text{Consequently}}$, the number of nonnegative integral solutions of the equation $x_1 + x_2 + \ldots + x_n = m$ is the same as the number of $n$-tuples of nonnegative integers $(y_1, y_2, \ldots, y_n)$ such that $0 \le y_1 \le y_2 \le \ldots \le y_n = m$.

I don't see how the conclusion $\color{red}{\text{bolded in red}}$ above follows from the preceding steps. Is there some sort of unspoken/implicit bijection somewhere in the text above?


To make sure the question is not too short, I'll add the way I personally understand the connection between integral solutions to equations like the one above and words:

Questions:

$1.$ What's the number of words of length $n$ sourced out of $\{|,*\}$ where the $m$ letters are reserved for *s?

$2.$ How many integral solutions are there for $\sum_{i=1}^nx_i=m?$

Answers:

I'll do a special case where $n = 4, m = 7$ which is similar to the general case.

$1$. Consider the following example word: *|***|**|*. To count words of this kind, we simply choose seven places out of ten for stars which can be done in $\binom{10}{7} = \binom{7 + 4 - 1}{7} = \left(\!\!{4\choose 7}\!\!\right)$ ways. The last equality is by definition.

$2.$ Consider the word *|***|**|* again. The letter "|" naturally divides the word into four substrings. If we let each of these substrings stand for a variable and the number of *s -- for variable values, then this problem is exactly the same as the one above.

1

There are 1 best solutions below

2
On BEST ANSWER

There is an explicit bijection there: it’s between the set $S_0$ of solutions in non-negative integers to the equation $$x_1+\ldots+x_n=m\tag{1}$$ and the set $S_1$ of $n$-tuples $\langle y_1,\ldots,y_n\rangle$ of integers such that $0\le y_1\le\ldots\le y_n=m$. The map $\varphi:S_0\to S_1$ takes a solution $x_1,\ldots,x_n$ to $(1)$ to the $n$-tuple $\langle y_1,\ldots,y_n\rangle$, where $y_k=x_1+\ldots+x_k$ for $k=1,\ldots,n$.

For instance, if $n=4$ and $m=6$, the solution $2+1+0+3=6$ to $(1)$ would be taken to the $4$-tuple $\langle 2,3,3,6\rangle$

This is clearly a bijection, because it has an inverse, which is also described in the opening paragraph: given an $n$-tuple $\langle y_1,\ldots,y_n\rangle\in S_1$, we can reconstruct the solution to $(1)$ that corresponds to it, namely, $x_1=y_1$, $x_2=y_2-y_1$, and in general $x_k=y_k-y_{k-1}$ for $k=2,\ldots,n$.