% LaTeX solution template for Math 235
% -----------------------------------------------------------------

% Like most advanced LaTeX files, this one begins with a lot of
% boilerplate. You don't need to understand (or even read) most of it.
% All you need to do is fill in your name, email address,
% and the number of the pset. (Search for "METADATA" to find the place
% for this.) Then, you can go straight to the "EXERCISE 1"
% section and start writing your solutions.
% The "VARIOUS USEFUL COMMANDS" section is probably worth taking a
% look at at some point.

% If you are here to learn about LaTeX, search for
% "START READING HERE" and start reading there.

%----------------------------------------------------------------------------------------
%	PACKAGES AND OTHER DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------
\documentclass[paper=a4, fontsize=12pt]{scrartcl} % A4 paper and 12pt font size
\usepackage[T1]{fontenc} % Use 8-bit encoding that has 256 glyphs
\usepackage[english]{babel} % English language/hyphenation
\usepackage{amsmath,amsfonts,amsthm,amssymb} % Math packages
\usepackage{mathrsfs}    % More math packages
\usepackage{sectsty}  % Allows customizing section commands
\allsectionsfont{\centering \normalfont\scshape} % Make all section titles centered, the default font and small caps %remove this to left align section tites
\usepackage{hyperref} % Turns cross-references into hyperlinks,
                      % and defines \url and \href commands.
\usepackage{graphicx} % For embedding graphics files.
\usepackage{framed}   % For the "leftbar" environment used below.
\usepackage{ifthen}   % Used for the \powset command below.
\usepackage{lastpage} % for counting the number of pages
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[height=10in,a4paper,hmargin={1in,0.8in}]{geometry}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}     % This is a powerful tool to draw vector
                      % graphics inside LaTeX. In particular, you can
                      % use it to draw graphs.
\usepackage{verbatim} % For the "verbatim" environment, in which
                      % special symbols can be used freely without
                      % confusing the compiler. (And it's typeset in
                      % a constant-width font.)
                      % Useful, e.g., for quoting code (or ASCII art).

%\numberwithin{table}{section} % Number tables within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)

\setlength\parindent{20pt} % Makes indentation for paragraphs longer.
                           % This makes paragraphs stand out more.

