Chapter 15 Cardinality Rules494
(b)How many nonnegative integer solutions are there for the following equality?x 1 Cx 2 CCxmDk: (15.9)(c)How many nonnegative integer solutions are there for the following inequal-
ity?
x 1 Cx 2 CCxmk: (15.10)
(d)How many length-mweakly increasing sequences of nonnegative integersk
are there?
Homework Problems
Problem 15.12.
In this problem, all graphs will have verticesŒ1;nçWWDf1;2;:::;ng; equivalently,
all binary relations are on this setŒ1;nç.
(a)How many simple undirected graphs are there?(b)How many digraphs are there?(c)How many asymmetric binary relations are there?(d)How many path-total strict partial orders are there?Problem 15.13.
Answer the following questions with a number or a simple formula involving fac-
torials and binomial coefficients. Briefly explain your answers.
(a)How many ways are there to order the 26 letters of the alphabet so that no two
of the vowelsa,e,i,o,uappear consecutively and the last letter in the ordering
is not a vowel?
Hint:Every vowel appears to the left of a consonant.
(b)How many ways are there to order the 26 letters of the alphabet so that there
areat least twoconsonants immediately following each vowel?
(c)In how many different ways can2nstudents be paired up?(d)Twon-digit sequences of digits 0,1,... ,9 are said to be of thesame typeif the
digits of one are a permutation of the digits of the other. FornD 8 , for example,
the sequences 03088929 and 00238899 are the same type. How many types of
n-digit integers are there?