(a2-a1) = (a3-a2) = ... an-an-1 = 3

Read the assignment content very carefully and create a short summary for the provided content in a paragraph.

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.