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 product principle for EGFs and the idea of coloring a set in two colors to prove the formula \(e^x\cdot e^x = e^{2x}.\)

2

Find the EGF for the number of ordered functions from a \(k\)-element set to an \(n\)-element set.

3

Find the EGF for the number of ways to string \(n\) distinct beads onto a necklace.

4

Find the exponential generating function for the number of broken permutations of a \(k\)-element set into \(n\) parts.

5

Find the EGF for the total number of broken permutations of a \(k\)-element set.

6

Find the EGF for the number of graphs on \(n\) vertices in which every vertex has degree 2.

7

Recall that a cycle of a permutation cannot be empty.

  1. What is the generating function for the number of cycles on an even number of elements (i.e. permutations of an even number \(n\) of elements that form an \(n\)-cycle)? Your answer should not have a summation sign in it. Hint: If \(y= \sum_{i=0}^\infty \frac{x^{2i}}{2i}\text{,}\) what is the derivative of \(y\text{?}\)

  2. What is the generating function for the number of permutations on \(n\) elements that are a product of even cycles?

  3. What is the generating function for the number of cycles on an odd number of elements?

  4. What is the generating function for the number of permutations on \(n\) elements that are a product of odd cycles?

  5. How do the generating functions in parts b and d of this problem related to the generating function for all permutations on \(n\) elements?