THE DISCRETE MATHEMATICS

DISCRETE MATHEMATICS
Problem 1
Assume X={1,2,3,4} be a set containing four corners of the 4x4 grid.
Let C be a constituents of two colors ,that is,5blue and 4 red square balls.
Let C4 be a set of of 4-tupples of colors.
If x∈C4 then x=(c1,c2,c3,c4) whereby c1,c2,c3,c4 are each of the two colors.
Consider a 4x4 grid to be seated on a plane.
⫪ 1 2 3 4
1
2
3
4
But because the 4 X 4 grid is of two dimensions, you can only move it through rotation.
Suppose that r is the permutation in S4,that is associated with a rotation of 900 in the clock-wise or anti-
clockwise direction.
You will realize that the rotation of the grid is on four coners i.e 1,2,3,4.
And the presentation of S4 can be expressed as a circular notation of of:
r =(1,2,3,4)
r2 =(1,3)(2,4)
r3 =(1,4)(2,1)
Let G=<r> and assume that it acts on X.
|G|=|<r>|=4
You can view the coloring of the corners of a 4 X 4 grid as (2,G)-coloring of X because G acts on X.
By proposition of 2.2,G acts on C which is the set of all the 4-tupples of colors.
The orbit of (c1,c2,c3,c4) ∈C4 do corresponds to 4 different ways of viewing the 4x4 grid.
From the theorem, we can obtain the number of ways on to which any of the four corners can be
colored.

N= 1
4 [|Fix(1)| +|Fix(r)| +|Fix(r2)| +|Fix(r3)|]
You will realize that the identity permutations (1) fixes every x ∈C4,and therefore |Fix(1)|=24 because
any of the corners can be any of the two colors.
Suppose x=(c1,c2,c3,c4) is fixed by r,,then C1=C3=c1 ,then two choices of colors i.e c1,,c3 are bounded in
such a way that c3 is bounded to c1 and c1 bounded to c3 in such a way that c1,c2,c3 and c3 have only one
choice of color each.
|Fix(r) |=22 which is the same as |Fix(r3)|=22 because r3 =rr-1 hence |Fix(r3)| =|Fix(r)|=22
|Fix(r2)|=21
Consider the 4x 4 Grid
The total number of black and red colors are as given;
4x4(1*1) + 4(2*2) + 1(3*3) + 1(4*4)
=16 + 4 + 1 +1
=22
5 x 5 Grid
Assume X={1,2,3,4 ,5} be a set containing five corners of the 5x5 grid.
Let C be a constituents of two colors ,that is,5blue and 4 red square balls.
Let C5 be a set of of 5-tupples of colors.
If x∈C5 then x=(c1,c2,c3,c4, c5) whereby c1,c2,c3,c4 ,c5 are each of the two colors.
⫪ 1 2 3 4 5
1
2
3
4
5
But because the 4 X 4 grid is of two dimensions, you can only move it through rotation.

Suppose that r is the permutation in S4,that is associated with a rotation of 720 in the clock-wise or anti-
clockwise direction.
You will realize that the rotation of the grid is on four coners i.e 1,2,3,4,5
And the presentation of S4 can be expressed as a circular notation of of:
r =(1,2,3,4,5)
r2 =(1,3)(2,4,)(5,1)
r3 =(1,4)(2,5)(3,1)
r4 =(1,5)(2,1)(3,2)
Let G=<r> and assume that it acts on X.
|G|=|<r>|=5
You can view the coloring of the corners of a 5 X 5 grid as (2,G)-coloring of X because G acts on X.
By proposition of 2.2,G acts on C which is the set of all the 4-tupples of colors.
The orbit of (c1,c2,c3,c4,,c5) ∈C5 do corresponds to 4 different ways of viewing the 5x 5grid.
From the theorem, we can obtain the number of ways on to which any of the four corners can be
colored.
N= 1
5 [|Fix(1)| +|Fix(r)| +|Fix(r2)| +|Fix(r3)| +|Fix(r4)]
You will realize that the identity permutations (1) fixes every x ∈C5,and therefore |Fix(1)|=25 because
any of the corners can be any of the two colors.
Suppose x=(c1,c2,c3,c4,c5) is fixed by r,,then C1=C3=c5=c1 ,then two choices of colors i.e c1,,c5 are bounded
in such a way that c5 is bounded to c1 and c5bounded to c3 in such a way that c1,c2,c3,c4 and c3 have only
one choice of color each.
|Fix(r) |=23 which is the same as |Fix(r3)|=23 because r3 =rr-1 hence |Fix(r3)| =|Fix(r)|=22
|Fix(r2)|=22
Consider the grid of size 5x5,

The total number of colored squares are:
5X5(1*1) +6(2*2) + 2(3*3) + 1(4*4) +1(5*5)
=25+6 +2 +1 +1
=35
Problem b
Because n is always smaller than m,you can say that your grid will have atmost squares of size nxn.
Therefore,we can find the sum of the number of squares of different sizes i.e squares of size
{1x1,2x2,3x3,4x4,…..,nxn).
You will realize that the grid of size 1x1 has only one square and the grid of size 1xm has m squares.
Grid of nxn
Generalization of the number of Squares
Assume that the grid is of size nxn,
Number of squares of the grid =nxn(1*1)+(n-1)*(n-1) +(n-2)*(n-2) +…………….+(n-(n-1)*(n-(n-1))
You are to cut the first and the last step because they are fixed.
This implies,Cnk is a disjoint pairs of p and q i.e (p,q) paths.
Hence p is such that p:(0,1)→k-1,n+k-k
q : (1,0) →(k,n-k)
Cnk =|
[ n−1 n−1
k−1 k
n−1 n−1 ]|
= [n−1
k−1 ]2 - [n−1
k ][n−1
k−2 ]

= 1
n [n
k ][ n
k −1 ]
Hence,
Cn =∑
k
Ck n
= 1
n ∑
k [ n
k ][ n
k −1 ]
Problem 2
Assume Munchkin Land is at the origin (0,0).
Dorothy can either moves eastward or westwards of the land. However ,she has decided to maintain
movement on the eastward side.
On the Eastward side ,Dorothy’s movement is controlled by a mirror line (x=y) in such a way that she
cannot move beyond that line.
Steps Covered by Dorothy along the x-axis =|(x+1,y)-(x,y)|
=1 step.
Steps Covered by Dorothy along the y-axis i.e northwards from her original position ;
=|(x+1,y+1)-(x.y+1)|
=1 step
Consider that that the quadrant is a two dimension with only the x and y axis hence a 2 X 2 grid.
⫪ 1 2
1
2
Total Number of steps made by Dorothy on the first quadrant= 1
2[22 +21]

= 1
2[4+2]
=3 steps
REFERENCES
1.Van,J.H & Wilson,R.M.(2009).A course On Combinatorics.Cambridge:Cambridge University Press.
2.Ford,L.R,Fulkerson,D.R.(2010).Flow In Networks.Princeton:Princeton University Press.
3.Bruijn,N.G.(2005).Generalization of Burnside’s lemma and Polya’s theorem, Technical
report.Notitie:Technical University of Eindhoven.
4.Brualdi,R.A.(2008).Introductory Combinatorics.North Holland: Holland Press.
5.Liu,C.L.(2012).Elements of Discrete Mathematics.Tokyo:Ohmsha
6.Oyama,T.(2015).Power-Up Discrete Mathematics.Tokyo:Kyoristsu.