Doce maneras

En combinatoria , la vía duodecimal es una clasificación sistemática de 12 problemas enumerativos relacionados entre sí que conciernen a dos conjuntos finitos, entre los que se incluyen los problemas clásicos de contar permutaciones , combinaciones , multiconjuntos y particiones de un conjunto o de un número . La idea de la clasificación se atribuye a Gian-Carlo Rota , y el nombre fue sugerido por Joel Spencer . ^[1]

Descripción general

Sean $N$ y $X$ conjuntos finitos . Sean y las cardinalidades de los conjuntos. Por lo tanto, $N$ es un conjunto con $n$ elementos y $X$ es un conjunto con $x$ elementos. $n=|N|$ $x=|X|$

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

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

Sin condición: cada $a$ en $N$ puede ser enviado por $f$ a cualquier $b$ en $X$ , y cada $b$ puede aparecer varias veces.
$f$ es inyectiva : cada valor de $a$ en $N$ debe ser distinto de todos los demás, y por lo tanto cada $b$ en $X$ puede aparecer como máximo una vez en la imagen de $f$ . $f(a)$
$f$ es sobreyectiva : para cada $b$ en $X$ debe haber al menos una $a$ en $N$ tal que , por lo tanto cada $b$ aparecerá al menos una vez en la imagen de $f$ . $f(a)=b$

(La condición " $f$ es biyectiva " sólo es una opción cuando ; pero entonces es equivalente tanto a " $f$ es inyectiva" como a " $f$ es sobreyectiva".) ${\estilo de visualización n=x}$

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

igualdad;
igualdad hasta una permutación de $N$ ;
igualdad hasta una permutación de $X$ ;
igualdad hasta permutaciones de $N$ y $X$ .

Las tres condiciones de las funciones y las cuatro relaciones de equivalencia se pueden emparejar de $3 \times 4 = 12$ maneras.

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 multiplicativa 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 dado de partes).

La incorporación de problemas de enumeración clásica en este entorno es la siguiente.

Contar $n$ -permutaciones (es decir, permutaciones parciales o secuencias sin repetición) de $X$ es equivalente a contar funciones inyectivas N → X.
Contar $n$ combinaciones de $X$ es equivalente a contar funciones inyectivas N → X hasta permutaciones de N.
Contar permutaciones del conjunto $X$ es equivalente a contar funciones inyectivas $N \to X$ cuando $n$ = $x$ , y también a contar funciones sobreyectivas N → X cuando $n = x$ .
Contar multiconjuntos de tamaño $n$ (también conocidos como $n$ -combinaciones con repeticiones) de elementos en $X$ es equivalente a contar todas las funciones N → X hasta permutaciones de N.
Contar particiones del conjunto $N$ en $X$ subconjuntos es equivalente a contar todas las funciones sobreyectivas N → X hasta permutaciones de X.
Contar composiciones del número $n$ en $x$ partes es equivalente a contar todas las funciones sobreyectivas N → X hasta permutaciones de N.

Puntos de vista

Los diversos problemas del camino duodécimo pueden considerarse desde diferentes puntos de vista.

Pelotas y cajas

Tradicionalmente, muchos de los problemas de la vía doce veces se han formulado en términos de colocar bolas en cajas (o alguna visualización similar) en lugar de definir funciones. El conjunto $N$ puede identificarse con un conjunto de bolas y $X$ con un conjunto de cajas; la función describe entonces una forma de distribuir las bolas en las cajas, es decir, colocando cada bola $a$ en la caja . 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 solo en una caja (junto con el requisito de que ninguna bola debe quedar fuera de las cajas), mientras que cualquier caja puede acomodar una cantidad arbitraria de bolas. Exigir además que sea inyectiva significa prohibir colocar 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. $f:N\to X$ $f(a)$ ${\estilo de visualización f}$ ${\estilo de visualización f}$

El recuento módulo permutaciones de $N$ o $X$ se refleja en el hecho de que las bolas o las cajas, respectivamente, son "indistinguibles". Se trata de una formulación imprecisa, destinada a indicar que no se deben contar por separado las diferentes configuraciones 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 de permutaciones.

Muestreo

