Permutaciones con restricción

Question

Tenemos $n$ tipos de objetos, y el número de objetos de tipo $i$ es $a_i$, $1\leq i\leq n.

¿Cuál es el número de permutaciones de los objetos $\sum_{i=1}^n a_i$, si ningún par de objetos del mismo tipo están juntos?

Un ejemplo simple: Si tenemos los objetos $\{a,a,a,b,b,c,c\}$, entonces permitimos $abcabac$ pero no $aaabbcc$.

Answer 1

Gessel da una fórmula para esto (Sección 6) como una aplicación de su teoría de polinomios de alfil generalizados (ver también http://arxiv.org/abs/1306.6232). Sea $L^{(\alpha)}_n(x)$ el polinomio de Laguerre generalizado $\sum_{k=0}^n (-1)^k \frac{1}{k!}{n+\alpha \choose n-k} x^k$ y $q_n(x) = (-1)^n L^{(-1)}_n(x)$, y sea $\Phi$ el funcional lineal en polinomios que lleva $x^n$ a $n!$. Entonces $$ \Phi(q_{n_1}(x) \cdots q_{n_k}(x)) $$ es el número de palabras con $n_i$ letras $i$ donde ninguna dos letras son adyacentes. Para tratar las $i$ como diferentes, reemplace $q_n$ por $n! q_n$.

Por ejemplo, $$q_2(x) = -x + \frac{1}{2}x^2\\ q_3(x) = x - x^2 + \frac{1}{6}x^3, $$ así que el número de permutaciones de $aaabbcc$ sin letras idénticas adyacentes es \begin{align*}\Phi(q_3(x)q_2(x)^2) &= \Phi(x^3 - 2x^4 + \frac{17}{12}x^5 - \frac{5}{12}x^6 + \frac{1}{24}x^7)\\ &= 3! - 2\cdot 4! + \frac{17}{12}\cdot 5! - \frac{5}{12}\cdot 6! + \frac{1}{24}\cdot 7!\\ &= 38. \end{align*}

No sorprendentemente, esto proviene de la inclusión-exclusión. Sea $$B_p = \{(i,j) : n_1 + \cdots + n_{p-1} + 1 \leq i \neq j \leq n_1 + \cdots + n_p\},$$ y $B = B_1 \cup \cdots \cup B_p$. Digamos que una permutación $w_1 \cdots w_n$ de $n = n_1 + \cdots + n_p$ concuerda con $A$ si $j$ sigue inmediatamente a $i$ en $w$ para cada $(i,j) \in A$, y digamos que $A$ es compatible si alguna permutación concuerda con ella. Queremos el número de permutaciones de $n$ que no concuerdan con ningún subconjunto no vacío de $B$. Por inclusión-exclusión, esto es $$ \sum_{\substack{A \subseteq B\\ A \text{ compatible}}} (-1)^{|A|} (n-|A|)! = \Phi(r_B(x)), $$ donde $\displaystyle r_B(x) = \sum_{\substack{A \subseteq B\\ A \text{ compatible}}} (-1)^{|A|} x^{n-|A|}$.

Define $r_{B_p}(x)$ de manera similar; entonces $r_B = r_{B_1} \cdots r_{B_k}$. Se obtiene un $i$-subconjunto compatible de $B_p$ eligiendo un orden en $\{n_1 + \cdots + n_{p-1} + 1, \ldots, n_1 + \cdots + n_p\}$, luego eligiendo $n_p-i-1$ comas para dividir la lista en fragmentos (por ejemplo, si el conjunto ordenado es $(2,3,1,5,4)$, podrías dividirlo en fragmentos $23|1|54$, lo que significa que las condiciones $3$ sigue a $2$ y $4$ sigue a $5$), y finalmente dividiendo por $(n_p-i)!$ ya que el orden de los fragmentos no importa.

Por lo tanto, $$r_{B_p}(x) = \sum_{i=0}^{n_p} (-1)^i n_p! {n_p - 1 \choose n_p - i - 1} \frac{x^{n_p - i}}{(n_p-i)!},$$ lo cual termina siendo $n_p! q_{n_p}(x)$ tras un poco de reindexación.

Answer 2

Dejen que $\mathbf e_1$ hasta $\mathbf e_n$ sean los vectores unitarios en $\mathbb R^n$, y que $\mathbf a = \sum_{i=1}^n a_i \mathbf e_i\in\mathbb N^n$ sea el vector de conteo. Así que $\mathbf a-\mathbf e_i$ es una forma de decir "tomar los conteos de $\mathbf a$ y restar uno del conteo $i$-ésimo".

Dejen que $C(\mathbf a)$ sea el número de formas de organizar elementos de acuerdo al vector de conteo $\mathbf a$ sin duplicados, y dejen que $D(i, \mathbf a)$ sea el número de formas de organizar elementos de acuerdo a los conteos $\mathbf a$ de tal manera que $i$ sea el primer elemento. Obten estas relaciones:

\begin{align*} C(\mathbf a) &= \sum_{i=1}^n D(i, \mathbf a) \\ D(i, \mathbf a) &= C(\mathbf a - \mathbf e_i) - D(i, \mathbf a - \mathbf e_i) \end{align*}

Esta formulación no considera los casos en los que los conteos se vuelven cero. Pero la idea debería ser bastante clara: tienes $n$ formas de comenzar tu secuencia, y para cada posible elemento de inicio, cuentas el número de formas de organizar los restantes, pero luego nuevamente eliminas esas disposiciones que hubieran repetido el primer elemento. Puedes reformular esto sin $D$:

$$C(\mathbf a) = \sum_{i=1}^n C(\mathbf a-\mathbf e_i) - C(\mathbf a-2\mathbf e_i) + C(\mathbf a-3\mathbf e_i) \dots = \sum_{i=1}^n\sum_{j=1}^{a_i}(-1)^{j+1}C(\mathbf a-j \,\mathbf e_i)$$

Ahora sabes cómo calcular $C(\mathbf a)$ si tienes el número de combinaciones $C(\mathbf{a'})$ para todos los $\mathbf{a'}$ con $\lVert \mathbf{a'}\rVert_1=\lVert \mathbf a\rVert_1-1$, es decir, para todos los vectores de conteo donde se ha reducido un conteo por uno. También tienes $$C(\mathbf 0)=1$$ como base para todos tus conteos. Así que puedes calcular $C(\mathbf a)$ usando programación dinámica. En el camino, todos los vectores de conteo $\mathbf{a'}$ para los cuales calculas $C(\mathbf{a'})$ serán menores o iguales a $\mathbf a$ en cada coordenada, así que puedes calcular un límite para el número de esos valores intermedios como

$$\prod_{i=1}^n a_i+1$$

Dependiendo de los conteos $a_i$, esto puede o no ser adecuado para tu aplicación.

Para tu caso de ejemplo (calculado ya sea sin $D$ o con $D$), obtengo $C(3,2,2)=38$, lo cual es consistente con una computación de fuerza bruta de ese conteo. En caso de que realmente desees distinguir los diferentes objetos del mismo tipo, debes considerar todas las permutaciones dentro de cada tipo, y obtener $38\cdot3!\cdot2!\cdot2!=912$ que según una computación de fuerza bruta similar debería ser el número correcto para esa configuración también.

Para el caso de $a=(2,2,2,2)$, es decir, $n=4$ y $a_1=a_2=a_3=a_4=2$, mi enfoque da una respuesta de 864, consistente con esta respuesta a una pregunta relacionada pero más específica.