Unit - 3

Elementary Combinations

Q1) Explain sum rule and product rule.

A1)

Sum rule-

Suppose S be a set and | S | denote the number of elements in S.

If S is a union of disjoint non-empty subsets

A1, A2,…,An then-

|S| = |A1| + |A2| + … + |An|

In the above statement the subsets Ai of S are all disjoint i.e., they have no element in common. If Ai

A nd Aj an two subsets of S, then-

Ai ∩Aj= ∅i≠j

And we have

S = A1 ∪A2 ∪A3 ∪... ∪An

That is each element of S is exactly in one of the subsets Ai. In other words, the subsets A1, A2,…An is a partition of S. We now state the sum rule for counting events.

Let S be a sample space. Two events E1 and E2 of X are said to be mutually exclusive if the events have no elements in common. If E1, E2, E3, …En, are mutually exclusive events of S, then we can state

Sum rule for counting events as follows:

If E1, E2… En are mutually exclusive events of a sample space S and E1 can happen in m1 ways. E2 can happen in m2 ways…

En can happen in mn ways then E1 or E2 or … or En can happen m1 + m2 + …

+ mn ways.

Sum rule principle-

Let A and B are two disjoint sets, then-

n(A ∪ B) = n(A) + n(B)

Product rule principle-

Let A×B is the Cartesian product of two sets A and B, then-

n(A  B) = n(A). n(B)

Product rule-

If E1, E2, …., En are events, and E can happen in m1 ways E2 can happen m2 ways, … En can happen in mn ways, then the sequence of events E, first followed by E2 followed by E3, . . .,  followed by En can happen in m1 × m2 × … × mn ways

Example: In how many different ways one can answer all the questions of a true-false test consisting of 4 questions?

Solution: There are two ways of answering each of the 4 questions. Therefore by product rule the

Number of ways in which all the 4 questions can be answered-

= 2 × 2 × 2 × 2 = 16

Q2) How many ways can we draw a club or a diamond from a pack of cards?

A2)

As we know that there are 13 clubs and 13 diamonds in a pack of cards.

The number of ways a club or a diamond may be drawn 13 + 13 = 26.

Q3) In how ways can be drawn an ace or a king from an ordinary deck of playing cards?

A3)

Number of Aces in a pack = 4

Number of kings in a pack = 4

Number ways an Ace or a king can be drawn from the pack = 4 + 4 =

Q4) What is Combinations and Permutations?

A4)

Permutations-

A permutation of n objects taken r at a time is an arrangement of r of the objects

(r≤n).

The symbols of permutations of n things taken r at a time are- P or nPr 

Example 1: Consider the three letters x, y, z. The arrangements of the letter x, y, z taken two at a time are-

Xy, yx, xz, zx, yz, zy

∴The number of 2-arrangements are 6 i.e., the number of permutation of 3 letters taken 2 at a time

P= 6

Note-A permutation of n objects taken r at a time is also called r-permutation

Factorial function-

The product of the positive integers from 1 to n is denoted by n! and we read it as “factorial “

Expressed as-

n! = 1.2.3.4…(n – 3)(n – 2)(n – 1)n

Note- 1! = 1 and 0! = 1n! = n(n – 1)!

Binomial coefficient-

Example:

1.

2. 

Permutation-

The arrangement of a set of n objects in a given order is called a permutation.

Any arrangement of any r≤n of these objects in a given order is said to be r-permutation.

The number of permutations of n objects taken r will be denoted as-

P(n, r)

Formula-                                   P(n, r) =        

Permutation with repetitions-

The number of permutations of n objects of which are q1 are alike, q2 are alike, qr

Are alike is-

P(n,q,q2, . . ., qr) = n!/(q1! q2!...qr!)

Sampling with or without replacement-

Suppose we chose the samples with repetition, from example if we draw a ball from a urn then we put back that ball in the urn and again we pick a ball and we continue the process, so this is the case of sampling with repetition

Then the product rule tells us that the number of such samples is-

n.n.n.n.n……….n.n = nr

And if we pick a ball from the urn and we do not put it back to the urn, then this is the case of sampling without replacement.

So that in this case the number of samples are given as-

P(n, r) = n!/(n – r)!

Example-

Three cards are chosen one after the other from a 52-card deck. Find the number m of ways

This can be done: (a) with replacement; (b) without replacement.

Sol.

(a) Each card can be chosen in 52 ways. Thus m = 52(52)(52) = 140 608.

(b) Here there is no replacement. Thus the first card can be chosen in 52 ways, the second in 51 ways, and the third in 50 ways. So that-

P(52, 3) = 52(51)(50) = 132 600

Circular permutations-

A circular permutation of n objects is an arrangement of the objects around a circle.

If the n objects are to be arranged round a circle we take an objects and fix it in one position.

Now the remaining (n – 1) objects can be arranged to fill the (n – 1) positions the circle in (n – 1)! ways.

Hence the number of circular permutations of n different objects = (n – 1)!

Combinations-

A combination of n objects taken at a time is an unordered selection of r of the n

Objects (r ≤n).

A combination of n objects taken r at a time is also called r-combination of n objects.

The number of combinations is given by-

C(n, r)

Note-

1. Property-1

C(n, r) = P(n, r)/r!

2. Property-2

C(n, n) = n!/(n!(n – n)!) = n!/(n!0!) = 1

3. Property-3

C(n, 0) = n!/(0!(n – 0)!) = n!/(0!n!) = 1

Q5) There are 4 black, 3 green and 5 red balls. In how many ways can they be arranged in a row?

A5)

Total number of balls = 4 black + 3 green + 5 red = 12

The black balls are alike,

The green balls are, and the red balls are alike,

The number of ways in which the balls can be arranged in a row = 12!/(4!3!5!) = 27,720

Q6) A box contains 10 light bulbs. Find the number n of ordered samples of:

(a) Size 3 with replacement,

(b) Size 3 without replacement.

A6)

(a) n= 10r = 103 = 10  10  10 = 1,000

(b) P (10, 3) = 10 × 9 × 8 = 720

Q7) In how many ways can a person invite one or more of his 5 friends to a party?

A7)

For every friend there are two possibilities i.e., he may be invited or he may not be invited to attend the party.

The number of ways in which we can invite his five friends at a party is 25.

But this includes the case when none of his friend is invited.

Hence, the number of ways in which he invites one or more of his five friends to a party is

– 1 = 32 – 1 = 31

Q8) Prove that C (n, r) = C (n, n – r)

A8)

C (n, r) denotes the number of selections of n objects when r-things are selected, and the remaining (n – r) objects are not selected. Therefore, selecting of r-things is the same as discarding (n – r) objects. For each selection of r things i.e., for each r-combination there is a discarding of n – r, remaining objects. The number of ways in which we discord (n – r) objects is C (n, n – r).

Since the set of r-combinations and the set of discarding of (n – r) objects are in one-one corresponding we get

C (n, r) = C (n, n – r)

Q9) Show that C (n, r) = C (n – 1, r – 1) + C (n – 1, r)

A9)

C (n, r) is the number of r-combinations of n objects. Let n be any one of the n objects. Fix the object x the C (n, r) combinations can be grouped into:

(i) Those r-combinations that contain the objects x.

(ii) Those r-combinations that do not contain the object x.

Since the objects x is in all r-combinations of (i) we are to choose (r – 1) objects in each combinations of (i) from the remaining (n – 1) objects, this can be done in C (n – 1, r – 1) ways.

The number of combinations that contain x, is

C (n – 1, r – 1)

To count the number of r-combinations of (ii) i.e., the number of r-combinations which do not contain x, we omit the objects x from n objects and choose r objects from the remaining (n – 1) objects.

Therefore, the number r-combinations that do not contain x is C (n – 1, r).

Thus C (n, r) = C (n – 1, r – 1) + C (n – 1, r)

Q10) Show that C (n, 0) + C (n, 1) + … + C (n, n) =

A10)

This is equivalent to finding the number of subsets of a set A with n elements. The number of subsets of A can be considered as follows:

The number of subsets having no elements (i.e., subsets with 0 elements is C (n, 0)

The number of subsets having 1 elements is C (n, 1) …

The number of subsets with n elements is C (n, n). Adding we get the number of elements in the power set of A.

i.e., | (A) | = C (n, 0) + C (n, 1) + … + C (n, n)

But the number of elements in the power set of A is .

Hence C (n, 0) + C (n, 1) + … + C (n, n) =

Q11) A farmer buys 4 cows, 2 goats and 5 ducks from a person who has 7 cows, 5 goats and 8 ducks. How many choices the farmer have:

A11)

The farmer can choose 4 cows from 7 cows in C (7, 4) ways, 2 goats from 5 goats in C (5,

2) ways and 5 ducks from 8 ducks in C (8, 5) ways.

∴ The farmer can choose 4 cows, 2 goats and 5 ducks in C (7, 4) C (5, 2) C (8, 5)

Q12) There are twelve students in a class. Find the number of ways that the twelve students take three different tests if four students are to take each test.

A12)

We find the number of ordered partitions of twelve students into cells containing four students each. There are

The required number of ways, the students can write the take the tests is 34,650.

Q13) Enumerating Combinations and Permutations with Repetitions

A13)

Generalized sum rule-

If we have tasks that can be done in ways respectively, and no two of these tasks can be done at the same time then there are ways to do one of these task.

Generalized product rule-

If we have sequential task that can be done in , then there are to do the procedure.

Permutation and combination with unlimited repetitions-

Suppose U (n, r) denotes r-permutations of n-objects with unlimited repetitions and v (r, n) denotes the r-combination with unlimited repetitions, then-

Let us consider a set where are all distinct.

Any r-combination is of the form here each is a non-negative integer and

The numbers are called repetition numbers. Conversely any sequence of non-negative integers-

Corresponds to a r-combination .

The following observation we get-

The number of r-combination of

= the number of non-negative integer solution of

= the number of ways of placing r indistinguishable balls in n numbered boxes.

= the number of binary numbers with n – 1 one’s and zeros.

= C (n – 1 + r, r)

= C (n – 1 + r, n - 1)

Example-How many outcomes are possible by costing a 6 faced die 10 times?

Solution:

This is same as placing 10 similar balls into 6 numbered boxes.

There are C (6 – 1 + 10, 10)

= C (15, 10) possible outcomes.

Q14) Find the number of non-negative integral solutions to

A14)

We have n = 4, r = 20

The number of non-negative integral solutions

= C (4 – 1 + 20, 20)

= C (23, 20)

= 1,771

Q15) Find the number of ways of placing 8 similar balls in 5 numbered boxes.

A15)

The number of ways of placing similar balls in 5 numbered boxes is

= C (5 – 1 + 8, 8)

= C (12, 8) = 495

Q16) Find the 4-combinations of {1, 2, 3, 4, 5, 6}.

A16)

The 4-combinations are 1234, 1235, 1236, 1245, 1246, 1256, 1345, 1346, 1356, 1456, 2345, 2346, 2456, 3456.

A17) Find the number of non-negative integral solutions to n1 + n2 + n3 + n4 = 20

A17)

We have n = 4, r = 20

The number of non-negative integral solutions

= C (4 – 1 + 20, 20)

= C (23, 20) = 1,771

Q17) Find the number of ways of placing 8 similar balls in 5 numbered boxes.

A18)

The number of ways of placing similar balls in 5 numbered boxes is

= C (5 – 1 + 8, 8)

= C (12, 8) = 495

Q18) Find the number binary numbers with five 1’s and three 0’s.

A19)

The number of binary numbers with five 1’s and three 0’s is

= C (5 + 3, 3)

= C (8, 3)

= 56

Q19) Explain Binomial Coefficients, The Binomial and Multi-Nominal Theorems with examples.

A20)

The numbers are called the binomial coefficients.

Binomial theorem-

Binomial theorem gives a formula for the coefficients in the expansion of .

According to theorem-

Let n be a positive integer then for all a and b, then

Example-1: Expand

Sol.

Here we have-

By using binomial theorem, we get

= C (4, 0)(2a)4 + C(4, 1)(2a)3b + C(4, 2) (2a)2b2 +C(4,3)(2a)b3+C(4,4)b4

=16a4 + 32a3b + 24 a2b2 + 8ab3 + b4.

Example-2: Find the term containing in the expansion of

