Forma duodecimal

La forma duodecimal o doce escenarios 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 un número . La idea de clasificación se atribuye a Gian-Carlo Roth, y el nombre camino duodecimal fue propuesto por Joel Spencer [1] por analogía con el término camino óctuple de la física, que a su vez proviene del concepto de camino óctuple en el budismo . [2]. El nombre sugiere que usando los mismos enfoques en 12 casos, pero con ligeros cambios en las condiciones, obtenemos 12 resultados diferentes.

Resumen

Sean y sean conjuntos finitos . Denote por y la cardinalidad de estos conjuntos (el número de elementos). Diremos que es -conjunto, y es -conjunto. $norte$ $X$ ${\ estilo de visualización n=|N|}$ ${\ estilo de visualización x = | X |}$ $norte$ $norte$ $X$ $X$

La tarea principal que consideraremos es calcular las clases de equivalencia de funciones . ${\ estilo de visualización f: N \ a X}$

Las funciones caen bajo una de las tres restricciones siguientes:

No hay restricciones: la función puede asignar cualquier elemento de a cualquier elemento de , y cada elemento puede aparecer varias veces. $a$ $norte$ $F$ $b$ $X$ $b$
$F$ es una inyección : cada valor de from debe ser diferente de todos los demás, de modo que cada elemento de from pueda aparecer como máximo una vez en la imagen de la función . $fa)$ $a$ $norte$ $b$ $X$ $F$
$F$ es una sobreyección : para cualquier elemento de allí debe haber al menos un elemento de tal que , es decir, cada elemento aparecerá al menos una vez en la imagen de la función . $b$ $X$ $a$ $norte$ ${\ estilo de visualización f (a) = b}$ $b$ $F$

(La condición " es una biyección " solo es posible si , pero entonces es equivalente tanto a " inyección" como a " es una sobreyección".) $F$ ${\ estilo de visualización n = x}$ $F$ $F$

Hay cuatro relaciones de equivalencia diferentes que se pueden definir en el conjunto de funciones de a : $F$ $norte$ $X$

igualdad;
igualdad hasta permutación de elementos ; $norte$
igualdad hasta una permutación del conjunto ; $X$
igualdad hasta una permutación de los conjuntos y . $norte$ $X$

Cualquiera de estas relaciones de equivalencia da una partición del conjunto de funciones en clases de equivalencia.

(La clase de equivalencia es la órbita de la función bajo la acción del grupo considerado: f , o , o , o , donde es el grupo simétrico en N y es el grupo simétrico en X .) $F$ ${\ Displaystyle f \ circ S_ {n}}$ $S_{x}\circ f$ $S_{x}\circ f\circ S_{n}$ $S_{n}$ $S_{x}$

Tres condiciones sobre funciones y cuatro relaciones de equivalencia se pueden combinar en escenarios. ${\ estilo de visualización 3 \ veces 4 = 12}$

Los doce problemas de clases de equivalencia de funciones de conteo no son equivalentes en complejidad y no existe un método sistemático único para resolverlos. Dos 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 en n y x , y los cinco problemas restantes tienen una respuesta en términos de funciones combinatorias ( Números de Stirling de la segundo tipo y funciones de partición para un número dado de partes).

Los problemas de conteo clásicos son consistentes con estas configuraciones de la siguiente manera.

Contar n -permutaciones (es decir, permutaciones parciales o secuencias sin repeticiones) de un conjunto X es equivalente a contar funciones inyectivas ${\ estilo de visualización N \ a X}$ .
Contar n combinaciones de un conjunto X es equivalente a contar funciones inyectivas hasta una permutación del ${\ estilo de visualización N \ a X}$ conjunto N.
Contar permutaciones de un conjunto X es equivalente a contar funciones inyectivas , donde , así como contar funciones sobreyectivas , donde . ${\ estilo de visualización N \ a X}$ ${\ estilo de visualización n = x}$ ${\ estilo de visualización N \ a X}$ ${\ estilo de visualización n = x}$
Contar conjuntos múltiples de tamaño n (también conocidos como n -combinaciones con repeticiones) de elementos de X es equivalente a contar todas las funciones hasta las permutaciones del conjunto N ${\ estilo de visualización N \ a X}$ .
Contar particiones de un conjunto N en x subconjuntos es equivalente a contar todas las funciones sobreyectivas hasta las permutaciones del ${\ estilo de visualización N \ a X}$ conjunto X.
Contar las expansiones de un número n en x partes es equivalente a contar todas las funciones sobreyectivas hasta las permutaciones del conjunto N ${\ estilo de visualización N \ a X}$ .

