UNIT-III

Algebraic structures

Algebraic systems:

An algebraic system, loosely speaking, is a set, together with some operations on the set. Before
formally defining what an algebraic system is, let us recall that a n -ary operation (or operator)
on a set A is a function whose domain is An and whose range is a subset of A . Here, n is a non-
negative integer. When n=0 , the operation is usually called a nullary operation, or a constant,
since one element of A is singled out to be the (sole) value of this operation. A finitary operation
on A is just an n -ary operation for some non-negative integer n .

Definition. An algebraic system is an ordered pair (A O) , where A is a set, called the

underlying set of the algebraic system, and O is a set, called the operator set, of finitary
operations on A .

We usually write A , instead of (A O) , for brevity.

A prototypical example of an algebraic system is a group, which consists of the underlying set G
, and a set O consisting of three operators: a constant e called the multiplicative identity, a unary
operator called the multiplicative inverse, and a binary operator called the multiplication.

For a more comprehensive listing of examples, please see this entry.

Remarks.

 An algebraic system is also called algebra for short. Some authors require that A be non-empty.

Note that A is automatically non-empty if O contains constants. A finite algebra is an algebra

whose underlying set is finite.
 By definition, all operators in an algebraic system are finitary. If we allow O to contain infinitary
operations, we have an infinitary algebraic system. Other generalizations are possible. For
example, if the operations are allowed to be multivalued, the algebra is said to be a multialgebra.
If the operations are not everywhere defined, we get a partial algebra. Finally, if more than one
underlying set is involved, then the algebra is said to be many-sorted.

The study of algebraic systems is called the theory of universal algebra. The first important thing
in studying algebraic system is to compare systems that are of the same ``type''. Two algebras are
said to have the same type if there is a one-to-one correspondence between their operator sets
such that an n -ary operator in one algebra is mapped to an n -ary operator in the other algebra.
Examples:

Some recurring universes: N=natural numbers; Z=integers; Q=rational numbers;

R=real numbers; C=complex numbers.

N is a pointed unary system, and under addition and multiplication, is both the standard
interpretation of Peano arithmetic and a commutative semiring.

Boolean algebras are at once semigroups, lattices, and rings. They would even be abelian
groups if the identity and inverse elements were identical instead of complements.

Group-like structures

 Nonzero N under addition (+) is a magma.

 N under addition is a magma with an identity.
 Z under subtraction (−) is a quasigroup.
 Nonzero Q under division (÷) is a quasigroup.
−1
 Every group is a loop, because a * x = b if and only if x = a * b, and y * a = b if
−1
and only if y = b * a .
2x2 matrices(of non-zero determinant) with matrix multiplication form a group.
Z under addition (+) is an abelian group.
 Nonzero Q under multiplication (×) is an abelian group.
m n m+n n+m
Every cyclic group G is abelian, because if x, y are in G, then xy = a a = a =a =
n m
a a = yx. In particular, Z is an abelian group under addition, as is the integers modulo n
Z/nZ.
A monoid is a category with a single object, in which case the composition of
morphisms and the identity morphism interpret monoid multiplication and identity
element, respectively.
The Boolean algebra 2 is a boundary algebra.

General Properties:

Property of Closure

If we take two real numbers and multiply them together, we get another real number. (The real
numbers are all the rational numbers and all the irrational numbers.) Because this is always true,
we say that the real numbers are "closed under the operation of multiplication": there is no way
to escape the set. When you combine any two elements of the set, the result is also included in
theset.
Real numbers are also closed under addition and subtraction. They are not closed under the
square root operation, because the square root of -1 is not a real number.

Inverse

The inverse of something is that thing turned inside out or upside down. The inverse of an
operation undoes the operation: division undoes multiplication.

A number's additive inverse is another number that you can add to the original number to get the
additive identity. For example, the additive inverse of 67 is -67, because 67 + -67 = 0, the
additive identity.

Similarly, if the product of two numbers is the multiplicative identity, the numbers are
multiplicative inverses. Since 6 * 1/6 = 1 (the multiplicative identity), the multiplicative inverse
of 6 is 1/6.

Zero does not have a multiplicative inverse, since no matter what you multiply it by, the answer
is always 0, not 1.

Equality

The equals sign in an equation is like a scale: both sides, left and right, must be the same in order
for the scale to stay in balance and the equation to be true.

The addition property of equality says that if a = b, then a + c = b + c: if you add the same
number to (or subtract the same number from) both sides of an equation, the equation continues
to be true.

