Skip to main content
\(\newcommand{\cycle}[1]{\arraycolsep 5 pt \left(\begin{array}#1\end{array}\right)} \newcommand{\importantarrow}{\Rightarrow} \newcommand{\qchoose}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_q} \def\neg1choose#1#2{\genfrac{[}{]}{0pt}{}{#1}{#2}_{-1}} \newcommand{\bp}{ \begin{enumerate}{\setcounter{enumi}{\value{problemnumber}}}} \newcommand{\ep}{\setcounter{problemnumber}{\value{enumi}} \end{enumerate}} \newcommand{\ignore}[1]{} \renewcommand{\bottomfraction}{.8} \renewcommand{\topfraction}{.8} \newcommand{\apple}{\text{šŸŽ}} \newcommand{\ap}{\apple} \newcommand{\banana}{\text{šŸŒ}} \newcommand{\ba}{\banana} \newcommand{\pear}{\text{šŸ}} \newcommand{\pe}{\pear} \DeclareMathOperator{\Fix}{Fix} \DeclareMathOperator{\Orb}{Orb} \newcommand{\F}{\mathcal{F}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section Supplementary Problems

1

Use the inductive definition of \(a^n\) to prove that \((ab)^n=a^nb^n\) for all nonnegative integers \(n\text{.}\)

2

Give an inductive definition of \(\displaystyle \bigcup_{i=1}^nS_i\) and use it and the two set distributive law to prove the distributive law \(\displaystyle{A\cap \bigcup_{i=1}^n S_i=\bigcup_{i=1}^n A\cap S_i}\text{.}\)

3

A hydrocarbon molecule is a molecule whose only atoms are either carbon atoms or hydrogen atoms. In a simple molecular model of a hydrocarbon, a carbon atom will bond to exactly four other atoms and hydrogen atom will bond to exactly one other atom. Such a model is shown in FigureĀ 2.0.8. We represent a hydrocarbon compound with a graph whose vertices are labelled with C's and H's so that each C vertex has degree four and each H vertex has degree one. A hydrocarbon is called an ā€œalkaneā€ Common examples are methane (natural gas), butane (one version of which is shown in FigureĀ 2.0.8)propane, hexane (ordinary gasoline), octane (to make gasoline burn more slowly), etc.

Figure 2.0.8 A model of a butane molecule
  1. How many vertices are labelled \(H\) in the graph of an alkane with exactly \(n\) vertices labelled \(C\text{?}\)
  2. An alkane is called butane if it has four carbon atoms. Why do we say one version of butane is shown in FigureĀ 2.0.8?
4
  1. Give a recurrence for the number of ways to divide \(2n\) people into sets of two for tennis games. (Don't worry about who serves first.)
  2. Give a recurrence for the number of ways to divide \(2n\) people into sets of two for tennis games and to determine who serves first.
5

Give a recurrence for the number of ways to divide \(4n\) people into sets of four for games of bridge. (Don't worry about how they sit around the bridge table or who is the first dealer.)

7

Give an inductive definition of the product notation \(\displaystyle \prod_{i=1}^n a_i\text{.}\)

8

Using the fact that \((ab)^k =a^kb^k\text{,}\) use your inductive definition of product notation in ProblemĀ 2.7 to prove that \(\displaystyle \left(\prod_{i=1}^n a_i\right)^k=\prod_{i=1}^n a_i^k\text{.}\)

9

How many labelled trees on \(n\) vertices have exactly four vertices of degree 1?

10

The degree sequence of a tree is a list of the degrees of the vertices in nonincreasing order. For example the degree sequence of the first graph in FigureĀ 2.3.3 is \((4,3,2,2,1)\text{.}\) For a graph with vertices labeled 1 through \(n\text{,}\) the ordered degree sequence of the graph is the sequence \((d_1,d_2,\dots,d_n)\) in which \(d_i\) is the degree of vertex \(i\text{.}\) For example, the ordered degree sqeuence of the first graph in FigureĀ 2.3.1 is \((1,2,3,3,1,1,2,1)\text{.}\)

  1. How many labelled trees are there on \(n\) vertices with ordered degree sequence \(d_1,d_2,\ldots d_n\text{?}\) (This problem appears again in the next chapter since some ideas in that chapter make it more straightforward.)
  2. How many labeled trees are there on \(n\) vertices with the degree sequence in which the degree \(d\) appears \(i_d\) times?