Discrete 3

Question 1

Suppose that a procedure can be broken down into a sequence of two tasks
(task 1 followed by task 2). If there are n1 ways to do the first task and n2 ways to do the second
task following the first task

Answer 1

then there are n1·n2 ways to do the procedure.

Question 2

Suppose that there are n1 ways to do task 1 and n2 ways to do task 2. If
there is no overlap between the two tasks,

Answer 2

then there are n1 + n2 ways to do task 1 or task 2.

Question 3

Suppose that there are n1 ways to do task 1, n2 ways to

do task 2, and k ways to do both.

Answer 3

Then there are n1 + n2 – k ways to do task 1 or task 2.

Question 4

To find the smallest N such that in k boxes there are t guarunteed

Answer 4

N = k (t −1) + 1.

cieling (n/k) = t

Question 5

binomial theorem

Answer 5

sumk=0ton (n/k)x^ky^(n-k)

Question 6

order matters and repeats allowed

Answer 6

n^r

Question 7

order matters and repeats not allowed

Answer 7

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

Question 8

order does not matter and repeats allowed

Answer 8

n-1 bars and r stars

C(n-1+r,r)

Question 9

order doesn’t matter and repeats are not allowed

Answer 9

c(n,r) n!/((n-r)!r!)

Question 10

To solve a recurrence relation of the form 𝑎𝑛 = 𝑐𝑎𝑛−1

Answer 10

𝑎𝑛 = 𝛼(𝑟1)^𝑛

𝑛 ≥ 0. with initial conditions and r = c

Question 11

To solve a recurrence relation of the form 𝑎𝑛 = 𝑐1𝑎𝑛−1 + 𝑐2𝑎𝑛−2

Answer 11

𝑟^2 − 𝑐1𝑟 − 𝑐2 = 0
find r1 and r2.

if r1 != r2
then 𝑎𝑛 = 𝛼(𝑟1)^𝑛 + 𝛽(𝑟2)^𝑛
, 𝑛 ≥ 0

else if r1=r2
𝑎𝑛 = 𝛼(𝑟1)^𝑛 + 𝛽N(𝑟1)^𝑛
, 𝑛 ≥ 0