Puntos de vista

Las diferentes tareas en los doce escenarios se pueden ver desde diferentes perspectivas.

Bolas y cajas

Tradicionalmente, muchos de los problemas en los doce escenarios se formulan en términos de colocar bolas en cajas (u otras visualizaciones similares) en lugar de definir funciones. El conjunto N se puede identificar con bolas y el conjunto X con cajas. Luego , la función describe cómo se distribuyen las bolas a las cajas, es decir, la bola a se coloca en la caja . Entonces, la propiedad de que la función asigna una imagen única a cada valor en el dominio se refleja en la propiedad de que cualquier pelota puede entrar en una sola caja (junto con el requisito de que no se deben dejar pelotas fuera de las cajas), donde cualquier caja puede entrar. aceptar (en principio) un número arbitrario de bolas. Requerir que ƒ sea inyectiva significa que ninguna caja puede contener más de una bola, mientras que requerir que ƒ sea sobreyectiva significa que cada caja debe contener al menos una bola. ${\ estilo de visualización f: N \ a X}$ ${\ estilo de visualización f' (a)}$

El cálculo de las relaciones de equivalencia de permutaciones del conjunto N y/o del conjunto X se refleja en el reconocimiento de bolas y cajas como "indistinguibles". Este reconocimiento no es una declaración precisa (en la práctica, las bolas y cajas individuales se pueden distinguir por su posición y diferentes bolas se pueden colocar en diferentes cajas), pero indica que las diferentes configuraciones no se consideran separadas si una de ellas se puede convertir en otra. por intercambio de bolas o cajas. Esto es exactamente lo que se formaliza permutando los conjuntos N y / o X. Las cajas indistinguibles son más difíciles de imaginar que las bolas indistinguibles, ya que la configuración implica inevitablemente cierto orden de las cajas. La reorganización de las cajas aparecerá como un intercambio de su contenido.

Selecciones

Otro enfoque para tratar con los mismos casos es en términos de muestras en estadística . Imagine una población de X objetos (o personas) de la que elegimos N. Comúnmente se consideran dos esquemas, conocidos como " muestreo con retracción" y "muestreo sin reemplazo" . En el primer caso (selección con devolución), tras la selección del objeto, lo devolvemos a la población, para que nos vuelva a golpear. El resultado de cada una de estas muestras es independiente de todas las demás muestras, y el conjunto de muestras se considera técnicamente como variables aleatorias independientes distribuidas de forma idéntica . En el segundo caso, sin embargo, después de seleccionar el objeto, lo apartamos y el objeto no puede aparecer por segunda vez. Esto significa que el hecho de que se seleccione un objeto tiene un efecto en todas las muestras posteriores (no se puede golpear un objeto en particular por segunda vez), por lo que nuestras muestras se vuelven dependientes entre sí.

En el caso de muestreo con backtracking, diremos abajo “Cualquier f' ”, mientras que para muestreo sin backtracking, diremos “Inyectivo f' ”. Cada cuadro indica cuántas selecciones diferentes de conjuntos se realizaron en un esquema particular. Una línea con la palabra "Diferente" significa que se tiene en cuenta el pedido. Por ejemplo, si tenemos objetos de los cuales seleccionamos dos, entonces la muestra (4,7) es diferente de (7,4). Por otro lado, la línea etiquetada como "S n order" significa que el orden no importa; en este caso las selecciones (4.7) y (7.4) son equivalentes. En términos de una distribución de probabilidad , las muestras de reentrada, donde se tiene en cuenta el orden, son comparables a describir la distribución conjunta de N variables aleatorias individuales , cada una con una distribución categórica de X veces . El caso en el que no se tiene en cuenta el orden es comparable a la descripción de una única distribución multinomial de N muestras de una categoría X , donde solo importa el número de cada categoría. El caso en el que no se tiene en cuenta el orden y las muestras se hacen sin reemplazo es comparable a una distribución hipergeométrica multivariante separada , y la comparación de la cuarta posibilidad con algo no es visible. Tenga en cuenta que en todos los casos "inyectivos" (es decir, muestras sin reemplazo), el número de conjuntos de muestras es cero a menos que . (La palabra "comparable" en los casos anteriores significa que cada elemento del espacio de eventos elemental de la distribución correspondiente corresponde a un conjunto separado de muestras y, por lo tanto, el número en la celda indica el tamaño del espacio de eventos para esta distribución). $N\leqslant X$

Desde este punto de vista, el caso marcado como "Surjective f' " parece extraño. Esencialmente, seguimos seleccionando hacia atrás hasta que hayamos seleccionado todos los elementos al menos una vez. Ahora contamos cuantas veces hemos sacado las bolas, y si este número no es igual a N , descartamos toda la muestra y repetimos. Esto recuerda vagamente al problema de selección de cupones , donde el proceso consiste en "recoger" (obtener y devolver) un conjunto de X cupones hasta que tengamos un conjunto en el que cada cupón aparezca al menos una vez. Tenga en cuenta que en todos los "casos sobreyectivos" el número de conjuntos de muestras es igual a cero si no . ${\ Displaystyle N \ geqslant X}$

Selección, marcado, agrupación

Una función se puede ver en términos de X o N. Esto lleva a diferentes puntos de vista: ${\ estilo de visualización f: N \ a X}$

la función ƒ marca cada elemento del conjunto N con un elemento de X .
la función ƒ elige un elemento del conjunto X para cada elemento del conjunto N , obteniendo n muestras en total.
la función ƒ agrupa elementos del conjunto N si se asignan al mismo elemento del conjunto X.

Estos puntos de vista no se aplican por igual a todos los casos. Los puntos de vista de "etiqueta" y "selección" no son del todo compatibles con la permutación de los elementos del conjunto X , ya que cambian etiquetas y selecciones. Por otra parte, el punto de vista de la "agrupación" no da información completa sobre la configuración si los elementos del conjunto X no se pueden permutar. Los puntos de vista de "muestreo" y "selección" son más o menos equivalentes cuando N no está permutado, pero en este caso el punto de vista de "selección" es más apropiado. La muestra se puede ver entonces como una muestra desordenada: se selecciona un conjunto (múltiple) de n elementos del conjunto X.

Etiquetado y muestreo con o sin repeticiones

Si pensamos en ƒ como el etiquetado de los elementos del conjunto N , las letras pueden pensarse como ordenadas en una secuencia y las etiquetas como asignadas secuencialmente a los elementos. El requisito de que la función ƒ sea inyectiva significa que ninguna etiqueta puede usarse dos veces. El resultado será una secuencia de etiquetas sin repeticiones . En ausencia de este requisito, se utiliza la terminología "secuencias con repeticiones", lo que significa que las etiquetas se pueden usar más de una vez (aunque también se permiten secuencias en las que no hay repeticiones).

Para una muestra desordenada, se aplica el mismo tipo de distinción. Si f va a ser inyectiva, entonces la elección debe involucrar n elementos distintos del conjunto X , por lo que será un subconjunto del conjunto X de tamaño n , la llamada n - combinación . Sin este requisito, el mismo elemento del conjunto X puede aparecer en la muestra varias veces, de modo que el resultado sea un multiconjunto de n elementos del conjunto X , que también se denomina n - multi -match o n -match con repetición.

En estos casos, el requisito de que ƒ sea sobreyectiva significa que cualquier etiqueta debe usarse al menos una vez, o que cualquier elemento de X debe incluirse en la muestra al menos una vez. Tal requisito es menos natural en la consideración matemática y, además, el caso anterior se considera más fácilmente como una agrupación de elementos de N con la adición de etiquetas de grupo de elementos del conjunto X.

Particiones de conjuntos y números

Si consideramos f como una agrupación de elementos del conjunto N (lo que implica identificación por permutaciones del conjunto X ), el requisito de que f sea sobreyectiva significa que el número de grupos debe ser exactamente igual a x . Sin este requisito, el número de grupos no puede exceder x . El requisito de que f sea inyectiva significa que cada elemento de N debe ser en sí mismo un grupo, lo que deja solo una agrupación válida y, por lo tanto, no es un problema de conteo interesante.

Si, además, la identificación se hace por permutaciones del conjunto N , esto lleva a olvidar los grupos, sólo quedan sus tamaños. Estas dimensiones no aparecen en ningún orden en particular y las propias dimensiones pueden aparecer más de una vez. Puede ordenar los tamaños en una lista ligeramente decreciente de números que suman n [3] . Esto da una representación combinatoria de dividir el número n en exactamente x (para una ƒ sobreyectiva ) o como máximo x (para una ƒ arbitraria ).

Fórmulas

Las fórmulas para los diversos casos de los doce escenarios se resumen en una tabla, con cada elemento de la tabla vinculado a una sección a continuación que explica la fórmula.

Doce objetos combinatorios y sus fórmulas.

clase f	Cualquier f	f inyectiva	sobreyectiva f
F	n -secuencia en X $x^n$	n -permutación del conjunto X ${\ estilo de visualización x ^ {\ subrayado {n}}}$	composición N con x subconjuntos $\textstyle x!\{{n \encima de x}\}$
${\displaystyle f'\circ S_{n))$	n -multisubconjunto de X ${\binom {x+n-1}{n))$	n -subconjunto del conjunto X ${\binom {x}{n))$	composición n con x miembros ${\binom{n-1}{nx))$
$S_{x}\circ f$	partición de N en subconjuntos ${\ estilo de visualización \ leqslant x}$ ${\displaystyle \sum _{k=0}^{x}\left\{{n \atop k}\right\))$	dividir N en elementos ${\ estilo de visualización \ leqslant x}$ ${\ estilo de visualización [n \ leqslant x]}$	partición de N en subconjuntos ${\ estilo de visualización \ leqslant x}$ $\left\{{n \encima de x}\right\}$
$S_{x}\circ f\circ S_{n}$	dividir n en partes ${\ estilo de visualización \ leqslant x}$ $p_{x}(n+x)$	dividir n en partes 1 ${\ estilo de visualización \ leqslant x}$ ${\ estilo de visualización [n \ leqslant x]}$	dividir n en x partes ${\ estilo de visualización p_ {x} (n)}$

Notación utilizada:

Factorial decreciente , $x^{\subrayado {n}}={\frac {x!}{(xn)!}}=x(x-1)(x-2)\cdots (x-n+1)$
Factorial creciente , $x^{\overline {n}}={\frac {(x+n-1)!}{(x-1)!}}=x(x+1)(x+2)\cdots ( x+n-1)$
Factorial $n!=n^{\subrayado {n}}=n(n-1)(n-2)\cdots 1$
Los números de Stirling del segundo tipo expresan el número de formas de dividir un conjunto de n elementos en k subconjuntos ${\ estilo de visualización \ estilo de texto \ {{n \ encima de k}} \}}$
Coeficiente binomial $\textstyle {\binom {n}{k}}={\frac {n^{\underline {k}}}{k!)}}$
Los corchetes de Iverson codifican la verdad o falsedad de una declaración (como 1 o 0)
número de particiones de un número n en k partes $p_{k}(n)$

