Número de soluciones del número entero a $|x_1|+|x_2|+...+|x_n| \le m$

Question

Demostrar que las siguientes dos desigualdades tienen el mismo número de soluciones del número entero.

(A) $|x_1|+|x_2|+...+|x_n| \le m$

(B) $|y_1|+|y_2|+...+|y_m| \le n$, donde m y n son dos números enteros positivos.

Bueno, he intentado solucionar esto usando el argumento de caminos de enrejado que es eficaz para demostrar que A y B tienen el mismo número de soluciones no negativo pero fallido. Quiero saber las pruebas biyectiva y cerrado también forma el número de soluciones si es que existe.

Answer 1

Considerar la desigualdad de $$x_1+x_2+\dots+x_n \le m,$$

donde $x_1,\dots,x_n$ son variables de tipo integer. Sabemos que el número de positivos y no negativos solución de vectores $(x_1,\dots,x_n)$ la satisfacción de esta desigualdad se $\binom{m}{n}$$\binom{m+n}{n}$, respectivamente (véase por ejemplo, ENLACE 1 y ENLACE 2).

El número de no-negativo entero de soluciones a $$|x_1|+|x_2|+\dots+|x_n| \le m,$$ is the same as the number of non-negative integer solutions to $$x_1+x_2+\dots+x_n \le m,$$

que es igual a $\binom{m+n}{n}$. Por la misma razón, el número de no-negativo entero de soluciones a $$|x_1|+|x_2|+\dots+|x_m| \le n,$$ is equal to $\binom{m+n}{m}$. Ya tenemos

$$\binom{m+n}{m} = \binom{m+n}{n},$$

podemos concluir que el número de no-negativo soluciones a $\sum_{i=1}^{n} |x_i| \le m$ $\sum_{i=1}^{m} |x_i| \le n$ son los mismos.

El caso general:

Considere la posibilidad de un no-negativos solución de $\sum_{i=1}^{n} |x_i| \le m$ que $1 \le k \le \min(m,n)$ variables son positivas ($k>m$ es imposible). El número de este tipo de soluciones es igual al número de formas en que podemos seleccionar $k$ variables de $n$ variables de veces el número de positivos soluciones a

$$x_1+x_2+\dots+x_k \le m.$$

Desde allí se $\binom{n}{k}$ formas de seleccionar $k$ variables de $n$ variables y hay $\binom{m}{k}$ soluciones positivas a la última desigualdad, hay $\binom{n}{k}\binom{m}{k}$ no negativo soluciones a $\sum_{i=1}^{n} |x_i| \le m$ $k$ positivo de las variables. Por otro lado, hay $2^k$ número de soluciones correspondientes a cada una de estas soluciones que pueden ser alcanzados por el cambio de signo de las variables. Por lo que el número total de número entero soluciones a $\sum_{i=1}^{n} |x_i| \le m$ sería

$$N_1 = 1+\sum_{k=1}^{\min(m,n)} 2^k \binom{n}{k}\binom{m}{k}.$$

Tenga en cuenta que hemos añadido a $1$ como también debemos considerar el vector solución $(x_1,\dots,x_n) = (0,\dots,0)$. Por la misma razón, el número de soluciones a $\sum_{i=1}^{m} |x_i| \le n$ es igual a

$$N_2 = 1+\sum_{k=1}^{\min(m,n)} 2^k \binom{m}{k}\binom{n}{k}.$$ It is clear that $N_1 = N_2$.

Answer 2

La siguiente generación de la función de enfoque resulta de la simetría, pero no se da una fórmula final tan simple como Optar a la respuesta.

Comenzamos con $$x_1+x_2+\ldots+x_n\leq m\ .\tag{1}$$ Consider the set of all functions $$f:\quad [n]\to{\mathbb Z}, \qquad k\mapsto x_k\ .\tag{2}$$ El valor de $v(f)$ de dicha función está definida para ser $$v(f):=z^{|x_1|+\ldots+|x_n|}\ ,$$ where $z$ is an indeterminate. If $n=1$ the total value of all $f:\>[1]\{\mathbb Z}$ is given by the formal power series $$1+2z+2z^2+2z^3+\ldots={1+z\over1-z}\ .$$ La ley distributiva implica entonces que para arbitrario $n\geq1$ el valor total de todos los $f$ $(2)$ está dado por $$S:=\left({1+z\over1-z}\right)^n\ .$$ Cada una de las $f$ $\sum_{k=1}^n |x_k|=m$ contribuye $z^m$$S$, de ahí que el número de estos $f$s es el coeficiente de $z^m$$S$. Ya que queremos que el número de soluciones de la desigualdad de $(1)$ multiplicamos $S$ $1+z+z^2+\ldots={1\over1-z}$ y ahora determinar el coeficiente de $z^m$ en $$S':={(1+z)^n\over(1-z)^{n+1}}=\sum_{j=0}^n{n\choose j}z^j\cdot\sum_{k=0}^\infty{n+k\choose k} z^k\ .$$ Este coeficiente viene a $$\sum_{j+k=m}{n\choose j}{n+k\choose k}=\sum_{j=0}^{\min\{m,n\}}{n\choose j}{n+m-j\choose m-j}\ .$$ Persiguiendo factoriales permite reescribir la última suma como $${m+n\choose m}\sum_{j=0}^{\min\{m,n\}}{{m\choose j}{n\choose j}\over{m+n\choose j}}\ ,$$ que obviamente es simétrica en $m$$n$.