Números catalanes usando la recurrencia.

Question

Números catalanes usando la recurrencia.

Matemáticas
combinatoria
numeros-catalan

Rohit Pandey

Un jugador lanza una moneda, gana 1 $ si sale cara y pierde 1 $ si sale cruz. sabemos que tienen $t$ colas y $k+t$ cabezas, ganando así $k$ $ . Las formas totales en que esto podría haber sucedido es ${2t+k \choose t}$ y el número de formas en que llegaron $k$ $ por primera vez en el último lanzamiento que hicieron (llámese a esto "la restricción catalana") viene dado por los números catalanes: ${2t+k-1 \choose t}-{2t+k-1 \choose t-1}$ . Ver aquí: Probabilidad de que la caminata aleatoria alcance el estado $k$ por primera vez en el paso $n$ .

Ahora deja $n(k,t)$ sea el número de formas en que llegan a $k$ por primera vez en lanzamiento $2t+k$ (que sabemos por otros medios son los números catalanes generalizados). Luego, condicionando en el primer lanzamiento, obtenemos la recurrencia:

\begin{matrix} (1) & norte (k, t) = norte (k - 1, t) + norte (k + 1, t - 1) \end{matrix}

$n(k,t)=n(k-1,t)+n(k+1,t-1) \tag{1}$

Tanto el número total de caminos (formas totales de llegar a $k$ $ en $2t+k$ tiradas), así como los caminos con la constricción catalana (modos de llegar a $k$ $ por primera vez después $2t+k$ lanzamientos) satisfacen la recurrencia anterior. La única diferencia está en las condiciones iniciales. Para ambas series, tenemos:

norte (0, 0) = 1

$n(0,0)=1$

Por caminos con la limitación catalana;

norte (0, t) = 0 \forall t > 0

$n(0,t)=0 \;\;\forall \;\; t>0$

Mientras que para rutas sin restricciones;

norte (0, t) = (\binom{2 t}{t})

$n(0,t)={2t \choose t}$

Debe haber una manera de pasar de la recurrencia en la ecuación (1) a las soluciones para los conteos de los dos tipos de caminos (dependiendo de las condiciones iniciales que sustituyamos), usando funciones generadoras u otras técnicas. ¿Hay alguna forma de hacer esto?

Tenga en cuenta que la respuesta de @robjohn en la pregunta vinculada anteriormente hace esto, pero usa la interpretación de que estos son caminos en la cuadrícula. Esperaba una solución que no dependiera de esta intuición y solo de la ecuación (1) con las condiciones iniciales.

Especificando las condiciones iniciales de forma explícita. Además de la recurrencia dada por la ecuación (1) que cumplen ambas series, tenemos las siguientes condiciones iniciales:

Caso-1: Caminos que satisfacen la restricción catalana.

norte (0, 0) = 1

$n(0,0)=1$

norte (0, t) = 0 \forall t > 0

$n(0,t)=0 \forall t>0$

Sabemos que la solución de la recurrencia en la ecuación (1) con estas condiciones iniciales es:

norte (k, t) = (\binom{2 t + k - 1}{t}) - (\binom{2 t + k - 1}{t - 1})

$n(k,t) = {2t+k-1 \choose t}-{2t+k-1 \choose t-1}$

Caso-2: Todos los caminos (sin restricción).

norte (0, 0) = 1

$n(0,0)=1$

norte (0, t) = (\binom{2 t}{t}) \forall t > 0

$n(0,t)={2t \choose t} \forall t>0$

Sabemos que la solución de la recurrencia en la ecuación (1) con estas condiciones iniciales es:

norte (k, t) = (\binom{2 t + k}{t})

$n(k,t) = {2t+k \choose t}$

Juan muestras

¿Qué quieres decir con "Ahora, deja

n (k, t)

$n(k,t)$ sea el número de formas (que sabemos por otros medios son los números catalanes generalizados)." ¿El número de formas de qué? Tan pronto como aclares esto, estoy seguro de que alguien responderá de golpe.

Rohit Pandey

@JohnSamples: agregó algunas aclaraciones en la pregunta. Déjame saber si está claro ahora.

