Contando las formas en la cuadrícula si uno puede moverse de (x,y)(x,y)(x,y) a (x+a,x+b)(x+a,x+b)(x+a, x +b) para x,y,a,b≥0x,y,a,b≥0x,y,a,b\geq 0 arbitrario.

Question

Contando las formas en la cuadrícula si uno puede moverse de (x,y)(x,y)(x,y) a (x+a,x+b)(x+a,x+b)(x+a, x +b) para x,y,a,b≥0x,y,a,b≥0x,y,a,b\geq 0 arbitrario.

Matemáticas
combinatoria
exclusión inclusión
Matemáticas discretas
relaciones de recurrencia
coeficientes binomiales

ueir

En una cuadrícula de 2 dimensiones, considere la situación de la que uno puede moverse $(p,q)$ a $(p+α,q+β)$ a la vez para un entero arbitrario $p,q,α,β\geq 0 \land (α,β)\neq(0,0)$ . Quiero contar cuántas maneras hay de pasar de (0,0) a (x,y). probé que hay $\sum_{i=0}^{\min(x,y)}\binom{x}{i}\binom{y}{i}2^{x+y-(i+1)}$ por vista combinatoria. Entonces, ¿podemos derivar esto usando series de potencias formales?

He tratado de derivar esto, sin embargo, aparecen diferentes fórmulas y no puedo obtener la interpretación combinatoria de esa fórmula.

El número de formas de conseguir $(x,y)$ por $n$ se mueve es

\begin{aligned} [s^{X} t^{y}] {(\frac{1}{1 - s} \frac{1}{1 - t} - 1)}^{norte} \\ = & [s^{X} t^{y}] {(\frac{s + t - s t}{(1 - s) (1 - t)})}^{norte} \end{aligned}

$\begin{align} &[s^x t^y]\left(\frac{1}{1-s}\frac{1}{1-t}-1 \right)^n \\ =&[s^x t^y]\left(\frac{s+t-st}{(1-s)(1-t)}\right)^n \end{align}$

Tenga en cuenta que $[s^x t^y] f(s,t)$ es el coeficiente de $s^x t^y$ término de $f(s,t)$ .

resumiendo para $n=1,2,...,$ podemos obtener el número de formas de ir a $(x, y)$ por un número arbitrario de movimientos.

\begin{aligned} [s^{X} t^{y}] \sum_{norte = 1}^{\infty} {(\frac{s + t - s t}{(1 - s) (1 - t)})}^{norte} \\ = & [s^{X} t^{y}] \frac{s + t - s t}{1 - 2 (s + t - s t)} \\ = & [s^{X} t^{y}] \sum_{i = 0}^{min (X, y)} 2^{X + y - i - 1} (s + t - s t)^{X + y - i} \\ = & \sum_{i = 0}^{min (X, y)} 2^{X + y - i - 1} (- 1)^{i} \frac{(X + y - i)!}{(X - i)! (y - i)! i!} \end{aligned}

$\begin{align} &[s^x t^y]\sum_{n=1}^\infty \left(\frac{s+t-st}{(1-s)(1-t)}\right)^n \\ =&[s^x t^y]\frac{s+t-st}{1-2(s+t-st)} \\ =&[s^x t^y]\sum_{i=0}^{\min(x,y)}2^{x+y-i-1} (s+t-st)^{x+y-i} \\ =&\sum_{i=0}^{\min(x,y)}2^{x+y-i-1} (-1)^i \frac{(x+y-i)!}{(x-i)!(y-i)!i!} \end{align}$

Sin embargo, esto parece diferente de $\sum\binom{x}{i}\binom{y}{i}2^{x+y-(i+1)}$ . Además, no puedo dar con la interpretación combinatoria de la fórmula que obtenemos.

ACTUALIZAR

Quiero explicar en detalle lo siguiente.

\begin{aligned} [s^{X} t^{y}] \sum_{norte = 1}^{\infty} {(\frac{s + t - s t}{(1 - s) (1 - t)})}^{norte} \\ = & [s^{X} t^{y}] (\frac{s + t - s t}{1 - 2 (s + t - s t)} - \frac{(1 - s) (1 - t) \underset{norte \to \infty}{límite} {(\frac{s + t - s t}{(1 - s) (1 - t)})}^{norte}}{1 - 2 (s + t - s t)}) \end{aligned}

$\begin{align} &[s^x t^y]\sum_{n=1}^\infty \left(\frac{s+t-st}{(1-s)(1-t)}\right)^n \\ =&[s^x t^y]\left(\frac{s+t-st}{1-2(s+t-st)} - \frac{(1-s)(1-t)\lim_{N\to\infty}\left(\frac{s+t-st}{(1-s)(1-t)}\right)^N}{1-2(s+t-st)} \right)\\ \end{align}$

