Combinatorics - Sin orden

Question

Dispone de 10 diferentes tipos de bolas para elegir. De cuántas maneras diferentes hay para elegir 5 bolas de tal manera que ningún tipo de pelota aparece más de dos veces.

Mi intento:

Caso 1 (selección de diferentes tipos): análogos para la elección de los 5 elementos de un conjunto de 10 - 10C5 = 252

Caso 2 (1 elemento se repite dos veces) - 10C4 para seleccionar 4 objetos y 4 para seleccionar el cual aparece dos veces - 10C4*4 = 840

Caso 3 (2 elementos de repetición) - 10C3 para seleccionar 3 objetos y 3 para seleccionar la que aparece una vez - 10C3*3 = 360

Total : 252 + 210 + 360 = 1452

Gracias,

Answer 1

Supongamos que usted ha $k$ diferentes bolas y desea contar cuántas maneras puede elegir $n$ bolas con la sustitución de tal manera que cada bola se elige menos de $\mu$ veces. Deje $x_i$ ser el número de veces que recoger el balón $i$. Entonces estamos contando el número de entero no negativo soluciones a

$$ x_1 + x_2 + ... + x_k = n $$

donde tenemos la restricción $x_i < \mu$ por cada balón. Podemos resolver esto mediante la inclusión a la exclusión. Si $S$ es el conjunto de restricciones y soluciones de $P_i$ es el subconjunto con $x_i \geq \mu$, luego tenemos

$$ \begin{array} (| S - (P_1 \cup P_2 \cup ... \cup P_k )| &= & |S| \;\;-\;\; \sum_i |P_i| \;\;+ \;\;\sum_{i,j} |P_i \cap P_j| \;\; - \;\; ... \\ \; &= & {n+k-1 \choose k-1} \;-\; k {n+k-1-\mu \choose k-1} \;+\; {k \choose 2} {n+k-1-2\mu \choose k-1} \;\;-\;\; ... \\ && \\ \; &= &\sum_{i=0}^\gamma \; (-1)^i {k \choose i} {n+k-1-i\mu \choose k-1} \end{array} $$

Donde $\gamma = \min \{k, \lfloor \tfrac{n}{\mu} \rfloor \}$. El taponamiento en los valores de $k=10, n=5, \mu=3$ resuelve la pregunta que usted plantea.

$$ \begin{array} ( \sum_{i=0}^{1} \; (-1)^i {10 \choose i} {14-3i \choose 9} = 1452 \end{array} $$

---

Me explicó todo en un post reciente resolución de un problema similar.