Significado intuitivo de filas y columnas

Aquí hay un breve resumen de lo que significa cada clase. Las clases se describen en detalle a continuación.

Considere un conjunto de X elementos numerados (números del 1 al x ), de los cuales seleccionamos n , lo que da una lista ordenada de elementos. Por ejemplo, si hay elementos de los que seleccionamos , el resultado podría ser una lista (5,2,10). Ahora contamos cuántas listas distintas de este tipo hay, a veces primero transformando las listas de tal manera que se reduzca el número de posibilidades distintas. ${\ estilo de visualización x = 10}$ $n=3$

Entonces las columnas significan:

Any f : Después de seleccionar un elemento, lo apilamos de nuevo para poder seleccionarlo de nuevo.
Inyectiva f : Después de haber seleccionado un elemento, lo apartamos para que no podamos volver a seleccionarlo. Por lo tanto, terminamos con n elementos distintos. Por supuesto, en este caso, si no está satisfecho , no obtendremos ninguna lista. $n\leqslant x$
Sobreyectiva f : Después de haber seleccionado un elemento, lo volvemos a colocar para poder sacarlo nuevamente, pero al final, tenemos que seleccionar cada elemento al menos una vez. Por supuesto, en este caso, si no está satisfecho , no obtendremos ninguna lista. ${\ Displaystyle n \ geqslant x}$

