SEARCH HOME
 Math Central Quandaries & 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 IE 111 112 ETC

Jon,

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)!).

Victoria

Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences.