\documentclass[12pt]{article}
\usepackage[margin=1in,dvips]{geometry}
\usepackage{fancyhdr,lastpage}
\usepackage{amsmath,amssymb}
\usepackage[misc]{ifsym}
\pagestyle{fancy}
\lhead{MATH 387}
\chead{Problem Set \#3 solutions}
\rhead{}
\lfoot{}
\cfoot{Page \thepage\ of \pageref{LastPage}}
\rfoot{February 5, 2008}
\makeatletter
\renewcommand\theenumi{\@alph\c@enumi}
\renewcommand\labelenumi{(\theenumi)}
\makeatother
\begin{document}
\begin{description}
\item[2.5.3.] {\em Find the coefficient of $x^6y^2$ in $(y-2x)^8$.}
By the Binomial Theorem, the coefficient of $y^2(-2x)^6$ will be
$\binom 82$; rearranging that expression, we may write that term as
$\binom82(-2)^6x^6y^2$, so the coefficient in question is
$\binom82(-2)^6=28\cdot 64=1792$.
\item[2.5.4.] {\em Find the sum of all the coefficients in the
expansion of $(3x+4y)^6$.}
One can do this by expanding out the binomial, but doing so is
unnecessary. Note that if we posit the expansion:
$$(3x+4y)^6=a_0y^6+a_1xy^5+a_2x^2y^4+a_3x^3y^3+a_4x^4y^2+a_5x^5y+a_6x^6$$
with unknown $a_i$, what we seek is
$a_0+a_1+a_2+a_3+a_4+a_5+a_6$. We can achieve this easily with a
substitution for $x$ and $y$:
\begin{align*}
a_0+a_1+a_2+a_3+a_4+a_5+a_6&=a_0y^6+a_1xy^5+a_2x^2y^4+a_3x^3y^3+a_4x^4y^2+a_5x^5y+a_6x^6\bigr|_{x=1,y=1}\\
&=(3x+4y)^6\bigr|_{x=1,y=1}\\
&=7^6=117649\\
\end{align*}
\item[2.5.8.] {\em Find the coefficient of $x^5$ in the expansion of
$(2x+3)(x+1)^8$.}
There are two ways to get $x^5$ terms: They can draw an $x$ term
from the expression $(2x+3)$ and 4 $x$ terms from $(x+1)^8$, or they
can draw a constant term from $(2x+3)$ and 5 $x$ terms from
$(x+1)^8$. To put it more plainly, we know that the relevent terms
in the expansion of $(x+1)^8$ are $\binom84x^4$ and
$\binom85x^5$. Considering
$(2x+3)\left[\binom84x^4+\binom85x^5\right]$, we see that the
coefficient of the $x^5$ term will be $2\binom84+3\binom85=2\cdot
70+3\cdot 56=308$.
\item[2.5.9.] {\em In a family with six children what is the
probability of having three children of each sex?}
There are $2^6$ different possible gender combinations, since each
child in turn, from the eldest to the youngest, can be male or
female with equal probability: this will form our space of all
possible events. The number of ways to have 3 males and 3 females is
the number of ways to select 3 to be male and have the remainder
being female (or the other way around, if preferred): this is
exactly $\binom63$. Thus, the probability of having 3 children of
each sex is $\frac{\binom63}{2^6}=\frac{20}{64}=\frac5{16}$
{\em What is the probability of having two children of one sex and
four of another?}
As above, there are $2^6$ different possible gender combinations
forming our universe of events: the desired event here is either
exactly two males or exactly two females. We may select two males in
any of $\binom62$ ways; likewise, we could select two females in any
of $\binom 62$ ways. Thus, there are $\binom62+\binom62=30$ possible
gender combinations maching our desideratum, so the probability of
this event is $\frac{30}{64}=\frac{15}{32}$.
\item[\em 2.5.12.] {\em A player tosses a coin repeatedly. A head is
counted as one point, tails as two points. A player tosses until
his score equals or exceeds $n$. Show that the probability of
scoring exactly $n$ points is
$\frac{2+\left(\frac{-1}2\right)^n}3$.}
Let $f(n,k)$ be the number of $k$-toss sequences which score exactly
$n$ points. Note that $f(n,k)=0$ if $k<\frac n2$ or $k>n$, so we
need only determine $f(n,k)$ for $\frac n2\leq k\leq n$. If $k$ is
in this range, then in order to get $n$ points with $k$ tosses, we
need $x$ heads and $y$ tails satisfying:
$$\left\{\begin{aligned}
x+y=k\\
x+2y=n
\end{aligned}\right.$$
which has solution $x=2k-n$, $y=n-k$. Thus, the number of ways to do
so is the number of ways to select $2k-n$ heads out of $k$ flips, so
$f(n,k)=\binom{k}{2k-n}$. The {\em probability} of getting exactly
$n$ points in $k$ flips is simply $\frac{f(n,k)}{2^k}$, since there
are $2^k$ possible equally likely results, of which $f(n,k)$ form
the desired set. Thus, to find the total probability of reaching $n$
exactly, we add up the probability of reaching $n$ after each
possible number of flips to get the probability:
$$\sum_{k=\lceil\frac n2\rceil}^n\frac{\binom{k}{2k-n}}{2^k}=\frac{\binom{n}{n}}{2^n}+\frac{\binom{n-1}{n-2}}{2^{n-1}}+\frac{\binom{n-2}{n-4}}{2^{n-2}}+\cdots$$
Note that the final term of this may include either the binomial
$\binom{\lceil\frac n2\rceil}1$ or $\binom{\lceil\frac n2\rceil}0$,
depending on the parity of $n$. Let us deal with these cases
separately: If $n$ is even, then the above probability may be
rewritten as follows:
\begin{align*}
\sum_{k=\lceil\frac n2\rceil}^n\frac{\binom{k}{2k-n}}{2^k}
&=\frac1{2^n}\left[\binom{n}{n}+2\binom{n-1}{n-2}+4\binom{n-2}{n-4}+\cdots+2^{\frac n2}\binom{\frac n2}0\right]\\
\end{align*}
\item[2.5.18.] {\em Find the number of ways to travel from $(0,0)$ to
$(5,7)$ if any unit steps in the positive $x$ and positive $y$
direction are allowed, except that it is not possible to travel
from $(3,2)$ to $(4,2)$.}
Since a path from $(0,0)$ to $(5,7)$ can be represented as a series
of 12 instructions, 5 of which are ``right'' and 7 of which are
``up'', there are $\binom{12}5$ paths in total. From these, we want
to subtract out those which traverse the edge from $(3,2)$ to
$(4,2)$. Paths traversing this edge are precisely those which pass
through both $(3,2)$ and $(4,2)$, since such a path must follow the
edge between $(3,2)$ and $(4,2)$. We may assemble such a path from
its contituent sub-paths: a path from $(0,0)$ to $(3,2)$, followed
by a path from $(3,2)$ to $(4,2)$, followed by a path from $(4,2)$
to $(5,7)$. There are $\binom52$ ways to select the first path,
$\binom 10$ ways to select the second, and $\binom61$ ways to select
the third. Thus, there are $\binom52\binom10\binom61$ ways to select
three subpaths assembling into a path from $(0,0)$ to $(5,7)$ by way
of $(3,2)$ and $(4,2)$; subtracting that from the total number of
paths, we get that there are
$\binom{12}5-\binom52\binom10\binom61=732$ paths through the grid
that do not visit both $(3,2)$ and $(4,2)$, which is an identical
condition to not traversing the edge from $(3,2)$ to $(4,2)$.
\item[2.6.6.] {\em Consider sequences of length $8$ formed from 2 As,
2 Bs, 2 Cs, and 2 Ds.}
\begin{enumerate}
\item {\em How many of these have no consecutive As?}
We may count the total number of arrangements using the
multinomial coefficient $\binom8{2,2,2,2}$; now let us subtract
out those in which the As {\em are} consecutive. The easiest way
to do that is two consider the As as a cohesive block, so now we
investigate sequences of length $7$ formed from the item A\!\!A as
well as 2 Bs, 2 Cs, and 2 Ds, which can be done in
$\binom7{1,2,2,2}$ ways. Thus, the number of arrangements without
adjacent As is $\binom8{2,2,2,2}-\binom7{1,2,2,2}=1890$.
\item {\em How many of these have two consecutive As and two
consecutive Bs?}
We follow the smae procedure as above, but this time with the
cohesive blocks A\!\!A and B\!\!B together with 2 Cs and 2
Ds. These 6 elements can be arranged in $\binom6{2,2,1,1}=180$
ways.
\end{enumerate}
\item[2.6.10.] {\em What is the probability that a random $3n$-digit
ternary sequence has an equal number of 0s, 1s, and 2s?}
There are $3^{3n}$ ternary sequences with $3n$ digits; of those,
$\binom{3n}{n,n,n}$ consist of equal numbers of 0s, 1s, and
2s. Thus, the probability of having equal numbers of 0s, 1s, and 2s
in a ternary sequence is
$$\frac{\binom{3n}{n,n,n}}{3^{3n}}=\frac{3n!}{3^{3n}(n!)^3}$$
\item[2.6.12.] {\em Find the sum of all the coefficients of
$(w+2x+y+2z)^6$.}
Much as in 2.5.4, the easiest way to find the sum of all the
coefficients is to consider the expansion under the evaluation
$w=x=y=z=1$, and folding that evaluation back into the original,
unexpanded form to get that the sum of the coefficients is
$(1+2+1+2)^6=6^6=46656$.
\item[2.6.14.] {\em If the letters of the word ALGEBRA are randomly
arranged, what is the probability that the two As are together?}
Ignoring the location of every letter except the As, there are
$\binom 72$ ways to locate the As, of which $6$ locate them adjacent
to each other, so this probability is $\frac{6}{\binom
72}=\frac{6}{21}=\frac27$.
Alternatively, one can note, using the same arguments as in 2.6.6,
that there are $\binom 7{2,1,1,1,1,1}=\frac{7!}2$ total
arrangements, and $\binom 6{1,1,1,1,1,1}=6!$ arrangements with the
As adjacent, so the probability of adjacency is $\frac{\binom
6{1,1,1,1,1,1}}{\binom 7{2,1,1,1,1,1}}=\frac27$
\item[\em 2.6.18.] {\em How many arragements are there of 4 As, 4 Bs,
and 4 Cs in which each letter is next to an identical letter?}
If each letter is next to an identical letter, the As can divide
either into pairs or all be collected as a single group of 4 As;
arrangements such as 3 adjacent As and a loner are prohibited by
this condition. Thus, we can really think of such an arrangement of
4 As as an arrangement of 2 A\!\!A blocks; likewise for B and
C. This arrangement is thus no more than an arrangement of 2
A\!\!As, 2 B\!\!Bs, and 2 C\!\!Cs, which can be achieved in
$\binom6{2,2,2}=90$ ways.
Note: this problem would be far more difficult if, instead of 4
instances of each letter, there were 6; then a division into
double-letter pairs would suffice to cover the groupings AA/AA/AA,
AA/AAAA, and AAAAAA, but would not catch the case AAA/AAA.
\end{description}
\end{document}