Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

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.

share|improve this answer
    
Thanks, are you sure of Ck,k? How you do it in the example I reported above? Because just adding a single row (like 'f1') increase the number of doubles in the set. Please can you show me how you solve the specific case so I can try to generalise ? –  user53358 Dec 17 '12 at 1:33
    
@user53358: I added a code example. If I understood the problem right, $C_{n,n}$ means I must take an element of each row, then the combinations is given by that product , don't you agree? –  leonbloy Dec 17 '12 at 1:41
    
@leonbly : yes I agree, the code seems to works very well. You are giving me a strong help to understand. Many thanks !!! –  user53358 Dec 17 '12 at 1:52
add comment

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.

share|improve this answer
    
Thanks for the answer. Please can you clarify with the example above? For instance above the first row has 4 elements, the second 3 elements, the third 2 elements and the last two rows has 1 element. How you compute the total number of doubles and trebles? I tried your (1) in the example but I am probably doing something wrong. Thanks Brian ! –  user53358 Dec 17 '12 at 0:50
    
@user53358: You’re welcome. –  Brian M. Scott Dec 17 '12 at 0:51
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.