The multiplication property of equality says that if a = b, then a * c = b * c: if you multiply (or
divide) by the same number on both sides of an equation, the equation continues to be true.

The reflexive property of equality just says that a = a: anything is congruent to itself: the equals
sign is like a mirror, and the image it "reflects" is the same as the original.

The symmetric property of equality says that if a = b, then b = a.

The transitive property of equality says that if a = b and b = c, then a = c.

Semi groups and monoids:

In the previous section, we have seen several algebraic system with binary operations.
Here we consider an algebraic system consisting of a set and an associative binary operation on
the set and then the algebraic system which possess an associative property with an identity
element. These algebraic systems are called semigroups and monoids.

Semi group
Let S be a nonempty set and let * be a binary operation on S. The algebraic system (S, *) is
called a semi-group if * is associative
if a * (b*c) = (a * b) * c for all a, b, c Î S.

Example The N of natural numbers is a semi-group under the operation of usual addition of
numbers.

Monoids
Let M be a nonempty set with a binary operation * defined on it. Then (M, * ) is called a
monoid if

 * is associative

(i.e) a * (b * c) = (a * b) * c for all a, b, c Î M and

there exists an element e in M such that

a * e = e * a = a for all a Î M
e is called the identity element in (M,*).

It is easy to prove that the identity element is unique. From the definition it follows that (M,*) is
a semigroup with identity.

Example1 Let S be a nonempty set and r(S) be its power set. The algebras (r(S),U) and (r(S), Ç )
are monoids with the identities f and S respectively.

Example2 Let N be the set of natural numbers, then (N,+), (N, X) are monoids with the
identities 0 and 1 respectively.

Groups Sub Groups:

Recalling that an algebraic system (S, *) is a semigroup if the binary operation * is associative. If
there exists an identity element e Î S, then (S,*) is monoid. A further condition is imposed on the
elements of the monoid, i.e., the existence of an inverse for each element of S then the algebraic
system is called a group.
Definition
Let G be a nonempty set, with a binary operation * defined on it. Then the algebraic system
(G,*) is called a group if
 * is associative i.e. a * (b * c) = (a * b) * c for all a, b, c,Î G.
 there exists an element e in G such that a * e = e * a = a for all a Î G
 for each a Î G there is an element denoted by a-1 in G such that

a * a-1 = a-1 * a = e, a-1 is called the inverse of a.

From the definition it follows that (G,*) is a monoid in which each element has an inverse w.r.t.
* in G.

A group (G,*) in which * is commutative is called an abelian group or a commutative

group. If * is not commutative then (G,*) is called a non-abelian group or non-commutative
group.

The order of a group (G,*) is the number of elements of G, when G is finite and is denoted
by o(G) or |G|

Examples 1. (Z5, +5) is an abelian group of order 5.

2. G = {1, -1, i, -i} is an abelian group with the binary operation x is defined
as 1 x 1 = 1, -1 x -1 = 1, i x i = -1 , -i x -i = 1, …

Homomorphism of semigroups and monoids

Semigroup homomorphism.

Let (S, *) and (T, D) be any two semigroups. A mapping g: S ® T such that any
two elements a, b Î S , g(a * b) = g(a) D g(b) is called a semigroup homomorphism.

Monoid homomorphism
Let (M, *,eM) and (T, D,eT) be any two monoids. A mapping g: M® T such that any
two elements a, b Î M ,
g(a * b) = g(a) D g(b) and
g(eM) = eT
is called a monoid homomorphism.

Theorem 1 Let (s, *) , (T, D) and (V, Å) be semigroups. A mapping g: S ® T and

h: T ® V be semigroup homomorphisms. Then (hog): S ® V is a
semigroup homomorphism from (S,*) to(V,Å ).
Proof. Let a, b Î S. Then
(h o g)(a * b) = h(g(a* b))
= h(g(a) D g(b))
= h(g(a)) Å h(g(b))
= (h o g)(a) Å (h o g)(b)

Theorem 2 Let (s,*) be a given semigroup. There exists a homomorphism g: S ® SS,

where (SS, o) is a semigroup of function from S to S under the operation of
composition.

Proof For any element a Î S, let g(a) = fa where f aÎ SS and f a is defined by

f a(b) = a * b for any a, bÎ S
g(a * b) = f a*b
Now f a*b(c ) = (a * b) * c = a*(b * c)
where = f a(f b(c )) = (f a o f b) (c ).
Therefore, g(a * b) = f a*b = f a o f b = g(a) o g(b), this shows that g: S ® SS is a
homomorphism.

