## Introduction to Discrete Mathematics, Fall 2000 Problem Set 2, 3-5 Oct.

1. Prove the following claims:
1. All subsets of the set of natural numbers are either finite or countably infinite.
2. The cartesian product is countably infinite. (Hint: Think of the pairs as laid down in a two-dimensional table. Enumerate the elements of the table along diagonals that go in the lower left to upper right direction.) Note: It follows easily from this result that also the set of rational numbers is countably infinite.

2. Prove that in any group of people, there are at least two persons who have exactly equally many acquaintances in the group. A person is not counted among his/her own acquaintances, and we assume that the acquaintedness relation is symmetric, so that if is acuainted with , then also is acquainted with . (Hint: Apply the pigeonhole principle.)

3. A pack of cards contains 52 cards that are divided into four suites'' (hearts, diamonds, clubs, spades). The cards belonging to each suite are numbered 1,...,13.
1. How many different five-card poker hands'' (five-card subsets) are there?
2. In how many ways is it possible to form a five-card flush'', i.e. a subset of five cards where all the cards are of the same suite?
3. In how many ways is it possible to form a full house'', i.e. a five-card subset consisting of a three-of-a-kind'' (three cards of the same numerical value), and a pair'' (two cards of the same numerical value)? The same card in a full house obviously cannot belong both to the pair and the three-of-a-kind combination.

4. Prove the following properties of the binomial coefficients:
1. Deduce from this fact that the binomial coefficients are increasing with respect to the index ( ), when , and decreasing ( ), when .
2. Verify Pascal's formula by a direct calculation based on the defining formula for the binomial coefficients.
3. by induction on . Which familiar formula do you obtain from this identity in the case ? Can you come up with a combinatorial argument for proving the identity?

5. Estimate the size of the middlemost'' binomial coefficient , by approximating the factorial function with Stirling's formula: .

6. Natural numbers ja are relatively prime, if they have no common factors, i.e. if their greatest common denominator is . The value of Euler's totient function indicates the number of natural numbers less than that are relatively prime to , i.e. (Thus, for instance, , .) Show, using the inclusion-exclusion principle, that if the different prime factors of number are , ,..., , then