Page 465 - Discrete Mathematics and Its Applications

444 6 / Counting

Computations and Explorations

Use a computational program or programs you have written to do these exercises.

1. Find the number of possible outcomes in a two-team play- 4. Find as many odd integers n less than 200 as you can for
off when the winner is the first team to win 5 out of 9, 6 which C(n,
n/2 ) is not divisible by the square of a prime.
out of 11, 7 out of 13, and 8 out of 15. Formulate a conjecture based on your evidence.
∗ 5. For each integer less than 100 determine whether C(2n, n)
2. Which binomial coefficients are odd? Can you formulate a is divisible by 3. Can you formulate a conjecture that tells
conjecture based on numerical evidence? us for which integers n the binomial coefficient C(2n, n)
is divisible by 3 based on the digits in the base three ex-
3. Verify that C(2n, n) is divisible by the square of a prime, pansion of n?
when n = 1, 2, or 4, for as many positive integers n as 6. Generate all the permutations of a set with eight elements.
you can. [The theorem that tells that C(2n, n) is divisible
7. Generate all the 6-permutations of a set with nine elements.
by the square of a prime with n = 1, 2, or 4 was proved
in 1996 by Andrew Granville and Olivier Ramaré. Their 8. Generate all combinations of a set with eight elements.
proof settled a conjecture made in 1980 by Paul Erd˝os and 9. Generate all 5-combinations with repetition allowed of a
Ron Graham.] set with seven elements.

Writing Projects

Respond to these with essays using outside sources.

1. Describe some of the earliest uses of the pigeonhole prin- Maxwell–Boltzmann, Bose–Einstein, and Fermi–Dirac
ciple by Dirichlet and other mathematicians. statistics. In each case, describe the counting techniques
2. Discuss ways in which the current telephone numbering used in the model.
plan can be extended to accommodate the rapid demand 6. Define the Stirling numbers of the first kind and describe
for more telephone numbers. (See if you can find some some of their properties and the identities they satisfy.
of the proposals coming from the telecommunications in- 7. Describe some of the properties and the identities that Stir-
dustry.) For each new numbering plan you discuss, show ling numbers of the second kind satisfy, including the con-
how to find the number of different telephone numbers it nection between Stirling numbers of the first and second
supports. kinds.
3. Discuss the importance of combinatorial reasoning in gene 8. Describe the latest discoveries of values and bounds for
sequencing and related problems involving genomes. Ramsey numbers.
4. Many combinatorial identities are described in this book. 9. Describe additional ways to generate all the permutations
Findsomesourcesofsuchidentitiesanddescribeimportant of a set with n elements besides those found in Section 6.6.
combinatorial identities besides those already introduced Compare these algorithms and the algorithms described
in this book. Give some representative proofs, including in the text and exercises of Section 6.6 in terms of their
combinatorial ones, of some of these identities. computational complexity.
5. Describe the different models used to model the dis- 10. Describe at least one way to generate all the partitions of
tribution of particles in statistical mechanics, including a positive integer n. (See Exercise 47 in Section 5.3.)