Theorem 3 For any commutative monoid (M, *),the set of idempotent elements of M forms a
submonoid.

Proof. Let S be the set of idempotent elements of M.

Since the identity element e Î M is idempotent, e Î S.
Let a, b Î S, so that a* a = a and b * b = b
Now (a * b ) * (a * b) = (a * b) * (b * a) [( M, *) is a commutative monoid ]
= a * (b * b) * a
=a*b*a
=a*a*b
=a*b

Hence a * b Î S and (S, *) is a submonoid.

Isomorphism:
−1
In abstract algebra, an isomorphism is a bijective map f such that both f and its inverse f are
homomorphisms, i.e., structure-preserving mappings. In the more general setting of category
theory, an isomorphism is a morphism f: X → Y in a category for which there exists an "inverse"
−1 −1 −1
f : Y → X, with the property that both f f = idX and f f = idY.

Informally, an isomorphism is a kind of mapping between objects, which shows a relationship

between two properties or operations. If there exists an isomorphism between two structures, we
call the two structures isomorphic. In a certain sense, isomorphic structures are structurally
identical, if you choose to ignore finer-grained differences that may arise from how they are
defined.

Purpose:

Isomorphisms are studied in mathematics in order to extend insights from one phenomenon to
others: if two objects are isomorphic, then any property which is preserved by an isomorphism
and which is true of one of the objects, is also true of the other. If an isomorphism can be found
from a relatively unknown part of mathematics into some well studied division of mathematics,
where many theorems are already proved, and many methods are already available to find
answers, then the function can be used to map whole problems out of unfamiliar territory over to
"solid ground" where the problem is easier to understand and work with.
 Elementary Combinatorics
Basis of counting:
If X is a set, let us use |X| to denote the number of elements in X.

Two Basic Counting Principles

Two elementary principles act as “building blocks” for all counting problems. The
first principle says that the whole is the sum of its parts; it is at once immediate and elementary.

Sum Rule: The principle of disjunctive counting :

If a set X is the union of disjoint nonempty subsets S1, ….., Sn, then | X | = | S1 | + | S2 | + ….. +
| Sn |.

We emphasize that the subsets S1, S2, …., Sn must have no elements in common.
Moreover, since X = S1 U S2 U ……U Sn, each element of X is in exactly one of the subsets
Si. In other words, S1, S2, …., Sn is a partition of X.

If the subsets S1, S2, …., Sn were allowed to overlap, then a more profound
principle will be needed--the principle of inclusion and exclusion.
Frequently, instead of asking for the number of elements in a set perse, some
problems ask for how many ways a certain event can happen.
The difference is largely in semantics, for if A is an event, we can let X be the set of ways
that A can happen and count the number of elements in X. Nevertheless, let us state the sum rule
for counting events.
If E1, ……, En are mutually exclusive events, and E1 can happen e1 ways, E2 happen e2

ways,…. ,En can happen en ways, E1 or E2 or …. or En can happen e1 + e2 + …….. + en ways.

Again we emphasize that mutually exclusive events E1 and E2 mean that E1 or E2 can
happen but both cannot happen simultaneously.
The sum rule can also be formulated in terms of choices: If an object can be selected from
a reservoir in e1 ways and an object can be selected from a separate reservoir in e2 ways and an
object can be selected from a separate reservoir in e2 ways, then the selection of one
object from either one reservoir or the other can be made
in e1 + e2 ways.

Product Rule: The principle of sequencing counting

If S1, ….., Sn are nonempty sets, then the number of elements in the Cartesian product
S1 x S2 x ….. x Sn is the product ∏in=1 |S i |. That is,
| S1 x S2 x . . . . . . . x Sn | = ∏in=1| S i |.

Observe that there are 5 branches in the first stage corresponding to the 5 elements of S1
and to each of these branches there are 3 branches in the second stage corresponding to the 3
elements of S2 giving a total of 15 branches altogether. Moreover, the Cartesian product S1 x S2
can be partitioned as (a1 x S2) U (a2 x S2) U (a3 x S2) U (a4 x S2) U (a5 x S2), where (ai x S2)
= {( ai, b1), ( ai i, b2), ( ai, b3)}. Thus, for example, (a3 x S2) corresponds to the third branch in
the first stage followed by each of the 3 branches in the second stage.