Las líneas significan:

Varios: Dejar las listas como están, contarlas directamente.
S n orbitas: Antes de contar, ordene las listas por los números de los elementos seleccionados, para que el orden no importe, por ejemplo (5,2,10), (10,2,5), (2,10,5) etc. .todo → (2,5,10).
S x órbitas: antes de contar, vuelva a numerar los elementos de modo que el primer elemento de la lista sea el número 1, el segundo (si no es igual) el número 2, y así sucesivamente. Los números se pueden repetir si un elemento aparece más de una vez en la lista. enumere, por ejemplo, (3,5,3), (5,2,5), (4,9,4), etc. → (1,2,1), mientras que (3,3,5), ( 5,5,3), (2,2,9), etc. → (1,1,2).

$\mathbf {S} _{n}\times \mathbf {S} _{x}$ órbitas: antes de contar, la lista se ordena y se vuelve a numerar como se describe anteriormente. (Nota: la renumeración seguida de la clasificación puede generar listas diferentes en algunos casos, pero la cantidad de listas posibles no cambiará).

Detalles de varios casos

Los casos a continuación están ordenados a medida que se cuentan, que no es el mismo orden en la tabla.

Funciones de N a X

Este caso es equivalente a contar secuencias de n elementos del conjunto X sin restricciones: la función está definida por n imágenes de elementos de N , que pueden elegirse independientemente de elementos traza de x . Esto da un total de x n posibilidades. ${\ estilo de visualización f: N \ a X}$

