# Combinations

Tag:

Combination Versus Permutation

Combination and permutation are terms that refer to the selection of a subset of objects from a larger set or pool of objects.

Combination refers to the selection process where the order of the selected objects is not important to the problem being addressed. An example of a combination is finding how many groups of four people can be formed from a population of fifteen people.

Permutation refers to the selection of a group of elements or objects from the total available number of elements or objects, and the arrangement of the selected items in a certain order. To follow the above example, if the groups of four people were sub-divided into president, vice-president, secretary and treasurer, then the order of those selected would be important and would need to be factored in when selecting the groups.

Statistical theory, in particular those concepts termed set theory, are important to computer related privacy and security issues. By use of programs that can rapidly project combinations and permutations of letters and symbols, hackers are often able to gain unauthorized access to programs and data. Such brute-force hacking often involves the generation of millions of expressions to be checked against the actual password. Although not elegant, programs without some non-randomized security element or key are often easily cracked by the high-speed generation of combinations and permutations of symbols.

Formula #1: Find the number of combinations of n elements taken r at a time.

nCr= n!/r!(n-r)!

Example:
In how many ways can a sample of 4 chocolates be selected from a box of 12 chocolates?
12C4 = 12!/[4!—(12-4)!] = 12!/(4!—8!) = 495
Hence, there are 495 possible ways to select 12 chocolates taken 4 chocolates at a time.

Formula #2: Find the number of combinations of n elements with n1 elements taken r1 at a time, n2 elements taken r2 at a time, etc.

C = n1Cr1 — n2Cr2 — ...

(a) Number of combinations of n different things taken r at a time, when p particular things are always included = n-pCr-p.

(b) Number of combination of n different things, taken r at a time, when p particular things are always to be excluded = n-pCr Example: In how many ways can a cricket-eleven be chosen out of 15 players? If (i) A particular player is always chosen,(ii) A particular is never chosen.

Ans: (i) A particular player is always chosen, it means that 10 players are selected out of the remaining 14 players. =. Required number of ways = 14C10 = 14C4= 14!/4!x19! = 1365

(ii) A particular player is never chosen, it means that 11 players are selected out of 14 players. => Required number of ways = 14C11 = 14!/11!x3! = 364

(c) Number of ways of selecting zero or more things from n different things is given by:- 2n-1

Example: John has 8 friends. In how many ways can he invite one or more of them to dinner? Ans. John can select one or more than one of his 8 friends.=> Required number of ways = 28 -1 1= 255.

(d) Number of ways of selecting zero or more things from n identical things is given by :- n+1

Example: In how many ways, can zero or more letters be selected form the letters AAAAA?

Ans. Number of ways of : Selecting zero 'A's=1, Selecting one 'A's = 1 , Selecting two 'A's =1, Selecting three 'A's = 1 Selecting four 'A's = 1 , Selecting five 'A's = 1 => Required number of ways = 6 [5+1]

(e) Number of ways of selecting one or more things from p identical things of one type qidentical things of another type, r identical things of the third type and n different things is given by: - (p+1) (q+1) (r+1)2n - 1

Example: Find the number of different choices that can be made from 3 apples, 4 bananas and 5 mangoes, if at least one fruit is to be chosen.

Ans: Number of ways of selecting apples = (3+1) = 4 ways Number of ways of selecting bananas = (4+1) = 5 ways. Number of ways of selecting mangoes = (5+1) = 6 ways. Total number of ways of selecting fruits = 4 x 5 x 6 But this includes, when no fruits i.e. zero fruits is selected => Number of ways of selecting at least one fruit = (4x5x6) -1 = 119 Note: - There was no fruit of a different type, hence here n=o => 2n = 20=1

(f) Number of ways of selecting r things from n identical things is 1.

(g) nCk = nCn - k