Otra forma de pensar en algunos de los casos es en términos de muestreo , en estadística . Imaginemos una población de $X$ elementos (o personas), de los cuales elegimos $N.$ Normalmente se describen dos esquemas diferentes, conocidos como " muestreo con reposición " y " muestreo sin reposición ". En el primer caso (muestreo con reposición), una vez que hemos elegido un elemento, lo volvemos a poner en la población, de modo que podamos elegirlo de nuevo. El resultado es que cada elección es independiente de todas las demás opciones, y el conjunto de muestras se denomina técnicamente independiente idénticamente distribuido . En el último caso, sin embargo, una vez que hemos elegido un elemento, lo dejamos de lado para no poder elegirlo de nuevo. Esto significa que el acto de elegir un elemento tiene un efecto en todas las elecciones 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 orden es importante; por otro lado, si el orden no es importante, entonces las opciones (4, 7) y (7, 4) son equivalentes.

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 etiquetada "Cualquiera ", mientras que los casos de muestreo sin reemplazo se encuentran en la columna etiquetada "Inyectivo ". Los casos en los que el orden importa se encuentran en la fila etiquetada "Distinto", y los casos en los que el orden no importa se encuentran en la fila etiquetada " $S$ _$n$ órbitas". 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 $de X$ pliegues . 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 $de X$ pliegues, donde solo importa el número visto de cada categoría. El muestreo sin reemplazo donde el orden no importa es comparable a una única distribución hipergeométrica multivariada . El muestreo sin reemplazo, en el que el orden sí importa, no parece corresponder a una distribución de probabilidad. ^[2] En todos los casos inyectivos (muestreo sin reemplazo), el número de conjuntos de opciones es cero a menos que $N$ $\leq$ $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 apropiado indica el tamaño del espacio muestral para la distribución dada). ${\estilo de visualización f}$ ${\estilo de visualización f}$

Desde la perspectiva del muestreo, la columna denominada "Sobreyectiva " es algo extraña: Básicamente, 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$ , descartamos todo el conjunto y repetimos. Esto es vagamente comparable al problema del recolector de cupones , donde el proceso implica "recolectar" (por muestreo con reemplazo) un conjunto de $X$ cupones hasta que cada cupón haya sido visto al menos una vez. En todos los casos sobreyectivos, el número de conjuntos de elecciones es cero a menos que $N$ $\geq$ $X$ . ${\estilo de visualización f}$

Etiquetado, selección, agrupamiento

Una función puede considerarse desde la perspectiva de $X$ o de $N.$ Esto da lugar a diferentes puntos de vista: $f:N\to X$

La función etiqueta cada elemento de $N$ con un elemento de $X.$ ${\estilo de visualización f}$
la función selecciona (elige) un elemento del conjunto $X$ para cada elemento de $N$ , un total de $n$ opciones. ${\estilo de visualización f}$
La función agrupa los elementos de $N$ que están asignados al mismo elemento de $X.$ ${\estilo de visualización f}$

Estos puntos de vista no son igualmente adecuados para todos los casos. Los puntos de vista de etiquetado y selección no son muy 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 da 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 sí se permuta, el punto de vista de selección es más adecuado. La selección puede entonces verse como una selección desordenada: se realiza una única elección de un (multi-)conjunto de $n$ elementos de $X.$

Etiquetado y selección con o sin repetición

Si 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. Un requisito de que sean inyectivas significa que ninguna etiqueta se puede usar una segunda vez; el resultado es una secuencia de etiquetas sin repetición . En ausencia de tal requisito, se utiliza 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 secuencias que no tengan repetición). ${\estilo de visualización f}$ ${\estilo de visualización f}$

Cuando se considera como una selección no ordenada de los elementos de $X$ , se aplica el mismo tipo de distinción. Si 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 una $n$ - combinación . Sin el requisito, un mismo elemento de $X$ puede aparecer varias veces en la selección, y el resultado es un multiconjunto de tamaño $n$ de elementos de $X$ , también llamado una $n$ - multicombinación o $n$ -combinación con repetición. ${\estilo de visualización f}$ ${\estilo de visualización f}$

