Assignment 1: Discrete Math Problems and Solutions

This assignment solution covers a range of discrete mathematics topics. It begins by finding the multiplicative inverse of several matrices, explaining when an inverse does not exist. The solution then explores combinatorics, calculating the number of ways to rearrange letters with constraints. Generating functions are derived for various sequences. The assignment also includes problems on binomial expansion, finding specific coefficients. Additionally, it addresses a problem involving integer solutions to an equation with constraints. Finally, the assignment delves into automata theory, requiring the design of deterministic machines for specific languages and a Turing machine to compute a given function. The solution provides step-by-step explanations and detailed calculations for each problem.

Assignment
1. For each of the following matrices find the multiplicative inverse, or explain why it
doesn’t have one.
(a) [ 3 5
2 3 ]
Solution: A= [ 3 5
2 3 ]
|A| = 3*3 – 2*5
= 9-10= -1
Minors are
M11 = 3, M12=2, M21=5, M22=3
Co factors of matrix are
C11 = C11
C12 = -C12
C21 = -C21
C22 = C22
Cofactors Matrix [ 3 −2
−5 3 ]
A-1 = 1/|A| * (Cofactor)T
A-1 = 1/-1 * [ 3 −5
−2 3 ]
A-1 = [ −3 5
2 −3 ]
(b) [2 3 6
3 2 4
6 6 9 ]
Solution: A= [2 3 6
3 2 4
6 6 9 ]
|A| = 2*(2*9-6*4)– 3*(3*9-6*4) +6*(3*6-6*2)
= 2*(-6)- 3*(3) +6*(6) = 15
Minors are
M11=-6, M12=3, M13=6,
M21=-9, M22=-18, M23=-6,
M31=0, M32=-10, M33=-2

Cofactors Matrix [−6 −3 6
9 −18 6
0 10 −2 ]
A-1 = 1/|A| * (Cofactor)T
A-1 = 1/15 * [−6 9 0
−3 −18 10
6 6 −2 ]
A-1 = [ −2/5 −3/5 0
−1/5 −6 /5 2/3
2/5 5 /2 −2 /15 ]
(c)
[ 1 2 5 7
0 1 3 6
0 0 1 4
0 0 0 1 ]
Solution: A=
[ 1 2 5 7
0 1 3 6
0 0 1 4
0 0 0 1 ]
|A| = 1*(1*1-3*0-0*4)– 2*(0*0-3*0+6*0) +5*(0*0-1*0+6*0)-7*(0*0-1*0+3*0)
= 1
Minors are
M11=1, M12=0, M13=0, M14=0,
M21=2, M22=1, M23=0, M24=0,
M31=1, M32=3, M33=1, M34=0,
M41=-1, M42=6, M43=4, M44=1,
Cofactors Matrix
[ 1 0 0 0
−2 1 0 0
1 −3 1 0
1 6 −4 1 ]
A-1 = 1/|A| * (Cofactor)T

A-1 = 1/1 *
[ 1 −2 1 1
0 1 −3 6
0 0 1 −4
0 0 0 1 ]
A-1 =
[ 1 −2 1 1
0 1 −3 6
0 0 1 −4
0 0 0 1 ]
2. How many ways can we rearrange the letters a b c d e f g h i j so that no vowel ends
up in the position where it began?
Solution: n=10 (a, b, c, d, e, f, g, h, i, j) Vowels a, e, i (3 vowels)
No. of Ways= 241914
3. Find a closed form for the generating function for each of these sequences.
(a) 7, 3, 4, 6, 7, 3, 4, 6, 7, 3, 4, 6, . . .
Solution:
1 mod 4 = 1
2 mod 4 = 2
3 mod 4 = 3
4 mod 4 = 0
5 mod 4 = 1
6 mod 4 = 2
7 mod 4 = 3
8 mod 4 = 0
And so on…
F (n) =
{
if n mod 4=1, 7
if n mod 4=2 ,3
if n mod 4=3 ,3
if n mod 4=0 ,6 } n E |N
(b) .1, 0.01, 0.001, 0.0001, . . .
Solution:
a2/a1= a3/a2=…… an/an-1= 1/10
a1= 1/10
f(n) = an/an-1= 1/10; n≥2; n E |N; a1=1/10
(c) 2, 5, 8, 11, 14, 17, 20, . . .

Solution:
a2-a1= a3-a2=…… an-an-1= 3
f(n) = an-an-1= 3; n≥2; n E |N; a1=2
(d) 1 * 2 * 3, 2 * 3 * 4, 3 * 4 * 5, 4 * 5 * 6, . . .
Solution:
a2/a1= a3/a2= an/an-1 = (n+2)/(n+1)
f(n)= an/an-1 = (n+2)/(n+1); n≥2; n E |N; a1=6
(e) 11, 101, 1001, 10001, 100001, . . .
Solution:
10+1, 102+1, 103+1…. 10n+1
f(n)= (an-1)/ (an-1-1)=10; n≥2; n E |N; a1=11
4. Find the coefficient of x24 in the expansion of each of the following.
(a) ( 7x3 − 5x4)7
Solution: To calculate (r+1) th term
Tr + 1 = nC r an-r b r = 7C r (7x3)7-r (-5x 4) r
= 7C r (7)7-r (-5) r x3(7-r) x 4r
Consider x21-3r+4r
We need power x24
 21+r = 24