Sol.

The general term will be-

Tr+1 = C(8, r) a8 – r(-2/a)r

= C(8, r) a8-r(-2a-1)r

= C (8, r)a8-r(-2)r(a-1)r

= C(8, r) (-2)ra8-ra-r

= C(8, r)(-2)ra8-2r

Put 8 – 2r = 4 we get r = 2

Therefore the term contains is-

Tr+1 = T3 = C(8, r) (-r)ra4

= C (8, r) 4 a4

= 284 a4

=112 a4

Note-

If we replace ‘a’ and ‘b’ by ‘x’ and ‘1’ then we get another form of the binomial theorem-

(x + 1)n =

Example-3: In the expansion of , prove the following result-

C02 + C12 + C22 + . . . + Cn2 = 2n!/(n!)2

Sol. We have-

(1+x)n = C(n, 0) + C(n, 1) x + . . . + C(n, n)xn

As we know that the coeff. Of the terms equivalent from the beginning and end are equal, so that-

(1+x)n = C(n, n) + C(n, n -1) x + . . . + C(n, 0)xn

By multiplying the above two equations, we get-

(1+x)2n = [C(n, 0) + C(n, 1) x + . . . + C(n, n)xn]x[C(n, n) + C(n, n – 1)x + . . . + C(n, 0)]xn

From RHS, we see the coeff. Of

C(n, 0)2 + C(n, 1)2 + . . . + C(n, n)2

But the coeff. Of in is-

C(2n , n) = 2n!/n!.n! = 2n!/(n!)2

C02 + C12 + Cn2 = 2n!/(n!)2

Example: If If = C (n, 0) + C (n, 1) x + C (n, 2) + … + C (n, n)

Prove that C (n, 1) + 2 C (n, 2) + 3 C (n, 3) + … + n C (n, n) = n .

Sol:

C(n, 1)x + 2 C (n, 2) x2 + . . . + n C (n, n) xn

= nx + 2 . 2(n – 1)/2!  x2 + . . . + n xn

= nx + n(n – 1) x2 + . . . + nxn

= nx[1 + (n – 1)x + . . . + xn-1]

= nx[ C(n – 1, 0) + C(n – 1, 1) x + . . . + C(n – 1, n – 1) xn – 1]

= nx(1+x)n -1

Multi-Nominal Theorems:

Let n be a positive integer, then for all + + … +

Where the summation extends over all sets of non-negative integers , , …,

Where + + … + = n.

Example: Find the coefficients of in the expansion of .

Sol:

We have n = 25, x1 = x1, x2 = 74, x3 = 3 z, and x4 = w

∴ The coefficients of   in the expansion of .

Is

Q20) Prove that

A21)

We know that

Adding, we get

Note-

And

Q21) What is Principle of Inclusion-Exclusion?

A22)

The Inclusion-Exclusion principle can be stated as below-

Let A and B any two finite sets, then-

n(A ∪ B) = n(A) + n(B) – n(A ∩ B)

Meaning- Here if we have to find the number n(A∪B) of elements in the union of A and B.

So then we add n(A) and n\(B) which means we are including these two.

And then we exclude n(A∩B).

Note- For three sets-

If we have three finite sets A, B and C then-

n(A ∪ B ∪ C) = n (A) + n( B) + n(C) – n(A ∩B) – n(A∩C) – n(B∩C) +n(A∩B∩C)

Example: Find the number of students at a college choosing at least one of the subject from mathematics, physics and statistics.

The data is given as-

65 study maths, 45 study physics, 42 study statistics

20 study maths and physics, 25 study maths and statistics, 15 study physics and statistics and 8 study all the three subjects.

Sol.

Here we need to find n(M∪P∪S) where,

M = maths, P = physics and S = statistics

Now by using Inclusion-Exclusion principle-

n(M ∪ P ∪ S) = n(M) + n(P) + n(S) – n(M ∩ P) – n(M ∩ S) – n(P ∩ S) + n(M ∩ P ∩ S)

Which gives-

n(M ∪ P ∪ S) = 65 + 45 + 42 – 20 – 25 – 15 + 8 = 100

Therefore, we find that 100 students study at least one of the three subjects.