Doce veces - Twelvefold way

En combinatoria , la forma de doce es una clasificación sistemática de 12 problemas enumerativos relacionados con dos conjuntos finitos, que incluyen los problemas clásicos de contar permutaciones , combinaciones , conjuntos múltiples y particiones de un conjunto o de un número . La idea de la clasificación se le atribuye a Gian-Carlo Rota , y el nombre fue sugerido por Joel Spencer .

Visión general

Deje N y X sean conjuntos finitos . Sea y sea ​​la cardinalidad de los conjuntos. Por tanto, N es un conjunto de n y X es un conjunto de x . ${\ Displaystyle n = | N |}$${\ Displaystyle x = | X |}$

El problema general que consideramos es la enumeración de clases de equivalencia de funciones . ${\ Displaystyle f: N \ a X}$

Las funciones están sujetas a una de las tres restricciones siguientes:

1. Sin condición: cada a en N puede ser enviado por f a cualquier b en X , y cada b puede ocurrir varias veces.
2. f es inyectiva : cada valor de a en N debe ser distinto entre sí, por lo que cada b en X puede aparecer como máximo una vez en la imagen de f .${\ Displaystyle f (a)}$
3. f es sobreyectiva : para cada b en X debe haber al menos una a en N tal que , por lo tanto, cada b ocurrirá al menos una vez en la imagen de f .${\ Displaystyle f (a) = b}$

(La condición " f es biyectiva " es solo una opción cuando ; pero entonces es equivalente a " f es inyectiva" y " f es sobreyectiva"). ${\ Displaystyle n = x}$

Hay cuatro relaciones de equivalencia diferentes que pueden definirse en el conjunto de funciones f de N a X :

1. igualdad;
2. igualdad hasta una permutación de N ;
3. igualdad hasta una permutación de X ;
4. la igualdad hasta permutaciones de N y X .

Las tres condiciones de las funciones y las cuatro relaciones de equivalencia se pueden emparejar de 3 × 4 = 12 formas.

Los doce problemas de contar clases de equivalencia de funciones no implican las mismas dificultades y no existe un método sistemático para resolverlos. Dos de los problemas son triviales (el número de clases de equivalencia es 0 o 1), cinco problemas tienen una respuesta en términos de una fórmula multiplicativo de n y x , y los cinco problemas restantes tienen una respuesta en términos de funciones combinatorias ( números de Stirling y la función de partición para un número determinado de partes).

La incorporación de los problemas clásicos de enumeración en este escenario es la siguiente.

• Counting n -permutations (es decir, permutaciones parciales o secuencias sin repetición) de X es equivalente a contar funciones inyectivos N → X .
• Counting n -conjuntos de X es equivalente a contar funciones inyectivos N → X hasta permutaciones de N .
• Contar permutaciones del conjunto X equivale a contar funciones inyectivas N → X cuando n = x, y también a contar funciones sobreyectivas N → X cuando n = x .
• Contando conjuntos múltiples de tamaño n (también conocido como n -conjuntos con repeticiones) de elementos en X es equivalente a contar todas las funciones N → X hasta permutaciones de N .
• Contando las particiones del conjunto de N en x subconjuntos es equivalente a contar todas las funciones suprayectivos N → X hasta permutaciones de X .
• Contando composiciones del número n en x partes es equivalente a contar todas las funciones suprayectivos N → X hasta permutaciones de N .

Miradores

Los diversos problemas de la forma doce pueden considerarse desde diferentes puntos de vista.

Bolas y cajas

Tradicionalmente, muchos de los problemas de la forma doce se han formulado en términos de colocar bolas en cajas (o alguna visualización similar) en lugar de definir funciones. El conjunto N se puede identificar con un conjunto de bolas y X con un conjunto de cajas; la función ƒ  : N → X describe una forma de distribuir las bolas en las cajas, es decir, poniendo cada bola a en la caja ƒ ( a ). Una función atribuye una imagen única a cada valor en su dominio; esta propiedad se refleja en la propiedad de que cualquier bola puede entrar en una sola caja (junto con el requisito de que ninguna bola debe quedar fuera de las cajas), mientras que cualquier caja puede acomodar (en principio) un número arbitrario de bolas. Exigir además que ƒ sea ​​inyectable significa prohibir poner más de una bola en cualquier caja, mientras que exigir que ƒ sea ​​sobreyectiva significa insistir en que cada caja contenga al menos una bola.

El recuento de permutaciones de módulo de N o X se refleja llamando a las bolas o las cajas, respectivamente, "indistinguibles". Esta es una formulación imprecisa, destinada a indicar que las diferentes configuraciones no deben contarse por separado si una puede transformarse en la otra mediante algún intercambio de bolas o de cajas. Esta posibilidad de transformación se formaliza mediante la acción por permutaciones.

