Usando los números catalanes

Question

Usando los números catalanes

Matemáticas
numeros-catalan

yotamoo

Aquí hay una pregunta que tenemos como tarea:

Un partido de fútbol entre el equipo A y el equipo B termina con un empate 9-9. Se sabe que en algún momento del juego el equipo A tenía la delantera y que luego fue el equipo B quien la tuvo. ¿Cuántas series de 18 goles pueden representar el curso del juego?

Sugerencia: utilice la técnica de doble reflexión.

Entonces, esta sugerencia realmente no me ayuda, ya que no entiendo qué es un doble reflejo. Aparte de eso: pensé en contar todas las series posibles, que es el número catalán C ₉ , y luego restar todas las series donde B anotó el primer gol, pero es un poco vago en mi mente.

Cualquier pista que me ayudaría a empezar sería genial. ¡Gracias!

Hizo

El principio de reflexión se explica aquí . (Con respecto a su tercer párrafo, tenga en cuenta que el primer gol puede ser marcado por B.)

yotamoo

Entiendo el principio de reflexión, pero ¿qué significa doble reflexión? Probablemente sea una pregunta para mi TA, pero aún así... Además, la forma en que entiendo la pregunta A debe marcar el primer gol.

joriki

No creo que haya una implicación de que el equipo A deba marcar el primer gol. Tuvieron la ventaja en algún momento .

yotamoo

Bien, y si es así, ¿cómo empiezo?

Respuestas (5)

Usando los números catalanes

El principio de reflexión se explica aquí . (Con respecto a su tercer párrafo, tenga en cuenta que el primer gol puede ser marcado por B.)
Entiendo el principio de reflexión, pero ¿qué significa doble reflexión? Probablemente sea una pregunta para mi TA, pero aún así... Además, la forma en que entiendo la pregunta A debe marcar el primer gol.
No creo que haya una implicación de que el equipo A deba marcar el primer gol. Tuvieron la ventaja en algún momento .

loco · Answer 1

Sugerencia : probablemente sea más fácil contar las formas en que la condición puede fallar: es decir, el número de series en las que B gana/empata hasta cierto punto de inflexión, y luego A gana/empata por el resto del torneo.

Aquí hay una imagen canónica de tipo catalán que demuestra esto:

cuadro de tipo catalán

El punto marcado en rojo y amarillo es el punto de inflexión aquí. Ahora, ¿cómo puedes usar la técnica de reflexión en esto para obtener un gráfico catalán donde la línea negra siempre está arriba de la diagonal? ¿Puedes usar esto para terminar el problema?

Si reflexiono desde el punto marcado y en adelante, entonces cuento todas las series en las que B gana/empata (o A nunca lidera). ¿Son todas las formas para que la condición falle? ¿Qué pasa con una serie donde B nunca lidera? ¿Debo duplicar el número que encuentro para incluir ambas opciones?

joriki · Answer 2

No pude resolver el problema basándome solo en la sugerencia de Lopsy, así que aquí hay un poco más.

Primero, está muy bien aplicar ingeniosos trucos de reflexión, pero son mucho más fáciles de encontrar si ya sabes el resultado que estás buscando; así que primero derivemos mecánicamente el resultado usando funciones de generación y luego pensemos en cómo obtenerlo de manera más elegante.

Las secuencias que no cumplen el requisito constan de un segmento (posiblemente vacío) en el que $B$ está a la cabeza, seguido de un segmento (posiblemente vacío) en el que $A$ está a la cabeza. Dichos segmentos en los que la delantera no cambia se cuentan con los números catalanes, por lo que estas secuencias no válidas se cuentan mediante una convolución de los números catalanes consigo mismos (con la suma corriendo sobre el punto donde cambia la delantera). En términos de funciones generadoras, eso significa que la función generadora $G$ de las sucesiones inválidas es el cuadrado de la función generadora $C$ de los números catalanes. Con

C (X) = \frac{1 - \sqrt{1 - 4 X}}{2 X},

