Distributing Objects into Boxes

Case1: {\color{Green} }DISTINGUISHABLE OBJECTS AND DISTINGUISHABLE BOXES

EXAMPLE

How many ways are there to distribute hands of 5 cards to each of four players from the standard deck of 52 cards?

sol:

The first player can be choose 5 cards in C(52, 5) ways. The second player can be choose 5 cards in C(47, 5) ways, because only 47 cards are left. The third player can be choose 5 cards in C(42, 5) ways. Finally, the fourth player can be choose 5 cards in C(37, 5) ways. Hence, the total number of ways to deal four players 5 cards each is

here we use product rule,

C(52, 5)C(47, 5)C(42, 5)C(37, 5) = 52! /47! 5! · 47!/ 42! 5! · 42! /37! 5! · 37! /32! 5!

= 52!/ 5! 5! 5! 5! 32!

 

THEOREM  The number of ways to distribute n distinguishable objects into k distinguishable boxes so that ni objects are placed into box i, i = 1, 2,... , k, equals n! /n1! n2!··· nk!

 

Case2: INDISTINGUISHABLE OBJECTS AND DISTINGUISHABLE BOXES

Counting the number of ways of placing n indistinguishable objects into k distinguishable boxes turns out to be the same as counting the number of n-combinations for a set with k elements when repetitions are allowed.

 

EXAMPLE

 How many ways are there to place 10 indistinguishable balls into eight distinguishable bins?

 

Solution: The number of ways to place 10 indistinguishable balls into eight bins equals the number of 10-combinations from a set with eight elements when repetition is allowed.

 C(8 + 10 − 1, 10) = C(17, 10) = 17! /10!7!

= 19,448.

 

 This means that there are C(n + r − 1, n − 1) ways to place r indistinguishable objects into n distinguishable boxes

 

Case3: DISTINGUISHABLE OBJECTS AND INDISTINGUISHABLE BOXES

 

EXAMPLE

How many ways are there to put four different employees into three indistinguishable offices, when each office can contain any number of employees?

Solution:

First, we note that we can distribute employees so that all four are put into one office, three are put into one office and a fourth is put into a second office, two employees are put into one office and two put into a second office, and finally, two are put into one office, and one each put into the other two offices. Each way to distribute these employees to these offices can be represented by a way to partition the elements A, B, C, and D into disjoint subsets.

we find that there are 14 ways to put four different employees into three indistinguishable offices.

 

Case4: INDISTINGUISHABLE OBJECTS AND INDISTINGUISHABLE BOXES

EXAMPLE

How many ways are there to pack six copies of the same book into four identical boxes, where a box can contain as many as six books?

Solution:

here we will write all the ways we can pack books in the boxes

we will list the number of books in the box with the largest number of books, followed by the numbers of books in each box containing at least one book, in order of decreasing number of books in a box.

6

5, 1

4, 2

4, 1, 1

3, 3

3, 2, 1

3, 1, 1, 1

2, 2, 2

2, 2, 1, 1.

Contributor's Info

Created:
0Comment
Combinations

THEOREM  The number of r-combinations of a set with n elements, where n is a non-negative integer and r is an integer with 0 ≤ r ≤ n, equals
C(n, r) = n!\r!(n − r)!

 

Here note that we are only counting unordered selections of objects..i.e ordered not matter

Example :Let S be the set {1, 2, 3, 4}. Then {1, 3, 4} is a 3-combination from S. (Note that {4, 1, 3} is the same 3-combination as {1, 3, 4}, because the order in which the elements of a set are listed does not matter.)

 

 

An r-combination of elements of a set is an unordered selection of r elements from the set. Thus, an r-combination is simply a subset of the set with r elements.

EXAMPLE : How many poker hands of five cards can be dealt from a standard deck of 52 cards? Also, how many ways are there to select 47 cards from a standard deck of 52 cards?

 

Solution: Because the order in which the five cards are dealt from a deck of 52 cards does not matter, there are C(52, 5) = 52! /5!47!

 

To select 47 cards from 52 cards we can write as,

