Número de soluciones integrales de una desigualdad lineal

Question

Intento mostrar la siguiente identidad:

Dejemos que $k,n \in \mathbb{N}$ . Entonces $$\text{card}\{x \in \mathbb{Z}^n: \sum_{i=1}^n |x_i| \leq k\} =\sum_{i=0}^n 2^{n-i} {n \choose i}{k \choose n-i}.$$

Mi intento: Que $A=\{x \in \mathbb{Z}^n: \sum_{i=1}^n |x_i| \leq k\}$ . Sea $0\leq i \leq n$ . Sea $x_1,\ldots,x_{n-i}\geq 1$ sea tal que $x_1+\ldots+x_{n-i} \leq k$ . Entonces es fácil ver que $|A|=\sum_{i=0}^n 2^{n-i} {n \choose i} |\text{no. of positive integral solutions to } x_1+\ldots+x_{n-i} \leq k|$ .

Sin embargo, estoy obteniendo el número de soluciones integrales positivas a $x_1+\ldots+x_{n-i} \leq k$ como no igual a ${k \choose n-i}$ . ¿Puede alguien ayudarme?

Answer 1

Pista 1: número de soluciones integrales positivas de $x_1+\ldots+x_{n-i} \leq k$ es igual al número de todas las soluciones integrales no negativas de $y_1+\ldots+y_{n-i} \leq k-(n-i)$ .

Pista 2: para cualquier número entero $r\ge 1$ $${r-1 \choose r-1}+{r \choose r-1}+\cdots+{k-1 \choose r-1}={k \choose r}.$$

Answer 2

Obtenemos para el LHS que es

$$[z^k] \frac{1}{1-z} \left(1+2z+2z^2+\cdots\right)^n = [z^k] \frac{1}{1-z} \left(1+2\frac{z}{1-z}\right)^n \\ = [z^k] \frac{(1+z)^n}{(1-z)^{n+1}}.$$

Extrayendo los coeficientes obtenemos

$$\sum_{q=0}^k {n\choose q} {k-q+n\choose n} = \sum_{q=0}^k {n\choose q} {k-q+n\choose k-q}.$$

Introducir la integral $${k-q+n\choose k-q} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{k-q+n}}{z^{k-q+1}} \; dz.$$

Esto refuerza el alcance (el polo se desvanece cuando $q\gt k$ ) por lo que podemos extender la suma a $n$ , obteniendo

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{k+n}}{z^{k+1}} \sum_{q=0}^n {n\choose q} \frac{z^q}{(1+z)^q} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{k+n}}{z^{k+1}} \left(1+\frac{z}{1+z}\right)^n \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{k}}{z^{k+1}} (1+2z)^n \; dz.$$

Lo evaluamos utilizando el negativo del residuo en el infinito para encontrar (los residuos suman cero)

$$\mathrm{Res}_{z=\infty} \frac{(1+z)^{k}}{z^{k+1}} (1+2z)^n = -\mathrm{Res}_{z=0} \frac{1}{z^2} (1+1/z)^k z^{k+1} (1+2/z)^n \\ = -\mathrm{Res}_{z=0} \frac{1}{z} (1+z)^k \frac{(2+z)^n}{z^n} = -\mathrm{Res}_{z=0} \frac{1}{z^{n+1}} (1+z)^k (2+z)^n.$$

Extrayendo el residuo y volteando el signo obtenemos

$$\sum_{q=0}^n {n\choose q} 2^{n-q} {k\choose n-q}.$$

Este es el RHS como se reclama.

Observación. Esto también funciona cuando $k \gt n$ porque cuando bajamos el límite superior de la suma a $n$ estamos omitiendo términos que de todos modos habrían sido nulos debido a la ${n\choose q}$ plazo.

Answer 3

Dejemos que $t=k-\left(|x_1|+\cdots+|x_n|\right)$ , por lo que queremos encontrar el número de soluciones de $|x_1|+\cdots+|x_n|+t=k$

donde el $x_i$ y $t$ son números enteros y $t\ge0$ .

Para cada $i$ con $0\le i\le n$ podemos

1) elegir $i$ de los términos $x_1,\cdots,x_n$ sea 0 en $\binom{n}{i}$ formas

2) elegir los signos del resto $n-i$ términos en $2^{n-i}$ formas

3) Si dejamos que $y_1,\cdots,y_{n-i}$ sean los términos de la forma $|x_j|$ elegido para ser distinto de cero,

$\hspace{.2 in}$ debemos encontrar el número de soluciones de $y_1+\cdots+y_{n-i}+t=k$ con $y_j>0$ para cada $j$ y $t\ge0$ .

$\hspace{.2 in}$ Dejar $y_{n-i+1}=t+1$ da

$\hspace{.2 in}$$y_1+\cdots+y_{n-i+1}=k+1\;$ with $y_j>0$ for all $j$; so there are $\N - soluciones binom{k}{n-i}$.

Esto da un total de $\displaystyle\sum_{i=0}^n 2^{n-i}\binom{n}{i}\binom{k}{n-i}$ soluciones.