Muestreo

Otra forma de pensar en algunos de los casos es en términos de muestreo , en estadísticas . Imagínese una población de X artículos (o personas), de los cuales elegimos N . Normalmente se describen dos esquemas diferentes, conocidos como " muestreo con reemplazo " y " muestreo sin reemplazo ". En el primer caso (muestreo con reemplazo), una vez que hemos elegido un ítem, lo volvemos a poner en la población para poder elegirlo nuevamente. El resultado es que cada elección es independiente de todas las demás opciones, y el conjunto de muestras se denomina técnicamente como independientes distribuidos de forma idéntica . En el último caso, sin embargo, una vez que hemos elegido un artículo, lo dejamos a un lado para que no podamos volver a elegirlo. Esto significa que el acto de elegir un elemento tiene un efecto en todas las opciones siguientes (el elemento en particular no se puede volver a ver), por lo que nuestras elecciones dependen unas de otras.

Una segunda distinción entre los esquemas de muestreo es si el orden es importante. Por ejemplo, si tenemos diez elementos, de los cuales elegimos dos, entonces la opción (4,7) es diferente de (7,4) si el pedido es importante; por otro lado, si ordenar no importa, entonces las opciones (4,7) y (7,4) son equivalentes. (Otra forma de pensar en esto es ordenar cada opción por el número de artículo y descartar cualquier duplicado que resulte).

Las dos primeras filas y columnas de la tabla siguiente corresponden al muestreo con y sin reemplazo, con y sin consideración del orden. Los casos de muestreo con reemplazo se encuentran en la columna denominada "Cualquier f ", mientras que los casos de muestreo sin reemplazo se encuentran en la columna denominada "Inyectiva f ". Los casos en los que el orden es importante se encuentran en la fila denominada "Distinto" y los casos en los que el orden no importa se encuentran en la fila denominada " Órbitas S _n ". Cada entrada de la tabla indica cuántos conjuntos diferentes de opciones hay, en un esquema de muestreo particular. Tres de estas entradas de la tabla también corresponden a distribuciones de probabilidad . El muestreo con reemplazo donde el orden importa es comparable a describir la distribución conjunta de N variables aleatorias separadas , cada una con una distribución categórica X veces mayor . Sin embargo, el muestreo con reemplazo donde el orden no importa es comparable a describir una única distribución multinomial de N extracciones de una categoría X- veces, donde solo importa el número visto de cada categoría. El muestreo sin reemplazo donde el pedido no importa es comparable a una única distribución hipergeométrica multivariante . El muestreo sin reemplazo donde el orden es importante no parece corresponder a una distribución de probabilidad. Tenga en cuenta que en todos los casos "inyectables" (es decir, muestreo sin reemplazo), el número de conjuntos de opciones es cero a menos que N ≤ X. ("Comparable" en los casos anteriores significa que cada elemento del espacio muestral de la distribución correspondiente corresponde a un conjunto separado de opciones y, por lo tanto, el número en el cuadro correspondiente indica el tamaño del espacio muestral para la distribución dada).

Desde la perspectiva del muestreo, la columna denominada "Sobrejetiva f " es algo extraña: esencialmente, seguimos muestreando con reemplazo hasta que hayamos elegido cada elemento al menos una vez. Luego, contamos cuántas elecciones hemos hecho y, si no es igual a N , desechamos todo el conjunto y repetimos. Esto es vagamente comparable al problema del recolector de cupones , donde el proceso implica "recolectar" (muestreando con reemplazo) un conjunto de X cupones hasta que cada cupón se haya visto al menos una vez. Tenga en cuenta que en todos los casos "suprayectivos", el número de conjuntos de opciones es cero a menos que N ≥ X .

Etiquetado, selección, agrupación

Una función ƒ  : N → X se puede considerar desde la perspectiva de X o de N . Esto conduce a diferentes puntos de vista:

• la función ƒ etiquetas de cada elemento de N por un elemento de X .
• la función ƒ selecciona (desea) un elemento del conjunto X para cada elemento de N , un total de n opciones.
• la función ƒ grupos los elementos de N juntos que se asignan a un mismo elemento de X .

Estos puntos de vista no se adaptan por igual a todos los casos. Los puntos de vista de etiquetado y selección no son bien compatibles con la permutación de los elementos de X , ya que esto cambia las etiquetas o la selección; por otro lado, el punto de vista de agrupamiento no proporciona información completa sobre la configuración a menos que los elementos de X puedan permutarse libremente. Los puntos de vista de etiquetado y selección son más o menos equivalentes cuando N no se permuta, pero cuando lo está, el punto de vista de selección es más adecuado. La selección puede entonces ser visto como una selección no ordenada: una única elección de un conjunto (multi-) de n elementos de X se hace.

Etiquetado y selección con o sin repetición

