\documentclass[11pt]{article}
\usepackage{amsfonts}
%\pagestyle{empty} %This determines whether the page number appears.
\topmargin -1.00in
\textheight 9in
\oddsidemargin 14pt
\evensidemargin 14pt
\textwidth 440pt
\addtolength{\parskip}{0.5\parskip}
\newcommand{\binom}[2]{$\left( \begin{array}{c} 
#1 \\ #2 \end{array} \right)$}
\newcommand{\nopar}{\hspace{-\parindent}}
\newcommand{\fsp}{\hspace{5em}}
\newcommand{\tsp}{\hspace{3em}}
\newcommand{\osp}{\hspace{1em}}
\newcommand{\Rl}{\bf R}
\newcommand{\remove}[1]{}
\begin{document}
\begin{flushleft}
{\large MATH 642:582--Fall, 2008} \\
{\bf Assignment 1--Due September 25 (Version: September 22)} \\
\end{flushleft}

\parskip=10pt

\begin{itemize}
\item
Please read the guidelines for homework available on the course web page:

\begin{center}
http://www.math.rutgers.edu/~saks/582F08/
\end{center}
\item Please be on the look out for errors.  If something seems not
to make sense, check with me before investing a lot of time on the problem.
\item Stanley, Enumerative Combinatorics, Chapter 1, is a good
reference. 
\end{itemize}


\begin{enumerate}
\item
Define a total ordering on $2^{[n]}$ by $S < T$ if $|S|<|T|$ or
if $|S|=|T|$ and the
largest element in $S \oplus T$ (the symmetric difference $(S-T) \cup (T-S)$)
belongs to $T$. (Not to be handed in:
show that this relation is indeed a total order on ${\cal P}([n])$).
Let $A=\{a_1,a_2, \ldots, a_k\}$ be a $k$-subset 
of $[n]$ with $a_1<a_2< \ldots <a_k$.
Express (with explanation) the number of
sets $B \in {[n] \choose k}$  with $B < A$, as a sum
of binomial coefficients.

\item
Consider the following process: start with the trivial partition
of $[n]$ into one part.  Then apply the following step:
take a part of the partition that has more than one
element and break it into two parts.  Repeat this step
until the resulting partition consists of $n$ singleton blocks.
In how many ways can this be process be carried out?


\item
Let $Q$ be the set of all univariate polynomials  $p(x)$,
that map integers to integers.  
Show that a degree $n$ polynomial $p$ belongs to $Q$ if and only
if it can be written in the form 
$\sum_{i=0}^n a_i {x \choose i}$, where the $a_i$ are integers. (In other
words the polynomials ${x \choose i}$ form a basis for the ${\bf Z}$-module
$Q$.)

\item
A {\em partition
of an integer $n$} (as opposed to a partition of a set) 
is defined  to be a nonincreasing
sequence $\lambda=(\lambda_1,\ldots,
\lambda_k)$ of  positive integers that sum  to $n$.  The numbers
$\lambda_1,\ldots,\lambda_k$ are the {\em parts} of $\lambda$.

Let $m$ be a positive integer.   If $\lambda$ is a partition
of some integer, define $u_m(\lambda)$ to be the number
of integers that occur at least $m$ times in 
$\lambda$.  Let
$v_m(\lambda)$ be the number of parts that  are equal to $m$.
Show that, for fixed $m$, the sum of $u_m(\lambda)$ is
equal to the sum of $v_m(\lambda)$, where  both sums range over 
all partitions of some fixed integer $n$.  


\item
Recall that $B_n$ is the number of partitions of the set $[n]$.
Let $C_n$ be the number of partitions of $[n]$ such
that any two consecutive integers are in different blocks.   
The purpose of this problem is to give two proofs of 
(*) $C_n=B_{n-1}$, for all  $n \geq 1$.
\begin{enumerate}
\item
Prove (*) by giving an explicit bijection between the
sets counted (and carefully prove that it is a bijection).
\item Use recurrence equations to give an alternative proof
of (*) 
\end{enumerate}

\vspace{.2 in}
\begin{center}
Continued on page 2\ldots
\end{center}

\pagebreak
\item
Determine (with explanation)
the connection coefficients for expressing the rising factorials
in terms of falling factorials.  In other words, for each $n \geq 0$,
find coefficients $(a_{n,k}:0 \leq k \leq n)$ so that
$x^{\overline{n}}=\sum_{k=0}^n a_{n,k}x^{\underline{k}}$.
(Connection coefficients will be discussed in class.)

\item
Note: The combinatorial functions $S(n,k)$
and $s(n,k)$ will be defined in class (and are also defined in Stanley's book.)
\begin{enumerate}
\item
Show that $S(n,k)\sim k^n/k!$, provided that $k< \frac{n}{\ln n} $.
(Here we assume that $k$ is a function of $n$, which may be the constant
function).
\item
For fixed $k$,
determine the asymptotic behavior of $s(n,n-k)$ as $n \longrightarrow \infty$.
\item
(Bonus) The asymptotic behavior found in the previous part can be valid
even if $k$ is allowed to grow with $n$, as long
as it does not grow too fast.  Determine how fast $k$ can
grow without invalidating the formula. 

\end{enumerate}

\item
Let $H$ be the set of all real intervals of the form
$I=[a,b)$ where $a <b$ and $a,b$ are integers. Write $\ell(I)$ for the
length of $I$, which is $b-a$. Let
$W(n)$ be the set of all sequences $I_1=[a_1,b_1),\ldots,I_k=[a_k,b_k)$ 
of intervals (where $k$ is not fixed), such that
(1) each $I_j \in H$, (2) $a_1=0$, (3) For each $j \in \{1,\ldots,k-1\}$,
$I_j \cap I_{j+1} \neq \emptyset$ and (4) The sum of the lengths
of the $I_j$ is exactly $n$.  Let $w(n)=|W(n)|$.  (Thus
$w(1)=1$, $w(2)=2$ and $w(3)=6$.)  
The purpose of this problem is
to determine the ordinary generating function for $(w(n))$
and also to find a simple recurrence relation
for $w(n)$.

\begin{enumerate}
\item Let $W_r(n)$ be the set of sequences in $W(n)$ for which $b_1=r$
and let $w_r(n)=|W_r(n)|$.  Determine (with proof) constants
$(c_i(r): i \geq 1,r \geq 1)$ so that:

$$w_r(n)=\sum_{i \geq 1} c_i(r) w_i(n-r),$$
for all $1 \leq r < n$.
\item  Digression: For a formal power series in two variables
$x,y$, $H(x,y)=\sum_{n \geq 1} \sum_{r \geq 1} a(n,r)y^rx^n$ let
$L_1$ be the operator mapping $H(x,y)$ to the univariate
FPS $H(x,1)$
and $L_2$ be the operator mapping $H(x,y)$ to 
$\frac{\partial H}{\partial y}|_{y=1}$.  What conditions do we need
to impose on
$H$ so that these operators make sense as
formal power series operators?

\item Let $f(x,y)=\sum_{n \geq 1} \sum_{r \geq 1} w_r(n) y^rx^n$
and let $g(x)=L_1(f)$ and $h(x)=L_2(f)$.
Determine (with explanation) explicit
rational functions $r_1(x,y)$, $r_2(x,y)$
and $r_3(x,y)$ such that $f(x,y)$ can be expressed in the form:

\begin{eqnarray*}
f(x,y)&=&r_1(x,y)+r_2(x,y)g(x)+r_3(x,y)h(x).
\end{eqnarray*}
(This is somewhat tricky; hints are available upon request.)

\item 
Apply $L_1$ and $L_2$ to both sides of the previous
equation, and solve for $g(x)$ as a rational function.
\item Find a linear recurrence equation satisfied by $w(n)$.
\item (Open, I think.) Find a combinatorial explanation for the
recurrence equation found in the previous part.
\end{enumerate}








\end{enumerate}
\end{document}