Permutaciones con objetos idénticos

Question

¿Cómo puedo encontrar el número de $k$ -permutaciones de $n$ objetos, donde hay $x$ tipos de objetos, y $r_1, r_2, r_3, \cdots , r_x$ ¿dar el número de cada tipo de objeto?

Ejemplo:

Tengo 20 letras del alfabeto. Hay algunos duplicados - 4 de ellos son a 5 de ellos son b 8 de ellos son c y 3 son d . ¿Cuántas permutaciones únicas de 15 letras puedo hacer?

En el ejemplo:

$n = 20$

$k = 15$

$x = 4$

$r_1 = 4 \quad r_2 = 5 \quad r_3 = 8 \quad r_4 = 3$

Algunos antecedentes...

En un principio iba a resolver este problema para resolver otro más sencillo, pero en su lugar conseguí encontrar una solución más sencilla para ese problema. Ahora sigo buscando la solución a este problema más general por interés.

---

Editar:

He trabajado un poco más en este problema pero no he conseguido nada útil. La intuición me dice que, como sugiere Douglas a continuación, probablemente no haya una solución fácil. Sin embargo, no he podido comprobarlo con seguridad, ¿alguien más tiene alguna idea?

Editar:

Ahora he vuelto a plantear esta pregunta ( aquí ) en MO.

Answer 1

Probablemente no habrá una manera fácil de hacer esto... Considere dos ejemplos diferentes de "permutaciones" de 15 letras. Entonces el número de permutaciones con ese conjunto de dígitos depende de las proporciones de los dígitos elegidos.

Si realmente quieres hacer esto, puedes sumar $k!/(s(1)! s(2)! \cdots s(x)!)$ (llamado coeficiente del mulitnomio ) sobre todas las particiones de $s(1)+s(2)+ \cdots +s(x)=k$ [en esta partición se permite que s(i) sea cero y el orden es importante] tal que $s(i) \leq r(i)$ para todo i. La parte s(i) dice que se tienen s(i) copias de la letra i-ésima. El número de permutaciones con s(i) letras i-ésimas viene dado como en el caso anterior, por el Teorema del estabilizador orbital .

Aunque, esto es sólo un paso mejor que la fórmula de conteo del cavernícola: suma_P 1 donde P es el conjunto de permutaciones que quieres contar. Es decir, sólo hay que contarlas una a una.

EDIT: Mientras hago algunos retoques, aquí está el código GAP que implementa la fórmula anterior.

NrPermIdent:=function(k,T)
  local PSet,x;
  x:=Size(T);
  PSet:=Filtered(OrderedPartitions(k+x,x)-1,p->ForAll([1..x],i->p[i]<=T[i]));
  return Sum(PSet,p->Factorial(k)/Product(p,i->Factorial(i)));
end;;

donde T es una lista de límites y k es el número de términos de la partición.

Por ejemplo:

gap> NrPermIdent(15,[4,5,8,3]);
187957770

