Número de formas idénticas secuencias ordenadas de la interpolación

Question

¿Cuántas formas de intercalar tres secuencias idénticas (X, Y, Z) manteniendo el orden relativo? Posibilidades son XYZXYZXYZ, XXXYYYZZZ y etc., como usted puede seleccionar 3 grupos de XYZ con la orden.

Esta pregunta viene del concurso de matemáticas de la escuela de mi hijo. Para este problema particular, pude usar posterior aproximación pista y recursiva para obtener la respuesta que es 42. Pero creo que podría ser más general y simple enfoque dado la respuesta pasa a ser 7 x 6.

Answer 1

Demasiado largo para un comentario, pero no una respuesta completa.

Parece que la fórmula general podría ser:

$$\frac{1}{\binom{n+1}{1}\binom{n+2}{2}\cdots\binom{n+m-1}{m-1}}\frac{(nm)!}{n!^m}$$

cuando el intercalado de $n$ idénticas secuencias de longitud $m$.

Tenga en cuenta que, por los Jóvenes de Tableau argumento en los comentarios, esto tendría que ser simétrica en el $m,n$. Sorprendentemente, esta fórmula es simétrica, ya que puede ser reescrita como:

$$(nm!)\frac{1!2!3!...(m-1)!1!2!\dots (n-1)!}{1!2!\cdots(n+m-1)!}$$

---

Cómo llegué a esta conjetura

En resumen: la fuerza Bruta de los números, con algo de esperanza, que es como el catalán números.

Trabajando sobre la base de que es "como" el catalán números, he intentado el caso de $n$ secuencia de tres elementos, $X,Y,Z$, y la teoría de que el valor es de la forma:

$$\frac{1}{f(n)}\frac{(3n)!}{n!^3}$$

Como resulta, $f(n)$ es, durante los primeros 21 valores de, al menos, siempre un número entero, y, de acuerdo a OEIS, que coincide con la "Pentagonal números piramidales", por lo que podemos conjeturar que $f(n)=(n+1)^2(n+2)/2$.

$$\begin{matrix} n&f(n)\\ 0&1\\ 1&6\\ 2&18\\ 3&40\\ 4&75\\ 5&126\\ 6&196\\ 7&288\\ 8&405\\ 9&550\\ 10&726\\ 11&936\\ 12&1183\\ 13&1470\\ 14&1800\\ 15&2176\\ 16&2601\\ 17&3078\\ 18&3610\\ 19&4200\\ 20&4851 \end{de la matriz}$$

Así que parece que la que se obtiene la fórmula para $n$ secuencias de $3$ elementos es:

$$\frac{2}{(n+1)^2(n+2)}\binom{3n}{n,n,n}$$

---

Para el intercalado de las secuencias de los cuatro elementos, XYZW, usted parece conseguir:

$$\frac{12}{(n+1)^3(n+2)^2(n+3)}\binom{4n}{n,n,n,n}$$

---

Para las secuencias con los cinco elementos, el valor parece ser:

$$\frac{288}{(n+1)^4(n+2)^3(n+3)^2(n+4)}\binom{5n}{n,n,n,n,n}$$

OEIS me dijo la secuencia de $1,2,12,288$ fue el superfactorial secuencia, lo que significa que:

$$1=1!, 2=2!1!, 12=3!2!1!, 288=4!3!2!1!$$

Por eso, yo tengo mi conjetura respuesta en la parte superior.