Biyección entre conjuntos y multiconjuntos

La técnica habitual de estrellas y barras para probar la fórmula de conjuntos múltiples también da la biyección deseada. Es decir, tenemos dos biyecciones:

Multiconjuntos de tamaño$k$tomado de un conjunto con$n$elementos$\leftrightarrow$

Secuencias de$n-1$barras (divisores) y$k$estrellas$\leftrightarrow$

Subconjuntos de tamaño$k$tomado de un conjunto con$n + k-1$elementos.

Para ilustrar, con$k = 3$y$n = 5$, la secuencia de * y barras

por un lado codifica el multiset$3^2, 5$tomado de$\{1, 2, \dots, 5\}$, y por otro lado codifica el subconjunto$\{3,4,7\}$tomado de$\{1,2, \dots, 7\}$. ¿Cómo funcionan estas codificaciones? Para la interpretación multiconjunto, piense en el$4 = n-1$barras como marcado$n = 5$contenedores, y las estrellas que indican$2$objetos en el$3$tercer contenedor y$1$objeto en el$5$th bin. Para la codificación del subconjunto, el$*$'s que aparecen en las posiciones 3, 4 y 7, indicando el subconjunto$\{3,4,7\}$de$\{1,2, \dots, 7\}$.

La biyección usual toma la$n$-conjunto de elementos como$\{1,2\ldots,n\}$y toma el multiset$\{a_1,a_2,\ldots, a_k\}$con$a_1\le a_2\le\cdots\le a_k$a$\{a_1,a_2+1,a_3+2,\ldots,a_k+k-1\} \subseteq\{1,\ldots,n+k-1\}$.

Sí, puede ordenar su conjunto múltiple con repetición en un orden ligeramente creciente, por ejemplo