Número de permutaciones de los objetos de 2 tipos con la restricción de orden 2n

Question

Hay dos tipos de objetos: a y B. Todos los objetos son indistinguibles de los objetos del mismo tipo, pero no de los objetos de otro tipo.

Para un entero dado n, donde hay n objetos de cada tipo (por lo que hay 2n objetos) tengo que encontrar el número de permutaciones que satisfacen la siguiente condición:

Mirando la secuencia desde el principio, uno nunca debe encontrar más objetos de tipo B que las de tipo a, es decir, el i-ésimo objeto de tipo B sólo puede mostrar si hay al menos me objetos de tipo a antes.

Jurídico de las secuencias que incluyen:

• n=1: a B
• n=2: a a B B / a B a B

Secuencias ilegales incluyen:

• n=1: a B
• n=2: a B B a / B a a B B a / B a B a / B B a a

Sé que el número total de permutaciones es (2n)!/((n!)^2), pero no pude encontrar la forma de llegar a el número de permutaciones que satisfacen la condición.

Cualquier ayuda es muy apreciada.

Answer 1

Esto es equivalente a encontrar el número de rutas en una red de $(0,0)$ $(n,n)$que nunca caen por debajo de la diagonal, y la respuesta es dada por el catalán números, que tienen la relación de recurrencia $$C_{n+1}=\sum_{i=0}^{n}C_i\,C_{n-i}\quad\text{for }n\ge 0.$$

El catalán números son una de las secuencias que aparecen una y otra vez en la combinatoria. Son vale la pena conocer.

Probablemente sería instructivo para convencerse de que su problema no en el hecho de tener la recurrencia de la relación anterior.