\documentclass[11pt]{article}
\def\Z{\mathbb{Z}}
\def\Q{\mathbb{Q}}
\usepackage{latexsym,amsmath,amssymb,epsfig}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\textheight}{8.0in}
\begin{document}
\centerline{MATH 357 -- Combinatorics}
\centerline{Solutions for Problem Set 8}
\centerline{April 21, 2017}
\vskip 10pt
\noindent
7.1.19. {\it Solution 1 -- the ``brute force'' way}: 
Let $A$ be the set of distributions of the 25 gumdrops where Alice's requirement {\it is
satisfied}, $B$ the set where Bob's requirement {\it is satisfied}, etc.  We want to count the number
of elements in the \emph{complement of the union} $A \cup B \cup C \cup D$.  By the Inclusion-Exclusion
Principle, 
\begin{eqnarray*}
|A \cup B\cup C\cup D| &=& |A| + |B| + |C| + |D| - |A\cap B| - |A \cap C| - |A \cap D| - |B \cap C| 
- |B\cap D| - |C\cap D| \\
& & + |A \cap B\cap C| + |A\cap B \cap D| + |A \cap C\cap D| + |B\cap C\cap D| - |A \cap B \cap C \cap D|.
\end{eqnarray*}
The total number of ways to distribute the 25 gumdrops is $\binom{25 + 3}{3} = 3276$ (unlabeled
balls and labeled urns).  

Then $|A|$ is the coefficient of $x^{25}$ in the expansion of 
$\frac{x + x^5}{(1 - x)^3}$, which is $|A| = 556$.  $|B|$ is the coefficient of $x^{25}$ in
$\frac{1}{(1 - x)^3(1 - x^2)}$, which is $|B| = 1729$.  $|C|$ is the coefficient of $x^{25}$ in 
$\frac{x^4}{1 - x)^4}$, which is $|C| = 2024$.  $|D|$ is the coefficient of $x^{25}$ in
$\frac{1 + x + \cdots + x^6}{(1 - x)^3}$, which is $|D| = 1946$.  

Similarly, 
\begin{eqnarray*}
|A\cap B| &=&  {\rm coeff.\ of\ } x^{25}\ {\rm in}\  \frac{(x + x^5)}{(1 - x)^2(1 - x^2)} = 290\\ 
|A\cap C| &=& {\rm coeff.\ of\ } x^{25}\ {\rm in}\ \frac{(x + x^5)x^4}{(1 - x)^3} = 384\\
|A\cap D| &=& {\rm coeff.\ of\ } x^{25}\ {\rm in}\ \frac{(x + x^5)(1 + \cdots + x^6)}{(1 - x)^2} = 280\\
|B\cap C| &=& {\rm coeff.\ of\ } x^{25}\ {\rm in}\ \frac{x^4}{(1 - x)^3(1-x^2)} = 1078\\
|B\cap D| &=& {\rm coeff.\ of\ } x^{25}\ {\rm in}\ \frac{1 + \cdots + x^6}{(1 - x)^2(1 - x^2)} = 1014\\
|C\cap D| &=& {\rm coeff.\ of\ } x^{25}\ {\rm in}\ \frac{(1+\cdots+x^6)x^4}{(1 - x)^3} = 1344.
\end{eqnarray*}