El requisito de que sea sobreyectivo, desde el punto de vista del etiquetado de elementos de $N$ , significa que cada etiqueta debe usarse al menos una vez; desde el punto de vista de la selección a partir de $X$ , significa que cada elemento de $X$ debe incluirse en la selección al menos una vez. El etiquetado con sobreyección es equivalente a una agrupación de elementos de $N$ seguida del etiquetado de cada grupo por un elemento de $X$ y, en consecuencia, es algo más complicado de describir matemáticamente. ${\estilo de visualización f}$

Particiones de conjuntos y números

Al considerarlo como una agrupación de los elementos de $N$ (que supone que uno se identifica bajo permutaciones de $X$ ), el requisito de ser sobreyectivo 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 inyectiva 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 lugar a un problema de conteo bastante poco interesante. ${\estilo de visualización f}$ ${\estilo de visualización f}$ ${\estilo de visualización f}$

Cuando además se identifican permutaciones de $N$ , esto equivale a olvidar los grupos mismos pero retener solamente sus tamaños. Estos tamaños además no vienen en ningún orden definido, mientras que el mismo tamaño puede aparecer más de una vez; uno puede elegir ordenarlos en una lista débilmente decreciente de números, 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 arbitraria ) partes. ${\estilo de visualización f}$ ${\estilo de visualización f}$

Fórmulas

Las fórmulas para los diferentes casos del camino doce veces mayor se resumen en la siguiente tabla; cada entrada de la tabla tiene un enlace a una subsección a continuación que explica la fórmula.

Las notaciones particulares utilizadas son:

la potencia factorial descendente , ${\textstyle x^{\underline {n}}={\frac {x!}{(xn)!}}=x(x-1)(x-2)\cdots (x-n+1)}$
la potencia factorial ascendente , ${\textstyle x^{\overline {n}}={\frac {(x+n-1)!}{(x-1)!}}=x(x+1)(x+2)\cdots (x+n-1)}$
El factorial ${\textstyle n!=n^{\underline {n}}=n(n-1)(n-2)\cpuntos 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 no vacíos ${\textstyle \left\{{n \encima de k}\right\}}$
el coeficiente binomial ${\textstyle {\binom {n}{k}}={\frac {n^{\underline {k}}}{k!}}}$
el corchete de Iverson [ ] codifica un valor de verdad como 0 o 1
el número de particiones de $n$ en $k$ partes ${\textstyle p_{k}(n)}$

Significado intuitivo de las filas y columnas

A continuación se presenta un breve resumen de lo que significan los distintos casos. Los casos se describen en detalle a continuación.

Pensemos en un conjunto de $X$ elementos numerados (numerados del 1 al $x$ ), de los cuales elegimos $n$ , lo que da como resultado una lista ordenada de los elementos: por ejemplo, si hay elementos de los cuales elegimos n , el resultado podría ser la lista (5, 2, 10). Luego contamos cuántas listas diferentes de este tipo existen, a veces transformando primero las listas de manera que se reduzca el número de posibilidades distintas. $x=10$ ${\estilo de visualización n=3}$

Entonces las columnas significan:

Cualquier $f$: Después de elegir un artículo, lo devolvemos para poder elegirlo nuevamente.
$f$ inyectiva: Después de elegir un elemento, lo dejamos de lado, de modo que no podemos elegirlo nuevamente; por lo tanto, terminaremos con $n$ elementos distintos. Necesariamente, entonces, a menos que , no se puede elegir ninguna lista. $n\leq x$
$f$ sobreyectiva: Después de elegir un elemento, lo volvemos a colocar, por lo que podríamos elegirlo nuevamente, pero al final, tenemos que haber elegido cada elemento al menos una vez. Necesariamente, entonces, a menos que , no se pueda elegir ninguna lista. $n\geq x$

Y las filas significan:

Distinto: Deje las listas en paz; cuéntelas directamente.
Órbitas $S$ _$n$: 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).
Órbitas $S$ _$x$: Antes de contar, vuelva a numerar los elementos vistos de modo 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 se consideran iguales si es posible reordenarlas y reetiquetarlas como se indicó anteriormente y producir el mismo resultado. Por ejemplo, (3, 5, 3) y (2, 9, 9) se consideran iguales porque se pueden reordenar como (3, 3, 5) y (9, 9, 2) y, luego, reetiquetarlas produce la misma lista (1, 1, 2).

