Combinación

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 3 de diciembre de 2021; las comprobaciones requieren 2 ediciones .

En combinatoria , una combinación de by es un conjunto de elementos seleccionados de un conjunto de elementos , en el que no se tiene en cuenta el orden de los elementos. $norte$ $k$ $k$ $norte$

En consecuencia, las combinaciones que difieren solo en el orden de los elementos (pero no en la composición) se consideran iguales; así es como las combinaciones difieren de las ubicaciones . Entonces, por ejemplo, las combinaciones de 3 elementos 2 y 3 ( subconjuntos (no estrictos) para los cuales ) de un conjunto de 6 elementos 1 ( ) son iguales (mientras que los arreglos serían diferentes) y consisten en los mismos elementos 1. $k=3$ $n=6$

En general, el número de todos los posibles subconjuntos de elementos de un conjunto de elementos está en la intersección de la diagonal -ésima y la fila -ésima del triángulo de Pascal . [una] $k$ $norte$ $k$ $norte$

Número de combinaciones

Número de combinaciones de por $norte$ $k$ igual coeficiente binomial

{n \elegir k}=C_{n}^{k}={\frac {n!}{k!\left(nk\right)!}}).

Para una función generadora fija de la secuencia de números de combinación , , , ... es $norte$ ${\tbinom {n}{0))$ ${\tbinom {n}{1))$ ${\tbinom {n}{2))$

\sum _{k=0}^{n}{\binom {n}{k}}x^{k}=(1+x)^{n}.

La función generadora bidimensional de números de combinación es

\sum _{n=0}^{\infty}\sum _{k=0}^{n}{\binom {n}{k}}x^{k}y^{n}=\sum_{ n=0}^{\infty}(1+x)^{n}y^{n}={\frac {1}{1-y-xy}}.

Combinaciones con repeticiones

Una combinación con repeticiones de a es un conjunto de elementos de este tipo, en el que cada elemento puede participar varias veces, pero en el que no se tiene en cuenta el orden ( multiconjunto ). En particular, el número de funciones monótonas no decrecientes de un conjunto a otro es igual al número de combinaciones con repeticiones de a . $norte$ $k$ $k$ $norte$ ${\ estilo de visualización \ {1,2, \ puntos, k \))$ $\{1,2,\puntos,n\}$ $norte$ $k$

El número de combinaciones con repeticiones de por un coeficiente binomial igual $norte$ $k$

{\overline {C_{n}^{k}}}=C_{(n)}^{k}=\left(\!\!{\binom {n}{k}}\!\! \right)={\binom {n+k-1}{n-1}}={\binom {n+k-1}{k}}=(-1)^{k}{\binom {-n {k}}={\frac {(n+k-1)!}{k!\cdot (n-1)!}}.

Prueba

Que haya tipos de objetos, y los objetos del mismo tipo son indistinguibles. Sea un número ilimitado (o suficientemente grande, al menos no menos de) de objetos de cada tipo. De este surtido seleccionaremos objetos; la selección puede contener objetos del mismo tipo, el orden de selección no importa. Indicar por el número de objetos seleccionados del tipo -th, , . entonces _ Pero el número de soluciones de esta ecuación se puede calcular fácilmente con la ayuda de "bolas y particiones": cada solución corresponde a una disposición de bolas y particiones en fila, de modo que hay exactamente bolas entre la -ésima y la -ésima partición. Pero tales arreglos son exactamente lo que se requería probar. ■ $norte$ $k$ $k$ $x_{j}$ $j$ $x_{j}\geq 0$ $j=1,2,\puntos,n$ $x_{1}+x_{2}+\puntos +x_{n}=k$ $k$ $n-1$ $(j-1)$ $j$ $x_{j}$ ${\tbinom {n+k-1}{k))$

Para fijo , la función generadora de los números de combinaciones con repeticiones de por es igual a $norte$ $norte$ $k$

\sum _{k=0}^{\infty}\left[(-1)^{k}{-n \elegir k}\right]x^{k}=(1-x)^{ -norte}.

La función generadora bidimensional del número de combinaciones con repeticiones es

\sum _{n=0}^{\infty}\sum _{k=0}^{\infty}(-1)^{k}{-n \elegir k}x^{k}y^{n }=\sum _{n=0}^{\infty }(1-x)^{-n}y^{n}={\frac {1-x}{1-xy}}.

Véase también

Notas

↑ El asombroso triángulo del gran francés. . Consultado el 20 de abril de 2010. Archivado desde el original el 21 de abril de 2010. (indefinido)

Enlaces

R. Stanley. Combinatoria enumerativa. — M .: Mir, 1990.