Topología de los mensajes del foro

Question

Bien, aquí hay una pregunta interesante con respecto a los foros web. Digamos que tienes un foro típico, como la sección de comentarios de un blog, o lo que sea. Los espectadores pueden publicar comentarios en respuesta a la entrada inicial del blog (en cuyo caso la entrada aparece al final de la lista), o como respuesta a cualquier comentario existente previamente (en cuyo caso la entrada aparece debajo del comentario al que se responde, con sangría). Nada revolucionario, ya lo has visto en cientos de sitios web.

Esta es la pregunta. Después de que se hayan publicado N comentarios, ¿cuántos topológicamente único ¿acuerdos puede haber para los comentarios en el foro? Lo que quiero decir es que, si se observa la forma de los mensajes en el hilo (ignorando su contenido y la hora de publicación), ¿cuántas disposiciones únicas puede haber? Esto significa que para 3 carteles, A, B y C, los siguientes casos son equivalentes:

A        A
B      C
C        B

Así, para N = 3, el número total de arreglos es de 5:

A        A        A        A        A
B        B        B      B      B
C        C      C        C        C

Si no fuera por la restricción topológicamente única, la respuesta sería simplemente f(N-1) * N o N! . Para N < 3 Esto es realmente cierto; f(0) = f(1) = 1 y f(2) = 2 . El primero no puede elegir dónde publicar, y el segundo puede responder al blog inicial o al primero. Pero a partir de ahí, la cosa se complica. f(3) sería 3! o 6 si no fuera por ese caso duplicado. Para N's más altos, hay cada vez más casos equivalentes. ¿Alguien puede proponer una fórmula sencilla que cubra esto para cualquier N?

Answer 1

El anser es el número catalán $C(n)=\frac{(2n)!}{n!(n+1)!}$ que también es "el número de árboles con raíces ordenadas con $n$ nodos, sin incluir la raíz" (cf. OEIS ). Aquí, la raíz no incluida es "el propio foro".