\documentstyle[12pt,twoside,macpsfig,amssymb]{article}
\input{macros-course}

\addtolength{\topmargin}{-.35in}
\setlength{\textheight}{9.1in}

\remove{
  \newcommand{\problm}{\problem \rm}
  \renewcommand{\ppart}{\problempart \rm}
  \newcommand{\pf}{\begin{proof}\sf}
  \newcommand{\soln}{\sf}
  \newcommand{\thm}{\begin{theorem}\ \ }
}\newcommand{\mystrut}{\rule{0pt}{14pt}}


\begin{document}

\psol{7}{November 10, 1994}

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf Undirected graphs}

In an undirected graph on $n$ vertices, an edge is an unordered pair of
vertices, so there are ${n \choose 2}$ possible edges.
Each possible edge is either present or absent, so there are $2^{n \choose 2}$
possible undirected graphs on $n$ vertices.

\problem {\bf Rook paths}

The rook must make $m-1$ moves up and $n-1$ moves right, but the order is
arbitrary.  A path is defined by which of the $n+m-2$ total moves are
the ``up'' moves.  Thus we may choose different paths simply by choosing
which of the moves should be the ``up''s, so 
there are ${m+n-2 \choose m-1} = {m+n-2 \choose n-1}$ possible paths.

\problem {\bf Distinguishable dice}

Five ordinary distinguishable six-sided dice can land in $6^5=7776$ ways.  If
they land so that no pair shows up, there are $6\times 5\times 4\times 3\times
2 = 720$ possibilities.  To get a full house, there are ${5 \choose 2}$ ways to
pick which dice are the pair and which are the triple, and $6\times 5$ ways to
choose the values of the pair and triple: ${5\choose 2}\times 6\times 5 = 300$.

\problem {\bf Coefficients}

\begin{problemparts}
\problempart ${11\choose 5} = 462$.
\problempart ${10 \choose 2} = 45$.
\problempart $a^6b^6 = (a^2)^3 (b^3)^2$, so the coefficient is 
	${5 \choose 3} = 10$.
\problempart ${6 \choose 3}3^3 4^3 = 34560$.
\end{problemparts}

\problem {\bf Filenames}

\begin{problemparts}
\problempart $52^4 = 7311616$.
\problempart $52^4 \div 2^4 = 456976 = 26^4$.
\problempart $\sum_{i=1}^4 52^i = (52^5-52)/(52-1) = 7454980$; $\sum_{i=1}^4
26^i = (26^5-26)/(26-1) = 475254$.  The division rule can be applied only to
the individual terms of the summation.
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\problem {\bf Balls and urns}

\begin{problemparts}
\problempart $3\cdot 3\cdot 3\cdot 3=81$.
\problempart 14.
We can put either all 4 balls in one urn,
3 in one, 2 in one and 2 in another, or 2 in one and 1 in each of the other
two.  The balls are distinguishable, so there are $4\choose 3$ ways of
putting 3 in one.  There are $4\choose 2$ ways of putting 2 in one and 1 in
each of the other two.  There are ${4\choose 2}/2$ of putting 2 in one and
2 in another.
So the total number of ways is
\[
1 + {4\choose 3} + \frac{1}{2}{4\choose 2} + {4\choose 2} = 14.
\]
\problempart 15.
Create 6 slots and choose 2 to contain bars leaving
$r_1, r_2$ and $r_3$ consecutive
slots with stars with $r_1+r_2+r_3=4$.  This corresponds
to putting $r_i$ balls in urn $i$.  So the answer is ${6\choose 2}=15$.
\problempart 
4.
This is the number of ways to partition a multiset $\{1,1,1,1\}$
of 4 indistinguishable objects into 3 (possibly empty) subsets.
We can either put
$\{1,1,1,1,\}, \emptyset, \emptyset$, or
$\{1,1,1\}, \{1\}, \emptyset$, or
$\{1,1\}, \{1,1\},\emptyset$, or
$\{1,1\}, \{1\}, \{1\}$.
The ordering in which we list the subsets doesn't matter because
the urns are indistinguishable.

\end{problemparts}

\problem {\bf Generalized balls and urns}
\begin{problemparts}
\problempart  If both the balls and urns are distinguishable, then each ball
may be placed in one of $k$ urns, for a total of $k^n$ choices.  If only the
urns are distinguishable, then we may use a stars-and-bars arguments.  There
are $k-1$ bars separating the urns, and $n$ stars, giving $n+k-1 \choose n$
choices.

\problempart Here the balls are distinguishable but the urns are not.
$S(n,n-1)$ counts the number of ways of putting two balls in one
urn and one ball in each of the $n-2$ remaining urns.  There are $n \choose 2$
ways of picking the pair, so $S(n,n-1)= {n \choose 2}$.

If the $n$ balls have been placed in $k$ urns, then we may distinguish between
two cases.  In the first case, the ball \#1 is in an urn by itself.  Then
there are $S(n-1,k-1)$ ways to place the remaining $n-1$ balls into $k-1$ urns.
In the second case, for each of the ways of putting $n-1$ balls in $k$ urns,
we may place the ball \#1 in any of the $k$ (nonempty) urns.
%	In the second case, when we delete the last ball, 
%	we get a $k:1$ mapping to ways to place $n-1$
%	balls in $k$ urns.  
Hence for $n\geq 1$, we have $S(n,k) = S(n-1, k-1) + k\cdot S(n-1, k)$.

