Calculating how many m of n combinations in which an object appears

roncace · science forum beginner Joined: 04 Apr 2006 Posts: 2

Say there are n objects taken m at a time. How can I determine the
number of times any single object, or any one of a subset of the
objects (size <= m) appears in the combinations. Here is an example of
what I mean:

There are 5 objects { a, b, c, d, e } and I want to look at the
combinations of those objects taken 3 at a time:

a b c
a b d
a b e
a c d
a c e
a d e
b c d
b c e
b d e
c d e

Now, how many of those combinations contain either a or b? For this
example the answer is nine, by actual count. Can anyone help me with a
general expression to solve this type of problem without enumeration of
all of the combinations?

Thanks!
Bob

Jean-Pierre LEVREL · science forum beginner Joined: 04 Apr 2006 Posts: 1

"roncace" <rroncace@yahoo.com> a écrit dans le message de news:
1144113312.990889.201290@z34g2000cwc.googlegroups.com...
| Say there are n objects taken m at a time. How can I determine the
| number of times any single object, or any one of a subset of the
| objects (size <= m) appears in the combinations. Here is an example of
| what I mean:
|
| There are 5 objects { a, b, c, d, e } and I want to look at the
| combinations of those objects taken 3 at a time:
|
| a b c
| a b d
| a b e
| a c d
| a c e
| a d e
| b c d
| b c e
| b d e
| c d e
|
| Now, how many of those combinations contain either a or b? For this
| example the answer is nine, by actual count. Can anyone help me with a
| general expression to solve this type of problem without enumeration of
| all of the combinations?
|
| Thanks!
| Bob
|
1) nombre de combinaisons de m éléments pris parmi n :
Nt = C(n,m) = n!/m!/(n-m)!
ex : n = 5, m = 3 => Nt = 10

2) nombre de combinaisons contenant exactement un élément prédéfini :
N1 = C(n-1,m-1), mais aussi N1 = Nt - C(n-1,m)
ex : n = 5, m = 1 => N1 = C(4,2) = 6 mais aussi N1 = 10 - C(4,3) = 10 - 4 =
6

3) nombre de combinaisons contenant au moins un élément parmi k éléments
prédéfinis :
Nk = Nt - C(n-k,m) =
ex : n = 5, m = 3, k = 2 => N2 = 10 - C(3,3) = 10 - 1 = 9

autre exemple : n = 6, m = 3 =>
Nt = C(6,3) = 20
N1 = 20 - C(5,3) = 10
N2 = 20 - C(4,3) = 16
N3 = 20 - C(3,3) = 1

JPL (from France)

roncace · science forum beginner Joined: 04 Apr 2006 Posts: 2

Jean-Pierre;

Now I see it. Merci, beaucoup!

Bob

Google