Then, 
\begin{eqnarray*}
|A\cap B\cap C| &=&  {\rm coeff.\ of\ } x^{25}\ {\rm in}\  \frac{(x + x^5)x^4}{(1 - x)^2(1 - x^2)} = 202\\ 
|A\cap B\cap D| &=& {\rm coeff.\ of\ } x^{25}\ {\rm in}\ \frac{(x + x^5)(1 +\cdots +x^6}{(1-x)(1-x^2)} = 144\\
|A\cap C\cap D| &=& {\rm coeff.\ of\ } x^{25}\ {\rm in}\ \frac{(x + x^5)x^4(1 + \cdots + x^6}{(1 - x)^2} = 
224\\
|B\cap C\cap D| &=& {\rm coeff.\ of\ } x^{25}\ {\rm in}\ \frac{x^4(1 + \cdots + x^6)}{(1 - x)^2(1 - x^2)} 
= 706.
\end{eqnarray*}

Finally $|A\cap B\cap C\cap D|$ is the coefficient of $x^{25}$ in 
$\frac{(x + x^5)x^4(1 + \cdots + x^6)}{(1 - x)(1 - x^2)}$, which is $116$.  So the final answer
is 
$$3276 - 556 - 1729 - 2024 - 1946 + 290 + 384  + 280 + 1078 + 1014 + 1344 - 202 - 144 - 224 - 706 + 116 = 
251.$$
\noindent
{\it Solution 2 -- ``the lazy, clever way''} --  Note: several of you had
this idea, one did it completely correctly this way, others were very close, and a few others 
were on the right track.  In some cases, something must have gone wrong in entering stuff 
into Maple because your numerical answer was not correct -- I cannot tell what went wrong without
seeing what you entered into Maple, though; in other papers I couldn't tell what you meant at first 
and I had to change the scoring, making a mess in the process.  Sorry for that! 
{\it But please explain what you are doing so I don't have to try to read your mind!!!!!}
\vskip 10pt
\noindent
In any case we can also count what we want by counting
$$|\overline{A} \cap \overline{B} \cap \overline{C} \cap \overline{D}|$$
(here $\overline{A}$ is the complement of $A$ as above inside the set of all distributions;
in words it is the set of distributions where Alice's requirement is {\it not satisfied}, and 
the others are similar).  This count can be done with a single generating function computation.
We want the coefficient of $x^{25}$ in the product 
$$(1 + x^2 + x^3 + x^4 + x^6 + \cdots)(x + x^3 + x^5 + \cdots)(1 + x + x^2 + x^3)(x^7 + x^8 + \cdots)$$
The first factor has all the $x^k$ except $x$ and $x^5$, the second has all but the even exponents, 
the third has all the terms $x^k$ with $k < 4$ and the last has all the terms $x^k$ with $k > 6$.
This way also gives $ \cdots + 251 x^{25} + \cdots $ so the number we want is $251$.   

\noindent
7.3.6.  The number is 
$$S(n,k-m) = \frac{1}{(k-m)!}\sum_{i=1}^{k-m} (-1)^i \binom{k-m}{i} (k-m-i)!.$$
(Think about the terms in the sum $\sum_{i=1}^k S(n,k)$
for the labeled balls, unlabeled urns, no restrictions entry in Table 4.6; the second equality comes
from the equation at the top of page 211.)

\bigskip
\noindent
7.3.7.  There are $\binom{n}{k}$ ways to choose the fixed points, and then for each
such choice the permutation must be a derangement of the other $n - k$ numbers.
By the Multiplication Principle, the number of permutations of $[n]$ with exactly $k$ fixed points is
$$\binom{n}{k}\cdot D_{n-k} = \binom{n}{k} \cdot (n-k)! \sum_{i=0}^{n-k} \frac{(-1)^i}{i!}
= \frac{n!}{k!} \sum_{i=0}^{n-k} \frac{(-1)^i}{i!}.$$

\noindent
8.2.12.  As permutations of $[5]$, they are first the rotations:
$$(1)(2)(3)(4)(5),(12345),(13524),(14253),(15432),$$
then the reflections
$$(1)(25)(43),(2)(13)(45),(3)(24)(15),(4)(35)(12),(5)(14)(23).$$
The other information asked for is as follows
\[
\begin{array}{cccc}
g&\vert & Inv(g) & {\rm cyc}(g)\\ \hline
(1)(2)(3)(4)(5)&\vert & [5] & 5\\
(12345)&\vert & \emptyset & 1\\
(13524)&\vert & \emptyset & 1\\
(14253)&\vert & \emptyset & 1\\
(15432)&\vert & \emptyset & 1\\
(1)(25)(43) &\vert& \{1\} & 3\\
(2)(13)(45)&\vert & \{2\} & 3\\
(3)(24)(15)&\vert & \{3\} & 3\\
(4)(35)(12)&\vert & \{4\} & 3\\
(5)(14)(23)&\vert & \{5\} & 3\\
\end{array}
\]
and 
\[
\begin{array}{ccc}
x &\vert &  st(x) \\ \hline
1 &\vert&  \{(1)(2)(3)(4)(5), (1)(25)(43)\}  \\
2 &\vert & \{(1)(2)(3)(4)(5), (2)(13)(45)\}  \\
3 &\vert & \{(1)(2)(3)(4)(5), (3)(24)(15)\}  \\
4 &\vert& \{(1)(2)(3)(4)(5), (4)(35)(12)\}  \\
5 &\vert & \{(1)(2)(3)(4)(5), (5)(14)(23)\}  \\
\end{array}
\]

\noindent
8.2.13.  $S_4$ contains all the $4! = 24$ permutations of $[4]$, which have
disjoint cycle decompositions like this: the identity, then 6 4-cycles
$$(1)(2)(3)(4),(1234),(1432),(1243),(1342),(1324),(1423) $$ 
then 8 products of a 1-cycle and a 3-cycle and 3 products of two 2-cycles
$$(1)(234), (1)(243), (2)(134), (2)(143), (3)(124), (3)(142), (4)(123), (4)(132), (12)(34), (13)(24),
(14)(23),$$
and finally 6 products of a 2-cycle and two 1-cycles:
$$(12)(3)(4), (13)(2)(4), (14)(2)(3), (23)(1)(4), (24)(1)(3), (34)(1)(2).$$
The other information asked for is as follows.  Instead of listing all the 
elements here, I have included just one of each cycle type:
\[
\begin{array}{cccc}
g &\vert & Inv(g) & {\rm cyc}(g)\\ \hline
(1)(2)(3)(4) &\vert & [4] & 4\\
(1234) &\vert& \emptyset & 1\\
(1)(234) &\vert& \{1\} & 2\\
(12)(34) &\vert& \emptyset & 2\\
(12)(3)(4) &\vert& \{3,4\} & 3\\
\end{array}
\]
The stabilizers of each $x \in [4]$ look like a copy of 
$S_3$ sitting inside $S_4$.  For instance:
\[
\begin{array}{ccc}
x &\vert & st(x) \\ \hline
4 &\vert & \{(1)(2)(3)(4), (123)(4),(132)(4), (12)(3)(4),(13)(2)(4),(23)(1)(4)\}  \\
\end{array}
\]
(If you strip the $(4)$ from the end of each of these permutations, you
have the list of $3!$ elements of $S_3$.)
\vskip 10pt
\noindent
8.3.13.  We use Burnside's Lemma: 
\begin{eqnarray*}
{\rm Inv}(e) &=& [6]\\
{\rm Inv}(\pi_1) &=& \{4,5,6\}\\
{\rm Inv}(\pi_2) &=& \{4,5,6\}\\
{\rm Inv}(\pi_3) &=& \{1,2,3\}\\
{\rm Inv}(\pi_4) &=& \emptyset\\
{\rm Inv}(\pi_5) &=& \emptyset\\
{\rm Inv}(\pi_6) &=& \{1,2,3\}\\
{\rm Inv}(\pi_7) &=& \emptyset\\
{\rm Inv}(\pi_8) &=& \emptyset\\
\end{eqnarray*}
Therefore,
\begin{eqnarray*}
|\{\rm orbits\}| &=& \frac{1}{|G|} \sum_{g\in G} |{\rm Inv}(g)|\\
&=& \frac{1}{9}(6 + 3 + 3 + 3 + 0 + 0 + 3 + 0 + 0)\\
&=& 2.
\end{eqnarray*}
By examining the form of the cycle decompositions of the elements of $G$, it is
clear that the two orbits are $\{1,2,3\}$ and $\{4,5,6\}$.
\end{document}


