From jacob_otto@hotmail.com Thu Jul 12 21:10:08 2001
Date: Fri, 13 Jul 2001 01:01:57
From: Jacob Otto
To: dimitrik@MIT.EDU
Subject: discrete math, PS-7
Discrete Math Problem Set 7
1a) 101 99
99 2 101 = 1*99+2 --> 2 = 101 - 1*99
2 1 99 = 49*2+1 ---> 1 = 99 - 49*2
gcd(99,101) = 1 = 99 - 49*2 = 99 - 49 *(101-1*99) = 99 - 49*101 + 49 *99 =
50*99-49*101
which is also equivalent to 50*101-51*99
(x=50, y=49, u=50, v=51)
1b)
35 10
10 5 35 = 3*10+5 --> 5 = 35 - 3*10
5 0
gcd(10,35) = 5 = 1*35-3*10
which is also equivalent to 32*10-9*35
(u=1, w=3, x=32, y=9)
1c)
12 7
7 5 12=1*7+5 --> 5 = 12 - 1*7
5 2 7=1*5+2 --> 2 =7-1*5
2 1 5=2*2+1 --> 1 = 5 -2*2
gcd(7,12) = 1=5 - 2*2 = 5 - 2*(7-1*5) = 3*5 -2*7 = 3*(12-1*7)-2*7=3*12-5*7
which is also equivalent to 7*7-4*12
(u=3,v=5,x=7,y=4)
1d)
42 36
36 6 42=1*36+6 --> 42-1*36
6 0
gcd(36,42) = 6 = 42-1*36
which is also equivalent to 41*36-35*42
(u=1,v=1,x=41,y=35)
2) See printout
3a)
(1+x+x^2+x^3+x^4)^3
= (1 + 3x + 6x^2 + 10x^3 + 15x^4 + ...)
since the coefficients are those of the 3rd diagonal of Pascal's triangle:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
x^4 has coefficient 15.
3b)
(1+x^2+x^4)^2 * (1+x+x^2)^2
= (1+2x^2+3x^4+2x^6+x^8) * (1 + 2x + 3x^2 + 2x^3 + x^4)
Coefficient of x^4: 1+2*3+3 = 10
3c)
>From a): (1+x+x^2+x^3+x^4+...) = (1+3x+6x^2+10x^3+15x^4+...)
x^4 has coefficient 15
4)
We have to find the number of solutions to:
e(h) + e(e) + e(l) + e(p) = 5
where e(l) <=1, e(p) <=1, e(h) <=5, e(e) <=5
The generating function is:
(1+x)(1+x)(1+x+x^2+x^3+x^4+x^5)(1+x+x^2+x^3+x^4+x^5)
and the answer is the coefficient in fornt of x^5 which is 20.
5)
1/(1-10x+21x^2) = 1/((1-7x)(1-3x)) = A/(1-7x) + B/(1-3x)
Solving for A and B:
A - 3Ax + B - 7Bx = 1
implies
A+B = 1 and 3A=-7B
implies
A=7/4 and B= -3/4
Therefore:
A/(1-7x) + B/(1-3x) = (7/4)/(1-7x) - (3/4)/(1-3x)
Coefficient of x^n = (7/4) * 7^n - (3/4) * 3^n = 7^(n+1)/4 - 3^(n+1)/4
6a)
The distinct divisors for p^a are p^0(=1), p, p^2, p^3, ..., p^a.
Therfore, number of divisors = a+1.
6b)
m = p1^a1*p2^a2*...pn^an where p1, p2, ... are distinct primes.
Then we have a1 + 1 choices for p1, a2 + 1 choices for p2, ....
Therefore, number of distinct divisors = (a1 + 1)(a2 + 1)...(an + 1).
7)
Is the coefficient of x^k in the following expression:
(1+x+x^2+x^3+...)(1+x^5+x^10+x^15+...)(1+x^10+x^20+x^30+...)(1+x^25+x^50+x^75+...)
8a)
(x+x^2+x^3+...+x^10)(1+x^5+x^10+...)(1+x^10+x^20+...)(1+x^25+x^50+...)
Coefficient in front of x^100 = 79.
(got this by using scheme polynomial package from SICP PS-6)
8b)
(x+x^2+x^3+...)(x^5+x^10+...)(x+10+x^20+...)(x^25+x^50+....)
Coefficient of x^100 = 21
(got this by using scheme polynomial package from SICP PS-6)
9) See printout
10) See printout
11a) R is not an equivalence relation since it is not transitive.
11b) RoR means that we have ordered pairs {a,b} where a and b have a common
co-author.
11c) Let R* be the set of ordered pairs {a,b} where a is connected to b via
any number of co-authors.
R* is reflexsive since {a,a} belongs to R* for every author a.
R* is symmetric since {a,b} belongs to R* implies {b,a} belongs to R*
because if we can trace a path of co-authors from a to b, we can re-trace
the path from b to a.
R* is transitive since if both {a,b} and {b,c} belongs to R* then {a,c}
belongs to R* because if we can trace a path from a to b and b to c, we can
also trace a path from a to c.
11d)
Shai: 2
Kenneth Rosen: 3
Greenspun: 4
Ron Graham: 1
Donald Knuth: 2
Tara Holm: 3
_________________________________________________________________________
Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com.