Ejemplo:

${\displaystyle X=\{a,b,c\},N=\{p,q\))$ , después

$\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 equivale a contar secuencias de n elementos diferentes del conjunto X , que también se denominan n -permutaciones del conjunto X , o secuencias sin repetición . De nuevo, la secuencia está formada por n patrones de elementos de N . Este caso difiere de las sucesiones sin restricciones (arriba) en que la elección del segundo elemento es uno menos, el segundo es dos menos, y así sucesivamente. Por tanto, en lugar de la potencia de x , el resultado vendrá dado por un factorial decreciente de x , en el que cada siguiente factor es uno menos que el anterior. Fórmula para el número de combinaciones.

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

Tenga en cuenta que en el caso de que , uno de los factores sea igual a cero, por lo que en este caso no hay funciones inyectivas . Esto es simplemente una reafirmación del principio de Dirichlet . ${\ estilo de visualización n> x}$ ${\ estilo de visualización N \ a X}$

Ejemplo:

$X=\{a,b,c,d\},N=\{1,2\}$ , después

$\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^{\subrayado {2}}=4\times 3=12$

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

Este caso equivale a contar subconjuntos con n elementos de X , también llamados n -combinaciones de X- entre secuencias de n elementos diferentes de X , aquellas que difieren sólo en el orden de los elementos se identifican con permutaciones de N. Dado que en todos los casos todos estos grupos tienen exactamente n ! secuencias diferentes, podemos dividir el número de tales secuencias por n ! para obtener el número de n combinaciones del conjunto X. Este número se conoce como coeficiente binomial y viene dado por la fórmula ${\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\}$ , después

$\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 multiconjuntos con n elementos de X (que se denominan n -multicombinaciones). La razón es que para cada elemento del conjunto X , la combinación está determinada por cuántos elementos del conjunto N se asignan a ese elemento mediante la función f , mientras que dos funciones que dan el mismo número de "multiplicidad" para cada elemento del conjunto X pueden siempre se transformará de uno a otro permutando los elementos del conjunto N . La fórmula que cuenta todas las funciones no sirve aquí, ya que el número de elementos agrupados por permutaciones de N varía de una función a otra. Más bien, como se explica en Combinaciones con repeticiones , el número de n -combinaciones múltiples de un conjunto con x elementos se puede considerar como el número de n -combinaciones de un conjunto con x + n − 1 elementos. Esto reduce el problema a otro caso en "forma duodecimal", y da el resultado ${\ estilo de visualización N \ a X}$

{\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=\{p,q\))$ , después

$\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 es equivalente a contar multiconjuntos con n elementos de X para los cuales cada elemento de X aparece al menos una vez. Esto es equivalente a contar las expansiones de un número n en x elementos (distintos de cero) , enumerando la multiplicidad de x elementos en orden ascendente. La correspondencia entre funciones y multiconjuntos es la misma que en el caso anterior, y el requisito de sobreyectividad hace que todas las multiplicidades sean al menos una. Cuando todas las multiplicidades se reducen por 1, se reduce el problema al caso anterior. Como tal cambio reduce el valor de n en x , el resultado es

{\binom{n-1}{nx)).

Tenga en cuenta que en el caso no hay funciones sobreyectivas en absoluto . Esto se tiene en cuenta en la fórmula si se considera que los coeficientes binomiales siempre son 0 si el subíndice es negativo. El mismo valor también viene dado por la expresión ${\ estilo de visualización n <x}$ ${\ estilo de visualización N \ a X}$

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

Excepto en el caso extremo de , en el que la fórmula anterior da el valor correcto , pero la última fórmula da . ${\ estilo de visualización n = x = 0}$ ${\tbinom {-1}{0}}=1$ ${\tbinom {-1}{-1}}=0$