$C(x)=\frac{1-\sqrt{1-4x}}{2x}\;,$

que rinde

GRAMO (X) = C (X)^{2} = \frac{1}{X} (\frac{1 - \sqrt{1 - 4 X}}{X} - 1) = \frac{C (X) - 1}{X} .

$G(x)=C(x)^2=\frac1x\left(\frac{1-\sqrt{1-4x}}x-1\right)=\frac{C(x)-1}x\;.$

De este modo, $G$ es solo $C$ con el término constante eliminado y desplazado hacia abajo en uno, es decir, $G_n=C_{n+1}$ .

Conociendo el resultado, es un poco más fácil ver cómo aplicar la reflexión. El problema de seguir la sugerencia de Lopsy es que no es obvio cómo obtener una biyección: es fácil reflejar la parte debajo de la diagonal hacia arriba, pero no está claro qué biyección establece. Sabiendo que queremos terminar con los números catalanes uno más arriba, podemos usar la ranura adicional para hacer que la secuencia reflejada sea única: al insertar un paso hacia arriba antes del segmento reflejado y un paso hacia abajo después, obtenemos una biyección de las secuencias inválidas a las secuencias que evitan la diagonal con dos pasos más, ya que el punto de inflexión ahora está marcado únicamente como la última intersección con la diagonal en la nueva secuencia.

La convolución de números catalanes que produce $G=C^2$ en su respuesta corresponde a la descomposición de @Lopsy de cada camino (in)admisible en un camino desde (0,0) a algún (x+1,x) que permanece por encima de la diagonal excepto en su punto final, y un camino desde (x, x) a (9,10) que permanece por debajo de la diagonal excepto en su punto final.
@Didier: a) No entiendo por qué incluye un segmento adicional en las rutas; ¿no sería más sencillo decir que la descomposición es en una ruta de (0,0) a (x,x ) y uno de (x,x) a (9,9)? b) Acepto que esta descomposición corresponde a la convolución; pero no veo cómo esto da una pista sobre cómo usar la reflexión para configurar una biyección.
Re (a), no es necesario sumar estos segmentos elementales, pero mencioné el punto (x+1,x) (y el correspondiente (9,10)) para aclarar la razón por la cual la descomposición es biyectiva: uno no corte la ruta global en el primer golpe de la diagonal pero en su primer cruce de la diagonal. Re (b), supongo que la idea es reflejar la segunda parte para tener dos caminos similares en sucesión. Una vez más, estoy de acuerdo contigo en que esto no es necesario.
@Didier: Lo siento, puede que esté siendo un poco denso, pero no lo entiendo. Entiendo que el camino se corta en el primer cruce, no en el primer golpe, pero una vez que se refleja, ¿cómo se decide cuál de los golpes se convierte en un cruce para volver al original y hacer el mapeo biyectivo? ¿O de alguna manera está utilizando estos segmentos adicionales de manera similar a como lo hice en mi respuesta para evitar más aciertos en la parte reflejada? (Tomé la sugerencia de Lopsy en el sentido de que uno simplemente debe reflejar en la diagonal).
¡Por supuesto que no hay biyección con el conjunto de caminos de longitud 18 completamente por encima de la diagonal! (De lo contrario, se tendría G=C.) Cada uno de estos caminos p corresponde a tantos caminos admisibles como el número n(p) de veces que llega a la diagonal. Seguramente los verdaderos combinatorianos saben de memoria que la función generadora C^2 enumera el conjunto de caminos p ponderados por n(p)...
@Didier: No soñaría con considerarme un verdadero combinatorista :-) De hecho, una gran parte de lo que sé sobre combinatoria lo aprendí en este sitio durante el último año. Me temo que todavía no entiendo a qué te refieres. Incluso asumiendo el conocimiento rutinario de los verdaderos combinatores, eso solo nos dice que a) el número de caminos (in)admisibles, b) el número de pares de caminos de Dyck y c) el número de caminos de Dyck ponderados por $n(p)$ son todos iguales, pero para saber que este es el catalán número uno más arriba, ¿todavía necesitamos el cálculo de la función generadora o una biyección?
Creo que la escuela de Flajolet (y el mismo Flajolet) desarrollaron formas de automatizar, hasta cierto punto, exactamente eso: la traducción de descomposiciones de estructuras discretas y/o sus ponderaciones, en términos de relaciones entre las funciones generadoras que las enumeran. Lamento ser tan vago, pero no tengo tiempo para ampliar esto en este momento. Diapositivas de charlas recientes o semi-recientes de Flajolet (o tal vez el mini-curso de Bousquet-Mélou en ALEA 2011) seguramente explican esto mejor que yo.
@Didier: Buena coincidencia: he estado leyendo Analytic Combinatorics de Flajolet y Sedgewick durante las vacaciones para dar una mejor respuesta a esta pregunta . Así que estoy al tanto de su enfoque (aunque no lo estaba hace dos semanas), y probablemente por eso se me ocurrió elevar al cuadrado la función generadora, pero me pareció que la pregunta requería una prueba biyectiva; eso es lo que me faltaba en la sugerencia y quería proporcionar.