More generally, if a1,….., an are the n distinct elements of S1 and b1,….,bm are the m
distinct elements of S2, then S1 x S2 = Uin =1 (ai x S2).
For if x is an arbitrary element of S1 x S2 , then x = (a, b) where a Î S1 and b Î S2.
Thus, a = ai for some i and b = bj for some j. Thus, x = (ai, bj) Î(ai x S2) and
therefore x Î Uni =1(ai x S2).
Conversely, if x Î Uin =1(ai x S2), then x Î (ai x S2) for some i and thus x = (ai, bj) where bj
is some element of S2. Therefore, x Î S1 x S2.

Next observe that (ai x S2) and (aj x S2) are disjoint if i ≠ j since if
x Î (ai x S2) ∩ (aj x S2) then x = ( ai, bk) for some k and x = (aj, b1) for some l.
But then (ai, bk) = (aj, bl) implies that ai = aj and bk = bl. But since i ≠ j , ai ≠ a j.
Thus, we conclude that S1 x S2 is the disjoint union of the sets (ai x S2). Furthermore |ai x
S2| = |S2| since there is obviously a one-to-one correspondence between the sets ai x S2 and
S2, namely, (ai, bj) → bj.
Then by the sum rule |S1 x S2| = ∑nni=1 | ai x S2|
7.(n summands) |S2| + |S2| +…….+ |S2|
8.n |S2|
9. nm.
Therefore, we have proven the product rule for two sets. The general rule follows by
mathematical induction.
We can reformulate the product rule in terms of events. If events E1, E2 , …., En can
happen e1, e2,…., and en ways, respectively, then the sequence of events E1 first, followed by
E2,…., followed by En can happen e1e2 …en ways.
In terms of choices, the product rule is stated thus: If a first object can be chosen e1
ways, a second e2 ways , …, and an nth object can be made in e1e2….en ways.

Combinations & Permutations:

Definition.

A combination of n objects taken r at a time (called an r-combination of n objects) is

an unordered selection of r of the objects.
A permutation of n objects taken r at a time (also called an r-permutation of n objects)
is an ordered selection or arrangement of r of the objects.
Note that we are simply defining the terms r-combinations and r-permutations here
and have not mentioned anything about the properties of the n objects.
For example, these definitions say nothing about whether or not a given element may
appear more than once in the list of n objects.
In other words, it may be that the n objects do not constitute a set in the normal usage of the
word.

SOLVED PROBLEMS

Example1. Suppose that the 5 objects from which selections are to be made are: a, a, a, b, c.
then the 3-combinations of these 5 objects are : aaa, aab, aac, abc. The permutations are:
 aaa, aab, aba, baa, aac, aca, caa,
abc, acb, bac, bca, cab, cba.
Neither do these definitions say anything about any rules governing the selection of the r-
objects: on one extreme, objects could be chosen where all repetition is forbidden, or on the other
extreme, each object may be chosen up to t times, or then again may be some rule of selection
between these extremes; for instance, the rule that would allow a given object to be repeated up
to a certain specified number of times.
We will use expressions like {3 . a , 2. b ,5.c} to indicate either
(1) that we have 3 + 2 + 5 =10 objects including 3a’s , 2b’s and 5c’s, or (2) that we have 3
objects a, b, c, where selections are constrained by the conditions that a can be selected at most
three times, b can be selected at most twice, and c can be chosen up to five times.
The numbers 3, 2 and 5 in this example will be called repetition numbers.

Example 2 The 3-combinations of {3. a, 2. b, 5. c} are:

aaa, aab, aac, abb, abc,

ccc, ccb, cca, cbb.

Example 3. The 3-combinations of {3 . a, 2. b, 2. c , 1. d} are:

aaa, aab, aac, aad, bba, bbc, bbd,

cca, ccb, ccd, abc, abd, acd, bcd.

In order to include the case where there is no limit on the number of times an object
can be repeated in a selection (except that imposed by the size of the selection) we use the symbol ∞
as a repetition number to mean that an object can occur an infinite number of times.

Example 4. The 3-combinations of {∞. a, 2.b, ∞.c} are the same as in Example 2 even
though a and c can be repeated an infinite number of times. This is because, in 3-combinations,
3 is the limit on the number of objects to be chosen.

If we are considering selections where each object has ∞ as its repetition number then
we designate such selections as selections with unlimited repetitions. In particular, a selection of
r objects in this case will be called r-combinations with unlimited repetitions and any ordered
arrangement of these r objects will be an r-permutation with unlimited repetitions.
Example5 The combinations of a ,b, c, d with unlimited repetitions are the 3-combinations of
{∞ . a , ∞. b, ∞. c, ∞. d}. These are 20 such 3-combinations, namely:
aaa, aab, aac, aad,
bbb, bba, bbc, bbd,
ccc, cca, ccb, ccd,
ddd, dda, ddb, ddc,
abc, abd, acd, bcd.
Moreover, there are 43 = 64 of 3-permutations with unlimited repetitions since the first position
can be filled 4 ways (with a, b, c, or d), the second position can be filled 4 ways, and likewise for
the third position.