Significado intuitivo del gráfico utilizando el escenario de bolas y cajas

El gráfico que se muestra a continuación es similar al gráfico anterior, pero en lugar de mostrar las fórmulas, ofrece una comprensión intuitiva de su significado utilizando el conocido ejemplo de las bolas y las cajas. Las filas representan la distinción entre las bolas y las cajas. Las columnas representan si se permiten paquetes múltiples (más de una bola en una caja) o cajas vacías. Las celdas del gráfico muestran la pregunta que se responde al resolver la fórmula que se proporciona en el gráfico de fórmulas anterior.

Detalles de los diferentes casos

Los casos a continuación están ordenados de tal manera que se agrupan aquellos casos en los que los argumentos utilizados en el recuento están relacionados, lo que no es el orden en la tabla dada.

Funciones de $norte$ a $incógnita$

Este caso es equivalente a contar secuencias de $n$ elementos de $X$ sin restricción: una función $f : N \to X$ está determinada por las $n$ imágenes de los elementos de $N$ , que pueden elegirse independientemente entre los elementos de $x$ . Esto da un total de $x$ ^$n$ posibilidades.

Ejemplo:
$X=\{a,b,c\},N=\{1,2\}{\text{, entonces }}$
$\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 $norte$ a $incógnita$

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

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

Nótese que si $n > x$ entonces se obtiene un factor cero, por lo que en este caso no hay funciones inyectivas $N \to X$ en absoluto; esto es simplemente una reformulación del principio del palomar .

Ejemplo:
$X=\{a,b,c,d\},N=\{1,2\}{\text{, entonces }}$
$\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 $norte$ a $incógnita$ , hasta una permutación de $norte$

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