Cuando se considera ƒ como un etiquetado de los elementos de N , se puede pensar que estos últimos están dispuestos en una secuencia, y que las etiquetas de X se les asignan sucesivamente. El requisito de que ƒ sea ​​inyectable significa que no se puede usar ninguna etiqueta por segunda vez; el resultado es una secuencia de etiquetas sin repetición . En ausencia de tal requisito, se usa la terminología "secuencias con repetición", lo que significa que las etiquetas se pueden usar más de una vez (aunque también se permiten las secuencias que no tienen repetición).

Al ver ƒ como una selección desordenada de los elementos de X , se aplica el mismo tipo de distinción. Si f debe ser inyectiva, entonces la selección debe involucrar n elementos distintos de X , por lo que es un subconjunto de X de tamaño n , también llamado n - combinación . Sin el requisito, un mismo elemento de X puede aparecer varias veces en la selección, y el resultado es un conjunto múltiple de tamaño n de elementos de X , también llamado n - multicombinación o n- combinación con repetición.

El requisito de que ƒ sea ​​sobreyectivo, desde el punto de vista de los elementos de etiquetado de N , significa que cada etiqueta debe usarse al menos una vez; desde el punto de vista de la selección de X , significa que cada elemento de X debe incluirse en la selección al menos una vez. Etiquetar con sobreyección equivale a agrupar elementos de N seguido de etiquetar cada grupo con un elemento de X y, por lo tanto, es algo más complicado de describir matemáticamente.

Particiones de conjuntos y números.

Cuando se ve a ƒ como una agrupación de los elementos de N (que asume que uno se identifica bajo las permutaciones de X ), requerir que ƒ sea ​​sobreyectiva significa que el número de grupos debe ser exactamente x . Sin este requisito, el número de grupos puede ser como máximo x . El requisito de ƒ inyectivo significa que cada elemento de N debe ser un grupo en sí mismo, lo que deja como máximo una agrupación válida y, por lo tanto, da un problema de conteo poco interesante.

Cuando además uno identifica bajo permutaciones de N , esto equivale a olvidar los grupos mismos pero reteniendo solo sus tamaños. Además, estos tamaños no vienen en ningún orden definido, mientras que el mismo tamaño puede aparecer más de una vez; se puede optar por organizarlos en una lista de números ligeramente decreciente, cuya suma es el número n . Esto da la noción combinatoria de una partición del número  n , en exactamente x (para ƒ sobreyectiva ) o como máximo x (para ƒ arbitrarias ) partes.

Fórmulas

Las fórmulas para los diferentes casos de la forma de doce se resumen en la siguiente tabla; cada entrada de la tabla se vincula a una subsección a continuación que explica la fórmula.

Los doce objetos combinatorios y sus fórmulas de enumeración.

f -clase	Cualquier f	Inyectiva f	Sobreyectiva f
Distinto f	n- secuencia en X ${\ Displaystyle x ^ {n}}$	n -permutación de X ${\ Displaystyle x ^ {\ underline {n}}}$	composición de N con x subconjuntos ${\ Displaystyle \ textstyle x! \ {{n \ encima de x} \}}$
S n órbitas f ∘ S n	n -multisubconjunto de X ${\ Displaystyle {\ binom {x + n-1} {n}}}$	n- subconjunto de X ${\ Displaystyle {\ binom {x} {n}}}$	composición de n con términos x ${\ Displaystyle {\ binom {n-1} {nx}}}$
S x órbitas S x ∘ f	partición de N en ≤ x subconjuntos ${\ Displaystyle \ sum _ {k = 0} ^ {x} \ left \ {{n \ encima de k} \ right \}}$	partición de N en ≤ x elementos ${\ Displaystyle [n \ leq x]}$	partición de N en x subconjuntos ${\ Displaystyle \ left \ {{n \ encima de x} \ right \}}$
S n × S x órbitas S x ∘ f ∘ S n	partición de n en ≤ x partes ${\ Displaystyle p_ {x} (n + x)}$	partición de n en ≤ x partes 1 ${\ Displaystyle [n \ leq x]}$	partición de n en x partes ${\ Displaystyle p_ {x} (n)}$

Las notaciones particulares utilizadas son:

• la caída del poder factorial ,${\ Displaystyle x ^ {\ underline {n}} = {\ frac {x!} {(xn)!}} = x (x-1) (x-2) \ cdots (x-n + 1)}$
• el poder factorial ascendente ,${\ Displaystyle x ^ {\ overline {n}} = {\ frac {(x + n-1)!} {(x-1)!}} = x (x + 1) (x + 2) \ cdots ( x + n-1)}$
• el factorial ${\ Displaystyle n! = n ^ {\ underline {n}} = n (n-1) (n-2) \ cdots 1}$
• el número de Stirling del segundo tipo , que denota el número de formas de dividir un conjunto de n elementos en k subconjuntos${\ Displaystyle \ textstyle \ {{n \ encima de k} \}}$
• el coeficiente binomial ${\ Displaystyle \ textstyle {\ binom {n} {k}} = {\ frac {n ^ {\ underline {k}}} {k!}}}$
• el corchete Iverson [] que codifica un valor de verdad como 0 o 1
• el número de particiones de n en k partes${\ Displaystyle p_ {k} (n)}$