%----------------------------------------------------------------------------------------
%	VARIOUS USEFUL COMMANDS
%----------------------------------------------------------------------------------------
% The commands below might be convenient. For example, you probably
% prefer to write $\powset[2]{V}$ for the set of $2$-element subsets
% of $V$, rather than writing $\mathcal{P}_2(V)$.
% Notice that you can easily define your own commands like this.
% Caveat: Some of these commands need to be properly "guarded" when
% they occur in subscripts or superscripts. So you should not write
% $K_\CC$, but rather $K_{\CC}$.
\newcommand{\CC}{\mathbb{C}} % complex numbers
\newcommand{\RR}{\mathbb{R}} % real numbers
\newcommand{\QQ}{\mathbb{Q}} % rational numbers
\newcommand{\NN}{\mathbb{N}} % nonnegative integers
\newcommand{\Z}[1]{\mathbb{Z}/#1\mathbb{Z}} % integers modulo k
                                            % (syntax: "\Z{k}")
\newcommand{\ZZ}{\mathbb{Z}} % integers
\newcommand{\id}{\operatorname{id}} % identity map
\newcommand{\Fix}{\operatorname{Fix}} % fixed points
\newcommand{\lcm}{\operatorname{lcm}}
% Lowest common multiple. For historical reasons, LaTeX has a \gcd
% command built in, but not an \lcm command. The preceding line
% rectifies that.
\newcommand{\rev}{\operatorname{rev}} % reversal of a walk
\newcommand{\ssum}{\operatorname{sum}} % sum of a set
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
% $\powset[k]{S}$ stands for the set of all $k$-element subsets of
% $S$. The argument $k$ is optional, and if not provided, the result
% is the whole powerset of $S$.
\newcommand{\set}[1]{\left\{ #1 \right\}}
% $\set{...}$ compiles to {...} (set-brackets).
\newcommand{\abs}[1]{\left| #1 \right|}
% $\abs{...}$ compiles to |...| (absolute value, or size of a set).
\newcommand{\tup}[1]{\left( #1 \right)}
% $\tup{...}$ compiles to (...) (parentheses, or tuple-brackets).
\newcommand{\ive}[1]{\left[ #1 \right]}
% $\ive{...}$ compiles to [...] (Iverson bracket, aka truth value).
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
% $\floor{...}$ compiles to |_..._| (floor function).
\newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)}
% $\verts{...}$ compiles to V(...) (vertex set of a graph/digraph).
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
% $\edges{...}$ compiles to E(...) (edge set of a graph).
\newcommand{\arcs}[1]{\operatorname{A}\left( #1 \right)}
% $\arcs{...}$ compiles to A(...) (arc set of a digraph).
\newcommand{\lf}[2]{#1^{\underline{#2}}}
% $\lf{...1}{...2}$ compiles to $...1^{\underline{...2}}$.
% This is a notation for the falling factorial.
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
% $\underbrack{...1}{...2}$ yields
% $\underbrace{...1}_{\substack{...2}}$. This is useful for doing
% local rewriting transformations on mathematical expressions with
% justifications. For example, try this out:
% $ \underbrack{(a+b)^2}{= a^2 + 2ab + b^2 \\ \text{(by the binomial formula)}} $
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}} % Create horizontal rule command with 1 argument of height
\newcommand{\nnn}{\nonumber\\} % Don't number this line in an "align" environment, and move on to the next line.
\newcommand{\explain}[1]{\tup{\hspace{-0.5pc}\text{\begin{tabular}{c}#1\end{tabular}\hspace{-0.5pc}}}}
% $\explain{...}$ interprets the "..." as text (you can
% nest some math inside by putting it in $...$'s as you
% would in any other text block) and puts it in parentheses.

%----------------------------------------------------------------------------------------
%	MAKING SUMMATION SIGNS ALWAYS PUT THEIR BOUNDS ABOVE AND BELOW
%	THE SIGN
%----------------------------------------------------------------------------------------
% The following are hacks to ensure that sums (such as
% $\sum_{k=1}^n k$) always put their bounds (i.e., the $k=1$ and the
% $n$) underneath and above the sign, as opposed to on its right.
% Same for products (\prod), set unions (\bigcup) and set
% intersections (\bigcap). Remove the 8 lines below if you do not want
% this behavior.
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}

%----------------------------------------------------------------------------------------
%	ENVIRONMENTS
%----------------------------------------------------------------------------------------
% The incantations below define how theorem environments
% (\begin{theorem} ... \end{theorem}) and their likes will look like.
\newtheoremstyle{plainsl}% <name>
  {8pt plus 2pt minus 4pt}% <Space above>
  {8pt plus 2pt minus 4pt}% <Space below>
  {\slshape}% <Body font>
  {0pt}% <Indent amount>
  {\bfseries}% <Theorem head font>
  {.}% <Punctuation after theorem head>
  {5pt plus 1pt minus 1pt}% <Space after theorem headi>
  {}% <Theorem head spec (can be left empty, meaning `normal')>

% Environments which make the text inside them slanted:
\theoremstyle{plainsl}
  \newtheorem{theorem}{Theorem}[section]
  \newtheorem{proposition}[theorem]{Proposition}
  \newtheorem{lemma}[theorem]{Lemma}
  \newtheorem{corollary}[theorem]{Corollary}
  \newtheorem{conjecture}[theorem]{Conjecture}
% Environments that don't:
\theoremstyle{definition}
  \newtheorem{definition}[theorem]{Definition}
  \newtheorem{example}[theorem]{Example}
  \newtheorem{exercise}[theorem]{Exercise}
  \newtheorem{examples}[theorem]{Examples}
  \newtheorem{algorithm}[theorem]{Algorithm}
  \newtheorem{question}[theorem]{Question}
 \theoremstyle{remark}
  \newtheorem{remark}[theorem]{Remark}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\begin{small}}{\end{small}}

%----------------------------------------------------------------------------------------
%	METADATA
%----------------------------------------------------------------------------------------
\newcommand{\myname}{Darij Grinberg} % ENTER YOUR NAME HERE
\newcommand{\mymail}{darij.grinberg@drexel.edu} % ENTER YOUR EMAIL HERE
\newcommand{\psetnumber}{7} % ENTER THE NUMBER OF THIS PSET HERE

%----------------------------------------------------------------------------------------
%	HEADER AND FOOTER
%----------------------------------------------------------------------------------------
\ihead{Solutions to homework set \#\psetnumber} % Page header left
\ohead{page \thepage\ of \pageref{LastPage}} % Page header right
\ifoot{\myname} % left footer
\ofoot{\mymail} % right footer

%----------------------------------------------------------------------------------------
%	TITLE SECTION
%----------------------------------------------------------------------------------------
\title{	
\normalfont \normalsize 
\textsc{Drexel University, Department of Mathematics} \\ [25pt] % Your university, school and/or department name(s)
\horrule{0.5pt} \\[0.4cm] % Thin top horizontal rule
\huge Math 235: Mathematical Problem Solving, \\
Fall 2024:
Homework \psetnumber\\% The assignment title
\horrule{2pt} \\[0.5cm] % Thick bottom horizontal rule
}
\author{\myname}

\begin{document}

\maketitle % This command causes the title part to be printed.

\begin{center}
{\Large
\textbf{Please solve 3 of the 8 exercises!} \\[0.7pc]
\textbf{Deadline:} November 27, 2024} \\[0.7pc]
{\large
Recall that $\ive{k} := \set{ 1,2,\ldots,k }$ for each $k \in \NN$.
}
\end{center}

%----------------------------------------------------------------------------------------
%	EXERCISE 1
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 1}

\subsection{Problem}

Let $n$ be a positive integer. A subset $S$ of
$\ive{n}$ is said to be \emph{cyclically lacunar} if
it is lacunar\footnote{Recall that a set of
integers is said to be \emph{lacunar} if it contains
no two consecutive integers.} and also satisfies
$\set{1, n} \not \subseteq S$ (that is,
$1\notin S$ or $n\notin S$). (In other words, if we
arrange the numbers $1, 2, \ldots, n$ in this order
on a circle, then a cyclically lacunar subset is a
subset that contains no two adjacent numbers.)

Let $k \in \set{ 0,1,\ldots,n-1 }$.
Prove that the \# of cyclically lacunar
$k$-element subsets of $\ive{n}$ is
$\dfrac{n}{n-k} \dbinom{n-k}{k}$.

\subsection{Remark}

Compare with the formula $\dbinom{n-k}{k}$ for
the \# of lacunar $k$-element subsets of $\ive{n-1}$.
This formula appeared in the proof of
Proposition 4.3.20 in
\href{https://www.cip.ifi.lmu.de/~grinberg/t/20f/mps.pdf}{the notes},
and can be used without proof.

\subsection{Solution}

...

%----------------------------------------------------------------------------------------
%	EXERCISE 2
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 2}

\subsection{Problem}

Let $n \in \NN$.

\begin{enumerate}

\item[\textbf{(a)}] Find an explicit formula for
\[
\sum_{k=0}^{n} \dfrac{\dbinom{n}{k}^2}{\dbinom{2n}{2k}}.
\]

\item[\textbf{(b)}] Find an explicit formula for
\[
\sum_{k=0}^{n} \dbinom{n}{k} k\wr \tup{n-k}\wr,
\]
where $m\wr$ denotes the product of the first $m$
odd positive integers (that is,
$1 \cdot 3 \cdot 5 \cdot \cdots \cdot \tup{2m-1}$).

\end{enumerate}

\subsection{Solution}

...

%----------------------------------------------------------------------------------------
%	EXERCISE 3
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 3}

\subsection{Problem}

Let $N \in \NN$. Let $\tup{f_0, f_1, \ldots, f_N}$
and $\tup{g_0, g_1, \ldots, g_N}$ be two $N$-tuples
of numbers. Assume that
\[
g_n = \sum_{i=n}^{N} \tup{-1}^i \dbinom{i}{n} f_i
\qquad \text{for every } n \in \set{0, 1, \ldots, N}.
\]
Prove that
\[
f_n = \sum_{i=n}^{N} \tup{-1}^i \dbinom{i}{n} g_i
\qquad \text{for every } n \in \set{0, 1, \ldots, N}.
\]

\subsection{Remark}

This is a ``mirror version'' of binomial inversion
(Exercise 7.7.8 in
\href{https://www.cip.ifi.lmu.de/~grinberg/t/20f/mps.pdf}{the notes}).

\subsection{Solution}

...

%----------------------------------------------------------------------------------------
%	EXERCISE 4
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 4}

\subsection{Problem}

Let $n$ be a positive integer.

\begin{enumerate}

\item[\textbf{(a)}]
A number $i \in \set{ 1,2,\ldots,n-1 }$ is called a
\emph{descent} of a permutation $w \in S_n$ if it
satisfies $w\tup{i} > w\tup{i+1}$. Compute the
average number of descents in a (uniformly random)
permutation $w \in S_n$. (That is, compute
$\dfrac{1}{n!} \sum_{w \in S_n}
\tup{\text{\# of descents of } w}$.)

\item[\textbf{(b)}]
A number $i \in \set{ 2,3,\ldots,n-1 }$ is called a
\emph{peak} of a permutation $w \in S_n$ if it
satisfies $w\tup{i-1} < w\tup{i} > w\tup{i+1}$.
Compute the average number of peaks in a (uniformly
random) permutation $w \in S_n$.

\end{enumerate}

\subsection{Hint}

Recall linearity of expectation.

\subsection{Solution}

...

%----------------------------------------------------------------------------------------
%	EXERCISE 5
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 5}

\subsection{Problem}

Let $n, m \in \NN$.

A function $f : \ive{n} \to \ive{m}$ is said to be
\emph{Smirnov} if $f\tup{i} \neq f\tup{i+1}$ for all
$i \in \ive{n-1}$. (In other words, $f$ is Smirnov
if and only if the $n$-tuple
$\tup{f\tup{1}, \ f\tup{2}, \ \ldots, \ f\tup{n} }$
is Smirnov, according to Definition 7.3.11 in
\href{https://www.cip.ifi.lmu.de/~grinberg/t/20f/mps.pdf}{the notes}.)

For any function $f : \ive{n} \to \ive{m}$, we let
$\Fix f := \set{ x \in \ive{n}\ \mid\ f\tup{x} = x }$.
(This is a slight extension of Definition 7.4.5 in
\href{https://www.cip.ifi.lmu.de/~grinberg/t/20f/mps.pdf}{the notes}.)

Prove that
\[
\sum_{\substack{f : \ive{n} \to \ive{m} \\ \text{is
Smirnov}}} \abs{\Fix f}
= \min\set{n,m} \cdot \tup{m-1}^{n-1}.
\]

\subsection{Solution}

...

%----------------------------------------------------------------------------------------
%	EXERCISE 6
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 6}

\subsection{Problem}

If $a$ and $b$ are two integers, then $\ive{a,b}$
shall denote the set $\set{a, a+1, a+2, \ldots, b}
\subseteq \ZZ$ (which is empty if $a > b$).

A function $f : \ive{a,b} \to \ive{c,d}$ is said to
be \emph{weakly increasing} if $f\tup{a} \leq
f\tup{a+1} \leq \cdots \leq f\tup{b}$. (This is
understood to be automatically satisfied when
$a \geq b$.)

\begin{enumerate}

\item[\textbf{(a)}]
Let $n,m \in \NN$. Prove that the \# of weakly
increasing functions $f : \ive{1,n} \to \ive{1,m}$
equals $\dbinom{n+m-1}{n}$.

\item[\textbf{(b)}]
Let $n$ be a positive integer. Prove that
\[
\sum_{\substack{f : \ive{1,n} \to \ive{1,n}\\
\text{is weakly increasing}}} \abs{\Fix f}
= 4^{n-1},
\]
where
$\Fix f := \set{ x \in \ive{1,n}\ \mid\ f\tup{x} = x }$.

\end{enumerate}

\subsection{Solution}

...


%----------------------------------------------------------------------------------------
%	EXERCISE 7
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 7}

\subsection{Problem}

If $S$ is a finite set of integers, then $\ssum S$
shall mean the sum of all elements of $S$ (that is,
$\sum_{s\in S} s$).

For any $n \in \NN$, we let
\begin{align*}
a_n &:= \tup{ \text{\# of subsets } S \text{ of }
\ive{n} \text{ satisfying } 2 \mid \ssum S}
\qquad \text{and} \\
b_n &:= \tup{ \text{\# of subsets } S \text{ of }
\ive{n} \text{ satisfying } 3 \mid \ssum S }.
\end{align*}
(For instance, $b_4 = 6$, since the subsets of
$\ive{4}$ whose sum of elements is divisible by $3$
are $\varnothing$, $\set{ 3 }$, $\set{ 1,2 }$,
$\set{ 2,4 }$, $\set{ 1,2,3 }$ and $\set{ 2,3,4 }$.)

\begin{enumerate}

\item[\textbf{(a)}]
Prove that $a_n = 2^{n-1}$ for each $n \geq 1$.

\item[\textbf{(b)}]
Prove that $b_n = 2b_{n-3} + 2^{n-2}$ for any
$n \geq 3$.

\item[\textbf{(c)}]
Prove that $b_n = 2b_{n-1} - \ive{3 \mid n-1}
\cdot 2^{\tup{n-1}/3}$ for any $n \geq 1$.
(Here, $\ive{3 \mid n-1}$ denotes the truth value
of $3 \mid n-1$ -- that is, the number $1$ if
$3 \mid n-1$ and the number $0$ otherwise.)

\end{enumerate}

\subsection{Remark}

The sequence $\tup{b_0, b_1, b_2, \ldots}$ is
\href{https://oeis.org/A068010}{Sequence A068010 in the OEIS}.
An explicit formula -- with a case distinction
based on $n \% 3$ -- could be derived from part
\textbf{(c)}, but would not be particularly aesthetic.

\subsection{Solution}

...


%----------------------------------------------------------------------------------------
%	EXERCISE 8
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 8}

\subsection{Problem}

Let $n \in \NN$ be even.

An $n$-tuple $a = \tup{a_1, a_2, \ldots, a_n} \in
\set{1,-1}^n$ consisting of $1$'s and $-1$'s is
said to be \emph{balanced} if
$a_1 + a_2 + \cdots + a_n = 0$ (that is, if there
are equally many $1$'s and $-1$'s in the $n$-tuple).

\begin{enumerate}

\item[\textbf{(a)}]
Prove that the \# of balanced $n$-tuples $a \in
\set{1,-1}^n$ is $\dbinom{n}{n/2}$.

\end{enumerate}

If $a = \tup{a_1, a_2, \ldots, a_n} \in \set{1,-1}^n$
is a balanced $n$-tuple, then a
\emph{break-even point} of $a$ means a number
$k \in \set{0, 1, \ldots, n}$ such that
$a_1 + a_2 + \cdots + a_k = 0$.
Note that $0$ and $n$ always are break-even
points of $a$, but there may be more (e.g., the
number $4$ is a break-even point of
$\tup{1,1,-1,-1,1,-1}$).

\begin{enumerate}

\item[\textbf{(b)}]
Prove that any break-even point of a balanced
$n$-tuple $a \in \set{ 1,-1 }^n$ is even.

\item[\textbf{(c)}]
Prove that the average number of break-even
points of a (uniformly random) balanced $n$-tuple
$a \in \set{ 1,-1 }^n$ is $2^n / \dbinom{n}{n/2}$.
In other words, prove that
\[
\sum_{\substack{a \in \set{ 1,-1 }^n \\
\text{is balanced}}}
\tup{\text{\# of break-even points of }a}
= 2^n.
\]

\end{enumerate}

\subsection{Solution}

...


\horrule{0.3pt} \\[0.4cm]

\begin{thebibliography}{99999999}                                                                                         %
\end{thebibliography}

\end{document}

