Chapter 14 Cardinality Rules618
Exam Problems
Problem 14.55.
(a)Letrbe the number of lengthnbinary strings in which 011 occurs starting at
the 4th position. Write a formula forrin terms ofn.
(b)LetAibe the set of lengthnbinary strings in which 011 occurs starting at the
ith position. (SoAiis empty fori > n 2 .) Ifi¤j, the intersectionAi\Ajis
either empty or of sizes. Write a formula forsin terms ofn.
(c)Lettbe the number of intersectionsAi\Ajthat are nonempty, wherei < j.
Write a binomial coefficient fortin terms ofn.
(d)How many length 9 binary strings are there that contain the substring 011?
You should express your answer as an integer or as a simple expression which may
include the constants,r,sandtabove.
Hint:Inclusion-exclusion for
ˇ
ˇ
ˇ
S 7
1 Aiˇ
ˇ
ˇ.
Problem 14.56.
There are 10 studentsA;B;:::;Jwho will be lined up left to right according to
the some rules below.
Rule I: Student A must not be rightmost.
Rule II: Student B must be adjacent to C (directly to the left or right of C).
Rule III: Student D is always second.
You may answer the following questions with a numerical formula that may
involve factorials.
(a)How many possible lineups are there that satisfy all three of these rules?(b)How many possible lineups are there that satisfy at least one of these rules?