Aquí, supongo que el término, $-\frac{(1-s)(1-t)\lim_{N\to\infty}\left(\frac{s+t-st}{(1-s)(1-t)}\right)^N}{1-2(s+t-st)}$ puede ser tratado como $0$ porque si ponemos $s=0$ y $t=0$ , $\frac{s+t-st}{(1-s)(1-t)}=0$ lo que significa que el grado de este término irá $\infty$ si tomamos el poder de $\infty$ . Por lo tanto, este término no tiene nada que ver con el $s^x t^y$ término y está bien tratarlo como $0$ .

Respuestas (1)

Contando las formas en la cuadrícula si uno puede moverse de (x,y)(x,y)(x,y) a (x+a,x+b)(x+a,x+b)(x+a, x +b) para x,y,a,b≥0x,y,a,b≥0x,y,a,b\geq 0 arbitrario.

epi163sqrt · Answer 1

Consideramos enteros no negativos $x,y$ y para tener una primera impresión empezamos a calcular los primeros valores de

\begin{aligned} (1) & \sum_{j \geq 0} (\binom{X}{j}) (\binom{y}{j}) 2^{X + y - j + 1} \end{aligned}

$\begin{align*} \sum_{j\geq 0}\binom{x}{j}\binom{y}{j}2^{x+y-{j+1}}\tag{1} \end{align*}$ Nosotros escribimos

j \geq 0

$j\geq 0$ y recordar

(\binom{p}{q}) = 0

$\binom{p}{q}=0$ si

q > p

$q>p$ . Los valores de (1) se dan en la imagen a continuación y observamos que la secuencia está archivada en OEIS como A059576 .

Los valores en OEIS coinciden con (1) además $(x,y)=(0,0)$ que se establece en $1$ , de modo que el valor de $(x,y)$ es la suma de los valores con menor $x$ o más pequeño $y$ (un ejemplo marcado en azul).

Ahora asumimos $x,y\geq 0, x+y\geq 1$ y obtener
$\begin{aligned} [s^{X} t^{y}] & \sum_{norte = 1}^{\infty} {(\frac{s + t - s t}{(1 - s) (1 - t)})}^{norte} \\ = [s^{X} t^{y}] (\frac{1}{1 - \frac{s + t - s t}{(1 - s) (1 - t)}} - 1) \\ = [s^{X} t^{y}] \frac{s + t - s t}{1 - 2 (s + t - s t)} \\ (2) & = \frac{1}{2} [s^{X} t^{y}] \frac{1}{1 - 2 (s + t - s t)} \\ = \frac{1}{2} [s^{X} t^{y}] \sum_{j = 0}^{\infty} 2^{j} (s + t - s t)^{j} \\ = \frac{1}{2} [s^{X} t^{y}] \sum_{j = 0}^{\infty} 2^{j} \sum_{k = 0}^{j} (\binom{j}{k}) s^{k} (1 - t)^{k} t^{j - k} \\ (3) & = \frac{1}{2} [s^{X} t^{y}] \sum_{k = 0}^{\infty} \sum_{j = k}^{\infty} 2^{j} (\binom{j}{k}) s^{k} (1 - t)^{k} t^{j - k} \\ (4) & = \frac{1}{2} [t^{y}] \sum_{j = X}^{\infty} 2^{j} (\binom{j}{X}) (1 - t)^{X} t^{j - X} \\ = \frac{1}{2} [t^{y}] \sum_{j = 0}^{\infty} 2^{j + X} (\binom{X + j}{j}) t^{j} (1 - t)^{X} \\ = \frac{1}{2} \sum_{j = 0}^{y} 2^{j + X} (\binom{X + j}{j}) [t^{y - j}] (1 - t)^{X} \\ (5) & = \frac{1}{2} \sum_{j = 0}^{y} 2^{j + X} (\binom{X + j}{j}) (\binom{X}{y - j}) (- 1)^{y - j} \\ (6) & = \sum_{j = 0}^{y} (\binom{X + y - j}{y - j}) (\binom{X}{j}) 2^{X + y - j - 1} (- 1)^{y - j} \\ = 2^{X + y - 1} \sum_{j \geq 0} (\binom{X}{j}) {(- \frac{1}{2})}^{j} [z^{y - j}] (1 + z)^{X + y - j} \\ = 2^{X + y - 1} [z^{y}] (1 + z)^{X + y} \sum_{j \geq 0} (\binom{X}{j}) {(- \frac{z}{2 (1 + z)})}^{j} \\ = 2^{X + y - 1} [z^{y}] (1 + z)^{X + y} {(1 - \frac{z}{2 (1 + z)})}^{X} \\ = 2^{X + y - 1} [z^{y}] (1 + z)^{y} {(1 + \frac{z}{2})}^{X} \\ = 2^{X + y - 1} [z^{y}] (1 + z)^{y} \sum_{j \geq 0} (\binom{X}{j}) {(\frac{z}{2})}^{j} \\ = \sum_{j \geq 0} (\binom{X}{j}) [z^{y - j}] (1 + z)^{y} 2^{X + y - j - 1} \\ = \sum_{j \geq 0} (\binom{X}{j}) (\binom{y}{y - j}) 2^{X + y - j - 1} \\ = \sum_{j \geq 0} (\binom{X}{j}) (\binom{y}{j}) 2^{X + y - j - 1} \end{aligned}$ $\begin{align*} \color{blue}{[s^xt^y]}&\color{blue}{\sum_{n=1}^\infty\left(\frac{s+t-st}{(1-s)(1-t)}\right)^n}\\ &=[s^xt^y]\left(\frac{1}{1-\frac{s+t-st}{(1-s)(1-t)}}-1\right)\\ &=[s^xt^y]\frac{s+t-st}{1-2(s+t-st)}\\ &=\frac{1}{2}[s^xt^y]\frac{1}{1-2(s+t-st)}\tag{2}\\ &=\frac{1}{2}[s^xt^y]\sum_{j=0}^\infty 2^j(s+t-st)^j\\ &=\frac{1}{2}[s^xt^y]\sum_{j=0}^\infty2^j \sum_{k=0}^j\binom{j}{k}s^k(1-t)^kt^{j-k}\\ &=\frac{1}{2}[s^xt^y]\sum_{k=0}^\infty\sum_{j=k}^\infty 2^j\binom{j}{k}s^k(1-t)^kt^{j-k}\tag{3}\\ &=\frac{1}{2}[t^y]\sum_{j=x}^\infty 2^j\binom{j}{x}(1-t)^xt^{j-x}\tag{4}\\ &=\frac{1}{2}[t^y]\sum_{j=0}^\infty 2^{j+x}\binom{x+j}{j}t^j(1-t)^x\\ &=\frac{1}{2}\sum_{j=0}^y2^{j+x}\binom{x+j}{j}[t^{y-j}](1-t)^x\\ &=\frac{1}{2}\sum_{j=0}^y2^{j+x}\binom{x+j}{j}\binom{x}{y-j}(-1)^{y-j}\tag{5}\\ &=\sum_{j=0}^y\binom{x+y-j}{y-j}\binom{x}{j}2^{x+y-j-1}(-1)^{y-j}\tag{6}\\ &=2^{x+y-1}\sum_{j\geq 0}\binom{x}{j}\left(-\frac{1}{2}\right)^j[z^{y-j}](1+z)^{x+y-j}\\ &=2^{x+y-1}[z^y](1+z)^{x+y}\sum_{j\geq 0}\binom{x}{j}\left(-\frac{z}{2(1+z)}\right)^j\\ &=2^{x+y-1}[z^y](1+z)^{x+y}\left(1-\frac{z}{2(1+z)}\right)^x\\ &=2^{x+y-1}[z^y](1+z)^{y}\left(1+\frac{z}{2}\right)^x\\ &=2^{x+y-1}[z^y](1+z)^{y}\sum_{j\geq 0}\binom{x}{j}\left(\frac{z}{2}\right)^j\\ &=\sum_{j\geq 0}\binom{x}{j}[z^{y-j}](1+z)^y2^{x+y-j-1}\\ &=\sum_{j\geq 0}\binom{x}{j}\binom{y}{y-j}2^{x+y-j-1}\\ &\,\,\color{blue}{=\sum_{j\geq 0}\binom{x}{j}\binom{y}{j}2^{x+y-j-1}} \end{align*}$ y sigue la demanda.