Significado intuitivo de las filas y columnas.

Este es un resumen rápido de lo que significan los diferentes casos. Los casos se describen en detalle a continuación.

Piense en un conjunto de elementos numerados X (numerados de 1 ax ), de los cuales elegimos n , produciendo una lista ordenada de los elementos: por ejemplo, si hay elementos de los cuales elegimos , el resultado podría ser la lista (5, 2 , 10). Luego contamos cuántas listas diferentes existen, a veces transformando primero las listas de maneras que reducen el número de posibilidades distintas. ${\ Displaystyle x = 10}$${\ Displaystyle n = 3}$

Entonces las columnas significan:

• Cualquiera f : Después de elegir un artículo, lo volvemos a colocar, por lo que podríamos elegirlo nuevamente.
• Inyectiva f : Después de elegir un elemento, lo dejamos a un lado, por lo que no podemos volver a elegirlo; por lo tanto, terminaremos con n elementos distintos. Necesariamente, entonces, a menos que no se pueda elegir ninguna lista.${\ Displaystyle n \ leq x}$
• Sobrejetivo f : Después de elegir un elemento, lo volvemos a colocar, por lo que podríamos elegirlo nuevamente, pero al final, tenemos que terminar eligiendo cada elemento al menos una vez. Necesariamente, entonces, a menos que no se pueda elegir ninguna lista.${\ Displaystyle n \ geq x}$

Y las filas significan:

• Distinto: deje las listas en paz; cuéntelos directamente.
• S _n órbitas: antes de contar, ordene las listas por el número de elemento de los elementos elegidos, de modo que el orden no importe, por ejemplo, (5, 2, 10), (10, 2, 5), (2, 10, 5) → (2, 5, 10).
• S _x órbitas: antes de contar, vuelva a numerar los elementos vistos para que el primer elemento visto tenga el número 1, el segundo 2, etc. Los números pueden repetirse si un elemento se vio más de una vez, por ejemplo, (3, 5, 3), ( 5, 2, 5), (4, 9, 4) → (1, 2, 1) mientras que (3, 3, 5), (5, 5, 3), (2, 2, 9) → (1, 1, 2).
• Órbitas S _n × S _x : Dos listas cuentan como lo mismo si es posible reordenarlas y volver a etiquetarlas como se indicó anteriormente y producir el mismo resultado. Por ejemplo, (3, 5, 3) y (2, 9, 9) cuentan como lo mismo porque se pueden reordenar como (3, 3, 5) y (9, 9, 2) y luego volver a etiquetar ambos produce el mismo lista (1, 1, 2).

Detalles de los diferentes casos

Los casos a continuación están ordenados de tal manera que se agrupan aquellos casos para los cuales los argumentos usados ​​en el conteo están relacionados, que no es el orden en la tabla dada.

Funciones de N a X

Este caso equivale a contar secuencias de n elementos de X sin restricción: una función f  : N → X está determinada por las n imágenes de los elementos de N , cada una de las cuales puede elegirse independientemente entre los elementos de x . Esto da un total de x ⁿ posibilidades.

Ejemplo:

${\ Displaystyle X = \ {a, b, c \}, N = \ {1,2 \} {\ text {, luego}}}$

${\ Displaystyle \ left \ vert \ {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a) , (c, b), (c, c) \} \ right \ vert = 3 ^ {2} = 9}$

Funciones inyectivas de N a X

Este caso es equivalente a contar secuencias de n elementos distintos de X , también llamadas n -permutaciones de X , o secuencias sin repeticiones ; de nuevo esta secuencia está formada por las n imágenes de los elementos de N . Este caso se diferencia del de secuencias no restringidas en que hay una opción menos para el segundo elemento, dos menos para el tercer elemento, y así sucesivamente. Por tanto, en lugar de una potencia ordinaria de x , el valor viene dado por una potencia factorial descendente de x , en la que cada factor sucesivo es uno menos que el anterior. La formula es

${\ Displaystyle x ^ {\ underline {n}} = x (x-1) \ cdots (x-n + 1).}$

Tenga en cuenta que si n > x entonces se obtiene un factor cero, por lo que en este caso no hay funciones inyectables N → X en absoluto; esto es solo una reafirmación del principio de casillero .

Ejemplo:

${\ Displaystyle X = \ {a, b, c, d \}, N = \ {1,2 \} {\ text {, luego}}}$

${\ Displaystyle \ left \ vert \ {(a, b), (a, c), (a, d), (b, a), (b, c), (b, d), (c, a) , (c, b), (c, d), (d, a), (d, b), (d, c) \} \ right \ vert = 4 ^ {\ underline {2}} = 4 \ times 3 = 12}$

Funciones inyectivas de N a X , hasta una permutación de N

Este caso es equivalente a conteo subconjuntos con n elementos de X , también llamado n -conjuntos de X : entre las secuencias de n elementos distintos de X , los que difieren sólo en el orden de sus términos son identificados por permutaciones de N . Dado que en todos los casos esto agrupa exactamente n ! diferentes secuencias, podemos dividir el número de tales secuencias por n ! para obtener el número de n -conjuntos de X . Este número se conoce como coeficiente binomial , que por lo tanto viene dado por ${\ Displaystyle {\ tbinom {x} {n}}}$

${\ Displaystyle {\ binom {x} {n}} = {\ frac {x ^ {\ underline {n}}} {n!}} = {\ frac {x (x-1) \ cdots (x-n +2) (x-n + 1)} {n (n-1) \ cdots 2 \ cdot 1}}.}$

Ejemplo:

${\ Displaystyle X = \ {a, b, c, d \}, N = \ {1,2 \} {\ text {, luego}}}$

${\ Displaystyle \ left \ vert \ {\ {a, b \}, \ {a, c \}, \ {a, d \}, \ {b, c \}, \ {b, d \}, \ {c, d \} \} \ right \ vert = {\ frac {4 ^ {\ underline {2}}} {2!}} = {\ frac {4 \ times 3} {2}} = 6}$

Funciones de N a X , hasta una permutación de N

Este caso es equivalente a contar conjuntos múltiples con n elementos de X (también llamado n -multicombinaciones). La razón es que para cada elemento de X se determina cuántos elementos de N se asignan a él por f , mientras que dos funciones que dan las mismas "multiplicidades" a cada elemento de X siempre se pueden transformar en otro mediante una permutación de N . La fórmula que cuenta todas las funciones N → X no es útil aquí, porque el número de ellas agrupadas por permutaciones de N varía de una función a otra. Más bien, como se explica en combinaciones , se puede ver que el número de n- combinaciones de un conjunto con x elementos es el mismo que el número de n- combinaciones de un conjunto con x + n - 1 elementos. Esto reduce el problema a otro en la forma doce veces mayor, y da como resultado

${\ Displaystyle {\ binom {x + n-1} {n}} = {\ frac {(x + n-1) (x + n-2) \ cdots (x + 1) x} {n (n- 1) \ cdots 2 \ cdot 1}} = {\ frac {x ^ {\ overline {n}}} {n!}}.}$

Ejemplo:

${\ Displaystyle X = \ {a, b, c \}, N = \ {1,2 \} {\ text {, luego}}}$

${\ Displaystyle \ left \ vert \ {\ {a, a \}, \ {a, b \}, \ {a, c \}, \ {b, b \}, \ {b, c \}, \ {c, c \} \} \ right \ vert = {\ frac {3 ^ {\ overline {2}}} {2!}} = {\ frac {4 \ times 3} {2}} = 6}$

Funciones sobreyectivas de N a X , hasta una permutación de N

Este caso equivale a contar conjuntos múltiples con n elementos de X , para lo cual cada elemento de X ocurre al menos una vez. Esto también equivale a contar las composiciones de n con términos x (distintos de cero) , enumerando las multiplicidades de los elementos de x en orden. La correspondencia entre funciones y conjuntos múltiples es la misma que en el caso anterior, y el requisito de sobrejetividad significa que todas las multiplicidades son al menos una. Al disminuir todas las multiplicidades en 1, esto se reduce al caso anterior; dado que el cambio disminuye el valor de n en x , el resultado es

${\ Displaystyle {\ binom {n-1} {nx}}.}$

Nótese que cuando n < x no hay funciones sobreyectivas N → X en absoluto (una especie de principio de "casillero vacío"); esto se tiene en cuenta en la fórmula, por la convención de que los coeficientes binomiales son siempre 0 si el índice más bajo es negativo. El mismo valor también viene dado por la expresión

${\ Displaystyle {\ binom {n-1} {x-1}},}$

excepto en el caso extremo n = x = 0 , donde con la primera expresión da correctamente , mientras que la última da incorrectamente . ${\ displaystyle {\ tbinom {-1} {0}} = 1}$${\ displaystyle {\ tbinom {-1} {- 1}} = 0}$

