=========================preview======================
(comp170)[2007](f)midterm1~PPSpider^review_10152.pdf
Back to COMP170 Login to download
======================================================

COMP170 C Fall 2007
Midterm 1 Review


n guests are arranged seats in a row facing the audience
a) How many di.erent ways are there to seat the n guests at n seats?

n guests are arranged seats in a row facing the audience
a) How many di.erent ways are there to seat the n guests at n seats?
n!
Note that the order is important since the guests could be listed from left to right from the audiences perspective

n guests are arranged seats in a row facing the audience

b) Let n> 2. How many ways to seat n guests if two speci.c guests will not sit next to each other?

n guests are arranged seats in a row facing the audience

b) Let n> 2. How many ways to seat n guests if two speci.c guests will not sit next to each other?
# ways not sitting together = n!. # ways sitting together

Question 1 b) Let n > 2. (n . 1)! di.erent ways of seating the guests. # ways sitting together =

n guests are arranged seats in a row facing the audience

How many ways to seat n guests if two speci.c guests will not sit next to each other?
# ways not sitting together = n!. # ways sitting together

Treating the two people as one indivisible group, there are
Within the two-person group, there are 2 ways to sit them.

2(n . 1)! # ways not sitting together = n!.2(n.1)! = (n.2)(n.1)!

n guests are arranged seats in a row facing the audience
c) n> 10. Guests include 5 couples. For each couple,
husband must sit with wife. How many seatings are there?

Question 1 c) n > 10. Treat each couple as an individual groups. For each couple (group), # ways to seat guests =

n guests are arranged seats in a row facing the audience

Guests include 5 couples. For each couple, husband must sit with wife. How many seatings are there? indivisible group, and others as
There are (n . 5)! ways to seat n . 5 groups.

there are 2 ways to seat husband and wife.

25(n . 5)!


Zn = {0, ..., n . 1}
a) How many 5-element subsets of Z10 contain at least one element in Z3?
Question 2 # 5-element sets of Z10 = .10 5 . Zn = {0, ..., n . 1} element in Z3? = .10 5 . .

a) How many 5-element subsets of Z10 contain at least one

# 5-element sets of Z10 not containing elements of Z3 = 57

# 5-element sets of Z10 containing at least one element of Z3

7
5


b) How many 5-element subsets of Z10 contain two odd and three even numbers?
Question 2 three even numbers? Z10 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} .5 2 . .5 3 . By the product principle, we have .5 2 . .5 3

b) How many 5-element subsets of Z10 contain two odd and

ways to choose 2 numbers from {1, 3, 5, 7, 9}
ways to choose 3 numbers from {0, 2, 4, 6, 8}


c) Let n be positive and odd. Show that # of even-sized subsets of Zn equals # of odd-sized subsets of Zn
Question 2 c) Let n be positive and odd. subsets of Zn Let On = {1, 3, .5, ..., n} Since . n k . = . n n.k . , we have . kOn . n k . = . kOn . n En = {0, 2, 4, ..., n . 1} f(k) = n . k de.nes a bijecti