Número de ingredientes de pizza diferentes

Question

Krishna está preparando una pizza con 8 rebanadas, y tiene 10 ingredientes para poner en la pizza. Puede poner solo un ingrediente en cada rebanada pero puede usar el mismo ingrediente en cero o más rebanadas. ¿De cuántas maneras diferentes puede preparar las rebanadas para que no se use el mismo ingrediente en rebanadas adyacentes?

Answer 1

Estoy considerando el caso en el que dos pizzas se consideran diferentes si difieren por rotación. Como sugiere el OP en los comentarios, hay 10 opciones para la primera rebanada y 9 para la segunda, tercera, cuarta, quinta, sexta y séptima rebanada. Sin embargo, es incorrecto asumir que hay ocho opciones restantes para la octava rebanada: si la séptima rebanada tiene el mismo topping que la primera, entonces hay nueve opciones. Para considerar la cantidad de posibles toppings para la última rebanada, debemos calcular la probabilidad de que los toppings de la primera y séptima rebanada sean iguales. Denotemos como $P[T_k]$ la probabilidad de que la $k^{va}$ rebanada tenga el mismo topping $T$ que la primera rebanada. Para una pizza válida, obtenemos:

$$P[T_k] = \frac{0}{9} P[T_{k-1}] + \frac{1}{9} P[\neg T_{k-1}] = \frac{1}{9} (1-P[T_k])$$

Dado que $P[T_2] = 0$, obtenemos:

$$P[T_7] = \frac{1}{9}\bigg(1-\frac{1}{9}\bigg(1-\frac{1}{9}\bigg(1-\frac{1}{9}\bigg(1-\frac{1}{9}\bigg)\bigg)\bigg)\bigg) = \frac{12536380}{125361677} = 0.1000016935$$

Entonces, el número total de pizzas posibles, sin tener en cuenta la rotación, es:

$$10 \cdot 9^6 \cdot(P[T_7] \cdot 9 + P[\neg T_7] \cdot 8) = 43,046,730$$

Actualización: el siguiente programa en Python evalúa el número de pizzas válidas para $n$ rebanadas y $k$ toppings. Para $n=8$ y $k=10$, la salida efectivamente es igual a $43,046,730$.

import itertools

n = 8
k = 10
i = 0
for t in itertools.product(range(k), repeat=n):
  v = 1
  for s in range(n):
    if t[s] == t[(s+1)%n]:
      v = 0
      break
  i += v
print(i)

Answer 2

Existe alguna fórmula de recursión que se puede lograr para resolver el problema para cualquier cantidad de rebanadas de pizza (con un orden fijo). Para las pizzas que son consideradas iguales si solo difieren por rotación podemos extender ese resultado usando el lema de Burnside.

Para el orden fijo: Sea $n$ el número de rebanadas de pizza y $a_n$ el número de pizzas válidas. Para $n=1$, tenemos 10 soluciones diferentes, para $n=2$ tenemos $90=10\cdot 9$ soluciones diferentes y para $n=3$, tenemos $10\cdot 9\cdot 8$ soluciones diferentes. Para $n\geq 4$ dividimos los casos en función de si las rebanadas número 1 y $n-1$ tienen el mismo topping o no. Si tienen el mismo topping, al quitar las rebanadas $n-1$ y $n$ obtenemos una "pizza más pequeña" con la estructura deseada y para la rebanada $n$, hay 9 toppings posibles (ya que ambas rebanadas contiguas tienen el mismo topping).

Si 1 y $n-1$ tienen toppings diferentes al quitar solo la rebanada $n$ obtenemos una pizza más pequeña del mismo tipo y para la rebanada $n$, hay solo $8$ toppings posibles. Así que para $n\geq 4$ obtenemos $$a_n=8a_{n-1}+9a_{n-2}.$$

Resolviendo esta ecuación (ver p. ej. https://en.wikipedia.org/wiki/Recurrence_relation#Solving) obtenemos $a_n=9^n+8\cdot(-1)^n$. Para $n=8$, obtenemos 43 046 730 posibilidades.

Una manera más abstracta de lo que hemos hecho hasta ahora es decir que hay $n$ objetos diferentes en un círculo que están coloreados de 10 formas posibles de modo que los vecinos no tienen el mismo color (=topping).

Si las pizzas se identifican cuando difieren por rotación llamemos las rebanadas $1, \ldots 8$ y dejamos operar al grupo $G$ generado por la permutación $\sigma:=(1~2~3~4~5~6~7~8)$ en el conjunto $S$ que contiene esas 43 046 729 pizzas diferentes anteriores de manera obvia. Tenemos que contar el número de órbitas de este conjunto bajo la operación dada. Por lo tanto, debemos calcular el número de toppings fijos bajo cada uno de los 8 elementos del grupo. Observa que $\sigma^k$ para $k\in \{1,\ldots, 8\}$ es una permutación que consiste en $k$ ciclos de longitud $\frac{8}{\mathrm{ggT}(8, k)}$. Una pizza es fija bajo una permutación si todas las rebanadas en un ciclo tienen el mismo topping.

Para $\sigma^0$ así que tenemos 43 046 729 pizzas fijas. Para $\sigma^k$ con $k\in\{1,3,5,7\}$ no tenemos pizzas fijas. Para $\sigma^k$ con $k\in\{2,6\}$ tenemos 90 pizzas fijas. Para $\sigma^4$ tenemos 6570 pizzas fijas (estas se pueden contar de manera similar al primer caso). Así que, según el lema de Burnside, tenemos $$\frac18\cdot (43046730+4\cdot0+2\cdot90+ 6570)= 5381685$$ de tales pizzas.