Esta fórmula de resultado sugiere buscar una asociación de funciones sobreyectivas directamente con un subconjunto de n − x elementos elegidos entre n − 1 elementos, lo que se puede hacer de la siguiente manera. Primero elegimos una ordenación completa de los conjuntos N y X y notamos que al aplicar una permutación apropiada del conjunto N , cualquier función sobreyectiva puede transformarse en una única función de crecimiento lento [4] (y, por supuesto, todavía sobreyectiva). Si conectamos los elementos del conjunto N (según el orden) por n − 1 arcos en un gráfico de líneas , entonces elegir cualquier subconjunto de n − x arcos y eliminar el resto dará un gráfico con x componentes conectados, y mapearlos en elementos sucesivos del conjunto X dará una función sobreyectiva de crecimiento lento . Además, las dimensiones de los componentes conectados dan una composición de n en x partes. Este argumento es esencialmente el mismo que para los asteriscos y guiones , excepto que se elige x − 1 "separadores" ${\ estilo de visualización N \ a X}$ ${\ estilo de visualización N \ a X}$ ${\ estilo de visualización N \ a X}$

Ejemplo:

$X=\{a,b\},N=\{p,q,r\}$ , después

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

Funciones inyectivas de N a X hasta permutaciones de X

En este caso, consideramos sucesiones de n elementos diferentes de X , pero identificamos las funciones obtenidas entre sí permutando los elementos del conjunto X . Es fácil ver que siempre se pueden identificar dos secuencias diferentes: la permutación debe asignar el término i de la primera secuencia al término i de la segunda secuencia, y dado que el valor aparece dos veces en ambas secuencias, estos requisitos no se contradicen entre sí. . El mapeo permanece para mapear un elemento que no se encuentra en la primera secuencia a un elemento que no se encuentra en la segunda secuencia. Lo único que hace que el resultado dependa de nyx es la existencia de tales sucesiones, lo que se expresa como un requisito según el principio de Dirichlet. Por lo tanto, el número de permutaciones se expresa como cuando se usa el corchete de Iverson . $n\leqslant x$ ${\ estilo de visualización [n \ leqslant x]}$

Funciones inyectivas de N a X hasta permutaciones de los conjuntos N y X

Este caso se reduce al anterior: dado que todas las secuencias de n elementos diferentes de X se pueden transformar entre sí mediante permutaciones del conjunto X , lo que le permite reordenar los elementos sin crear nuevas entidades, el número permanece . ${\ estilo de visualización [n \ leqslant x]}$

Funciones sobreyectivas de N a X hasta una permutación del conjunto X

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. Además, para cualquier función sobreyectiva , la relación de tener la misma imagen cuando se mapea mediante la función f es una relación de equivalencia, y esta relación no cambia cuando se aplican sucesivamente permutaciones del conjunto X. Por otro lado, se puede convertir tal relación de equivalencia en una función sobreyectiva asignando ciertas clases de equivalencia a los elementos x del conjunto X. El número de tales particiones o relaciones de equivalencia es, por definición, el número de Stirling de segunda clase S ( n , x ), que también se escribe como . Los valores se pueden describir con una relación de recurrencia o con funciones generadoras , pero, a diferencia de los coeficientes binomiales, no existe una expresión de forma cerrada para estos números que no utilice la sumatoria . ${\ estilo de visualización N \ a X}$ ${\ estilo de visualización \ estilo de texto \ {{n \ encima de x}} \}}$

Funciones sobreyectivas de N a X

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

Ejemplo:

$X=\{a,b\},N=\{p,q,r\}$ , después

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

Funciones de N a X con la permutación exacta del conjunto X

Este caso es similar al caso correspondiente para funciones sobreyectivas, pero algunos elementos de x pueden no corresponder a ninguna clase de equivalencia en absoluto (dado que las funciones se consideran hasta una permutación del conjunto X , no importa qué elementos se consideren, solo importa cuántos ). En consecuencia, se calculan relaciones de equivalencia sobre N con como máximo x clases y el resultado se obtiene del caso mencionado sumando sobre x valores , lo que da . En el caso , el tamaño de x no impone restricción alguna y se cuentan todas las relaciones de equivalencia sobre 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 . $\textstyle \sum _{k=0}^{x}\{{n \sobre k}}\}$ ${\ estilo de visualización x \ geqslant n}$ $\textstyle \sum _{k=0}^{n}\{{n \sobre k}}\}$

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