The first few values of $S(n,k)$ are
\begin{tabular}{|r||*{8}{r|}}
\hline
$n\backslash k$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\
\hline
\hline
0 &   1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 &   0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
2 &   0 & 1 & 1 & 0 & 0 & 0 & 0 & 0\\
3 &   0 & 1 & 3 & 1 & 0 & 0 & 0 & 0\\
4 &   0 & 1 & 7 & 6 & 1 & 0 & 0 & 0\\
5 &   0 & 1 &15 &25 &10 & 1 & 0 & 0\\
6 &   0 & 1 &31 &90 &65 &15 & 1 & 0\\
7 &   0 & 1 &63 &301&350&140&21 & 1\\
\hline
\end{tabular}\\
$S(4,1)+S(4,2)+S(4,3)=14$ as computed in part {\bf (b)} above.

\problempart Here both the balls and urns are indistinguishable.
$p(n,2)$ counts the number of ways to get $n$ by adding two unordered positive
integers, which is $\lfloor n/2 \rfloor$.

If the balls have been placed in $k$ urns, then we may distinguish between two
cases.  In the first case, there is an urn with one ball.  Then there are
$p(n-1,k-1)$ ways to distribute the remaining balls.  Otherwise, each urn has
at least two balls.  Delete one ball from each urn; there are $p(n-k,k)$ ways
to distribute the remaining $n-k$ balls.  Hence for $n\geq 1$
\[ p(n,k) = p(n-1, k-1) + p(n-k, k)
\]
The first few values of $p(n,k)$ are
\begin{tabular}{|r||*{8}{r|}}
\hline
$n\backslash k$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\
\hline
\hline
0 &   1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 &   0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
2 &   0 & 1 & 1 & 0 & 0 & 0 & 0 & 0\\
3 &   0 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\
4 &   0 & 1 & 2 & 1 & 1 & 0 & 0 & 0\\
5 &   0 & 1 & 2 & 2 & 1 & 1 & 0 & 0\\
6 &   0 & 1 & 3 & 3 & 2 & 1 & 1 & 0\\
7 &   0 & 1 & 3 & 4 & 3 & 2 & 1 & 1\\
\hline
\end{tabular}

$p(4,1)+p(4,2)+p(4,3)=4$ as computed in part {\bf (d)} above.
\end{problemparts}

\problem {\bf More balls and urns}

Each urn gets at least $k$ balls, leaving $b-ku$ balls to distribute amongst
the urns.  Using the stars and bars argument, there are $b-ku$ stars and $u-1$
bars, so there are ${b-ku+u-1 \choose u-1}$ possibilities.

\problem {\bf Integers not divisible}

Here we use inclusion-exclusion to count the number of integers from 1 to 1000
not divisible by 6, 10, or 15.  Make a table, and add the numbers with
appropriate signs:

\begin{tabular}{|c|r|r|c|}
\hline
divisible by & least common multiple & number of integers & include/exclude \\
each of      & of divisors           &from 1 to 1000     & $+/-$\\
\hline
\hline
          &   1 & 1000 & $+$ \\
6         &   6 & 166 & $-$ \\
10        &  10 & 100 & $-$ \\
15        &  15 &  66 & $-$ \\
6, 10     &  30 &  33 & $+$ \\
6, 15     &  30 &  33 & $+$ \\
10, 15    &  30 &  33 & $+$ \\
6, 10, 15 &  30 &  33 & $-$ \\
\hline
\end{tabular}

\hspace{3in} These add up to 734.

\newpage
\problem{\bf Binomial coefficient identity}

\begin{problemparts}
\problempart 
\begin{eqnarray*}
x^{-n}(1+x)^n x^n (1+x^{-1})^n &=& x^{-n}(1+x)^n (x+1)^n \\
(1+x)^n (1+x^{-1})^n &=& x^{-n}(1+x)^{2n}\\
\sum_{i=0}^n {n\choose i}x^i \sum_{j=0}^n {n\choose j}x^{-j} &=& x^{-n}\sum_{i=0}^{2n} {2n\choose i}x^i\\
\sum_{i=0}^n {n\choose i}^2 &=& {2n\choose n}
\end{eqnarray*}
by equating the coefficients of $x^0$.

\problempart
Suppose we have $2n$ objects, $n$ of which are red, and $n$ of which are blue.
How many ways can we pick $r$ red ones and $n-r$ blue ones?  Clearly this is
$${n \choose r} {n \choose n-r} = {n \choose r}^2.$$  How many ways can we choose $n$ objects
total, regardless of how many are of each color?  This is just 
$$ \sum_{r=0}^n {n \choose r}^2.$$  But there are  ${2n \choose n}$ ways to
choose $n$ objects, so these must be the same number.
\end{problemparts}

\problem {\bf Seats of 26-100}

26-100 doesn't have nearly so many seats, but suppose it does.  Seat number $n$
is left turned down if and only if $n$ has an odd number of factors.  The
factors of $n$ can be paired of with one another: if $d|n$ then pair it with
$n/d$.  Each divisor $d$ gets paired with a different divisor unless $d = n/d$,
i.e., unless $d^2 = n$.  If $n$ is not a perfect square, then the divisors are
partitioned into groups of two, and so there are an even number of them.
Otherwise, if $n$ is a perfect square, there are an odd number of factors.
Hence the seats that get turned down are numbered
$1,4,9,16,25,\ldots,i^2,\ldots,900,961$, and there are 31 in total.

\problem{\bf Intersecting chords}

If two chords intersect in the interior of the circle, then their endpoints
must be four distinct points.  Since no three chords intersect, any
intersection in the interior corresponds to precisely one set of four points on
the circle.  Furthermore, for any set of four points on the circle, there
is precisly one way to draw a pair of chords which intersect in the interior.
Hence there is a bijection between the intersections in the interior and the
set of four-tuples of points, so there are ${n \choose 4}$ intersections in the
interior.













\end{problems}


\end{document}






















\end{problems}

\end{document}