r= 3
T3 + 1 = 7C 3 (7x3)7-3 (-5x 4)3
T4 = 7C 3 74x12 (-5)3x 12
T4 = 7C 3 74 (-5)3x 24

Coefficient of x24= 7C 3 74 (-5)3 = -75 54 = -10504375
(b) (1 − x) −7
Solution: To calculate (r+1) th term
Tr + 1 = nC r an-r b r = -7C r (1)-7-r (-x) r
= -7C r (-x) r
Consider xr
We need power x24
 r = 24
T24 + 1 = -7C 24 (1)-7-24(-x)24
T25 = -7C 24 x24
Coefficient of x24= -7C 24
(c) (1 − 2x + 3x2) (1 − x) −2
Solution: To calculate (r+1) th term
= -2C r (1) (-x) r +-2C r (-x) r (-2x) + (- 2C r (-x) r.(3x)2
=-2C r (-x) r +-2C r (-x) r+1 (-2)- 2C r (-x) r+2. (9)
= -2C r (-x) r +-2C r (-x) r+1 (-2)- 2C r (-x) r+2. (9)
= -2C 24 (-x) 24 + -2C 23 (-x)24 (-2) + -2C 22 (-x) 24. (9)
Coefficient of x24= -2C 24-2*2C 23 +9* 2C 22
5. Consider the equation a+b+c+d+e = 73 in which the variables all represent non-
negative integers.
(a) How many solutions are there with a ≥ 7, b ≤ 23, and 9 ≤ c ≤ 19?
Solution:
a≥7, b≥0, c≥9, d≥0, e≥0
 a-6≥1, a-6 = a1
a= a1+6
similarly, b= b1-1; c= c1+8; d=d1-1; e=e1-1
a+b+c+d+e=73

 a1+6+b1-1+c1+8+d1-1+e1-1=73
=a1+b1+c1+d1+e1= 62
No. of possible solutions for the above equation is 61C4
But, it has solutions with b≤23 and c≤19
 to find solutions with b≥24; c≥20
b-23≥1  b=b1+23 similarly c= c1+19; a=a1-1; d=d1-1; e=e1-1
a+b+c+d+e=73
 a1-1+b1+23+c1+19+d1-1+e1-1=73
=a1+b1+c1+d1+e1= 44
No. of possible solutions for the above equation is 43C4
So total possible solutions with a ≥ 7, b ≤ 23, and 9 ≤ c ≤ 19 is 61C4 -43C4
(b) How many solutions are there in which the variables are all at most 20?
Solution:
Condition 0 ≤ a, b, c, d, e, ≤ 20
consider {a, b, c, d, e ≤ 20}
Implies a= 20-a1; b= 20-b1; c= 20-c1; d=20-d1; e=20-e1
a+b+c+d+e=73
 20-a1+20-b1+20-c1+20-d1+20-e1=73
a1+b1+c1+d1+e1= 27
non-negative integer solutions for the above equation implies a1, b1, c1, d1, e1, cannot be
more than 27 which means a, b, c, d, e, are positive
no. of non- negative solutions to a+b+c+d+e= 73; 0 ≤ a, b, c, d, e, ≤ 20 is the no. of non-
negative integer solutions of a1+b1+c1+d1+e1= 27
a1= a11-1, similarly the other variables
a11+b11+c11+d11+e11= 32
No. of possible solutions for the above equation 31C4

6. The machine on the left below is a deterministic machine that accepts the language
L =( 1100 + 1110) ∗(01 + 10 + 11) ,
while the machine on the right is a deterministic machine that accepts the language,
M consisting of all binary strings in which the number of 1s is divisible by 3.
Create a deterministic machine which accepts the language L’ (all strings except
those in L) and a deterministic machine that accepts the language M’. Next construct
a non-deterministic machine that accepts the language L’ +M’ = (L ∩M)’. Convert this
machine to a deterministic machine, and hence produce a machine that accepts all
strings in the language L ∩M. Comment on any obviously equivalent states - it is not
necessary to do the full minimisation procedure, though you may do so.
7. Design a Turing Machine to construct the function f(n) = 3 [1/3n] + 2, (that is, 2 more
than 3× the integer part of 1/3 n) for n ∈ N. Do not just produce a TM, but also describe
briefly how it works. There is a TM in the Cooper notes that does almost this. Modify it
to produce the required TM.