C(52, 47) = 52! /47!5!

 

Note: Let n and r be nonnegative integers with r ≤ n. Then C(n, r) = C(n, n − r).

 

EXAMPLE  How many ways are there to select five players from a 10-member tennis team to make a trip to a match at another school?

Solution:

the number of 5-combinations of a set with 10 elements. By Theorem , the number of such combinations is C(10, 5) = 10! /5! 5! = 252.

 

EXAMPLE A group of 30 people have been trained as astronauts to go on the first mission to Mars. How many ways are there to select a crew of six people to go on this mission (assuming that all crew members have the same job)?

 

Solution:

The number of ways to select a crew of six from the pool of 30 people is the number of 6-combinations of a set with 30 elements

C(30, 6) = 30!/ 6! 24! = 30 · 29 · 28 · 27 · 26 · 25 /6 · 5 · 4 · 3 · 2 · 1 = 593,775.

 

EXAMPLE  How many bit strings of length n contain exactly r 1s?

 

Solution:

The positions of r 1s in a bit string of length n form an r-combination of the set {1, 2, 3,...,n}. Hence, there are C(n, r) bit strings of length n that contain exactly r 1s.

 

EXAMPLE :

 Suppose that there are 9 faculty members in the mathematics department and 11 in the computer science department. How many ways are there to select a committee to develop a discrete mathematics course at a school if the committee is to consist of three faculty members from the mathematics department and four from the computer science department?

 

Solution: By the product rule, the answer is the product of the number of 3-combinations of a set with nine elements and the number of 4-combinations of a set with 11 elements. The number of ways to select the committee is

C(9, 3) · C(11, 4) = 9! /3!6! · 11! /4!7!

                                         = 84 · 330

                                            = 27,720.

 

Contributor's Info

Created:
0Comment
Permutations

THEOREM 1 If n is a positive integer and r is an integer with 1 ≤ r ≤ n, then there are
P (n, r) = n(n − 1)(n − 2)···(n − r + 1)
r-permutations of a set with n distinct elements.

 

Note: If n and r are integers with 0 ≤ r ≤ n, then P (n, r) = n!/ (n − r)! .

 

EXAMPLE  How many ways are there to select a first-prize winner, a second-prize winner, and a third-prize winner from 100 different people who have entered a contest?

 

Solution: Because it matters which person wins which prize, So  for first prize we have 100 people now for second prize we havee 99 person left and third placed can be occupied by 98 people

Consequently, the answer is P (100, 3) = 100 · 99 · 98 = 970,200.

 

EXAMPLE  Suppose that there are eight runners in a race. The winner receives a gold medal, the secondplace finisher receives a silver medal, and the third-place finisher receives a bronze medal. How many different ways are there to award these medals, if all possible outcomes of the race can occur and there are no ties?

 

Solution: The number of different ways to award the medals is the number of 3-permutations of a set with eight elements. Hence, there are P (8, 3) = 8 · 7 · 6 = 336 possible ways to award the medals.

    OR 

We can say that we need to choose 3 person out of 8 ,after choosing we can arrange themi.e

C(8,3)*3! = (8!/5!*3!)*3! = P(8,3)

 

EXAMPLE  Suppose that a saleswoman has to visit eight different cities. She must begin her trip in a specified city, but she can visit the other seven cities in any order she wishes. How many possible orders can the saleswoman use when visiting these cities?

 

Solution:the first city is determined, So we have to find permutation for rest  7 cities but the remaining seven can be ordered arbitrarily. Consequently, there are 7! = 7 · 6 · 5 · 4 · 3 · 2 · 1 = 5040 ways for the saleswoman to choose her tour. 

 

EXAMPLE  How many permutations of the letters ABCDEFGH contain the string ABC ?

 

Solution: Because the letters ABC must occur as a block, we can find the answer by finding the number of permutations of six objects, namely, the block ABC and the individual letters D, E, F, G, and H. Because these six objects can occur in any order, there are 6! = 720 permutations of the letters ABCDEFGH in which ABC occurs as a block.

 

Contributor's Info

