# combinatorics - calculate the total number of combinations of a system

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

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.

-
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

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.

-
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