{\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:
$X=\{a,b,c,d\},N=\{1,2\}{\text{, then }}$
$\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 $norte$ a $incógnita$ , hasta una permutación de $norte$

Este caso es equivalente a contar multiconjuntos con $n$ elementos de $X$ (también llamados $n$ - multicombinaciones ). La razón es que para cada elemento de $X$ se determina cuántos elementos de $N$ se asignan a él mediante $f$ , mientras que dos funciones que dan las mismas "multiplicidades" a cada elemento de $X$ siempre se pueden transformar en otra mediante una permutación de $N$ . La fórmula que cuenta todas las funciones $N \to X$ no es útil aquí, porque el número de ellas agrupadas mediante permutaciones de $N$ varía de una función a otra. En cambio, como se explicó en combinaciones , el número de $n$ -multicombinaciones de un conjunto con $x$ elementos puede verse como el mismo que el número de $n$ -combinaciones de un conjunto con $x + n - 1$ elementos. Esto reduce el problema a otro de la manera doce veces mayor, y da como resultado

{\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:
$X=\{a,b,c\},N=\{1,2\}{\text{, then }}$
$\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 $norte$ a $incógnita$ , hasta una permutación de $norte$

Este caso es equivalente a contar multiconjuntos con $n$ elementos de $X$ , para los cuales cada elemento de $X$ ocurre al menos una vez. Esto también es equivalente a contar las composiciones de $n$ con $x$ términos (distintos de cero) , enumerando las multiplicidades de los elementos de $x$ en orden. La correspondencia entre funciones y multiconjuntos es la misma que en el caso anterior, y el requisito de sobreyectividad significa que todas las multiplicidades son al menos uno. 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

{\binom {n-1}{n-x}}.

Obsérvese que cuando $n$ < $x$ no existen funciones sobreyectivas $N \to X$ (una especie de principio de "casilla vacía"); esto se tiene en cuenta en la fórmula, por la convención de que los coeficientes binomiales son siempre 0 si el índice inferior es negativo. El mismo valor también lo da la expresión

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

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

La forma del resultado sugiere buscar una manera de asociar una clase de funciones sobreyectivas $N \to X$ directamente a un subconjunto de $n - x$ elementos elegidos de un total de $n - 1$ , lo que puede hacerse de la siguiente manera. Primero elija un ordenamiento total de los conjuntos $N$ y $X$ , y note que al aplicar una permutación adecuada de $N$ , cada función sobreyectiva $N \to X$ puede transformarse en una única función débilmente creciente (y por supuesto aún sobreyectiva). Si uno conecta los elementos de $N$ en orden por $n - 1$ arcos en un grafo lineal , luego eligiendo cualquier subconjunto de $n - x$ arcos y eliminando el resto, se obtiene un grafo con $x$ componentes conexos, y al enviar estos a los elementos sucesivos de $X$ , se obtiene una función sobreyectiva débilmente creciente $N \to X$ ; también los tamaños de los componentes conexos dan una composición de $n$ en $x$ partes. Este argumento es básicamente el dado en estrellas y barras , excepto que allí se hace la elección complementaria de $x - 1 "separaciones".$

Ejemplo:
$X=\{a,b\},N=\{1,2,3\}{\text{, then }}$
$\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 $norte$ a $incógnita$ , hasta una permutación de $incógnita$

En este caso, consideramos secuencias de $n$ elementos distintos de $X$ , pero identificamos aquellos obtenidos a partir de otros aplicando a cada elemento 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 al término $i$ de la segunda secuencia, y como ningún valor ocurre dos veces en ninguna de las secuencias, estos requisitos no se contradicen entre sí; queda mapear los elementos que no ocurren en la primera secuencia biyectivamente a 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 la existencia de tales secuencias para empezar requiere $n \leq x$ , por el principio del palomar. El número se expresa, por lo tanto, como , utilizando el corchete de Iverson . $[n\leq x]$

Funciones inyectivas de $norte$ a $incógnita$ , hasta permutaciones de $norte$ y $incógnita$

Este caso se reduce al anterior: como todas las secuencias de $n$ elementos distintos de $X$ ya pueden transformarse entre sí aplicando una permutación de $X$ a cada uno de sus términos, permitir también la reordenación de los términos no da ninguna identificación nueva; el número sigue siendo . $[n\leq x]$

Funciones sobreyectivas de $norte$ a $incógnita$ , hasta una permutación de $incógnita$

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

Funciones sobreyectivas de $norte$ a $incógnita$

Para cada función sobreyectiva $f : N \to 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$ , lo que siempre se puede escribir como para algún $i$ ∈ $N$ , y las composiciones diferirán entonces en $i$ ). De ello se deduce que el número para este caso es $x$ ! veces el número para el caso anterior, es decir $f(i)$ $\textstyle x!\{{n \atop x}\}.$

Ejemplo:
$X=\{a,b\},N=\{1,2,3\}{\text{, then }}$
$\left\vert \{(a,a,b),(a,b,a),(a,b,b),(b,a,a),(b,a,b),(b,b,a)\}\right\vert =2!\left\{{3 \atop 2}\right\}=2\times 3=6$

Funciones de $norte$ a $incógnita$ , hasta una permutación de $incógnita$

Este caso es como el correspondiente para funciones sobreyectivas, pero algunos elementos de $x$ podrían no corresponder a ninguna clase de equivalencia en absoluto (ya que uno considera funciones hasta una permutación de $X$ , no importa qué elementos estén involucrados, sólo cuántos). Como consecuencia, uno está contando relaciones de equivalencia en $N$ con a lo sumo $x$ clases, y el resultado se obtiene del caso mencionado por suma sobre valores hasta $x$ , dando . En caso de que $x$ ≥ $n$ , el tamaño de $x$ no plantea restricción alguna, y uno está contando todas las relaciones de equivalencia en un conjunto de $n$ elementos (equivalentemente todas las particiones de tal conjunto); por lo tanto da una expresión para el número de Bell $B$ _$n$ . $\textstyle \sum _{k=0}^{x}\{{n \atop k}\}$ $\textstyle \sum _{k=0}^{n}\{{n \atop k}\}$

Funciones sobreyectivas de $norte$ a $incógnita$ , hasta permutaciones de $norte$ y $incógnita$

Este caso es equivalente a contar particiones del número $n$ en $x$ partes no nulas . Comparado con el caso de contar funciones sobreyectivas hasta permutaciones de X solamente ( ), uno solo retiene los tamaños de las clases de equivalencia en las que la función particiona $N$ (incluyendo la multiplicidad de cada tamaño), ya que dos relaciones de equivalencia pueden transformarse una en otra por una permutación de $N$ si y sólo 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$ , de modo que como resultado uno obtiene por definición el número $p$ _$x$ ( $n$ ) de particiones de $n$ en $x$ partes no nulas. $\textstyle \{{n \atop x}\}$

Funciones de $norte$ a $incógnita$ , hasta permutaciones de $norte$ y $incógnita$

Este caso es equivalente 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$ $x$ partes no nulas como máximo se puede extender a dicha partición añadiendo el número requerido de ceros, y esto explica todas las posibilidades exactamente una vez, por lo que el resultado está dado por . Al añadir 1 a cada una de las $x$ partes, se obtiene una partición de $n$ $+$ $x$ en $x$ partes no nulas, y esta correspondencia es biyectiva; por lo tanto, la expresión dada se puede simplificar escribiéndola como . $\textstyle \sum _{k=0}^{x}p_{k}(n)$ $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 del conjunto vacío a $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 no vacío $N$ 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 hay funciones inyectivas $N \to X$ , y si $n < x$ no hay funciones sobreyectivas $N \to X$ .
Las expresiones utilizadas en las fórmulas tienen como valores particulares

0^{0}=0^{\underline {0}}=0!={\binom {0}{0}}={\binom {-1}{0}}=\left\{{0 \atop 0}\right\}=p_{0}(0)=1

(los primeros tres son instancias de un producto vacío , y el valor se da por la extensión convencional de los coeficientes binomiales a valores arbitrarios del índice superior), mientras que

{\tbinom {-1}{0}}={\tfrac {(-1)^{\underline {0}}}{0!}}=1

\left\{{n \atop x}\right\}=p_{x}(n)=0\quad {\hbox{whenever either }}n>0=x{\hbox{ or }}0\leq n<x.

En particular, en el caso de contar multiconjuntos 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 índice inferior negativo 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 estrellas y barras , pero la última da valores incorrectos para $n$ $= 0$ y todos los valores de $x$ . Para los casos en que el resultado implica una suma, es decir, aquellos de contar particiones de N en como máximo $x$ subconjuntos no vacíos o particiones de n en como máximo $x$ partes distintas de cero, el índice de suma se toma para comenzar en 0; aunque el término correspondiente es cero siempre que $n$ $> 0$ , es el único término distinto de cero cuando $n$ $= 0$ , y el resultado sería incorrecto para esos casos si se tomara que la suma comienza en 1. ${\tbinom {n+x-1}{n}}$ ${\tbinom {n+x-1}{x-1}}$ ${\tbinom {n-1}{n-x}}$ ${\tbinom {n-1}{x-1}}$

Generalizaciones

Podemos generalizar aún más permitiendo que otros grupos de permutaciones actúen sobre $N$ y $X$ . Si $G$ es un grupo de permutaciones de $N$ , y $H$ es un grupo de permutaciones de $X$ , entonces contamos clases de equivalencia de funciones . Dos funciones $f$ y $F$ se consideran equivalentes si, y solo si, existen de modo que . Esta extensión conduce a nociones como permutaciones cíclicas y diedricas , así como particiones cíclicas y diedricas de números y conjuntos. $f\colon N\rightarrow X$ $g\in G,h\in H$ $F=h\circ f\circ g$

El camino veinte veces

Kenneth P. Bogart desarrolló otra generalización llamada el método veinte veces mayor en su libro "Combinatorics Through Guided Discovery". En el problema de distribuir objetos en cajas, tanto los objetos como las cajas pueden ser idénticos o distintos. Bogart identifica 20 casos. ^[3] Robert A. Proctor ha construido el método treinta veces mayor. ^[4]

Véase también

Estrellas y barras (combinatoria)

Referencias

^ Richard P. Stanley (1997). Combinatoria enumerativa, volumen I. Cambridge University Press. ISBN 0-521-66351-2 . p. 41.
^ Robert V. Hogg y Elliot A. Tanis (2001). Probabilidad e inferencia estadística . Prentice-Hall, Inc. ISBN 0-13-027294-9 . p.81.
^ Kenneth P. Bogart (2004). Combinatoria a través del descubrimiento guiado, pág. 57
^ Proctor, Robert A. (2006). "¡Ampliemos el método de Rota para contar particiones en doce pasos!". arXiv : math/0606404 .