The 2-permutations of {∞. a, ∞. b, ∞. c, ∞. d} do not present such a formidable list

and so we tabulate them in the following table.

2-permutations
2-combinations with Unlimited Repetitions
with Unlimited
Repetitions
aa aa
ab ab, ba
ac ac, ca
ad ad, da
bb bb
bc bc, cb
bd bd, db
cc cc
cd cd, dc
dd dd
10 16

Of course, these are not the only constraints that can be placed on
selections; the possibilities are endless. We list some more examples just for concreteness. We
might, for example, consider selections of {∞.a, ∞. b, ∞. c} where b can be chosen only even
number of times. Thus, 5-combinations with these repetition numbers and this constraint would
be those 5-combinations with unlimited repetitions and where b is chosen 0, 2, or 4 times.
Example6 The 3-combinations of {∞ .a, ∞ .b, 1 .c,1 .d} where b can be chosen only an even
number of times are the 3-combinations of a, b, c, d where a can be chosen up 3 times, b can be
chosen 0 or 2 times, and c and d can be chosen at most once. The 3-cimbinations subject to these
constraints are:
aaa, aac, aad, bbc, bbd, acd.

As another example, we might be interested in, selections of {∞.a, 3.b, 1.c} where a can
be chosen a prime number of times. Thus, the 8-combinations subject to these constraints would
be all those 8-combinations where a can be chosen 2, 3, 5, or 7 times, b can chosen up to 3 times,
and c can be chosen at most once.
There are, as we have said, an infinite variety of constraints one could place on
selections. You can just let your imagination go free in conjuring up different constraints on
the selection, would constitute an r-combination according to our definition. Moreover, any
arrangement of these r objects would constitute an r-permutation.
While there may be an infinite variety of constraints, we are primarily interested in two
major types: one we have already described—combinations and permutations with unlimited
repetitions, the other we now describe.
If the repetition numbers are all 1, then selections of r objects are called r-combinations
without repetitions and arrangements of the r objects are r-permutations without repetitions.
We remind you that r-combinations without repetitions are just subsets of the n elements
containing exactly r elements. Moreover, we shall often drop the repetition number 1 when
considering r-combinations without repetitions. For example, when considering r-combinations
of {a, b, c, d} we will mean that each repetition number is 1 unless otherwise designated, and,
of course, we mean that in a given selection an element need not be chosen at all, but, if it is
chosen, then in this selection this element cannot be chosen again.

Example7. Suppose selections are to be made from the four objects a, b, c, d.

2-combinations 2-Permutations
without Repetitions without Repetitions
ab ab, ba
 ac ac, ca
ad ad, da
bc bc, cb
bd bd, db
cd cd, dc

6 12

There are six 2-combinations without repetitions and to each there are two 2-permutations
giving a total of twelve 2-permutations without repetitions.
Note that total number of 2-combinations with unlimited repetitions in Example 5
included six 2-combinations without repetitions of Example.7 and as well 4 other 2-
combinations where repetitions actually occur. Likewise, the sixteen 2-permutations with
unlimited repetitions included the twelve 2-permutations without repetitions.

3-combinations 3-Permutations
without Repetitions without Repetitions
abc abc, acb, bac, bca, cab, cba

abd abd, adb, bad, bda, dab, dba

acd acd, adc, cad, cda, dac, dca
bcd bcd, bdc, cbd, cdb, dbc, dcb

4 24

Note that to each of the 3-combinations without repetitions there are 6 possible 3-
permutations without repetitions. Momentarily, we will show that this observation can be
generalized.
Combinations And Permutations With Repetitions:
General formulas for enumerating combinations and permutations will now be presented.
At this time, we will only list formulas for combinations and permutations without repetitions or
with unlimited repetitions. We will wait until later to use generating functions to give general
techniques for enumerating combinations where other rules govern the selections.
Let P (n, r) denote the number of r-permutations of n elements without repetitions.

Theorem 5.3.1.( Enumerating r-permutations without repetitions).

P(n, r) = n(n-1)……. (n – r + 1) = n! / (n-r)!