Created:
0Comment
The Pigeonhole Principle

Theorem: If k is a positive integer and k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.

 

The abstract formulation of the principle: Let X and Y be finite sets and let 

F : X\rightarrowY  be a function then,

 

1) If X has more elements than Y, then f is not one-to-one.

2)If X and Y have the same number of elements and f is onto, then f is one-to-one.

3)If X and Y have the same number of elements and f is one-to-one, then f is onto.

 

Pigeonhole principle is one of the simplest but most useful ideas in mathematics. We will see more applications that proof of this theorem.

 

Example –: A bag contains 10 red marbles, 10 white marbles, and 10 blue marbles. What is the minimum no. of marbles you have to choose randomly from the bag to ensure that we get 4 marbles of same color?

 

Solution: Apply pigeonhole principle.
No. of colors (pigeonholes) n = 3
No. of marbles (pigeons) K+1 = 4
Therefore the minimum no. of marbles required = Kn+1
By simplifying we get Kn+1 = 10.
Verification: ceil[Average] is [Kn+1/n] = 4
[Kn+1/3] = 4
Kn+1 = 10
i.e., 3 red + 3 white + 3 blue + 1(red or white or blue) = 10

 

Pigeonhole principle another form –

Theorem: Let a1, a2, . . . , an be positive integers.
If a1+ a2+ . . . + an – n + 1 objects are put into n boxes, then either the 1st box contains at least a1 objects, or the 2nd box contains at least a2 objects, . . ., the nth box contains at least an objects.
 
Application of this theorem is more important, so let us see how we apply this theorem in problem solving.

Example – 1: In a computer science department, a student club can be formed with either 9 members from first year or 7 members from second year or 6 from third year or 3 from final year. What is the minimum no. of students we have to choose randomly from department to ensure that a student club is formed?

Solution: we can directly apply from the above formula where,
a1 =9, a2 =7, a3 =6, a4 =3 and n=4
Therefore the minimum number of students required to ensure department club to be formed is
9 + 7+ 6 + 3 – 4 + 1 = 22

Contributor's Info

Created:
0Comment
Some property of Eigen Values and Eigen vector
  1. The matrices A and AT have the same eigen values.                                                            we know that,
    (A-λI)=AT-λIT
    ∴ |(A-λI)T|=|AT-λI|                [i.e |AT|=|A|T]
    |A-λI|=|AT-λI|
    ∴ A & AT have same eigen values
  2. '0' is a characteristic root of a matrix if and only if the matrix is singular .i.e |A|=0
  3. The characteristic roots of a triangular matrix are just the diagonal elements of the matrix.
  4. If λ1,λ2...........λn are the eigen values of A ,then  kλ1,kλ2,kλ3......... are eigen values of kA.
  5. If  'A' is non singular, then eigen values of A-1 are the reciprocals of eigen values of 'A'.
  6. If 'λ' is a charactristicroot of matrix 'A' then (k+λ) is a characteristic root of matrix (A+kI).
  7. |A|=\prod ^{n}_{i=1}\lambda _{i}
  8. trace(A)=\sumλi  ,(i=1 to i=n)

Contributor's Info

Created:
0Comment
System of linear non homogeneous equations

Non Homogeneous Equations

a1x+b1y=c1

a2x+b2y=c2

If there is n equation & n unknown you will not find the unique solution always.

eg. x+y=1

       x+y=10 there is no solution for these equation.

Working rule for finding the solution of linear non homogeneous equation (AX=B)

  1. Suppose the coefficient matrix 'A' is of type M*N
  2. Write the augmented matrix [AB] and reduce to echlon form by applying only row transformations.
  3. This echelon form will enable us to know the ranks of the augmented matrix [AB] and the coefficient matrix A. Then the following different cases arise

Case1:  Rank A < Rank [AB] ⇒AX=B is inconsistant   ⇒ No solution

 

Case2: Rank A = Rank [AB]=r(say)

a)  r=n  ⇒ unique solution

b) r<n   ⇒ n-r linearly independnt solution

                ⇒n-r variable will be assigned random values 

                ⇒infinite no of  solutions

