5
$\begingroup$

I make an example but I need to understand the general formula. I have a system defined by rows as for instance:

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

And I need to find all possible combinations of elements choose by 2 (doubles) or I need to find all possible combinations of elements choose by 4 (4 fold) or trebles and so on. For instance valid doubles are:

A1,C1 A2,E1 A3,C2 etc.  

but not A1,A2 (because from the same row).

I need the same for trebles, for instance the following:

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

I know the C(n,k) in case the system is composed only by A1,B1,C1,D1,E1 but I cannot figure out how to include the fact that some of the rows can have different values.

In general a system can be composed by n rows, with each row that can have a different number of elements (different columns), I need a formula to calculate the total number of combinations generated choosing the elements in groups of k and, if possible, a generalisation which permits to find the totals for multiple k's (like total number of combinations for 4-folds, 5-folds and doubles).

Thank you very much in advance to who will help me. Highly appreciated.

2 Answers 2

1

Let $C_{n,k}$ the number of wanted combinations for the first $n$ rows, extracting $k$ elements. Let $m_j$ ($j=1\cdots n$) be the number of elements in each row, Then

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

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

With this, you can compute the value numerically (eg: http://ideone.com/VbFg5V ), a general formula seems too much to ask, unless something more is known about $m_j$.In particular, for $m_j=1$ we get $C_{n,k}={n \choose k}$ (of course), and for $m_j=m$, the formula from Brian's answer.

  • 0
    @leonbly : yes I agree, the code seems to works very well. You are giving me a strong help to understand. Many thanks !!!2012-12-17
1

I don’t think that you’re going to get a nice formula. Let $\mathscr{K}$ be the set of subsets of $\{1,\dots,n\}$ of cardinality $k$, and let $m_r$ be the number of elements in row $r$. Then the number you want is

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

If all rows were the same size, say with $m$ elements, $(1)$ would reduce to $\binom{n}km^k\;,$

but in general it’s going to be pretty messy.

  • 0
    @user53358: You’re welcome.2012-12-17