Proof. Since there are n distinct objects, the first position of an r-permutation may be filled in
n ways. This done, the second position can be filled in n-1 ways since no repetitions are
allowed and there are n – 1 objects left to choose from. The third can be filled in n-2 ways. By
applying the product rule, we conduct that

P (n, r) = n(n-1)(n-2)……. (n – r + 1).

From the definition of factorials, it follows that

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

When r = n, this formula becomes

P (n, n) = n! / 0! = n!
When we explicit reference to r is not made, we assume that all the objects are to be
arranged; thus we talk about the permutations of n objects we mean the case r=n.
Corollary 1. There are n! permutations of n distinct objects.

Example 1. There are 3! = 6 permutations of {a, b, c}.

There are 4! = 24 permutations of (a, b, c, d). The number of 2-permutations
{a, b, c, d, e} is P(5, 2) = 5! /
(5 - 2)! = 5 x 4 = 20. The number of 5-letter words using the letters a, b, c, d, and e at most once
is P (5, 5) = 120.
Example 2 There are P (10, 4) = 5,040 4-digit numbers that contain no repeated digits since each
such number is just an arrangement of four of the digits 0, 1, 2, 3 , …., 9 (leading zeroes are
allowed). There are P (26, 3) P(10, 4) license plates formed by 3 distinct letters followed by
4 distinct digits.

Example3. In how many ways can 7 women and 3 men be arranged in a row if the 3 men
must always stand next to each other?

There are 3! ways of arranging the 3 men. Since the 3 men always stand next to each
other, we treat them as a single entity, which we denote by X. Then if W1, W2, ….., W7
represents the women, we next are interested in the number of ways of arranging {X, W1, W2,
W3,……., W7}. There are 8! permutations these 8 objects. Hence there are (3!) (8!)
permutations altogether. (of course, if there has to be a prescribed order of an arrangement on the
3 men then there are only 8! total permutations).

Example4. In how many ways can the letters of the English alphabet be arranged so that there
are exactly 5 letters between the letters a and b?

There are P (24, 5) ways to arrange the 5 letters between a and b, 2 ways to place a and b,
and then 20! ways to arrange any 7-letter word treated as one unit along with the remaining 19
letters. The total is P (24, 5) (20!) (2).

permutations for the objects are being arranged in a line. If instead of arranging objects in a
line, we arrange them in a circle, then the number of permutations decreases.

Example 5. In how many ways can 5 children arrange themselves in a ring?

Solution. Here, the 5 children are not assigned to particular places but are only arranged
relative to one another. Thus, the arrangements (see Figure 2-3) are considered the same if the
children are in the same order clockwise. Hence, the position of child C1 is immaterial and it is
only the position of the 4 other children relative to C1 that counts. Therefore, keeping C1 fixed
in position, there are 4! arrangements of the remaining children.
Binomial Coefficients:In mathematics, the binomial coefficient is the coefficient of the x
k n
term in the polynomial expansion of the binomial power (1 + x) .

In combinatorics, is interpreted as the number of k-element subsets (the k-combinations) of an

