combinatoria - calcular el número total de combinaciones de un sistema de

Question

Hago un ejemplo, pero necesito entender la fórmula general. Tengo un sistema definido por filas como por ejemplo:

A1,A2,A3,A4
B1,B2,B3
C1,C2
D1
E1

Y necesito encontrar todas las combinaciones posibles de los elementos de elegir por 2 (dobles) o necesito encontrar todas las combinaciones posibles de los elementos de elegir por 4 (4 veces) o triples y así sucesivamente. Por ejemplo válido dobles son:

A1,C1
A2,E1
A3,C2
etc. 

pero no A1,A2 (porque de la misma fila).

Necesito lo mismo para los triples, por ejemplo, los siguientes:

A3,C1,D1
A2,C1,D1
etc.

Sé el C(n,k) en caso de que el sistema está compuesto sólo por A1,B1,C1,D1,E1 pero no puedo averiguar cómo incluir el hecho de que algunas de las filas pueden tener valores diferentes.

En general, un sistema puede estar compuesto por n filas, cada fila que puede tener un número diferente de elementos (columnas diferentes), necesito una fórmula para calcular el número total de combinaciones generadas elección de los elementos en grupos de k y, si es posible, una generalización que permite encontrar los totales para múltiples k (como el número total de combinaciones de 4 pliegues, de 5 pliegues y dobles).

Muchas gracias de antemano a quien me ayude. Muy apreciado.

Answer 1

No creo que vas a conseguir una buena fórmula. Que $\mathscr{K}$ ser el conjunto de subconjuntos de cardinalidad $\{1,\dots,n\}$ $k$, y que $m_r$ es el número de elementos en la fila $r$. Luego el número al que desea es

$$\sum_{S\in\mathscr{K}}\prod_{k\in S}m_k\;.\tag{1}$$

Si todas las filas eran del mismo tamaño, decir con elementos de $m$, $(1)$ reduciría a $$\binom{n}km^k\;,$ $

pero en general va a ser bastante desordenado.

Answer 2

Deje $C_{n,k}$ el número de ganas de combinaciones por primera $n$ filas, la extracción de $k$ elementos. Vamos $m_j$ ($j=1\cdots n$) ser el número de elementos en cada fila, a Continuación,

$$C_{n,k}= C_{n-1,k} + m_n \, C_{n-1,k-1} $$

con $C_{n,0}=1$, $C_{k,k}=\prod_{j=1}^k m_j$

Con esto, usted puede calcular el valor numérico (por ejemplo: http://ideone.com/VbFg5V ), una fórmula general parece mucho pedir, a menos que algo más se sabe acerca de $m_j$.En particular, para $m_j=1$ obtenemos $C_{n,k}={n \choose k}$ (por supuesto), y para $m_j=m$, la fórmula de Brian respuesta.