Como otra indicación de que encontrar una fórmula sencilla para estos números no va a ser fácil, observe que NrPermIdent(n,[n,k]) es igual a $\sum_{0 \leq i \leq k} {n \choose k}$ (que se considera una suma difícil de encontrar -- ver: https://mathoverflow.net/questions/17202/ ). Recuerdo haber leído en alguna parte (muy probablemente en A=B ) que puedes demostrar que no hay una solución de "forma cerrada" para esto.

Answer 2

Consideremos la suma definida por $$ \begin{align} &\sum_{k=0}^\infty s_k\frac{x^k}{k!}\\ &=\textstyle\underbrace{\left(1{+}x{+}\dots{+}\frac{x^8}{8!}\right)}_{\substack{\text{the exponent of $x$}\\\text{is the number of c's}}}\underbrace{\left(1{+}x{+}\dots{+}\frac{x^5}{5!}\right)}_{\substack{\text{the exponent of $x$}\\\text{is the number of b's}}}\underbrace{\left(1{+}x{+}\dots{+}\frac{x^4}{4!}\right)}_{\substack{\text{the exponent of $x$}\\\text{is the number of a's}}}\underbrace{\left(1{+}x{+}\dots{+}\frac{x^3}{3!}\right)}_{\substack{\text{the exponent of $x$}\\\text{is the number of d's}}}\tag1 \end{align} $$ Un término típico del producto que contribuye a $s_{15}\frac{x^{15}}{15!}$ es $\frac{x^7}{7!}\cdot\frac{x^2}{2!}\cdot\frac{x^3}{3!}\cdot\frac{x^3}{3!}$ que añade $\frac{15!}{7!\,2!\,3!\,3!}$ a $s_{15}$ . Esto tiene en cuenta todas las permutaciones con $7$ c's y $2$ b's y $3$ a's y $3$ d's. Sumando todas las colecciones de exponentes que suman $15$ obtenemos que $s_{15}$ tiene en cuenta todas las permutaciones de $15$ de la $20$ cartas.

Es decir, definir el función generadora exponencial de la función de indicador para el conjunto $\{i\in\mathbb{Z}:0\le i\le j\}$ : $$ P_j(x)=\sum_{i=0}^j\frac{x_i}{i!}\tag2 $$ entonces el número que busca es $$ \underbrace{15!\left[x^{15}\right]}_\text{extract $ s_{15} $}\underbrace{P_8(x)P_5(x)P_4(x)P_3(x)\vphantom{\left[x^{15}\right]}}_\text{product from $ (1) $}=187957770\tag3 $$

---

Código Mathematica

Defina

f = Sum[x^k/k!,{k,0,#}]&

f[j] da $P_j(x)$ de $(2)$ . Entonces f/@{8,5,4,3} proporciona la lista de $P_j(x)$ de $(1)$ . Times@@f/@{8,5,4,3} calcula su producto. Así,

15! Coefficient[Times@@f/@{8,5,4,3},x,15]

da el resultado de $(3)$ .

Answer 3

Hay 20! /4! 5! 8! 3! arreglos de los 20 alfabetos. Consideremos la acción de $S_5$ en los arreglos permutando los últimos 5 dígitos. Quieres calcular el número de órbitas. Entonces puedes intentar hacerlo mediante La fórmula de Burnside . No es difícil hacerlo al menos para este caso, ya que si una permutación de $S_5$ fija un arreglo, significa que cada ciclo de la permutación corresponde a un color.

Para el caso general, sospecho que el teorema de enumeración de Polya puede hacerlo, aunque no estoy seguro.

Answer 4

En respuesta de robjohn da un método para calcular la respuesta a esta pregunta utilizando Mathematica, o cualquier sistema de álgebra computacional que pueda multiplicar polinomios. Aquí hay un enfoque algorítmico diferente, que es más lento que el enfoque de robjohn, pero conceptualmente más simple y posiblemente más fácil de implementar.

Para cada $i\in \{1,2,\dots,x\}$ y cada $j\in \{0,1,\dots,k\}$ , dejemos que $$ A(i,j)= \begin{matrix} \text{number of arrangements of $j$ items from an urn with $i$ colors of tokens,}\\\text{with $r_1$ tokens of the first color, $r_2$ of the second color, ... , $r_i$ of the $i^\text{th}$ color} \end{matrix} $$ La respuesta a su problema es $A(x,k)$ mientras que $A(i,j)$ es un problema más sencillo cuando $i<x$ y $j<k$ . Estos subproblemas satisfacen la siguiente ecuación recursiva: $$ A(i,j) = \sum_{s=0}^{\min(j,a_i)} \binom{j}{s}A(i-1,j-s)\\ A(1,j)=\begin{cases}1 & 0\le j\le r_1 \\ 0 & r_1< j\end{cases} $$ La idea es que para contar el número de arreglos de $j$ elementos utilizando el primer $i$ colores, se consideran todas las posibilidades para el número de veces que el color $i$ se elige. Si el color $i$ aparece $s$ veces, entonces puede colocar esos $s$ tokens de la muestra en $\binom js$ formas y, a continuación, rellene el resto $j-s$ puntos con el primer $i-1$ colores en $A(i-1,j-s)$ maneras.

Esta ecuación recursiva permite calcular $A(n,m)$ rellenando un $x\times (k+1)$ tabla de programación dinámica, cuya entrada en el $i^{th}$ fila y $j^{th}$ columna es $A(i,j)$ . Dado que existen $O(kx)$ entradas, y cada entrada es una suma de $O(k)$ términos, el tiempo que esto lleva es $O(k^2x)$ . El tiempo que esto lleva se vuelve inmanejable muy rápidamente.