Rohit Pandey

Bien. Aunque, de lo que se trata es de sacar los números catalanes de aquí, así que

f (0, y) = 0

$f(0,y)=0$ , no los números catalanes.

Rohit Pandey

@PTDS: condiciones iniciales agregadas para las dos series explícitamente. En su notación,

f (2, 2)

$f(2,2)$ es el número de formas de ganar 2 $ obteniendo 2 cruces (es decir, 4 caras). La primera serie tiene la restricción catalana. Entonces, el número de formas es

(\binom{5}{2}) - (\binom{5}{1}) = 5

${5 \choose 2}-{5 \choose 1} = 5$ . Mientras que para la segunda serie, es simplemente

(\binom{6}{2}) = 15

${6 \choose 2}=15$

Respuestas (1)

Números catalanes usando la recurrencia.

¿Qué quieres decir con "Ahora, deja $n(k,t)$ sea el número de formas (que sabemos por otros medios son los números catalanes generalizados)." ¿El número de formas de qué? Tan pronto como aclares esto, estoy seguro de que alguien responderá de golpe.
@JohnSamples: agregó algunas aclaraciones en la pregunta. Déjame saber si está claro ahora.
Bien. Aunque, de lo que se trata es de sacar los números catalanes de aquí, así que $f(0,y)=0$ , no los números catalanes.
@PTDS: condiciones iniciales agregadas para las dos series explícitamente. En su notación, $f(2,2)$ es el número de formas de ganar 2 obteniendo 2 cruces (es decir, 4 caras). La primera serie tiene la restricción catalana. Entonces, el número de formas es ${5 \choose 2}-{5 \choose 1} = 5$ . Mientras que para la segunda serie, es simplemente ${6 \choose 2}=15$

PTDS · Answer 1

Estamos tratando de resolver la ecuación funcional

F (norte, k) = F (norte - 1, k) + F (norte + 1, k - 1)

$f(n, k) = f(n-1, k) + f(n+1, k-1)$ con diferentes condiciones de contorno.

Caso $1$

