# Counting the number of possible combinations

I have the following question. I have a set of elements $A,B,C$ like this: $$A_nB_mC_l$$ $n,m,l$ are the element counts.

How to calculate all possible combinations (without replacement, the order is not important) according to $n,m,l$?

For example if I have $A_2B_2C$ there are following combinations possible:

amount of elements = 1: $A,B,C$ - 3 combinations

amount of elements = 2: $A_2,B_2,AB,AC,BC$ - 5 combinations

amount of elements = 3: $A_2B,A_2C,AB_2,B_2C,ABC$ - 5 combinations

amount of elements = 4: $A_2BC,AB_2C,A_2B_2$ - 3 combinations

amount of elements = 5: $A_2B_2C$ - 1 combination

So, in total I have $3+5+5+3+1=17$ combinations

• (n+1)*(m+1)*(l+1)-1 ................... – hvedrung Oct 9 '14 at 13:05
• You have omitted one possibility: amount of elements = 0: one combination (the empty set). Including this will help you derive a simpler formula, because all you have to do to identify a "combination" is to stipulate the number of $A$'s (between $0$ and $n$ inclusive), the number of $B$'s (between $0$ and $m$ inclusive), and the number of $C$'s (between $0$ and $l$ inclusive). – whuber Oct 9 '14 at 18:38

You can see it this way

Every tuplet (a, b ,c) such as $a\in[0,n], b\in[0,m], c\in[0,l]$ maps to exactly one combination, and every combination maps to exactly one tuplet

that means that: $F(a,b,c) => A_aB_bC_c$ is a bijection between [0,n][0,m][0,l] and the set of all possible combinations hence both sets have the same cardinality.

The cardinatlity of [0,n][0,m][0,l], and hence of the number of possible combinations is (n+1)(m+1)(l+1)

I guess this can be seen as a simple example: Consider A and B and C as cities and m and n and l as different roads between these three cities respectively. the question can be pictured as following:

How many ways that a traveler can travel between these 3 cities, assuming that he or she can travel directly from A to C.

this can be answered as first, how many combinations of traveling choices?

ABC, AB, AC, BC and staying at either of A, B or C(just going through the paths and coming back to the city).

now, for traveling through ABC, we have k=m X n X l for AB we have q=m X n choices which is also equal to 4 for AC we have w=m X l choices which is equal to 2 for BC we have p=n X l choices which is equal to 2 and finally for staying in either cities , we have m and n and l choices.

the final answer is : k+q+w+p+m+n+l