\documentclass{amsart}
\usepackage{amssymb}
\usepackage{amsfonts}

\newcommand{\abs}[1]{\left|#1\right|}
\newcommand{\prob}[1]{\mathbb{P}\left(#1\right)}

\begin{document}



\noindent \textbf{Problem $2$:} If a permutation $a_1 a_2 \cdots a_n$ has inversion table $(b_1,b_2,\cdots b_n)$ what is the permutation that corresponds to the inversion table $(n-1-b_1, n-2-b_2,\cdots 0-b_n)$?

The answer is the ``reverse'' permutation $a_n a_{n-1} \cdots a_1$,
our original permutation written backwards.  \newline Let $k=a_j$ in
the permutation $a_1 a_2 \cdot a_n$.  Then $b_k$ denotes the number of
elements in the set $\{a_i$| $a_i>k$ and $i<j\}$.  Thus given $k$,
there are $b_k$ elements to the left of $k$ that are bigger than $k$
in the permutation $a_1 a_2 \cdots a_n$.  Note that in total, there
are $n-k$ elements which are greater than $k$ in the permutation,
since the entries of the permutation run from $1$ to $n$. Thus, it is
implied that there are $n-k-b_k$ elements to the right of $k$ which
are greater than $k$.  Now consider what happens when we reverse this
permutation.  Every element that was to the left of $k$ is now to the
right of $k$, which implies that in the reverse permutation there are
now $n-k-b_k$ elements to the left of $k$ bigger than $k$ which means
that the $k^{th}$ entry of the inversion table for the reverse
permutation is $n-k-b_k$, which was to be shown.  Note that this is
the unique answer becuase each permutation has a unique inversion
table, as was shown in class.

\section*{Problem 3}
\subsection{solutions}

We have recurrence relation that implies that $A(x)-x=4xA(x)-5x^2A(x)$,
thus we get a rational generating function 

$$A(x)=\frac{1}{1-4x+5x^2}$$

One needs to find the partial fraction decomposition of the right hand
side. At the end one can recover an expression

$$A(x)=\frac{i}{2} \sum_{n \geq 0} \frac{x^n}{a^n}- \frac{i}{2} \sum_{n\geq 0} \frac{x^n}{b^n}$$ 

where $a=0.4+0.2i$ and $b=0.4-0.2i$. We now can find the coefficient of
$x^n$ in $a_n$ to be 

$$ a_n=\frac{i}{2}(\frac{1}{a^n}-\frac{1}{b^n}).$$

Other formulas can be extracted from this one.

\section*{Problem 4}
Using generating functions, find an explicit formula for $a_n=na_{n-1}+(-1)^n$ and $a_0=1$.\\
Let
$$ f(x)=\sum_{n=0}^\infty \frac{a_nx^n}{n!}$$\\
$a_0=1$
$$ f(x)=\sum_{n=1}^\infty \frac{a_nx^n}{n!} +1$$
Substituting $na_{n-1}+(-1)^n$ for $a_n$, we have:
$$f(x)=\sum_{n=1}^\infty \frac{na_{n-1}x^n}{n!} + \sum_{n=0}^\infty \frac{(-1)^nx^n}{n!}$$\\
$$= \sum_{n=1}^\infty \frac{a_{n-1}x^n}{(n-1)!} + \sum_{n=0}^\infty \frac{(-1)^nx^n}{n!}$$\\
$$= x\sum_{n=0}^\infty \frac{a_nx^n}{n!} + \sum_{n=0}^\infty \frac{(-1)^nx^n}{n!}$$\\
$$= xf(x) + e^{-x}$$
So $f(x)$ is the exponential generating function times a geometric sum: 
$$f(x)=\frac{e^{-x}}{1-x} = (\sum_{n=0}^\infty \frac{(-x)^n}{n!})(\sum_{n=0}^\infty x^n)=\sum_{n=0}^\infty (\sum_{k=0}^n \frac{(-1)^k}{k!})x^n$$\\
$$\frac{a_n}{n!}=\sum_{k=0}^n \frac{(-1)^k}{k!}$$\\
$$a_n=n!\sum_{k=0}^n \frac{(-1)^k}{k!}$$\\\\


\section{Problem 5}
What is the number of Permutations in $S_n$ that there is no triple $i<j<k$
with $\pi(j)<\pi(i)<\pi(k)$?
\subsection{Solution}

Let $\bar{\pi}$ denote the number of those integers $1 \leq j \leq i$
with $\pi(j) \geq \pi(i)$. We will use this variation of inversion to
provide the answer.
If there is no triple $i <j <k$  with $\pi(j)<\pi(i)<\pi(k)$, then each
$i<j$ such that $\pi(i) > \pi(j)$ also satisfies $\pi(i) > \pi(j+1)$;
thus $\bar{\pi}$ is a monotone increasing vector. 
Conversely if $\bar{\pi}$ is monotone, then there no  triple $i<j<k$
with $\pi(j)<\pi(i)<\pi(k)$. To see this proceed by contradiction.
Consider the portion $\pi(j),\pi(j+1),\dots,\pi(k)$. In this sequence
there must be two consecutive terms $\pi(l), \pi(l+1)$ such that 
$\pi(l) <\pi(i) < \pi(l+1)$. Then for any $v <l+1$  with $\pi(v) > \pi(l+1)$
also satisfies $\pi(v) > \pi(l)$. Moreover $i$ itself satisfies $i<l$ and
$\pi(i) <\pi(l+1)$. Thus $\bar{\pi(l)} > \bar{\pi(l+1)}$, a contradiction.

Thus, the number we seek is equal to the
numbe of monotone mappings of $\{1,\dots,n\}$ into itself such that $1\leq \phi(i) \leq i$. 

We have counted a similar number before, but with the second condition we
get $\frac{1}{n+1}{ 2n \choose n}$.

\section{problem 6}

For two generating functions $f,g$ let $N,M$ be the least-order non-zero
term indexes for $f,g$ respectively. Then 

$$f=x^N \sum_{n=0} a_{n+N}x^n, \ g(x)=x^M \sum_{m=0} b_{m+M}x^m$$

and $a_N,b_M$ are non-zero. Therefore when we multiply $fg$.

$$fg:=x^{N+M} \sum c_n x^n$$

where $c_n=\sum_{k=0}^n a_{k+N} b_{n-k+M}$. In particular $c_0=a_N b_M$ so
$fg$ is not zero. Hence the ring of formal power series is an integral
domain.  Its quotient field is the field of formal Laurent series. 

\section{problem 7}

Solutions for this problem are in most books in basic combinatorics.
I recommend learning about Pr\"ufer codes.

\section{problem 8}

\subsection{solutions}
We first we find a recurrence for the Bell numbers.
Let $S$ be the set to be partitioned and $x \in S$. If the class
containing $x$ has $k$ elements, it can be chosen in ${n-1 \choose k-1}$
ways and the remaining $n-k$ elements can be partitioned in $B_{n-k}$ ways.
So the number of partitions in which the class containing $x$ has $k$ elements
is ${n-1 \choose k-1} B_{n-k}$. This remains true for $k=n$ if we set $B_0=1$.
Thus
$$ B_n=\sum_{k=1}^n {n-1 \choose k-1} B_{n-k}= \sum_{k=0}^{n-1} { n-1 \choose k}B_k$$

Next we prove that the
exponential generating function of $B_n$ is

$$ p(x)=\sum_{n=0}^{\infty} \frac{B_n}{n!} x^n=e^{e^x-1}$$

We saw a fast solution using the composition of generating functions.
But we can also use direct elementary calculations.

$ p(x)=\sum_{n=0}^{\infty} \frac{B_n}{n!} x^n= 1+ \sum_{n=1}^\infty \frac{x^n}{n!} \sum_{k=0}^{n-1} {n-1 \choose k} B_k$

This is equal to

$1+\sum_{k=0}^\infty \frac{B_k}{k!} \sum_{n=k+1}^\infty \frac{x^n}{n} \frac{1}{(n-k-1)!}$, and thus for the derivative

$p'(x)=\sum_{k=0}^\infty \frac{B_k}{k!} \sum_{n=k+1}^\infty \frac{x^{n-1}}{(n-k-1)!}=\sum_{k=0}^\infty \frac{B_kx^k}{k!} \sum_{r=0}^\infty \frac{x^r}{r!}=p(x)e^x$

In other words $(log(p(x)))'=\frac{p'(x)}{p(x)}=e^x$, and $p(x)=e^{e^x+c}$.
For some constant c, which can be determined by setting $x=0$:

$1=p(0)=e^{e^0+c},$ $c=-1$. Thus we have $p(x)=e^{e^x-1}$.

\end{document}