Comentario:

En (2) usamos $\frac{2(s+t-st)}{1-2(s+t-st)}=\frac{1}{1-2(s+t-st)}-1$ . Podemos ignorar el término $1$ que no contribuye a $[s^xt^y]$ desde $x+y\geq 1$ .
En (3) intercambiamos la suma de series.
En (4) seleccionamos el coeficiente de $s^x$ .
En (5) seleccionamos el coeficiente de $t^{y-j}$ .
En (6) cambiamos el orden de la suma $j\to y-j$ .

Nota: La expresión con el exponente $\infty$ matemáticamente no es sólido y debe evitarse.

Contando las formas en la cuadrícula si uno puede moverse de (x,y)(x,y)(x,y) a (x+a,x+b)(x+a,x+b)(x+a, x +b) para x,y,a,b≥0x,y,a,b≥0x,y,a,b\geq 0 arbitrario.

ueir

Respuestas (1)

epi163sqrt

Prueba combinatoria de x(n)=∑nk=1L(n,k)(x)kx(n)=∑k=1nL(n,k)(x)kx^{(n)} = \sum_{k = 1}^n L(n,k)(x)_k

Extraer coeficientes para resolver la relación de recurrencia

¿Trayectorias de coeficientes binomiales?

Prueba combinatoria (y algebraica) de una identidad que involucra números Lah

¿Inclusión/exclusión, al menos y exactamente arreglos?

nnn invitados, cada invitado trae un premio, ¿de cuántas maneras se pueden repartir los premios para que nadie reciba el premio que trajeron?

4 parejas y 4 personas solas sentadas en 3 mesas redondas

Encontrar una relación de recurrencia sobre un diccionario dado

Problema combinatorio: bolas negras y blancas divididas en k grupos con límites, y luego seleccionando una secuencia de solo bolas negras.

Parejas sentadas en una mesa redonda