La forma del resultado sugiere buscar una manera de asociar una clase de funciones sobreyectivas N → X directamente a un subconjunto de n - x elementos elegidos de un total de n - 1 , lo que se puede hacer de la siguiente manera. Primero elija un orden total de los conjuntos N y X , y observe que aplicando una permutación adecuada de N , cada función sobreyectiva N → X puede transformarse en una función única débilmente creciente (y por supuesto todavía sobreyectiva). Si uno conecta los elementos de N en orden por n - 1 arcos en un gráfico lineal , luego seleccionando cualquier subconjunto de n - x arcos y eliminando el resto, se obtiene un gráfico con x componentes conectados, y enviándolos a los elementos sucesivos de X , se obtiene una función sobreyectiva débilmente creciente N → X ; también los tamaños de los componentes conectados dan una composición de n en x partes. Este argumento es básicamente el que se da en estrellas y barras , excepto que allí se realiza la elección complementaria de x - 1 "separaciones".

Ejemplo:

${\ Displaystyle X = \ {a, b \}, N = \ {1,2,3 \} {\ text {, luego}}}$

${\ Displaystyle \ left \ vert \ {\ {a, a, b \}, \ {a, b, b \} \} \ right \ vert = {\ binom {3-1} {3-2}} = {\ binom {2} {1}} = {\ frac {2!} {1! \ times (2-1)!}} = 2}$

Funciones inyectivas de N a X , hasta una permutación de X

En este caso consideramos secuencias de n elementos distintos de X , pero identificamos los obtenidos entre sí aplicando a cada elemento de una permutación de X . Es fácil ver que siempre se pueden identificar dos secuencias diferentes: la permutación debe mapear el término i de la primera secuencia con el término i de la segunda secuencia, y dado que ningún valor aparece dos veces en ninguna secuencia, estos requisitos no se contradicen entre sí; queda por mapear los elementos que no ocurren en la primera secuencia bijetivamente con aquellos que no ocurren en la segunda secuencia de una manera arbitraria. El único hecho que hace que el resultado dependa de n y x es que, para empezar, la existencia de tales secuencias requiere n ≤ x , según el principio de casillero. Por lo tanto, el número se expresa como , utilizando el corchete de Iverson . ${\ Displaystyle [n \ leq x]}$

Funciones inyectivas de N a X , hasta permutaciones de N y X

Este caso se reduce al anterior: dado que todas las secuencias de n elementos distintos de X ya pueden transformarse entre sí mediante la aplicación de una permutación de X a cada uno de sus términos, permitir además que el reordenamiento de los términos no dé nuevas identificaciones; el número permanece . ${\ Displaystyle [n \ leq x]}$

Funciones sobreyectivas de N a X , hasta una permutación de X

Este caso es equivalente a contar particiones de N en subconjuntos x (no vacíos) , o contar relaciones de equivalencia en N con exactamente x clases. De hecho, para cualquier función sobreyectiva f  : N → X , la relación de tener la misma imagen bajo f es una relación de equivalencia, y no cambia cuando se aplica posteriormente una permutación de X ; a la inversa, se puede convertir tal relación de equivalencia en una función sobreyectiva asignando los elementos de X de alguna manera a las clases de equivalencia x . El número de tales particiones o relaciones de equivalencia es, por definición, el número de Stirling del segundo tipo S ( n , x ), también escrito . Su valor se puede describir usando una relación recursiva o usando funciones generadoras , pero a diferencia de los coeficientes binomiales, no existe una fórmula cerrada para estos números que no implique una suma . ${\ Displaystyle \ textstyle \ {{n \ encima de x} \}}$

Funciones sobreyectivas de N a X

Para cada función sobreyectiva f  : N → X , su órbita bajo permutaciones de X tiene x ! elementos, ya que la composición (a la izquierda) con dos permutaciones distintas de X nunca da la misma función en N (las permutaciones deben diferir en algún elemento de X , que siempre se puede escribir como f ( i ) para algún i ∈ N , y las composiciones entonces diferirán en i ). De ello se deduce que el número para este caso es x ! multiplicado por el número del caso anterior, es decir${\ Displaystyle \ textstyle x! \ {{n \ encima de x} \}.}$

Ejemplo:

${\ Displaystyle X = \ {a, b \}, N = \ {1,2,3 \} {\ text {, luego}}}$

${\ Displaystyle \ left \ vert \ {(a, a, b), (a, b, a), (a, b, b), (b, a, a), (b, a, b), ( b, b, a) \} \ right \ vert = \ textstyle 2! \ {{3 \ encima de 2} \} = 2 \ times 3 = 6}$

Funciones de N a X , hasta una permutación de X

