Math CentralQuandaries & Queries


Question from Jon:

How many distinct combinations can be made when choosing 3 numbers from 36?
IE you can only choose each number once

1 2 3
12 4 13
1 2 5
1 2 6
2 34 2
2 13 35

but no number can be chosen twice


The number of ways to choose a collection of k distinguishable objects from a collection of n distinguishable objects is denoted by the symbol C(n,k), and read as "n choose k". You are looking for C(36, 3), that is, 36 choose 3.

To find a formula for C(n, k), when 0 <= k <= n, count the number of arrangements of k out of n distinguishable objects in a line, where repetitions are not allowed, in two different ways and equate the answers. The two expressions we get are equal because they represent the same number.

First, imagine choosing the k objects and then arranging them in a line. There are C(n,k) ways to choose the k objects, and k! ways to arrange them in a line. Therefore, the number of such lines is C(n,k)k!.

Second, count the number of such lines directly. There are n choices for the object on the left end of the line, then n-1 choices for the one next to it, then n-2 choices for the next one, and so on until, finally, there are n-(k-1) choices for the last object in the line. Thus, the number of such lines is n(n-1)(n-2)...(n-(k-1)) = n!/(n-k)!.

Therefore, C(n,k)k! = n!/(n-k)!, so that C(n,k)=n!/(k!(n-k)!).



About Math Central


Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences.
Quandaries & Queries page Home page University of Regina PIMS