Combinations

• To get number of combinations (unordered)

• First calculate the number of ways we can create an ordered subset of length k from n distinct objects
• Then divide it by the number of ways to order k

• [ n! / ( n - k )! ] / k!

• n! / [ ( n - k )! * k! ]

• n choose k

• Example: 3 choose 2

• 3! / [ ( 3 - 2 )! * 2! ] = 3! / [ 1! * 2! ] = 3

• combinations of 2 from abc: ab, ac, bc