Example:

x+y+z=9

2x+5y+7z=52

2x+y-z=0

 

Solution:

[AB] = \begin{bmatrix} 1 & 1 &1 &: & 9\\ 2& 5 &7 & : & 52\\ 2& 1 &-1 & : & 0 \end{bmatrix}

 

R2-->R2-2R1

R3-->R3-2R1

\begin{bmatrix} 1 & 1 &1 &: & 9\\ 0& 3 &5 & : & 34\\ 0& -1 &-3 & : & 18 \end{bmatrix}

R2⇔R3

\begin{bmatrix} 1 & 1 &1 &: & 9\\ 0& -1 &-3 & : & 18\\ 0& 3 &5 & : & 34\\ \end{bmatrix}

 

 

R3-->R3+3R2

\begin{bmatrix} 1 & 1 &1 &: & 9\\ 0& -1 &-3 & : & 18\\ 0& 0 &-4 & : & -20\\ \end{bmatrix}

 

r(A)=r(AB)=3

n=3

n=r

therefor ,unique solution

x+y+z=9

-y-3z=-18

-4z=-20

z=5 , y=3, x=1

Contributor's Info

Created:
0Comment
System of homogeneous linear equation

Homogeneous linear equations:

a11x1 + a12x2 + .................................a1nxn=0

a21x1 + a22x2 +................................a2nxn=0

.

.

.

.

.

am1x1 + am2x2 + ..........................amnxn=0

is a system of m homogeneous equation in 'n' unknown x1,x2,....................xn

Let 

A=  \begin{bmatrix} a11 &a12 &....... &a1n \\ a21&a22 &....... &a2n \\ . &. &. &. \\ am1&am2 &am3 &amn \end{bmatrix}         X=\begin{bmatrix} x1\\ x2\\ .\\ xn \end{bmatrix}           0=\begin{bmatrix} 0\\ 0\\ .\\ 0 \end{bmatrix}

 

then         AX=0

The number of linearly independent solutions of 'm' homogeneous linear equation in 'n' variable ,AX=0 is (n-r)  where'r' is the rank of the matrix 'A'.

 

Conclusion:- 

Case1:if r=n,the equation AX=0 will have n-n i.e no linearly independent solutions.

 

Case2:Ifr<n, we have 'n-r' linearly indpendent solutions. Any linear combination of these 'n-r' solutions willalso be a solution of AX=0

∴infinite no. of solutions possible .

 

Working rule to find solutions of equations AX=0

  1. Reduce the cofficent matrix 'A' to Echelon form by applying row transformation only.
  2. If rank =r ,then it means that in this process of transformatons (m-r) equations are eliminated.
  3. The given system of 'm' equation will thus be replaced by an equivalent system of 'r' equations.
  4. Solving these 'r' equation, we can express the values of some 'r' unknown in terms of the remaining 'n-r' unknowns.
  5. if r=n , the zero solution will be the only solutions
  6. if r<n, there will be infinite no of solutions.

Example:

x+2y+3z=0

3x+4y=4z=0

7x+10y+12z=0

 

Solution:

make a cofficient matrix A from given equations

\begin{bmatrix} 1 & 2 &3 \\ 3& 4 &4 \\ 7&10 &12 \end{bmatrix}

 

we know that,for homogeneous equation to have solution

AX=0

\begin{bmatrix} 1 & 2 &3 \\ 3& 4 &4 \\ 7&10 &12 \end{bmatrix}   \begin{bmatrix} x\\ y\\ z \end{bmatrix}    =\begin{bmatrix} 0\\ 0\\ 0 \end{bmatrix}

 

R2-->R2-3R1

R3-->R3-7R1
\begin{bmatrix} 1 & 2 &3 \\ 0& -2 &-5\\ 0&-4 &-9 \end{bmatrix}   \begin{bmatrix} x\\ y\\ z \end{bmatrix}    =\begin{bmatrix} 0\\ 0\\ 0 \end{bmatrix}

 

now we get  rank 'r' =3 and we know that no of variable is also 3.

therefor n-r=0