robarjohn · Answer 3

Esto sigue de cerca la sugerencia de Lopsy y la respuesta de Joriki. Copio aquí mi respuesta a un problema de sci.math .

Pregunta: Supongamos que hay $n$ ' $-1$ ' y $n$ ' $+1$ '. ¿Cuál es la relación de recurrencia para las permutaciones donde todos los subtotales que comienzan desde la izquierda no son negativos?

Respuesta: Llamemos a un arreglo de $n$ ' $+1$ 'arena $n$ ' $-1$ 's un paseo de tipo $n$ . Llamemos también un paseo que no tiene suma parcial negativa un paseo unilateral.

Dejar $w(n)$ sea el número de caminatas unilaterales de tipo $n$ . Clasifiquemos estos paseos por el tipo de su subpaseo inicial más pequeño. Aquellos cuyo subpasillo inicial más pequeño es del tipo $k$ se parece a esto:

+ 1 < un paseo unilateral de tipo k - 1 > - 1 < un paseo unilateral de tipo norte - k >

$+1<\text{a unilateral walk of type }k{-}1>-1<\text{a unilateral walk of type }n{-}k>$ Al considerar todos los tipos posibles de subpaseo inicial, obtenemos la siguiente relación recursiva:

\begin{matrix} (1) & w (norte) = w (0) w (norte - 1) + w (1) w (norte - 2) + w (2) w (norte - 3) + \dots + w (norte - 1) w (0) \end{matrix}

$w(n) = w(0)w(n-1) + w(1)w(n-2) + w(2)w(n-3) + \dots + w(n-1)w(0)\tag{1}$ con la condición inicial de que

w (0) = 1

$w(0) = 1$ .

Ahora que tenemos la relación recursiva, intentemos encontrar una forma cerrada. La mejor manera es mirar la función generadora:

\begin{matrix} (2) & F (X) = w (0) + w (1) X + w (2) X^{2} + w (3) X^{3} + \dots \end{matrix}

$f(x) = w(0) + w(1)x + w(2)x^2 + w(3)x^3 + \dots\tag{2}$ La relación recursiva

(1)

$(1)$ da

f (x) = 1 + x f (x)^{2}

$f(x) = 1 + xf(x)^2$ . Resolviendo esto con la fórmula cuadrática da

f (x) = \frac{1 - \sqrt{1 - 4 x}}{2 x}

$f(x) = \frac{1 - \sqrt{1-4x}}{2x}$ . Podemos usar el teorema del binomio para obtener la serie de potencias para

\sqrt{1 - 4 x}

$\sqrt{1-4x}$ , resta eso de

1

$1$ , y dividir por

2 x

$2x$ . Esto da

