Chapter 14 Cardinality Rules608
(b)How many lengthmwords can be formed from ann-letter alphabet, if letters
can be reused?
(c)How many binary relations are there from setAto setBwhenjAj Dmand
jBjDn?
(d)How many total injective functions are there from setAto setB, wherejAjD
mandjBjDnm?
(e)How many ways are there to place a total ofmdistinguishable balls inton
distinguishable urns, with some urns possibly empty or with several balls?
(f)How many ways are there to place a total ofmindistinguishable balls inton
distinguishable urns, with some urns possibly empty or with several balls?
(g)How many ways are there to put a total ofmdistinguishable balls intondis-
tinguishable urns with at most one ball in each urn?
Exam Problems
Problem 14.35. (a)How many solutions over thepositiveintegers are there to the
inequality:
x 1 Cx 2 C:::Cx 10 100(b)In how many ways can Mr. and Mrs. Grumperson distribute 13 identical
pieces of coal to their three children for Christmas so that each child gets at least
one piece?
Problems for Section 14.8
Practice Problems
Problem 14.36.
Below is a list of properties that a group of people might possess.
For each property, either give the minimum number of people that must be in a
group to ensure that the property holds, or else indicate that the property need not
hold even for arbitrarily large groups of people.
(Assume that every year has exactly 365 days; ignore leap years.)
(a)At least 2 people were born on the same day of the year (ignore year of birth).
(b)At least 2 people were born on January 1.