thereis no linearly independent solution. The only solution possible is

x=0  y=0 z=0

 

 

Contributor's Info

Created:
0Comment
Adjoint

A=[aij]n*n

B=[Aij]n*n

Adj(A)=BT

 

Theorem:

If A be any n-rowed square matrix, then

(Adj A)A =A(Adj A) =|A|In where Iis n rowed unit matrix

A=\begin{bmatrix} a11&a12 &a13 \\ a21&a22 &a23 \\ a31 &a32 & a33 \end{bmatrix}

 

B=\begin{bmatrix} A11&A12 &A13 \\ A21&A22 &A23 \\ A31 &A32 & A33 \end{bmatrix}

 

BT=\begin{bmatrix} A11&A21 &A31 \\ A12&A22 &A32 \\ A13 &A23 & A33 \end{bmatrix}

 

 

A*BT=\begin{bmatrix} a11&a12 &a13 \\ a21&a22 &a23 \\ a31 &a32 & a33 \end{bmatrix}*\begin{bmatrix} A11&A21 &A31 \\ A12&A22 &A32 \\ A13 &A23 & A33 \end{bmatrix}

      

    =     \begin{bmatrix} |A|&0 &0 \\ 0&|A| &0 \\ 0 &0 & |A| \end{bmatrix}

 

 =|A|\begin{bmatrix} 1&0 &0 \\ 0&1 &0 \\ 0 &0 & 1 \end{bmatrix}

 

 

  1. If |A|≠0 then 'A' will be invertible ,since A is invertable there exist B such that                                AB=In   where B is inverse of A then,                                                               B=adjA/|A|
  2. If 'A' be a square matrix ,then adjAT=(adjA)T
  3. |adj A|=|A|n-1
  4. |adj(adjA)| =|A|(n-1)2
  5. adj(adjA) =|A|n-2A
  6. If A and B are square matrices of some order then                                                            adj (AB)=(adj B)(adj A)

Contributor's Info

Created:
0Comment
Cramer's rule