\begin{matrix} (3) & F (X) = 1 + X + 2 X^{2} + 5 X^{3} + 14 X^{4} + \dots + \frac{1}{norte + 1} (\binom{2 norte}{norte}) X^{norte} + \dots \end{matrix}

$f(x) = 1 + x + 2x^2 + 5x^3 + 14x^4 + \dots + \frac{1}{n+1}\binom{2n}{n} x^n + \dots\tag{3}$ e igualando los coeficientes de

(2)

$(2)$ y

(3)

$(3)$ obtenemos

w (n) = \frac{1}{n + 1} (\binom{2 n}{n})

$w(n) = \frac{1}{n+1}\binom{2n}{n}$ .

Respuesta a la pregunta mal leída

Al principio, interpreté mal la pregunta buscando la cantidad de juegos empatados en los que cada lado tenía la ventaja en algún momento. En caso de que esto responda alguna consulta futura, dejo esta solución, pero tenga en cuenta que no responde la pregunta realizada.

Puesto que hay $\binom{2n}{n}$ paseos de tipo $n$ , restando los paseos unilaterales a ambos lados, hay

\begin{matrix} (4) & (\binom{2 norte}{norte}) - 2 C_{norte} = \frac{norte - 1}{norte + 1} (\binom{2 norte}{norte}) \end{matrix}

$\binom{2n}{n}-2C_n=\frac{n-1}{n+1}\binom{2n}{n}\tag{4}$ paseos de tipo

n

$n$ cuyas sumas parciales son tanto positivas como negativas.

Respuesta a la pregunta formulada

La pregunta pide el número de juegos empatados donde A tiene la ventaja en algún momento y B tiene la ventaja en un punto posterior. La negación de esta condición es un juego empatado donde cualquier ventaja que tenga B es anterior a cualquier ventaja que tenga A. Así que el número de juegos que no queremos contar es

\begin{matrix} (5) & \sum_{k = 0}^{norte} \overset{B conduce}{\overset{⏞}{\frac{1}{k + 1} (\binom{2 k}{k})}} \overset{una lleva}{\overset{⏞}{\frac{1}{norte - k + 1} (\binom{2 norte - 2 k}{norte - k})}} \end{matrix}

$\sum_{k=0}^n\overbrace{\frac1{k+1}\binom{2k}{k}}^{\text{B leads}}\overbrace{\frac1{n-k+1}\binom{2n-2k}{n-k}}^{\text{A leads}}\tag5$ que es la convolución de los Números Catalanes consigo mismos, cuya función generadora es el producto de las funciones generadoras de los Números Catalanes. Entonces la función generadora de

(5)

$(5)$ es

f (x)^{2}

$f(x)^2$ , que por la relación anterior,

f (x) = 1 + x f (x)^{2}

$f(x)=1+xf(x)^2$ , es

\begin{matrix} (6) & \frac{F (X) - 1}{X} \end{matrix}

$\frac{f(x)-1}{x}\tag6$ Es decir, el número de juegos empatados que no queremos contar es

C_{n + 1}

$C_{n+1}$ . Por lo tanto, el número de juegos empatados que queremos contar es

(\binom{2 n}{n}) - C_{n + 1}

$\binom{2n}{n}-C_{n+1}$

\begin{matrix} (7) & (\binom{2 norte}{norte}) - C_{norte + 1} = \frac{norte (norte - 1)}{(norte + 2) (norte + 1)} (\binom{2 norte}{norte}) \end{matrix}

$\binom{2n}{n}-C_{n+1}=\frac{n(n-1)}{(n+2)(n+1)}\binom{2n}{n}\tag7$