Este caso es equivalente a contar las particiones del número n en x partes distintas de cero . El caso es comparable al caso de contar funciones sobreyectivas hasta permutaciones del conjunto X (solo sobre X , ), solo deben tenerse en cuenta los tamaños de las clases de equivalencia en las que la función divide el conjunto N (incluida la multiplicidad de cada tamaño), ya que dos relaciones de equivalencia pueden transformarse una en otra permutación del conjunto N si y sólo si los tamaños de las clases son iguales. Esto es exactamente lo que distingue la noción de una partición de n de la noción de una partición de N , de modo que el resultado se obtiene determinando el número p x ( n ) de particiones de n en x partes distintas de cero. ${\ estilo de visualización \ estilo de texto \ {{n \ encima de x}} \}}$

Funciones de N a X hasta una permutación de los conjuntos N y X

Este caso es equivalente a contar las particiones del número n en como máximo x partes . La asociación es la misma que en el caso anterior, incluyendo partir el 0 por cada elemento de X no incluido en la imagen de la función. Cada partición del número n en un máximo de x partes distintas de cero se puede extender a tal partición agregando el número necesario de ceros, y esto cuenta para todas las posibilidades exactamente una vez, de modo que el resultado viene dado por la fórmula . Sumando uno a cada una de las x partes, obtenemos una partición de n + x en x partes distintas de cero, y esta correspondencia es biyectiva. Por lo tanto, la expresión se puede simplificar a una notación (aunque este cambio no facilita el cálculo). $\textstyle \sum _{k=0}^{x}p_{k}(n)$ $p_{x}(n+x)$

Casos extremos

Las fórmulas anteriores dan los valores correspondientes 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 N o X vacíos . En estos casos se debe considerar lo siguiente.

Para cualquier conjunto X , hay exactamente una función del conjunto vacío en X (no hay valores para esta función), que siempre es inyectiva, pero nunca sobreyectiva, excepto cuando X está (también) vacía.
Para cualquier conjunto N no vacío , no hay función de N al conjunto vacío (es necesario que haya al menos un valor de la función, pero no lo hay).
Cuando , no hay función inyectiva , y si , no hay funciones sobreyectivas . ${\ estilo de visualización n> x}$ ${\ estilo de visualización N \ a X}$ ${\ estilo de visualización n <x}$ ${\ estilo de visualización N \ a X}$
Las expresiones utilizadas en las fórmulas tienen valores específicos

0^{0}=0^{\subrayado {0}}=0!={\binom {0}{0}}={\binom {-1}{0}}=\left\{{ 0 \encima de 0}\derecha\}=p_{0}(0)=1

(los tres primeros son representantes del producto vacío , y el significado está determinado por la extensión comúnmente aceptada de los coeficientes binomiales a valores arbitrarios del superíndice), mientras que

\scriptstyle {\tbinom {-1}{0}}={\frac {(-1)^{\subrayado {0}}}{0!)}}=1

\left\{{n \encima de x}\right\}=p_{x}(n)=0

alguna vez , o

{\ estilo de visualización n> 0 = x}

0\leqslant n<x.

En particular, para el caso de contar multiconjuntos con n elementos elegidos de X , la expresión anterior es equivalente en la mayoría de los casos a , pero la última expresión arroja 0 en el caso (con la convención habitual de que los coeficientes binomiales con subíndice negativo siempre son 0 ). De manera similar, para el caso de contar composiciones del número n con x partes distintas de cero, la expresión anterior es casi equivalente a la expresión dada por el enfoque del argumento de asterisco y guión , pero en el último caso obtenemos el resultado incorrecto para y todo valores de x . Para los casos en los que el resultado implica una suma, es decir, cuando se cuentan particiones de N por un máximo de x subconjuntos no vacíos o particiones de n por un máximo de x partes distintas de cero, el índice de suma comienza en 0, aunque el término correspondiente es cero para todos y se vuelve distinto de cero cuando . En caso de que el resultado sea incorrecto si comienza a sumar desde 1. ${\tbinom {n+x-1}{n))$ ${\tbinom {n+x-1}{x-1))$ ${\ estilo de visualización n = x = 0}$ ${\ estilo de visualización {\ tbinom {n-1} {nx}}}$ ${\ estilo de visualización {\ tbinom {n-1} {x-1}}}$ $n=0$ $n>0$ $n=0$ $n=0$

Generalizaciones