System of non homogeneous Linear equations(Cramer's rule)

 

ax+by+cz=0----homogeneous

ax+by+cz+d=0--------------------non homogeneous

 

Let 'n ' linear simultaneous equation in 'n' unknown x1,x2,x3............xn be

a11x1+a12x2+......................................a1nxn=b1

a21x1+a22x2+......................................a2nxn=b2

.

.

.

.

.

an1x1+an2x2+......................................annxn=bn

 

let Δ= \begin{vmatrix} a11&a12 &......a1n & \\ a21 &a22 & ......a2n& \\ .& .& &. \\ an1&an2 &ann & \end{vmatrix}    ≠0

 

suppose A11,A12 ,A13...................etc denotes the cofactors of a11, a12,a13.............. multiply given equation respectively by A11, A21, ................An1and we get 

 

A11(a11x1+a12x2+......................................a1nxn=b1)

A21(a21x1+a22x2+......................................a2nxn=b2)

.

.

.

.

.

An1(an1x1+an2x2+......................................annxn=bn)

 

that is,

         x1(a11A11+ a21A21+......................an1An1​) + x2(0)+x3(0)                            =b1A11+b2A21+..............bnAn1

⇒x1Δ=Δ1

x1=Δ1/Δ

where  Δ1 isobtained by replacing elements in the first column of  Δ bythe elements b1,b2...................bn

Similarly,

we get x2=Δ2/Δ

.

.

.

.

.xn=Δ2/Δ

 

Example:

solve by Cramer's rule

x+2y+3z=6

2x+4y+z=7

3x+2y+9z=14

 

 

solution

we have to first find the values of Δ i.e cofficent of x ,y,z

Δ=\begin{vmatrix} 6&2 &3& \\ 7 &4 & 1& \\ 14& 2& 9&\\ & \end{vmatrix}\begin{vmatrix} 1&2 &3& \\ 2 &4 & 1& \\ 3& 2& 9&\\ & \end{vmatrix}

 

Δ=-20

 

Δ1\begin{vmatrix} 6&2 &3& \\ 7 &4 & 1& \\ 14& 2& 9&\\ & \end{vmatrix}

=-20

x1

= -20/-20

=1

 

 

Δ2=\begin{vmatrix} 1&6 &3& \\ 2 &7 & 1& \\ 3& 14& 9&\\ & \end{vmatrix}

=-20

y=Δ2

=-20/-20

=1

similarly

Δ3=\begin{vmatrix} 1&2 &6& \\ 2 &4 & 7& \\ 3& 2& 14&\\ & \end{vmatrix}

=-20

z=Δ3/Δ

=1

 

Contributor's Info

Created:
0Comment
Perfect matching

 

 

Example:

find the no of perfect match in K6

 

Sol:

n=3

=6!/23*3!

=6*5*4/8

=15

Contributor's Info

Created:
0Comment
Distance Between Vertices and Connected Components of Graphs

 

If there is walk (and  hence a path from u to vin given graph G).

Let 

dG(u,v)= min { k  | u --- k-->v} be the distance between u and v.

 Disconnected

dG(u,v) =∞ by convention ,when thereis no walk

 

Note: A graph G is connected if dG(u,v) <∞ for all u,v∈G and disconnected otherwise.

The maximal connected sub graphs of G areits connected components

     c(G)=# of connected component of G

here c(G) is 2.

 

what maximality condition mean is ?

Maximality condition means that a sub graph H ⊆ G is a connected sub graph and for any w ∈ V(G) w ∉ H

then G[V(H) ∪{w}] is disconnected.

Contributor's Info

Created:
0Comment

Pages

Computer Science

ENGINEERING MATHEMATICS
Discrete Mathematics: Propositional and first order logic. Sets, relations, functions, partial orders and lattices. Groups. Graphs: connectivity, matching, coloring. Combinatorics: counting, recurrence relations, generating functions.
Linear Algebra: Matrices, determinants, system of linear equations, eigenvalues and eigenvectors, LU decomposition.
Calculus: Limits, continuity and differentiability. Maxima and minima. Mean value theorem. Integration.
Probability: Random variables. Uniform, normal, exponential, poisson and binomial distributions. Mean, median, mode and standard deviation. Conditional probability and Bayes theorem.
COMPUTER SCIENCE AND INFORMATION TECHNOLOGY
Digital Logic: Boolean algebra. Combinational and sequential circuits. Minimization. Number representations and computer arithmetic (fixed and floating point).
Computer Organization and Architecture: Machine instructions and addressing modes. ALU, data‐path and control unit. Instruction pipelining. Memory hierarchy: cache, main memory and secondary storage; I/O interface (interrupt and DMA mode).
Programming and Data Structures: Programming in C. Recursion. Arrays, stacks, queues, linked lists, trees, binary search trees, binary heaps, graphs.
Algorithms: Searching, sorting, hashing. Asymptotic worst case time and space complexity. Algorithm design techniques: greedy, dynamic programming and divide‐and‐conquer. Graph search, minimum spanning trees, shortest paths.
Theory of Computation: Regular expressions and finite automata. Context-free grammars and push-down automata. Regular and contex-free languages, pumping lemma. Turing machines and undecidability.
Compiler Design: Lexical analysis, parsing, syntax-directed translation. Runtime environments. Intermediate code generation.
Operating System: Processes, threads, inter‐process communication, concurrency and synchronization. Deadlock. CPU scheduling. Memory management and virtual memory. File systems.
Databases: ER‐model. Relational model: relational algebra, tuple calculus, SQL. Integrity constraints, normal forms. File organization, indexing (e.g., B and B+ trees). Transactions and concurrency control.
Computer Networks: Concept of layering. LAN technologies (Ethernet). Flow and error control techniques, switching. IPv4/IPv6, routers and routing algorithms (distance vector, link state). TCP/UDP and sockets, congestion control. Application layer protocols (DNS, SMTP, POP, FTP, HTTP). Basics of Wi-Fi. Network security: authentication, basics of public key and private key cryptography, digital signatures and certificates, firewalls.

You are not authorized to access this content.