# Explanations for Discrete Structures problems

11) Use generating functions to determine the number of different ways 12 identical action figures can be given to five children so that each child receives at most three action figures.

12) Use generating functions to find the number of ways to select 10 balls from an urn containing red, white and blue balls if:

a. The selection has at least two balls of each color.

b. The selection has at most two balls of each color.

c. The selection has an even number of red balls.

13) Determine whether the relation R on the set of all real numbers is reflexive, symmetric, antisymmetric, and/or transitive, where (x,y) E R, if and only if:

a) x + y = 0

b) xy = 0

14) Find:

a) R1 U R3

b) R1 - R2

c) R2 (symmetric difference) R4

15) Show that the sum, over the set of people at a party, of the number of people a person has shaken hands with, is even.? Assume that no one shakes his or her own hand.

16) What is the sum of the entries in a column of the adjacency matrix for an undirected graph?? For a directed graph?

17) Show that the PETERSON GRAPH, does not have a Hamilton circuit, but that the subgraph obtained by deleting a vertex v, and all edges incident with v, does have a Hamilton circuit.

#### Solution Preview

11). We can consider this question as follows. Labeling children 1,2,3,4,5.

1) Just four children have 3 action figures, so there are 5 cases.

2) three children have 3 action figures, there are 10 cases, but the rest two may have two or one , or one or two, so there are 10*2=20 cases.

3) two children have 3 action figures, there are 10 cases, but the rest three children must have two for each, so there are 10 cases.

2) one child has 3 action figure, then the rest four children have total 9. This is impossible. You can know this by pigeonhole principle.

So the total number is 5+20+10=35.

12. a) It is equivalent to choose 4 balls from urn containing red , white and blue balls. We consider as follows. Just consider ...

#### Solution Summary

The solution contains detailed explanations of whether the relation R on the set of all real numbers is reflexive, symmetric, antisymmetric, and/or transitive. Some problems in graph theory are discussed as well.