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

Question

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

Matemáticas
combinatoria
numeros-catalan
coeficientes binomiales

Rohit Pandey

Estaba revisando las preguntas: Manera rápida de obtener una posición de combinación (sin repeticiones) y (Manera rápida de) Obtener una combinación dada su posición en orden lexicográfico (inverso) para convertir una combinación a su posición lexicográfica y luego pasar de la posición a la combinación. Una extensión lógica de esto son los números catalanes generalizados que son básicamente combinaciones con una restricción adicional.

Considere a un jugador que lanza una moneda y gana 1 $ si sale cara y pierde 1 $ si sale cruz. Sabemos que consiguió $l$ colas y $l+k$ cabezas El número de formas en que podría haber hecho esto es: ${k+2l \choose l}$ y si quisiéramos generar los caminos reales, podemos hacerlo utilizando los enfoques de las preguntas vinculadas anteriormente (las representaciones binarias de las combinaciones serían los lanzamientos en los que obtuvo cruz).

Pero ahora, agregamos la restricción adicional que alcanza $k\$$ por primera vez despues $k+2l$ lanzamientos La publicación: Probabilidad de que la caminata aleatoria alcance el estado $k$ por primera vez en el paso $n$ muestra que el número de formas de hacer esto se convierte en: ${k+2l-1 \choose l} - {k+2l-1 \choose l-1}$ . Ahora, quiero recorrer estos caminos. Entonces, así como las dos primeras publicaciones anteriores muestran cómo pasar de combinaciones a posiciones lexicográficas y viceversa, ¿hay una manera eficiente de hacerlo también para estas rutas (que no implique almacenar todas las rutas en la memoria)? Para esta pregunta, consideremos que nos dan una ruta en binario. Algo así como: [0,1,0,0,0,1,1] (los 1 son lanzamientos donde obtuvo cruz) y quiere obtener un número entero que es la posición lexicográfica si enumera todas las rutas válidas (el número total de que es el número catalán generalizado).

Mike Earnest

Tienes una fórmula incorrecta para el número de caminatas; debería ser

(\binom{k + 2 yo - 1}{yo}) - (\binom{k + 2 k - 1}{k - 1}) .

$\binom{k+2l-1}{l}-\binom{k+2k-1}{k-1}.$ Comprobar con

k = 1

$k=1$ y

l = 1

$l=1$ .

Rohit Pandey

Con

k = 1

$k=1$ y

l = 1

$l=1$ , tenemos 3 lanzamientos en total, 2 caras y 1 cruz. Así que las formas totales son 3 (HHT, HTH, THH). Pero si va a llegar a 1 $ por primera vez en el lanzamiento 3, tenemos que excluir HHT, por lo que el número de formas se convierte en 3-1=2. La fórmula que tengo da

(\binom{3}{1}) - (\binom{3}{0}) = 2

${3 \choose 1}-{3 \choose 0} = 2$ . Tu fórmula da:

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

${2 \choose 1}-{2 \choose 0}=1$ . ¿Qué me estoy perdiendo?

Mike Earnest

También hay que excluir a HTH, porque en ese saca $ 1 en el primer lanzamiento.

Rohit Pandey

Tienes razón, arreglada la pregunta.

Respuestas (1)

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

Tienes una fórmula incorrecta para el número de caminatas; debería ser $(\binom{k + 2 yo - 1}{yo}) - (\binom{k + 2 k - 1}{k - 1}) .$ $\binom{k+2l-1}{l}-\binom{k+2k-1}{k-1}.$ Comprobar con $k=1$ y $l=1$ .
Con $k=1$ y $l=1$ , tenemos 3 lanzamientos en total, 2 caras y 1 cruz. Así que las formas totales son 3 (HHT, HTH, THH). Pero si va a llegar a 1 por primera vez en el lanzamiento 3, tenemos que excluir HHT, por lo que el número de formas se convierte en 3-1=2. La fórmula que tengo da ${3 \choose 1}-{3 \choose 0} = 2$ . Tu fórmula da: ${2 \choose 1}-{2 \choose 0}=1$ . ¿Qué me estoy perdiendo?
También hay que excluir a HTH, porque en ese saca $ 1 en el primer lanzamiento.

Mike Earnest · Answer 1

Dejar $N(k,l)=\binom{k+2l-1}{l}-\binom{k+2l-1}{l-1}$ indicar el número de caminos. Tenga en cuenta que

norte (k, yo) = norte (k - 1, yo) + norte (k + 1, yo - 1) (k > 0)

$N(k,l) = N(k-1,l) + N(k+1,l-1) \qquad (k>0)$ con los casos base

N (0, 0) = 1

$N(0,0)=1$ ,

N (0, l) = 0

$N(0,l)=0$ para

l > 0

$l>0$ . Esto proviene del condicionamiento de si el primer paso es cara o cruz. Además, con la codificación Heads = 1, Tails = 0, todos los caminos contados por

N (k + 1, l - 1)

$N(k+1,l-1)$ que comienzan con colas ocurrirán lexicográficamente antes que los contados por

N (k - 1, l)

$N(k-1,l)$ . Por lo tanto, para encontrar la posición lexicográfica de un camino, puede hacer lo siguiente:

Mantener una variable accum, inicialmente establecida en $0$ .
Recorra las entradas de la ruta de izquierda a derecha.
- Siempre que la entrada actual de la ruta sea cara, agregue el valor $N(k' + 1, l' - 1)$ a accum, donde $l'$ es el número de colas incluyendo y después de la entrada actual, y $k'+l'$ es el número de cabezas incluyendo y después de la entrada actual.
Después del bucle, accumigualará el índice lexicográfico deseado.

Por el contrario, para convertir de un índice lexicográfico a una ruta, puede usar el siguiente algoritmo:

Mantener una variable accum, establecida inicialmente en el índice lexicográfico dado.
Mantener dos variables $k'$ y $l'$ , inicialmente establecido en el dado $k$ y $l$ . A medida que se especifica la ruta, estos representarán los valores de $k$ y $l$ para la parte no asignada de la lista.
Mantener una lista de longitud $k+2l$ , cuyas entradas no están asignadas inicialmente (esta será la ruta de salida).
Para cada entrada de la ruta, haga lo siguiente:
- Revisa para ver si $N(k' + 1, l' -1)$ es menor o igual que accum. Si es así, entonces la entrada actual de la ruta debe establecerse en encabezados. Además, debes restar $N(k' + 1,l' -1)$ de accum. Finalmente, reste uno de $k'$ .
- De lo contrario, la entrada actual de la ruta debe establecerse en cruces y accumpermanece sin cambios. Luego, agrega uno a $k'$ , y restamos uno de $l'$ .

Si su único propósito es recorrer de manera eficiente todas estas rutas en orden lexicográfico, entonces no es necesario realizar conversiones entre rutas e índices lexicográficos. Todo lo que necesita es un método que, dado un camino, encuentre el siguiente camino lexicográficamente. Al llamar a este método repetidamente, recorrerá todas las rutas.

Aquí está la idea de tal método. Dado un camino como una secuencia de Hy T, el siguiente camino viene dado por...

Encontrar una instancia de TH(es decir, cruz seguida inmediatamente por cara) y reemplazarla con HT.
- Si hay varias instancias de TH, elija la más a la derecha para la que el cambio TH -> HTtodavía deja una ruta legal. El cambio es legal si y solo si la riqueza acumulada hasta pero sin incluir THes como máximo $k-2$ .
Reorganizando todos los lanzamientos a la derecha de esa instancia de THmodo que todas las colas ocurran antes que las caras.

Por ejemplo, supongamos que $k=4$ y $l=3$ , y la ruta actual es

T H H T H H H T H H

Hay tres instancias de TH. La riqueza acumulada ante cada uno de ellos, de izquierda a derecha, es $0$ , $1$ , y $3$ . Los que dejarían un camino legal si cambias son $0$ y $1$ ; el último $3$ es demasiado, ya que $k-2=2$ . Por lo tanto, cambiamos el último. Todas las cabezas posteriores se mueven lo más a la derecha posible. Aquí está el siguiente camino, donde las caras y las cruces que se intercambiaron están marcadas con ^.

T H H H T T H H H H
      ^ ^

¡Gracias, esto funciona! Pero todavía no entiendo por qué solo agregamos el término para acumular cuando vemos cara.
@RohitPandey Piense en contar la posición de "bacalao" en la lista ordenada lexicográficamente de palabras de tres letras. Esto se puede hacer una letra a la vez. mantener accum_ Primero miras 'c'. Ahora conoces cualquier obra de la forma a**o b**está debajo de la palabra, así que agregas $2\cdot 26^2$ a accum. El por la "o", le agregas $14\cdot 26^1$ , y añadir $3\cdot 26^0$ para $d$ ... La misma idea está sucediendo aquí. A medida que escanea la palabra, cuando ve "cabezas", sabe que un montón de palabras deben estar debajo de su palabra, por lo que agrega el número de esas para acumularlas. Al final, ha contado todas las palabras a continuación.

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

Rohit Pandey

Mike Earnest

Rohit Pandey

Mike Earnest

Rohit Pandey

Respuestas (1)

Mike Earnest

Rohit Pandey

Mike Earnest

¿Trayectorias de coeficientes binomiales?

Simplificando el producto de múltiples expansiones binomiales

Prueba combinatoria de la identidad 3n=∑nk=0(nk)2k3n=∑k=0n(nk)2k3^n=\sum_{k=0}^n \binom nk 2^k

Dos relaciones en serie, cada una implica a la otra - del libro de particiones de Andrews

Pregunta de prueba de suma binomial/combinatoria

Suma del producto de coeficientes binomiales: ∑nk=0(−1)k(nk)(n+kk)=(−1)n∑k=0n(−1)k(nk)(n+kk)=(− 1)n\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{n + k}{k} = (-1)^n

Un enfoque diferente en la distribución de 888 bolas distintas en 666 cajas distintas, de modo que cada caja tenga al menos 111 bolas.

cálculo de rutas permitidas

Probabilidad de sacar 5 cartas del mazo barajado

Muestra la identidad: ∏i=12n+1(x+n+1−i)=x∏i=1n(x2−i2)∏i=12n+1(x+n+1−i)=x∏i= 1n(x2−i2)\prod^{2n+1}\limits_{i=1}(x+n+1-i) = x\prod^{n}\limits_{i=1}(x^2- yo ^ 2)