n-element set, that is the number of ways that k things can be "chosen" from a set of n things.
Hence, is often read as "n choose k" and is called the choose function of n and k. The
notation was introduced by Andreas von Ettingshausen in 182, although the numbers were
already known centuries before that (see Pascal's triangle). Alternative notations include C(n, k),
n
nCk, Ck, , in all of which the C stands for combinations or choices.

For natural numbers (taken to include 0) n and k, the binomial coefficient can be defined as
k n
the coefficient of the monomial X in the expansion of (1 + X) . The same coefficient also occurs
(if k ≤ n) in the binomial formula

(valid for any elements x,y of a commutative ring), which explains the name "binomial
coefficient".

Another occurrence of this number is in combinatorics, where it gives the number of ways,
disregarding order, that a k objects can be chosen from among n objects; more formally, the
number of k-element subsets (or k-combinations) of an n-element set. This number can be seen to
be equal to the one of the first definition, independently
n of any of the formulas below to compute
it: if in each of the n factors of the power (1 + X) one temporarily labels the term X with an
index i (running from 1 to n), then each subset of k indices gives after expansion a contribution
k
X , and the coefficient of that monomial in the result will be the number of such subsets. This
shows in particular that is a natural number for any natural numbers n and k. There are many
other combinatorial interpretations of binomial coefficients (counting problems for which the
answer is given by a binomial coefficient expression), for instance the number of words formed
of n bits (digits 0 or 1) whose sum is k, but most of these are easily seen to be equivalent to
counting k-combinations.

Several methods exist to compute the value of without actually expanding a binomial power
or counting k-combinations.
Binomial Multinomial theorems:
Binomial theorem:
In elementary algebra, the binomial theorem describes the algebraic expansion of powers of a
n
binomial. According to the theorem, it is possible to expand the power (x + y) into a sum
b c
involving terms of the form ax y , where the coefficient of each term is a positive integer, and
the sum of the exponents of x and y in each term is n. For example,

The coefficients appearing in the binomial expansion are known as binomial coefficients. They
are the same as the entries of Pascal's triangle, and can be determined by a simple formula n−k k
involving factorials. These numbers also arise in combinatorics, where the coefficient of x y
is equal to the number of different combinations of k elements that can be chosen from an n-
element set.

According to the theorem, it is possible to expand any power of x + y into a sum of the form

where denotes the corresponding binomial coefficient. Using summation notation, the
formula above can be written

This formula is sometimes referred to as the Binomial Formula or the Binomial Identity.

A variant of the binomial formula is obtained by substituting 1 for x and x for y, so that
it involves only a single variable. In this form, the formula reads

or equivalently
EXAMPLE

Simplify (x+v(x2-1)) + (x- v(x2-1))6

Solution: let vx2-1 = a, so we have:

(x=a)6 + (x-a)6

= [x6+6C1x5.a+6C2.x4.a2 + 6C3x3a3 + 6C4x2a4 + 6C5xa5 +6C6a6]

[x6-6C1x5a+6C2.x4.a2 – 6C3x3a3 + 6C4x2a4 – 6C5xa5 +6C6a6]

2[x6+6C2x4a2+6C4x2a4+6C6a6]

2[x6+15x4(x2-1)+15x2(x2-1)2+(x2-1)3]

2[x6+15x6-15x4+15x6+15x2-30x4+x6-1-3x4+3x3]

2[32x6-48x4+18x2-1]

Multinomial theorem:

In mathematics, the multinomial theorem says how to write a power of a sum in terms of
powers of the terms in that sum. It is the generalization of the binomial theorem to polynomials.

For any positive integer m and any nonnegative integer n, the multinomial formula tells us how a
polynomial expands when raised to an arbitrary power:

The summation is taken over all sequences of nonnegative integer indices k1 through km such
the sum of all ki is n. That is, for each term in the expansion,0 the exponents must add up to n.
Also, as with the binomial theorem, quantities of the form x that appear are taken to equal 1
(even when x equals zero). Alternatively, this can be written concisely using multiindices as

α α α α
where α = (α1,α2,…,αm) and x = x1 1x2 2⋯xm m.
Example
3 3 3 3 2 2 2 2 2 2
(a + b + c) = a + b + c + 3a b + 3a c + 3b a + 3b c + 3c a + 3c b + 6abc.

We could have calculated each coefficient by first expanding

2 2 2 2 3
(a + b + c) = a + b + c + 2ab + 2bc + 2ac, then self-multiplying it again to get (a + b + c)
(and then if we were raising it to higher powers, we'd multiply it by itself even some more).
However this process is slow, and can be avoided by using the multinomial theorem. The
multinomial theorem "solves" this process by giving us the closed form for any coefficient we
might want. It is possible to "read off" the multinomial coefficients from the terms by using
the multinomial coefficient formula. For example:

2 01
a b c has the coefficient

1 11
a b c has the coefficient .

We could have also had a 'd' variable, or even more variables—hence the multinomial theorem.

The principles of Inclusion – Exclusion:

Let denote the cardinality of set , then it follows immediately that

(1)
where denotes union, and denotes intersection. The more general statement

(2)

also holds, and is known as Boole's inequality.

This formula can be generalized in the following beautiful manner. Let be a p-

system of consisting of sets , ..., , then

where the sums are taken over k-subsets of . This formula holds for infinite sets as well as
finite sets.

The principle of inclusion-exclusion was used by Nicholas Bernoulli to solve the

recontres problem of finding the number of derangements.

For example, for the three subsets , , and

of , the following table summarizes the terms appearing the
sum.
 # term set length
1 2, 3, 7, 9, 10 5
1, 2, 3, 9 4
2, 4, 9, 10 4
2 2, 3, 9 3
2, 9, 10 3
2, 9 2
3 2, 9 2

is therefore equal to, corresponding to the seven

elements .

Pigeon hole principles and its application:

The statement of the Pigeonhole Principle:

If m pigeons are put into m pigeonholes, there is an empty hole iff there's a hole with more than

one pigeon.

If n > m pigeons are put into m pigeonholes, there's a hole with more than one pigeon.

Example:

Consider a chess board with two of the diagonally opposite corners removed. Is it possible to
cover the board with pieces of domino whose size is exactly two board squares?

Solution

No, it's not possible. Two diagonally opposite squares on a chess board are of the same color.
Therefore, when these are removed, the number of squares of one color exceeds by 2 the number
of squares of another color. However, every piece of domino covers exactly two squares and
these are of different colors. Every placement of domino pieces establishes a 1-1 correspondence
between the set of white squares and the set of black squares. If the two sets have different
number of elements, then, by the Pigeonhole Principle, no 1-1 correspondence between the two
sets is possible.
Generalizations of the pigeonhole principle

A generalized version of this principle states that, if n discrete objects are to be allocated to m
containers, then at least one container must hold no fewer than objects, where is the
ceiling function, denoting the smallest integer larger than or equal to x. Similarly, at least one
container must hold no more than objects, where is the floor function, denoting the
largest integer smaller than or equal to x.

A probabilistic generalization of the pigeonhole principle states that if n pigeons are randomly
put into m pigeonholes with uniform probability 1/m, then at least one pigeonhole will hold more
than one pigeon with probability

where (m)n is the falling factorial m(m − 1)(m − 2)...(m − n + 1). For n = 0 and for n = 1 (and m >
0), that probability is zero; in other words, if there is just one pigeon, there cannot be a conflict.
For n > m (more pigeons than pigeonholes) it is one, in which case it coincides with the ordinary
pigeonhole principle. But even if the number of pigeons does not exceed the number of
pigeonholes (n ≤ m), due to the random nature of the assignment of pigeons to pigeonholes there
is often a substantial chance that clashes will occur. For example, if 2 pigeons are randomly
assigned to 4 pigeonholes, there is a 25% chance that at least one pigeonhole will hold more than
one pigeon; for 5 pigeons and 10 holes, that probability is 69.76%; and for 10 pigeons and 20
holes it is about 93.45%. If the number of holes stays fixed, there is always a greater probability
of a pair when you add more pigeons. This problem is treated at much greater length at birthday
paradox.

A further probabilistic generalisation is that when a real-valued random variable X has a finite
mean E(X), then the probability is nonzero that X is greater than or equal to E(X), and similarly
the probability is nonzero that X is less than or equal to E(X). To see that this implies the
standard pigeonhole principle, take any fixed arrangement of n pigeons into m holes and let X be
the number of pigeons in a hole chosen uniformly at random. The mean of X is n/m, so if there
are more pigeons than holes the mean is greater than one. Therefore, X is sometimes at least 2.

Applications:

The pigeonhole principle arises in computer science. For example, collisions are inevitable in a
hash table because the number of possible keys exceeds the number of indices in the array. No
hashing algorithm, no matter how clever, can avoid these collisions. This principle also proves
that any general-purpose lossless compression algorithm that makes at least one input file
smaller will make some other input file larger. (Otherwise, two files would be compressed to the
same smaller file and restoring them would be ambiguous.)

A notable problem in mathematical analysis is, for a fixed irrational number a, to show that the
set {[na]: n is an integer} of fractional parts is dense in [0, 1]. After a moment's thought, one
finds that it is not easy to explicitly find integers , such that | − | < , where > 0 is a n m ∈ na m e e

small positive number and a is some arbitrary irrational number. But if one takes M such that
1/M < e, by the pigeonhole principle there must be n1, n2 {1, 2, ..., M + 1} such that n1a and n2a
are in the same integer subdivision of size 1/M (there are only M such subdivisions between
consecutive integers). In particular, we can find n1, n2 such that n1a is in (p + k/M, p + (k + 1)/M),
and n2a is in (q + k/M, q + (k + 1)/M), for some p, q integers and k in {0, 1, ..., M − 1}. We can
then easily verify that (n2 − n1)a is in (q − p − 1/M, q − p + 1/M). This implies that [na] < 1/M <
e, where n = n2 − n1 or n = n1 − n2. This shows that 0 is a limit point of {[na]}. We can then use
this fact to prove the case for p in (0, 1]: find n such that [na] < 1/M < e; then if p (0, 1/M], we p j M j M k rN r na j M},one ob tains

are done. Otherwise in ( / , ( + 1)/ ], and by setting = sup{ : [ ]< / ∈

∈
|[(k + 1)na] − p| < 1/M < e.