Permutation and Combination

Permutation – position (order) matters. = N! / (N – r)!.

• Building words with {a,b,c} are also permutation problem with r = {1,2,3..N}

Combination – position (order) doesn’t matter = N! / (N – r)! * r! . Combination is a part of Permutation set. All possible combination means, generating combination for r = {0,1.. N}. For set {1,2,3}, the powerset is

• _{n = 0, combinations {}}
• _{n = 1, combinations {1},{2},{3}}
• _{n = 2, combinations {1,2},{2,3},{3,1}}
• _{n = 3, combinations {1,2,3}}

• Coins problems are combination problems with r= {1,2,3..N}. ex. combination of coins sum up to an amount. Repetition of coin is allowed.

• Ex. Amount =4 with coins{1,2,3}, combinations are {1,1,1,1},{1,1,2},{2,2},{1,3}. Take all possible combinations of coins
• {1},{2},{3}
• {1,1},{1,2},{1,3},{2,2},{2,3},{3,3}
• {1,1,1},{2,2,2},{3,3,3},{1,1,2},{1,1,3},{1,2,3},{1,2,2},{1,3,3},{2,3,3}
• {1,1,1,1},{2,2,2,2},{3,3,3,3}