Este caso es como el correspondiente para funciones sobreyectivas, pero algunos elementos de x pueden no corresponder en absoluto a ninguna clase de equivalencia (dado que se consideran funciones hasta una permutación de X , no importa qué elementos estén involucrados, solo cuántos) . Como consecuencia, se están contando relaciones de equivalencia en N con como máximo x clases, y el resultado se obtiene del caso mencionado mediante la suma de los valores hasta x , dando . En el caso de x ≥ n , el tamaño de x no presenta restricción alguna, y se están contando todas las relaciones de equivalencia en un conjunto de n elementos (equivalentemente todas las particiones de dicho conjunto); por lo tanto, da una expresión para el número de Bell B _n . ${\ Displaystyle \ textstyle \ sum _ {k = 0} ^ {x} \ {{n \ encima de k} \}}$${\ Displaystyle \ textstyle \ sum _ {k = 0} ^ {n} \ {{n \ encima de k} \}}$

Funciones sobreyectivas de N a X , hasta permutaciones de N y X

Este caso es equivalente a contar particiones del número n en x partes distintas de cero . En comparación con el caso de contar funciones sobreyectivas hasta permutaciones de X solamente ( ), solo se retienen los tamaños de las clases de equivalencia en las que la función divide N (incluida la multiplicidad de cada tamaño), ya que dos relaciones de equivalencia se pueden transformar en una otro por una permutación de N si y solo si los tamaños de sus clases coinciden. Esto es precisamente lo que distingue la noción de partición de n de la de partición de N , por lo que como resultado se obtiene por definición el número p _x ( n ) de particiones de n en x partes distintas de cero. ${\ Displaystyle \ textstyle \ {{n \ encima de x} \}}$

Funciones de N a X , hasta permutaciones de N y X

Este caso equivale a contar particiones del número n en ≤ x partes . La asociación es la misma que para el caso anterior, excepto que ahora algunas partes de la partición pueden ser iguales a 0. (Específicamente, corresponden a elementos de X que no están en la imagen de la función). Cada partición de n en como máximo x partes distintas de cero se pueden extender a dicha partición agregando el número requerido de ceros, y esto da cuenta de todas las posibilidades exactamente una vez, por lo que el resultado viene dado por . Sumando 1 a cada una de las x partes, se obtiene una partición de n + x en x partes distintas de cero, y esta correspondencia es biyectiva; por tanto, la expresión dada se puede simplificar escribiéndola como . ${\ Displaystyle \ textstyle \ sum _ {k = 0} ^ {x} p_ {k} (n)}$${\ Displaystyle p_ {x} (n + x)}$

Casos extremos

Las fórmulas anteriores dan los valores adecuados para todos los conjuntos finitos N y X . En algunos casos existen fórmulas alternativas que son casi equivalentes, pero que no dan el resultado correcto en algunos casos extremos, como cuando N o X están vacíos. Las siguientes consideraciones se aplican a tales casos.

• Para cada conjunto X hay exactamente una función desde el conjunto vacío hasta X (no hay valores de esta función para especificar), que siempre es inyectiva, pero nunca sobreyectiva a menos que X esté (también) vacío.
• Para cada conjunto N no vacío, no hay funciones desde N hasta el conjunto vacío (hay al menos un valor de la función que debe especificarse, pero no puede).
• Cuando n > x No existen funciones inyectivos N → X , y si n < x no hay funciones suprayectivos N → X .
• Las expresiones utilizadas en las fórmulas tienen como valores particulares

${\ displaystyle 0 ^ {0} = 0 ^ {\ underline {0}} = 0! = {\ binom {0} {0}} = {\ binom {-1} {0}} = \ left \ {{ 0 \ encima de 0} \ right \} = p_ {0} (0) = 1}$

(los tres primeros son instancias de un producto vacío , y el valor viene dado por la extensión convencional de coeficientes binomiales a valores arbitrarios del índice superior), mientras que ${\ displaystyle {\ tbinom {-1} {0}} = {\ tfrac {(-1) ^ {\ underline {0}}} {0!}} = 1}$

${\ Displaystyle \ left \ {{n \ encima de x} \ right \} = p_ {x} (n) = 0 \ quad {\ hbox {siempre que}} n> 0 = x {\ hbox {o}} 0 \ leq n <x.}$

En particular, en el caso de contar conjuntos múltiples con n elementos tomados de X , la expresión dada es equivalente en la mayoría de los casos a , pero la última expresión daría 0 para el caso n = x = 0 (por la convención habitual de que los coeficientes binomiales con un los índices inferiores negativos son siempre 0). De manera similar, para el caso de contar composiciones de n con x partes distintas de cero, la expresión dada es casi equivalente a la expresión dada por el argumento de barras y estrellas , pero este último da valores incorrectos para n = 0 y todos los valores de  x . Para los casos en los que el resultado implica una suma, es decir, los de contar particiones de N en un máximo de x subconjuntos no vacíos o particiones de n en un máximo de x partes distintas de cero, se considera que el índice de suma comienza en 0; aunque el término correspondiente es cero siempre que n > 0 , es el término único distinto de cero cuando n = 0 , y el resultado sería incorrecto para esos casos si se tomara la suma para comenzar en 1. ${\ Displaystyle {\ tbinom {n + x-1} {n}}}$${\ Displaystyle {\ tbinom {n + x-1} {x-1}}}$${\ Displaystyle {\ tbinom {n-1} {nx}}}$${\ Displaystyle {\ tbinom {n-1} {x-1}}}$

Generalizaciones

Podemos generalizar más allá al permitir otros grupos de permutaciones para actuar en N y X . Si G es un grupo de permutaciones de N y H es un grupo de permutaciones de X , entonces contamos las clases de equivalencia de funciones . Dos funciones f y F se consideran equivalentes si, y solo si, existen para que . Esta extensión conduce a nociones como permutaciones cíclicas y diédricas , así como a particiones cíclicas y diédricas de números y conjuntos. ${\ displaystyle f \ colon N \ rightarrow X}$${\ Displaystyle g \ en G, h \ en H}$${\ Displaystyle F = h \ circ f \ circ g}$

El camino veinte

Kenneth P. Bogart desarrolló otra generalización llamada la vía veinte veces en su libro "Combinatoria a través del descubrimiento guiado". En el problema de distribuir objetos en cajas, tanto los objetos como las cajas pueden ser idénticos o distintos. Bogart identifica 20 casos.

El camino veinte

n objetos y condiciones sobre cómo se reciben	x destinatarios y modelo matemático de distribución
	Distinto	idéntico
1. Distinto Sin condiciones	n- secuencia en X ${\ Displaystyle x ^ {n}}$	partición de N en ≤ x subconjuntos ${\ Displaystyle \ sum _ {i = 0} ^ {x} \ left \ {{n \ encima de i} \ right \}}$
2. Distinto Cada uno recibe como máximo uno	n -permutación de X ${\ Displaystyle x ^ {\ underline {n}}}$	${\ displaystyle {\ begin {cases} 1 & {\ text {if}} n \ leq x \\ 0 & {\ text {de lo contrario}} \ end {cases}}}$
3. Distinto Cada uno recibe al menos uno	composición de N con x subconjuntos ${\ Displaystyle x! \ left \ {{n \ encima de x} \ right \}}$	partición de N en x subconjuntos ${\ Displaystyle \ left \ {{n \ encima de x} \ right \}}$
4. Distinto Cada uno recibe exactamente uno	${\ Displaystyle n! = x!}$ permutaciones	${\ displaystyle {\ begin {cases} 1 & {\ text {if}} n = x \\ 0 & {\ text {de lo contrario}} \ end {cases}}}$
5. Distinto, el orden importa	${\ Displaystyle (n + x-1) ^ {\ underline {n}}}$ funciones ordenadas	${\ Displaystyle \ sum _ {i = 1} ^ {x} L (n, i)}$ permutaciones rotas ( partes) ¿Dónde está el número Lah?${\ Displaystyle \ leq x}$ ${\ Displaystyle L (n, i)}$
6. Distinto, el orden importa Cada uno recibe al menos uno	${\ Displaystyle (n) ^ {\ underline {x}} (n-1) ^ {\ underline {nx}}}$ ordenado en funciones	${\ Displaystyle L (n, x) = \ left ({n \ encima de x} \ right) (n-1) ^ {\ underline {nx}}}$ permutaciones rotas ( x partes) ¿Dónde está el número Lah?${\ Displaystyle L (n, x)}$
7. Idéntico Sin condiciones	n -multisubconjunto de X ${\ Displaystyle \ left ({x + n-1 \ encima de n} \ right)}$	${\ Displaystyle \ sum _ {i = 1} ^ {x} p_ {i} (n)}$ particiones numéricas ( partes) ${\ Displaystyle \ leq x}$
8. Idéntico Cada uno recibe como máximo uno	n- subconjunto de X ${\ Displaystyle \ left ({x \ encima de n} \ right)}$	${\ displaystyle {\ begin {cases} 1 & {\ text {if}} n \ leq x \\ 0 & {\ text {de lo contrario}} \ end {cases}}}$
9. Idéntico Cada uno recibe al menos uno	${\ Displaystyle \ left ({n-1 \ encima de x-1} \ right)}$ composiciones ( x partes)	partición de n en x partes ${\ Displaystyle p_ {x} (n)}$
10. Idéntico Cada uno recibe exactamente uno	${\ displaystyle {\ begin {cases} 1 & {\ text {if}} n = x \\ 0 & {\ text {de lo contrario}} \ end {cases}}}$	${\ displaystyle {\ begin {cases} 1 & {\ text {if}} n = x \\ 0 & {\ text {de lo contrario}} \ end {cases}}}$

Ver también

• Estrellas y barras (combinatoria)

Referencias