Page 464 - Discrete Mathematics and Its Applications

Supplementary Exercises 443

45. How many ways are there to distribute six objects to five 52. How many 11-element RNA sequences consist of 4 As,
boxes if 3Cs, 2Us, and 2Gs, and end with CAA?
a) both the objects and boxes are labeled? Exercises 53 and 54 are based on a discussion in [RoTe09].
b) the objects are labeled, but the boxes are unlabeled? A method used in the 1960s for sequencing RNA chains used
c) the objects are unlabeled, but the boxes are labeled? enzymes to break chains after certain links. Some enzymes
d) both the objects and the boxes are unlabeled? break RNA chains after each G link, while others break them
46. How many ways are there to distribute five objects into after each C or U link. Using these enzymes it is sometimes
six boxes if possible to correctly sequence all the bases in an RNA chain.
a) both the objects and boxes are labeled? ∗ 53. Suppose that when an enzyme that breaks RNA chains af-
b) the objects are labeled, but the boxes are unlabeled? ter each G link is applied to a 12-link chain, the fragments
c) the objects are unlabeled, but the boxes are labeled? obtained are G, CCG, AAAG, and UCCG, and when an
d) both the objects and the boxes are unlabeled? enzyme that breaks RNA chains after each C or U link
The signless Stirling number of the first kind c(n, k), is applied, the fragments obtained are C, C, C, C, GGU,
where k and n are integers with 1 ≤ k ≤ n, equals the number and GAAAG. Can you determine the entire 12-link RNA
of ways to arrange n people around k circular tables with at chain from these two sets of fragments? If so, what is this
least one person seated at each table, where two seatings of RNA chain?
m people around a circular table are considered the same if ∗ 54. Suppose that when an enzyme that breaks RNA chains af-
everyone has the same left neighbor and the same right neigh- ter each G link is applied to a 12-link chain, the fragments
bor. obtained are AC, UG, and ACG and when an enzyme that
47. Find these signless Stirling numbers of the first kind. breaks RNA chains after each C or U link is applied,
the fragments obtained are U, GAC, and GAC. Can you
a) c(3,2) b) c(4,2)
determine the entire RNA chain from these two sets of
c) c(4,3) d) c(5,4)
n fragments? If so, what is this RNA chain?
48. Show that if n is a positive integer, then c(n, j) =
j=1
n!. 55. Devise an algorithm for generating all the r-permutations
of a finite set when repetition is allowed.
49. Show that if n is a positive integer with n ≥ 3, then
c(n, n − 2) = (3n − 1)C(n, 3)/4. 56. Devise an algorithm for generating all the r-combinations
of a finite set when repetition is allowed.
∗ 50. Show that if n and k are integers with 1 ≤ k< n, then
c(n + 1,k) = c(n, k − 1) + nc(n, k). ∗ 57. Show that if m and n are integers with m ≥ 3 and n ≥ 3,
n
51. Give a combinatorial proof that 2 divides n! whenever n then R(m, n) ≤ R(m, n − 1) + R(m − 1,n).
is an even positive integer. [Hint: Use Theorem 3 in Sec- ∗ 58. Show that R(3, 4) ≥ 7 by showing that in a group of six
tion 6.5 to count the number of permutations of 2n objects people,whereanytwopeoplearefriendsorenemies,there
where there are two indistinguishable objects of n differ- are not necessarily three mutual friends or four mutual en-
ent types. emies.

Computer Projects

Write programs with these input and output.

1. Given a positive integer n and a nonnegative integer not 5. Given a positive integer n, list all the permutations of the
exceeding n, find the number of r-permutations and r- set {1, 2, 3,...,n} in lexicographic order.
combinations of a set with n elements. 6. Given a positive integer n and a nonnegative integer r
not exceeding n, list all the r-combinations of the set
2. Given positive integers n and r, find the number of
r-permutations when repetition is allowed and r-com- {1, 2, 3,...,n} in lexicographic order.
binations when repetition is allowed of a set with n el- 7. Given a positive integer n and a nonnegative integer r
ements. not exceeding n, list all the r-permutations of the set
{1, 2, 3,...,n} in lexicographic order.
3. Given a sequence of positive integers, find the longest in- 8. Given a positive integer n, list all the combinations of the
creasing and the longest decreasing subsequence of the set {1, 2, 3,...,n}.
sequence.
9. Given positive integers n and r, list all the r-permutations,
∗ 4. Given an equation x 1 + x 2 + ··· + x n = C, where C is a with repetition allowed, of the set {1, 2, 3,...,n}.
constant, and x 1 ,x 2 ,...,x n are nonnegative integers, list 10. Givenpositiveintegersnandr,listallther-combinations,
all the solutions. with repetition allowed, of the set {1, 2, 3,...,n}.