Unit - 5

Combinatorics

Q1) Define permutations.

A1)

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-

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

Any arrangement of any 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-                                          

Q2) What is factorial function?

A2)

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

Expressed as-

Note-

Q3) Explain the sampling with of without replacement.

A3)

Suppose we chose the samples with repetition, fro 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 =

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-

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

A4)

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 =

Q5) Define combination.

A5)

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

2. Property-2

3. Property-3

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

A6)

We have n = 4, r = 20

The number of non-negative integral solutions

= C (4 – 1 + 20, 20)

= C (23, 20)

= 1,771

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

A7)

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

= C (5 – 1 + 8, 8)

= C (12, 8) = 495 

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

Q8) Show that if seven numbers from 1 to 12 are chosen, then two of them will add up to 13.

A8)

First we will construct six different sets, each containing two numbers that add up to 13 as follows-

= {1, 12}, = {2, 11}, = {3, 10}, = {4, 9}, = {5, 8}, = {6, 7}.

Each of the seven numbers belong to one of these six sets.

Since there are six sets, then according to the pigeonhole principle that two of the numbers chosen belong to the same set. These numbers add upto 13.

Q9) Define the recurrence relations.

A9)

Recursion is a technique of defining a function, a set or an algorithm in terms of itself.

Suppose the set of natural numbers, we introduce the method of generating the set of natural numbers by recursion.

The natural numbers with zero are those objects which can be generated by starting with an initial object 0 and from any object “n” already generated passing to another uniquely determined object , the successor of n. The objects differently generated are always distinct. Thus the natural numbers appear as a set of objects 0,

The transition to the usual notation is made upon introducing 1, 2, 3, 4, … to stand for and then employing the notation.

The recursive formula for defining a sequence (or numeric function) is called a recurrence relation.

A recurrence relation is also called a difference equation.

The information accompanying a recursive formula about the beginning of the numeric function is called initial condition.

Q10) Check whether is a solution to the recurrence relation with .

A10)

Q11) What is linear recurrence relations with constant coefficients?

A11)

Suppose r and k are non-negative integers. A recurrence relation of the form

Here and f(r) are the functions of r is said to be a recurrence relation.

If  then it said to be a linear recurrence relation of degree k..

Q12) Consider a following recurrence relation-

A12)

It is a homogeneous linear second-order recurrence relation but it does not have constant coefficients because the coefficient of is not a constant given initial conditions , the next elements of the sequence follows-

Q13) What is the method of generating functions?

A13)

Recurrence relations can also be solved by using generating functions. Some equivalent expressions used are given below-

Then

Q14) Solve the recurrence relation-

A14)

Multiplying each term of the recurrence relation by , we find-

Now taking the sum to 2 to , we get

Replace each infinite sum by the corresponding equivalent expression given above, we obtain-

On simplifying, we obtain-

Decomposing A (z) as a sum of partial fractions, we can write

The solution is-

Q15) Define generating function.

A15)

For a numeric function-

An infinite series is defined as-

  which is called the generating function of a.

We denote it by A(Z).

The coefficient of is A (z) is the value of the numeric function a.

For example:

If the generating function is

Is

We can write the above series as below-

In   the term is called the constant term.

Let

And

Are the generating functions.