Por qué con mi método estoy contando más de lo dado en cada caso de más de 3 fichas

Question

El problema con el que me encontré fue este:

A $7 \times 1$ tablero está completamente cubierto por $m \times 1$ baldosas sin solapar.

Cada ficha puede cubrir cualquier número de casillas consecutivas, y cada ficha queda completamente en el tablero.

Cada ficha es roja, azul o verde.

Dejemos que $N$ sea el número de tilings de la $7 \times 1$ tablero en el que se utilizan los tres colores al menos una vez.

Por ejemplo, un $1 \times 1$ rojo seguido de un $2 \times 1$ azulejo verde, un $1 \times 1$ azulejo verde, un $2 \times 1$ azulejo azul, y un $1 \times 1$ El azulejo verde es un azulejo válido.

Tenga en cuenta que si el $2 \times 1$ azulejo azul se sustituye por dos $1 \times 1$ azulejos azules, esto da lugar a un alicatado diferente.

Lo que hice fueron casos hechos para el número total de baldosas:

como para 3 baldosas haciendo $x_1$ + $x_2$ + $x_3$ = 7 , donde $x_1$ , $x_2$ , $x_3$ ¡representa las longitudes de cada baldosa, que deben ser algunas hasta 7 y luego multiplicar por 3! Para 3 colores de este método para los casos más de 3 azulejos ,

me parece que siempre cuento mal, como por ejemplo para 5 fichas que hice primero $x_1$ +... $x_5$ = 7 esto indica que el número de combinaciones de azulejos posibles es 6C4 , y ahora los azulejos pueden ser de dos tipos (1,1,3) ,(1,2,2) , donde cada uno representa las combinaciones de colores de tres colores .

Ahora para el primer tipo es como elegir 1, luego otro 1, luego 3 así que es esto: ¡5C1 * 4C1 * 3C3 y luego 3! Para tres colores, el siguiente tipo sería 5C1 * 4C2 * 2C2 * 3. .

Pero creo que estoy cometiendo algún error de couting como tengo que hacer alguna división o multiplicación de números aquí que conduce a la respuesta correcta para cada caso. ¿Alguien puede decir lo que está mal en este caso de 5 fichas?

Answer 1

Has contado de más por un factor de $2$ al final. No deberías multiplicar por $3!$ sino por $3$ . Al asignar colores en el patrón $(1,1,3)$ Por ejemplo, sólo tiene que decidir qué color se produce $3$ veces; después no hay opción. En el patrón $(2,2,1)$ Sólo tienes que decidir qué color aparece una vez.

Otra forma de hacer esta parte del problema es la inclusión-exclusión. Hay $3^5$ formas de colorear $5$ baldosas con $3$ colores. Hay que restar las formas que sólo utilizan $2$ colores, por lo que tenemos $3^5-3\cdot2^5$ . Ahora bien, ¿qué hay de una coloración con un solo color? Se ha contado una vez originalmente, y se ha restado dos veces, ya que una de las dos coloraciones no la incluye, así que tenemos que volver a añadirla. Esto da una respuesta final de $$3^5-2\cdot2^5+3=150$$ Tenga en cuenta que esto es lo mismo que $$\binom51\binom41\cdot3+\binom51\binom42\cdot3=150$$