esto no es lo mismo que la respuesta de @joriki si estoy leyendo todo correctamente. Su respuesta indica que tomamos la $n+1$ número catalán y restarlo de $2n \choose n$ . Su resultado parece diferente de eso.
Consideremos $\binom{2n}{n}-\frac1{n+2}\binom{2n+2}{n+1}=\frac{n(n-1)}{(n+2)(n+1)}\binom{2n}{n}$ . El primer punto en el que esto no está de acuerdo con mi respuesta es $n=2$ , donde esto da $1$ y mi respuesta da $2$ . Ahora vamos a contar el número de $2$ - $2$ empates que existen donde cada lado tiene la ventaja en algún momento: $+--+$ y $-++-$ ; eso es, $2$ . Intentemos $n=3$ , donde esto da $6$ y mi respuesta da $10$ . Contemos: $\begin{array}{cc} + - + - - + & - + - + + - \\ + - - + + - & - + + - - + \\ - + + - + - & + - - + - + \\ + + - - - + & - - + + + - \\ - + + + - - & + - - - + + \end{array}$ $\begin{array}{c|c}+-+--+&-+-++-\\ +--++-&-++--+\\ -++-+-&+--+-+\\ ++---+&--+++-\\ -+++--&+---++\end{array}$ Eso es, $10$ .
La pregunta original pregunta el número de secuencias en las que A tuvo la iniciativa en algún momento y luego B la tuvo en un momento posterior . Para n=2 (un empate 2-2), de hecho, solo hay una forma de que esto suceda. +,-,-,+ o (A,B,B,A)=>2-2. Lo siento si me estoy perdiendo algo.
Ah, leí mal la pregunta. Sin embargo, no afirma que A tuvo la delantera primero, ni que B la tuvo al final, sino simplemente que A la tuvo en algún momento y B la tuvo después. voy a repensar
Aceptar. Pero en el caso de empate 2-2, la única forma en que B puede tener la ventaja después de A es si A tiene la ventaja primero.
Sí, sé que esto es diferente de lo que conté. Como digo, me lo replantearé.

hueco7 · Answer 4

No entiendo de qué están hablando los carteles anteriores, pero creo que este problema es sencillo. Básicamente, A está a la cabeza de $r$ goles y luego B toma la delantera para el otro $18-r$ objetivos.

Así que la respuesta es simplemente:

$\sum_{r=1}^{17} C_r C_{18-r}$ dónde $C_n$ es el número catalán $\frac{1}{n+1}{2n \choose n}$

Esto solo funciona si asumes que después $B$ ha tomado la iniciativa, $A$ ya nunca toma la delantera...
Sí, tienes razón, interpreté mal la pregunta, supongo jaja.

Rohit Pandey · Answer 5

En este caso, en realidad es mucho más fácil aplicar el doble reflejo en la pista de la pregunta que el enfoque de la función generadora en las respuestas. Si reflexiona una vez (alrededor de y=1 donde y es el déficit de objetivos entre A y B), obtiene los caminos en los que A estaba a la cabeza al menos una vez. esto te da ${2n \choose n-1}$ , el término que restamos de los caminos totales para obtener los números catalanes. Pero, queremos caminos donde A estaba a la cabeza y luego, B estaba a la cabeza. Entonces, necesitamos reflexionar una vez más, esta vez sobre la línea y=-1. Cuando hacemos esto, obtenemos ${2n \choose n-2}$ . Enchufar $n=9$ aquí y allá está tu respuesta. Vea la respuesta aquí: Caminos en una cuadrícula que no van por debajo $0$ o superior $l$ antes de llegar a su objetivo. para otra demostración de este truco de "reflexión múltiple" en acción.

Usando los números catalanes

yotamoo

Hizo

yotamoo

joriki

yotamoo

Respuestas (5)

loco

yotamoo

joriki

Hizo

joriki

Hizo

joriki

Hizo

joriki

Hizo

joriki

robarjohn

Rohit Pandey

robarjohn

Rohit Pandey

robarjohn

Rohit Pandey

robarjohn

robarjohn

hueco7

TMM

hueco7

Rohit Pandey

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úmeros catalanes usando la recurrencia.

Correlación entre número de caminos y números catalanes.

Número de caminos en una grilla con restricciones

¿Hay alguna forma de determinar si un número entero se encuentra entre 2 números racionales sin conocerlos?

Vladímir Zorich contra Rudin/Pugh/Abbott