F (0, k) = {\begin{cases} 1 & k = 0 \\ 0 & de lo contrario \end{cases}

$f(0, k) = \begin{cases} 1 & k = 0\\ 0 &\text{otherwise} \end{cases}$

Caso $2$

F (0, k) = {\begin{cases} 1 & k = 0 \\ (\binom{2 k}{k}) & de lo contrario \end{cases}

$f(0, k) = \begin{cases} 1 & k = 0\\ \binom{2k}{k} &\text{otherwise} \end{cases}$

Definir la función generadora

F_{norte} (X) = \sum_{k = 0}^{\infty} F (norte, k) X^{k}

$F_n(x) = \sum_{k=0}^\infty f(n, k) x^k$

Multiplica la ecuación original por $x^k$ y suma $k \geq 1$ para obtener

\sum_{k \geq 1} F (norte, k) X^{k} = \sum_{k \geq 1} F (norte - 1, k) X^{k} + \sum_{k \geq 1} F (norte + 1, k - 1) X^{k}

$\sum_{k \geq 1} f(n, k) x^k = \sum_{k \geq 1} f(n-1, k) x^k + \sum_{k \geq 1} f(n+1, k-1) x^k$

O,

F_{norte} (X) - 1 = F_{norte - 1} (X) - 1 + X F_{norte + 1} (X)

$F_n(x) - 1 = F_{n-1}(x) - 1 + x F_{n+1}(x)$

O,

X F_{norte + 1} (X) - F_{norte} (X) + F_{norte - 1} (X) = 0

$x F_{n+1}(x) - F_n(x) + F_{n-1}(x) = 0$

La ecuación característica de la relación de recurrencia anterior para la función generadora $F_n(x)$ es dado por

X {metro}^{2} - metro + 1 = 0 ⟹ metro = \frac{1 \mp \sqrt{1 - 4 X}}{2 X}

$xm^2 - m + 1 = 0 \implies m = \frac{1 \mp \sqrt{1-4x}}{2x}$

Por lo tanto la solución es

F_{norte} (X) = C_{1} {metro}_{1}^{norte} + C_{2} {metro}_{2}^{norte}

$F_n(x) = c_1 m_1^n + c_2 m_2^n$ dónde

m_{1} = \frac{1 - \sqrt{1 - 4 x}}{2 x} = \frac{2}{1 + \sqrt{1 - 4 x}}

$m_1 = \frac{1 - \sqrt{1-4x}}{2x} = \frac{2}{1+ \sqrt{1-4x}}$ y

m_{2} = \frac{1 + \sqrt{1 - 4 x}}{2 x} = \frac{2}{1 - \sqrt{1 - 4 x}}

$m_2 = \frac{1 + \sqrt{1-4x}}{2x} = \frac{2}{1- \sqrt{1-4x}}$

Tenga en cuenta que $m_2$ no está definido para $x = 0$

Asumimos que $F_n(x)$ se define para $x = 0$ y por lo tanto establecemos $c_2 = 0$

Finalmente

F_{norte} (X) = C_{1} {(\frac{2}{1 + \sqrt{1 - 4 X}})}^{norte}

$F_n(x) = c_1 \left(\frac{2}{1+ \sqrt{1-4x}}\right)^n$

Dado que el coeficiente de $x^k$ en $F_n(x)$ da el valor de $f(n, k)$ , necesitamos calcular ese valor para encontrar $f(n, k)$

Caso $1$ : En este caso,

F_{norte} (0) = 1 ⟹ C_{1} = 1 ⟹ F_{norte} (X) = {(\frac{2}{1 + \sqrt{1 - 4 X}})}^{norte}

$F_n(0) = 1 \implies c_1 = 1 \implies F_n(x) = \left(\frac{2}{1+ \sqrt{1-4x}}\right)^n$

El coeficiente de $x^k$ en $F_n(x)$ o

F (norte, k) = (\binom{norte + 2 k - 1}{k}) - (\binom{norte + 2 k - 1}{k - 1})

$f(n, k) = \binom{n+2k-1}{k} - \binom{n+2k-1}{k-1}$

Caso $2$ : En este caso,

F_{norte} (0) = \sum_{k = 0}^{\infty} (\binom{2 k}{k}) X^{k} = \frac{1}{\sqrt{1 - 4 X}}

$F_n(0) = \sum_{k = 0}^\infty \binom{2k}{k} x^k = \frac{1}{\sqrt{1-4x}}$

⟹ C_{1} = \frac{1}{\sqrt{1 - 4 X}} ⟹ F_{norte} (X) = \frac{1}{\sqrt{1 - 4 X}} {(\frac{2}{1 + \sqrt{1 - 4 X}})}^{norte}

$\implies c_1 = \frac{1}{\sqrt{1-4x}} \implies F_n(x) = \frac{1}{\sqrt{1-4x}} \left(\frac{2}{1+ \sqrt{1-4x}}\right)^n$

El coeficiente de $x^k$ en $F_n(x)$ o

F (norte, k) = (\binom{norte + 2 k}{k})

$f(n, k) = \binom{n+2k}{k}$

Números catalanes usando la recurrencia.

Rohit Pandey

Juan muestras

Rohit Pandey

Rohit Pandey

Rohit Pandey

Respuestas (1)

PTDS

Aclaración sobre uno de los problemas de Stanley sobre los números catalanes

Rutas en una cuadrícula que no bajan de 000 ni de lll antes de alcanzar su objetivo.

Una pregunta que pide probar una secuencia igual a números catalanes en la que no puedo pensar

Método rápido para convertir ruta catalana a posición lexicográfica.

Encontrar el número de caminos monótonos que no cruzan la diagonal

Número de caminos en una grilla con restricciones

Personas sentadas alrededor de dos mesas con sillas numeradas

¿Cuál es el número de números de 4 dígitos no crecientes?

¿Cuál es la probabilidad de que una caminata aleatoria que comienza en 0 llegue a +2 en 2 pasos, 3 pasos, 4 pasos, etc.? [duplicar]

Probabilidad de que dos elementos particulares se agrupen en una partición aleatoria con tamaños fijos