\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 2}
\centerline{February 10, 2017}
\vskip 10pt
\noindent
2.3.5.  A derangement is a permutation with no fixed points.  The permutations of
$[4]$ that are derangements have the cycle decompositions:
$$(1234), (1243), (1324), (1342), (1423), (1432), (12)(34), (13)(24), (14)(23).$$
(That is, 9 out of the 24 elements of $S_4$ are derangements.  We will consider 
ways to count the derangements of $[n]$ in general later in the course.  This question
was just asking for all the derangements for this one value of $n$.)   
\vskip 10pt
\noindent
2.3.6.  There are $\frac{P(8,2)}{2!} = \frac{8\cdot 7}{2} = 28$ different ways to choose the positions
of the two numbers. We divide by 2 here since the ordering of the two positions does not matter.  
(Equivalently this number $28 = \binom{8}{2}$.   Then 
the total number of passwords is 
$$28\cdot 10^2 \cdot 26^6$$
by the Multiplication Principle.    
\vskip 10pt
\noindent
2.3.7.  {\it Solution 1:}  The matrices we are considering here are all obtained
by permuting the columns (or the rows) of the $n\times n$ identity matrix.  There
are $n!$ such permutations and they all yield different matrices.  So the total
number is $n!$.
\vskip 10pt
\noindent
{\it Solution 2:} Say the 1 in column $i$ appears in row $m_i$ for each $i$ from $1$ to $n$.  
Then the ordered
list $(m_1,m_2,\ldots,m_n)$ defines a permutation of $[n]$.  Moreover, every
such permutation corresponds to a binary matrix with exactly one $1$ in each
row and each column.  Therefore the number of such matrices is exactly $n!$.
\vskip 10pt 
\noindent
(Comment:  The set of such matrices is called the set of $n\times n$
permutation matrices.  They form a subgroup of the group of invertible $n \times n$
matrices with operation matrix multiplication.  This subgroup is isomorphic as
a group to $S_n$.  For instance, the 6 $3\times 3$ permutation matrices are 
$$\begin{pmatrix} 1& 0 & 0\\ 0 &1 & 0\\ 0& 0& 1\end{pmatrix}, 
\begin{pmatrix} 1& 0 & 0\\ 0 &0 & 1\\ 0& 1& 0\end{pmatrix},
\begin{pmatrix} 0& 0 & 1\\ 0 &1 & 0\\ 1& 0& 0\end{pmatrix},$$
$$\begin{pmatrix} 0& 1 & 0\\ 1 &0 & 0\\ 0& 0& 1\end{pmatrix}, 
\begin{pmatrix} 0& 1 & 0\\ 0 &0 & 1\\ 1& 0& 0\end{pmatrix},
\begin{pmatrix} 0& 0 & 1\\ 1 &0 & 0\\ 0& 1& 0\end{pmatrix}.$$
These correspond to the identity permutation $(1)(2)(3)$, $(1)(23),(2)(13),(3)(12),(123),(132)$ respectively
under the most obvious way to set up the isomorphism.)
\vskip 10pt
\noindent
2.4.9.  By Legendre's theorem, the number $200!$ is divisible by $7^m$ where
$$m = \sum_{k\ge 1} \left\lfloor \frac{200}{7^k}\right\rfloor = 28 + 4 + 0 + \cdots = 32.$$ 
\vskip 10pt
\noindent
2.4.10.  By Legendre's theorem, the number $333!$ is divisible by 
$2^m$ where 
$$m = \sum_{k\ge 1} \left\lfloor \frac{333}{2^k}\right\rfloor = 166 + 83 + 41 + 20 + 10 + 5 + 2 + 1 = 328.$$
Similarly, the number $333!$ is divisible by 
$5^n$ where 
$$n = \sum_{k\ge 1} \left\lfloor \frac{333}{5^k}\right\rfloor = 66 + 13 + 2 = 81.$$
Since $10 = 2\cdot 5$, the number of zeroes at the end of $333!$ is $81$.   (You can check 
this by asking Maple to compute $333!$ for instance! That's a real exclamation point, not
a factorial!  When I was in college it would have been inconceivable to be able to compute
explicitly and \emph{exactly} with numbers that large.)
\vskip 10pt
\noindent
2.5.6.  Note that we certainly want to assume that there is no way to distinguish one rook from another (they are all equivalent and it does not matter which of the rooks goes where).  The condition that 
two rooks are non-attacking is just that they are not in the same row or column of the board.  
\vskip 10pt
\noindent
{\it Solution 1:} No two of the $k$ rooks can be in the same column, so 
there are rooks in each of the $k$ columns of the board.  
There are $n$ choices for the row containing the rook in the first column, 
then $n - 1$ choices for the row containing the rook in the second column, etc.  By the
Multiplication Principle, the total number of ways to place the rooks is
$$n(n - 1) \cdot \cdots \cdot (n - (k-1)) = P(n,k).$$
\vskip 10pt
\noindent
{\it Solution 2:}  Many people noticed that this is related to 2.3.7 above.  
If $n = k$, then this is exactly the same as the earlier problem -- 
there are $n!$ such placements when $n = k$.  If $n > k$,
there must be one rook in each of the $k$ columns and they must appear in $k$
distinct rows if they are non-attacking. So, 
from each such position we can make an $n\times k$ binary matrix by putting
1's in the positions of the rooks and 0's elsewhere.  Then the positions on the board are
in 1-1 correspondence with $n \times k$ binary matrices with exactly one 1 in each column and
where the 1's appear in distinct rows.  Those columns are $k$ of the columns of an $n\times n$
identity matrix, and they can appear in any order, so the total number of possible
matrices of this form is $P(n,k) = n(n-1)\cdots (n - k + 1)$.  
\vskip 10pt
\noindent
{\it Solution 3:}  Yet another way to see this is that you can choose the $k$
\emph{rows} to contain the rooks first and ignore any other rows.  Then 
you can place the rooks in the chosen $k$ rows as in the case $n = k$, hence
in $k!$ different ways.    By the Multiplication Principle, the number of placements is 
$\binom{n}{k} \cdot k! = P(n,k)$.
\vskip 10pt
\noindent
2.5.8.  Note that the representative and the alternate from each club must be different people -- 
they are ``distinguishable'' from each other. If
they are chosen once and for all at the start of the year, then it's possible
that either one of them could
attend any meeting of the council, and by the Multiplication Principle there are
$2 \cdot 2\cdot 2\cdot 2 \cdot 2 = 2^5 = 32$ 
possible sets of people who could show up at a council meeting (since there
are 5 clubs).  If you think the representative and the alternate might get chosen 
before every council meeting (which seems unlikely to me, but ... ) then any one of the
$n_i$ members of the $i$th club could end up attending the council meeting and
the total number of ``meetings'' is $n_1\cdot n_2 \cdot \cdots \cdot n_5$ (Multiplication
Principle again).    Comment:  In the second case the selection of the representative and
the alternate turns out to be irrelevant because any two people could get chosen every time.  
This question is \emph{not} asking about how many 
ways you could choose the representative and the delegate from the $i$th club (that would be
$P(n_i,2)$).  It's asking how many different ways 5 people, one from each club, could be
selected if each of them has to be either the representative or the alternate.  
\vskip 10pt
\noindent
2.7.13.  This is the permutation $(15372)(496)(8)$.  Note that $8$ is fixed.  
The cycle index is ${\rm cyc}(\tau) = 3$
and the type is $[5,3,1]$.
\vskip 10pt
\noindent
2.7.14.  In $S_{20}$, there are 
$$\frac{P(20,7)}{7} \cdot \frac{1}{3!}\left( \frac{P(13,3)}{3}\cdot \frac{P(10,3)}{3}\cdot \frac{P(7,3)}{3}\right) \cdot \frac{P(4,2)}{2} \cdot \frac{1}{2!} \cdot \left(\frac{P(2,1)}{1}\frac{P(1,1)}{1}\right)
\doteq 5.364 \times 10^{14}$$
permutations with cycle type $[7,3,3,3,2,1,1]$.  (This is out of the $20! \doteq 2.433 \times 10^{18}$
permutations of $[20]$, so it's actually a small fraction of the total.)  The factors of 
$\frac{1}{3!}$ and $\frac{1}{2!}$ must be included to avoid double-counting.  Recall that disjoint
cycles commute, so the product of the three $3$-cycles can be written with the factors in any one
of the $3!$ different orderings.  Similarly for the two $1$-cycles.
(See explanation for Example 2.7.4, which is very similar.)
\vskip 10pt
\noindent
2.7.20.  The Stirling number of the first kind $s(n,k)$ is the number of permutations in $S_n$
that have cycle index $k$.  Since the cycle index is just the number of cycles in the disjoint
cycle decomposition, every element of $S_n$ has cycle index $k$ for some $k$ with $1 \le k \le n$.
Let $S_{n,k}$ be the set of permutations in $S_n$ that have cycle index $k$.  Then 
$$S_n = S_{n,1} \cup S_{n,2} \cup \cdots S_{n,n}$$
and $S_{n,i} \cap S_{n,j} = \emptyset$ if $i\ne j$.  By the Addition Principle,
$$n! = |S_n| = \sum_{k = 1}^n |S_{n,k}| = \sum_{k=1}^n s(n,k),$$
and that also equals $\sum_{k=0}^n s(n,k)$
since $s(n,0) = 0$ for all $n\ge 1$ (there are no permutations of $[n]$ with 0 cycles if $n \ge 1$).  Our
book also allows $n = 0$, though, and in that case $s(0,0)$ is defined to $= 1$.  Then the 
equality says $0! = 1 = s(0,0)$.      


\end{document}