Podemos generalizar aún más al permitir que otros grupos de permutación actúen sobre N y X. Si G es el grupo de permutación del conjunto N y H es el grupo de permutación del conjunto X , entonces contamos las clases de equivalencia de las funciones . Dos funciones y se consideran equivalentes si y sólo si existen , tales que . Esta extensión conduce a conceptos tales como permutaciones cíclicas y diédricas , así como particiones cíclicas y diédricas de números y conjuntos. ${\ estilo de visualización f \ dos puntos N \ a X}$ $F$ $F$ ${\ estilo de visualización g \ en G, h \ en H}$ $F=h\circ f\circ g$

Manera decimal

Otra generalización, llamada la vía 20 , fue desarrollada por Kenneth P. Bogart en su libro Combinatorics Through Guided Discovery . En el problema de distribuir objetos en cajas, los objetos y las cajas pueden considerarse indistinguibles o diferentes. Bogart distinguió 20 casos [5] .

2 manera decimal

n objetos y condiciones, cómo se obtienen	x destinatarios y modelo matemático de distribución
n objetos y condiciones, cómo se obtienen	Varios	Lo mismo
1. Varios Sin condiciones	n -secuencias en X $x^n$	partición de N en subconjuntos ${\ estilo de visualización \ leqslant x}$ ${\displaystyle \sum _{i=0}^{n}\left\{{x \atop i}\right\))$
2. Varios Cada uno se selecciona no más de una vez	n -permutaciones del conjunto X ${\ estilo de visualización x ^ {\ subrayado {n}}}$	${\begin{casos}1&n\leqslant x;\\0&n>x\end{casos))$
3. Varios Cada uno se selecciona al menos una vez	composiciones N con x subconjuntos $x!\left\{{n \encima de x}\right\}$	dividir N en x subconjuntos $\left\{{n \encima de x}\right\}$
4. Diferente Cada uno se elige exactamente una vez	$n!=x!$ permutaciones	$1{\begin{casos}1&n=x\\0&n\neq x\end{casos))$
5. Varios, se respeta el orden	${\ estilo de visualización (n + x-1) ^ {\ subrayado {n))}$ funciones ordenadas	${\ estilo de visualización \ suma _ {i = 1} ^ {x} L (n, i)}$ permutaciones rotas (en partes) ${\ estilo de visualización \ leqslant x}$ ¿Dónde está el número de Lach? ${\ estilo de visualización L (n, i)}$
6. Varios, orden contados Cada uno se selecciona al menos una vez	$(n)^{\subrayado {x}}(n-1)^{\subrayado {nx}}$ ordenado en funciones	$L(n,x)=\left({n \atop x}\right)(n-1)^{\subrayado {nx))$ permutaciones rotas (en x partes) donde esta el numero de lach ${\ estilo de visualización L (n, x)}$
7. Igual sin condiciones	n -multiconjuntos del conjunto X ${\ estilo de visualización \ izquierda ({x + n-1 \ sobre n} \ derecha)}$	${\ estilo de visualización \ suma _ {i = 1} ^ {x} p_ {i} (n)}$ número de particiones (en partes) ${\ estilo de visualización \ leqslant x}$
8. Idéntico Cada uno se selecciona no más de una vez	n -subconjuntos del conjunto X ${\ estilo de visualización \ izquierda ({x \ encima de n} \ derecha)}$	${\begin{casos}1&n\leqslant x;\\0&n>x\end{casos))$
9. Igual Cada uno se selecciona al menos una vez	${\ estilo de visualización \ izquierda ({n-1 \ encima de x-1} \ derecha)}$ composiciones ( x partes)	dividir n en x partes ${\ estilo de visualización p_ {x} (n)}$
10. Igual Cada uno se elige exactamente una vez	${\begin{casos}1&n=x\\0&n\neq x\end{casos))$	${\begin{casos}1&n=x;\\0&n\neq x\end{casos))$

Notas

↑ Stanley, 1997 , pág. 41.
↑ Ricardo Stanley. Combinatoria enumerativa. - Mir, 1990. - T. 1. - S. 55.
↑ Una lista débilmente decreciente es una lista descendente con posibilidad de repetición.
↑ Se dice que una función crece lentamente si es monótona, pero es posible la repetición de valores.
↑ Bogart, 2004 , pág. 57.

Literatura

Richard P. Stanley. Combinatoria enumerativa, volumen I. - Prensa de la Universidad de Cambridge, 1997. - ISBN 0-521-66351-2 .
Kenneth P. Bogart. Combinatoria a través del descubrimiento guiado . — Universidad de Dartmouth, 2004.