Homework #1: Text: 1.3:2,3 1.8:6,12,20,21,23,32 2.1:9,12 2.5: 2,3
1.3.2: There are $2^{n-1}$ such subsets. Just choose any subset of the complement, which has $n-1$ elements, and union with that point.
1.3.3: Let the set be $[n]$ with $n$ elements. We give a bijection $\phi$ between the collections of all subsets of even cardinality to the collections of all subsets of odd cardinality. Define $$ \phi(A)= \begin{cases} A-\{n\} \text{ if } n\in A\\ A\cup \{n\} \text{ if } n\notin A. \end{cases} $$
1.8.5: Proof #1: This is $$ \frac{n(n-1)}{2}+\frac{n(n+1)}{2}=n^2. $$ Proof \#2: Let's count the $n^2$ ordered pairs $(x,y).$ If $x\lt y$, this is a subset of size 2, $\binom{n}{2}.$ Otherwise imagine $n$ and 2 bars, and how many stars $(y,x)$ are the left of the two bars. Since $y\ge 1$ we can delete one star, giving $\binom{n+1}{2}.$
1.8.12:(a) the empty set, ends in 3 is odd (b) divisible by 10, 5 and 2 are relatively prime.
1.8.20:No in general. You could an element form each set not in the other, if they exist.
Yes. 2-element subsets of theunion are contained in 2-element subsets of each part.
yes and yes. Any 2-element subset of A and B is a 2-element subset of their intersection.
1.8.21: Drawing a Venn diagram, we see that the choices for $S\cap B$ are $\binom{k}{1}$ and then $2^{n-k}$ choices outside of $B$.
1.8.23: This is just saying each positive integer has a unique binary
expansion.
Proof of existence by induction on n: $n=1=2^0$
Suppose $n=2^{k_1}+2^{k_2}+\cdots+2^{k_a}$, where $k_1\gt k_2\gt\cdots
\gt k_a\gt 0.$
CASE 1: If $k_a\ge 1$, just add $2^0$. (this is the case when $n$ is even.)
CASE 2: If $k_a=0$, change the final string of exponents $0,1,2\cdots,M$ to just
$M+1$. This is correct because $2^0+2^1+\cdots+2^M+1=2^{M+1}.$
Proof of uniqueness: Could there be two such expressions? Cancel all leading terms which are equal in two expressions to where the leading power of $2$ is different. The expression with the larger power of $2$ could never equal the smaller one, because it is greater: $2^M\gt 2^{M-1}+2^{M-2}+\cdots +2^0=2^M-1.$
1.8.32: This is $$ \binom{a-c}{b-c}=2 $$ whose only solution is $\binom{2}{1}$, so $b=c+1$, $a=c+2$.
2.1.9: We have already used this, it is a finte geometric series with ratio 2.
2.1.12: No initial case was verified, in fact this proves that it is always even, using the initial case.
2.5.2: Proof #1: Count pairs $(s,S)$, where $s\in S$ and $S$ is a subset of $[n].$
If you count $S$ first with $k$ elements, there $\binom{n}{k}$ choices, then $k$
choices for $s$. This is the sum over $k$. If you choose $s$ first there are $n$ choices,
and then $2^{n-1}$ subsets $S$ containing $s$.
Proof #2: If you differentiate the binomial theorem and put $x=1$
you get $n2^{n-1}.$
2.5.3: Differentiate the finite geometric series then put x=2.
Additional Problems for HW #1
E1: Let $inv(\pi)$ be the number of inversions of a permutation $\pi=\pi_1\pi_2\cdots \pi_n$. $$ inv(\pi)=|\{(i,j): i\lt j, \pi_i\gt \pi_j\}|. $$ An inversion is a pair of numbers out of order. For example, if $\pi=6257134$, then $inv(\pi)=5+1+3+3+0+0=12.$
(a) If $\pi$ is a permutation on $\{1,2,\cdots,n\}$ of length $n$, what
is the maximum value of $inv(\pi)$?
(b) What is the average value of $inv(\pi)$ over all permutations
of $n$?
(c) How many permutations $\pi$ of $n$ have $inv(\pi)=1$? have
$inv(\pi)=2$?
Solution (a) $\pi=n (n-1)\cdots 1$ has all pairs out or
order, the max is $\binom{n}{2}.$
(b) The average is $\binom{n}{2}/2.$ If we pair each permutation with its reverse, the
average of these two inversion numbers is $\binom{n}{2}/2$ so the entire set has
the same average.
(c) There are $n-1$ with one inversion. Let's prove this by induction on $n$, let
$E_n$ be the number of permutations with 1 inversion. Then $E_1=0, E_2=1$ and
$E_n=E_{n-1}+1$: If $\pi_n=n$, then $\pi_1\pi_2\cdots \pi_{n-1}$ is a permutation
of length $n-1$ with one inversion. Otherwise we must have $\pi_{n-1}=n$, and
$\pi_1\cdots \pi_{n-2} \pi_n$ is a permutation with no inversions, it is
uniquely defined.
There are $\binom{n}{2}-1$ with two inversions for $n \ge 2$.
Let's prove this by induction on $n$,
let $F_n$ be the number of permutations with two inversions. Note that
$F_2=0, F_3=2.$ We will show for $n \gt 3$
$$
F_n=F_{n-1}+(n-3)+1+1
$$
This time there are
three cases.
(i) $\pi_n=n$, so $\pi_1\pi_2\cdots \pi_{n-1}$ is a permutation with two
inversions, $F_{n-1}$ choices.
(ii) $\pi_{n-1}=n.$ If $\pi_n=n-1$, then $\pi_1\pi_2\cdots \pi_{n-2}$ has exactly one
inversion, there are $n-3$ choices by the previous part of this question.
The only other value of $\pi_n$ is $n-2$, and the preceding $n-2$ entries must be
increasing, one choice.
(iii) If $\pi_{n-2}=n$ we must have the remaining $n-1$ entires increasing, one
choice.
The solution to this recurrence is $F_n=\binom{n}{2}-1.$
Proof #2 Use generating functions. By inserting $n$ into a permutation of length $n-1$, the number of inversions increases by $0$, $1, \cdots, n-1$, so $$ \sum_{\pi} x^{inv(\pi)} = (1+x)(1+x+x^2)*\cdots *(1+x+x^2+\cdots + x^{n-1}). $$ This is $$ \frac{(1-x^2)(1-x^3)\cdots (1-x^n)}{(1-x)^{n-1}}. $$ The coefficient of $x^1$ is $n-1$ while the coefficient of $x^2$ is $\binom{n}{2}-1.$
E2: Let $V$ be the complex vector space of homogeneous polynomials of degree $n$ in three variables $x$, $y$, and $z$.
(a) What is $dim(V)$?
(b) What is the answer to (a) if we have $k$ variables instead of $3$
variables?
Solution A basis for $V$ is given by the monomials. So we need just count them. We imagine $n$ and $2$ bars, $\binom{n+2}{2}.$ In general we have $n$ stars and $k-1$ bars, so $\binom{n+k-1}{k-1}.$
E3: Let $a_n$ be the number of non-negative integer solutions
$(e_1,e_2,e_3,e_4)$ to $e_1+e_2+e_3+e_4=n$ such that $e_3$ is even,
$2\le e_2 \le 5$, and $e_4\ge 3.$
(a) What is $A(x)=\sum_{n=0}^\infty a_n x^n$?
(b) Use (a) and calculus to find $a_n.$
Solution $$ A(x)= \frac{1}{1-x}(x^2+x^4+x^5+x^6+x^5)\frac{1}{1-x^2}\frac{x^3}{1-x}. $$ This is $$ \frac{x^5(1-x^4)}{(1+x)(1-x)^4} $$ Since $$ \frac{1}{(1+x)(1-x)^4}=\frac{1}{2(1-x)^4}+\frac{1}{4(1-x)^3}+\frac{1}{8(1-x)^2} +\frac{1}{16(1-x)}+\frac{1}{16(1+x)} $$ has coeffs of $x^n$ of $$ b_n= \frac{1}{2}\binom{n+3}{3}+\frac{1}{4}\binom{n+2}{2}+\frac{1}{8}\binom{n+1}{1} +\frac{1}{16}(1+(-1)^n) $$ the answer is $0$ for $n\lt 5$, $b_{n-5}$ for $5 \le n \lt 9,$ and otherwise $$ b_{n-5}-b_{n-9}. $$
E4: This is a stars and bars question, $n$ stars and $k-1$ bars. Delete 3 stars from each of the $k$ compartment, we now have $n-3k$ stars and $k-1$ bars with no restriction. The answer is $\binom{n-3k+k-1}{k-1}.$