% LaTeX solution template for Math 222 (Owen Levin, Darij Grinberg)
% -----------------------------------------------------------------

% 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{\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{\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{\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}{0} % 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 222: Enumerative Combinatorics, \\
Fall 2019:
Homework \psetnumber\\% The assignment title
\horrule{2pt} \\[0.5cm] % Thick bottom horizontal rule
}
\author{\myname}

\begin{document}

% START READING HERE.

% LaTeX documents properly begin at the "\begin{document}"
% line. Everything before it is called the "header" and
% serves to set options, define macros and import packages,
% and also to specify metadata (title, author, date, etc.).
% Usually, you don't need to deal with the header;
% just copy it into your own file and make the changes you
% need (like replacing the author name).

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

This document serves several purposes:

\begin{enumerate} % This command creates a numbered list.

\item demonstrate how mathematical prose is written
      in \LaTeX.
      % "\LaTeX" prints the logo of LaTeX.
      % Arguably the least useful LaTeX command, but
      % if there's a place where it fits, it's here;

\item introduce some basic conventions and facts that will
      be used in this combinatorics class, such as
      the product rule (see the solution of Exercise 1
      below) or the telescope principle (see the solution
      of Exercise 2 below) or the conventions for
      empty sums and empty products.
      % Did you notice something?
      % The way we broke our lines here does not affect
      % how the lines are broken in the final PDF.
      % For example, there is no linebreak between
      % "will" and "be" in the PDF.
      % Instead, LaTeX breaks lines where it considers
      % it most appropriate. (This is similar to HTML.)
      % If you want to manually override this, use the
      % command "\\" (or, equivalently, "\newline") to
      % force a real linebreak.
      % Also, as we will see later, while LaTeX ignores
      % a single linebreak in the sourcecode, it does
      % not ignore two consecutive linebreaks (i.e., an
      % empty line); it treats them as signalling the
      % start of a new paragraph;

\item give examples of rigorous proofs in combinatorics
        (as opposed to handwavy explanations that the
   reader either ``gets'' or doesn't).
      % As you see here, LaTeX doesn't care about how
      % (or if) we are indenting the lines in the "\item"s.
      % The indentation in the PDF is automatic.

\end{enumerate} % This ends the list.

Some caveats are in order.
The use of \LaTeX\ is highly recommended
% Why the backslash after "\LaTeX"? Because otherwise,
% the whitespace that follows this command would be
% considered as being merely as signaling the end of
% the command, rather than as a real whitespace.
% (So you would not be seeing a whitespace in the PDF.)
but not required; simple or short arguments can be
written equally well in systems like Microsoft Office
or even as plain text
(\LaTeX\ is best for long-form with lots of formulas,
cross-references and citations).
The proofs given below are, in many ways, more rigorous
and detailed than necessary; they intend to alert you
to the tacit details ``under the hood'' of many
common-sense arguments,
but you don't have to write at this level of detail.

%----------------------------------------------------------------------------------------
%	EXERCISE 1
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]
% This "\horrule" is just a horizontal line that separates
% different exercises.

\section{Exercise 1}

\subsection{Problem}

% By all means, read the code and comments below if you want to
% learn how to use LaTeX.
% Ideally, you should have the PDF output file open (or printed
% out) while doing so, so you can see what code leads to what
% output.
% Comments in LaTeX (i.e., things that do not effect the output
% PDF) are marked with "%" signs. More precisely: On each line,
% everything from the first "%" sign on gets ignored.
% Thus, for example, the lines you are currently reading get
% ignored entirely. Don't go looking for them in the PDF.
% (There is an exception: If a "%" sign is part of a "\%", then
% it does not mark the start of a comment, but rather gets
% compiled into an actual percentage sign.)
% Now let us actually write some output:

Let $n \in \NN$.
% "\in" is the symbol for "element of". It looks a bit like an epsilon,
% but it is not an epsilon! So don't use "\epsilon" for it.
% "\NN" is an abbreviation for "\mathbb{N}", and stands for the
% set of all nonnegative integers.
% Finally, the dollar signs ("$") switch between text mode
% (used for text) and math mode (used for mathematical symbols
% and formulas, at least when these formulas are "inline" as
% opposed to "displayed" -- see below for that).
(Here and in the following, $\NN$ stands for the set $\set{0, 1, 2, \ldots}$.)
% The "\set{...}" command puts the "..." in set-braces.
% The "\ldots" command gives an ellipsis that looks a bit better than what you
% would get by just writing "...". It's mostly a matter of taste.

\begin{enumerate} % This creates a list.

\item[\textbf{(a)}]
% "\item[\textbf{(a)}]" starts the first item of the list, and names
% (or numbers) it by a boldfaced "(a)".
% (The "\textbf{...}" part is responsible for making it boldfaced.)
Show that the number of all subsets of $\set{1, 2, \ldots, n}$ is $2^n$.

\item[\textbf{(b)}]
A \textit{composition} of $n$ shall mean a
list\footnote{``List'' means the same as ``tuple'';
              lists are always ordered and finite.}
% "\footnote" does what you would expect it to do.
% Caveat: You cannot put a \footnote inside a mathematical
% expression or formula. (But you shouldn't anyway -- it would
% look like an exponent.)
$\tup{i_1, i_2, \ldots, i_k}$
of positive integers such that $i_1 + i_2 + \cdots + i_k = n$.
% The "\tup{...}" command puts the "..." in parentheses.
% The "\cdots" is the "right" way to get a vertically centered ellipsis.
(For example, the compositions of $3$ are
$\tup{3}$, $\tup{1, 2}$, $\tup{2, 1}$ and $\tup{1, 1, 1}$.)

Show that the number of all compositions of $n$ is
\[  % These "\[" and "\]" brackets are one way to delimit
    % a "displayed" formula.
    % "Displayed" means that it will be put on its own line
    % and centered, as opposed to "inline" formulas (which
    % are just put between the rest of the line).
\begin{cases}
2^{n-1}, & \text{ if } n > 0 ; \\
1,       & \text{ if } n = 0 .
\end{cases}
\]
% Note that we had to write "2^{n-1}", not "2^n-1", in order to get
% the whole of "n-1" into the exponents, rather than just the "n".
% For example, 2^{3-1} = 2^2 = 4 whereas 2^3-1 = 8-1 = 7.
% 
% "\text{...}" is a way to write text inside a mathematical expression.
% 
% The "&" character vertically aligns symbols on different rows.
% (Here, we have used it in the "cases" environment; it works
% similarly in "align" environments. In tables/matrices, it
% separates columns from each other.)

\end{enumerate} % This ends the list.

\subsection{Solution}

% The following solution is wordy and tries to be pedagogical.
% You don't need all that detail and all that exposition.
% See the solutions to the other two exercises for examples
% of more concise writing.

Let us first introduce two shorthand notations:

\begin{enumerate}

\item[\textbf{1.}]
If $\mathcal{A}$ is any statement (such as ``$1 + 1 = 2$''
% "\mathcal{A}" gives a calligraphic "A".
% You can use this with any other uppercase letter, too.
or ``$1 + 1 = 1$'' or ``there exist infinitely many primes''),
then $\ive{\mathcal{A}}$ stands for the number
% "\ive{...}" puts the "..." in square brackets.
% The name of this command refers to the "Iverson bracket notation",
% which is how this shorthand notation is called.
\[
\begin{cases}
1, & \text{ if } \mathcal{A} \text{ is true} ; \\
0, & \text{ if } \mathcal{A} \text{ is false} .
\end{cases}
\]
This number belongs to $\set{0, 1}$, and
is called the \textit{truth value} of $\mathcal{A}$.
For example,
\[
\ive{1 + 1 = 2} = 1, \qquad
% "\qquad" (short for "double quadratone") a few centimeters of white space.
% It is common to use this to separate different formulas written on the same
% line. There is also "\quad", which is half as long.
\ive{1 + 1 = 1} = 0, \qquad
\ive{\text{there exist infinitely many primes}} = 1.
\]
This shorthand is called the \textit{Iverson bracket notation}.

\item[\textbf{2.}]
If $m \in \ZZ$, then $\ive{m}$ shall mean the set $\set{1, 2, \ldots, m}$.
% Note that we are using "\ive{...}" here even though this is
% no longer the Iverson bracket notation.
% It would be slightly better to define a different command for it
% even though the output should be the same.
When $m \leq 0$, this is understood to be the empty set.

\end{enumerate}

These two shorthand notations use the same symbol (square brackets), but they
will never clash, since the former always has a statement inside the square
brackets, whereas the latter always has an integer inside the square brackets.

Recall the following basic principle (known as the \textit{product rule}):

\begin{proposition}
If $m \in \NN$, and if $A_1, A_2, \ldots, A_m$ are $m$ finite sets, then
the Cartesian product $A_1 \times A_2 \times \cdots \times A_m$ is a finite
set again, and satisfies
\begin{equation}
\abs{A_1 \times A_2 \times \cdots \times A_m}
= \abs{A_1} \cdot \abs{A_2} \cdot \cdots \cdot \abs{A_m} .
% "\abs{...}" puts the "..." inbetween "|" brackets.
% This is used for absolute values of numbers and for sizes of sets
% (here, it's the latter).
% 
% Do you write "\cdot \cdots \cdot" or just "\cdots" in the product?
% Matter of taste.
\label{exe1.sol.prod-rule}
% The "\label{...}" command gives a label to the equation.
% This label can later be used to refer to this equation
% (search for "\eqref{exe1.sol.prod-rule}" below).
% Note that you have to use "\begin{equation}" and "\end{equation}"
% (not "\[" and "\]") to delimit this equation if you want to give
% it a label.
% Also note that you have to compile a TeX file TWICE in order for
% the references to show up correctly.
\end{equation}
\end{proposition}

(Note that if $m = 0$, then the Cartesian product
$A_1 \times A_2 \times \cdots \times A_m$ has $0$ factors;
in this case it just consists of a single element, which is the $0$-tuple
$\tup{}$.
Meanwhile, in this case, the right hand side of \eqref{exe1.sol.prod-rule}
becomes a product of $0$ numbers, which is $1$ by definition.
Thus, \eqref{exe1.sol.prod-rule} turns into ``$1 = 1$'' when $m = 0$.)
% "``" and "''" are the ways to get opening and closing quotation marks
% in LaTeX. Some editors (e.g. Kile) will automatically generate these
% for you when you try to type usual "" quotation marks.
% Anyway, usual quotation marks also work -- they just look a bit worse.

% Note the empty line we just left. This tells LaTeX to start a new
% paragraph.
Applying \eqref{exe1.sol.prod-rule} to $m = n$ and $A_i = \set{0, 1}$,
we get
\[
\abs{\underbrace{\set{0, 1} \times \set{0, 1} \times \cdots \times \set{0, 1}}_{n \text{ factors}}}
= \underbrace{\abs{\set{0, 1}} \cdot \abs{\set{0, 1}} \cdot \cdots \cdot \abs{\set{0, 1}}}_{n \text{ factors}} .
\]
% "\underbrace{...}_{...}" draws a brace under the first "..." and puts the second "..."
% under this brace (in a smaller font). Just see how the above looks like in the PDF!
% 
% Also, note that there are two whitespaces in "n \text{ factors}", but only
% the second one is visible in the PDF. That's because whitespaces *in math mode*
% are mostly ignored, whereas those inside "\text" are treated like regular
% whitespaces.
This rewrites as
\begin{equation}
\abs{\set{0, 1}^n}
= \abs{\set{0, 1}}^n .
\label{exe1.sol.pow-n.1}
\end{equation}
Here, we are using the standard notation $S^n$ (where $S$ is a set and $n \in \NN$)
for the Cartesian product
$\underbrace{S \times S \times \cdots \times S}_{n \text{ factors}}$.
In view of $\abs{\set{0, 1}} = 2$, we can rewrite \eqref{exe1.sol.pow-n.1} as
\begin{equation}
% Tired of writing "\begin{equation}" and "\end{equation}" all the time?
% Some editors (like Kile) will automatically let you "tab-complete"
% "\begin{equation}" when you start writing it, and will also automatically
% end the matching "\end{equation}" after it.
\abs{\set{0, 1}^n} = 2^n .
\label{exe1.sol.pow-n.2}
\end{equation}
Note that $\set{0, 1}^n$ is the set of all $n$-tuples of elements of
$\set{0, 1}$. These are also known as ``binary strings of length $n$''.
For example, $\tup{0, 1, 1, 0, 1, 0} \in \set{0, 1}^6$.

Another basic principle (some call it the \textit{bijection principle})
is the following:

\begin{proposition}
If $X$ and $Y$ are two sets,
and if $f : X \to Y$ is a bijection (i.e., a bijective map), then
\begin{equation}
\abs{X} = \abs{Y} .
\label{exe1.sol.bij-size}
\end{equation}
In other words, if there is a bijection between two sets, then these two sets have
the same size.
\end{proposition}

Note that the size of a set is in general just a
\href{https://en.wikipedia.org/wiki/Cardinal_number}{cardinal number}.
% This is an example of a hyperlink created by the "\href" command.
% The general syntax is "\href{URL}{text}". If you want just the URL
% itself to appear, you can also use "\url{URL}".
But if the set is finite, this cardinal number is an actual nonnegative integer.

Part \textbf{(a)} of the exercise asks us to show that
the number of all subsets of $\set{1, 2, \ldots, n}$ is $2^n$.
In other words, it asks us to show that
the number of all subsets of $\ive{n}$ is $2^n$
(since $\ive{n} = \set{1, 2, \ldots, n}$).
In other words, it asks us to show that
\begin{equation}
\abs{\set{\text{subsets of } \ive{n}}}
= 2^n .
\label{exe1.sol.a.claim}
% You really don't have to follow my style of labeling equations.
% "\label{1}" or "\label{blah}" does the trick just as well, as long
% as the labels are distinct.
\end{equation}

We will show this by constructing a bijection from the set
$\set{\text{subsets of } \ive{n}}$ to $\set{0, 1}^n$.
This will then let us apply \eqref{exe1.sol.bij-size} and \eqref{exe1.sol.pow-n.2}
and obtain \eqref{exe1.sol.a.claim}.
So let us construct such a bijection:

We define the map $A : \set{\text{subsets of } \ive{n}} \to \set{0, 1}^n$
by setting
\[
A \tup{S}
= \tup{ \ive{1 \in S}, \ive{2 \in S}, \ldots, \ive{n \in S} }
\qquad \text{for each subset } S \text{ of } \ive{n} .
\]
% Sure, you can write "A(S)" instead of "A \tup{S}". This is just a matter of style.
(This is well-defined, since each of the truth values
$\ive{1 \in S}, \ive{2 \in S}, \ldots, \ive{n \in S}$
belongs to $\set{0, 1}$.)
% You don't need to write things like the previous sentence in your solutions.
% I'm just trying to be ultra-detailed here.
For example, if $n = 5$ and $S = \set{2, 4, 5}$, then
$A \tup{S} = \tup{0, 1, 0, 1, 1}$.
% You don't HAVE to give examples for your definitions, but it never hurts.
% Just make sure that you don't forget the definition itself; an example
% alone is not a definition :)
(Some call $A \tup{S}$ the \textit{indicator vector} of $S$, since its
$i$-th entry indicates whether $i$ belongs to $S$ or not.)

We want to show that $A$ is a bijection.
There are two standard ways to prove that a map is a bijection:
One is to show that it is injective and surjective;
another is to exhibit its inverse.
Either of these ways works here; we shall use the latter.

We define the map $B : \set{0, 1}^n \to \set{\text{subsets of } \ive{n}}$
by setting
\[
B \tup{\tup{i_1, i_2, \ldots, i_n}}
= \set{ k \in \ive{n} \mid i_k = 1 }
% "\mid" gives a vertical bar with a bit of space on both sides.
% It is also used for divisibility of numbers.
% Compare this to "|", which does not leave any space.
\qquad \text{for each } \tup{i_1, i_2, \ldots, i_n} \in \set{0, 1}^n .
\]
% Note that we're using double parentheses in
% "B \tup{\tup{i_1, i_2, \ldots, i_n}}":
% one set of parentheses to mark the tuple, and another to show
% that we're applying $B$ to it.
% Commonly people don't do that, but I'm trying to be particularly precise
% at this point.

We want to show that the maps $A$ and $B$ are mutually inverse.
In order to do this, we must show that $A \circ B = \id$ and
that $B \circ A = \id$.
(We are using the notation ``$\id$'' for an identity map.
We don't specify which set this map acts on, since it is clear
from the context: For example, in ``$A \circ B = \id$'', the
``$\id$'' must be the identity map of $\set{0, 1}^n$, because
the domain of $A \circ B$ is $\set{0, 1}^n$.
If you really want to be precise, you could denote this
identity map by $\id_{\set{0, 1}^n}$.)
So let us prove this\footnote{On an actual homework set,
you can leave both of these proofs to the reader.
I am merely demonstrating the basics of rigorous combinatorial
reasoning here; otherwise I'd do the same.}:

\begin{itemize}
% "\itemize" is like "\enumerate", but instead of numbering the items
% it just makes bullet points.

\item
In order to show that $A \circ B = \id$, we fix some
$\tup{i_1, i_2, \ldots, i_n} \in \set{0, 1}^n$.
We shall show that
$\tup{A \circ B} \tup{\tup{i_1, i_2, \ldots, i_n}} = \tup{i_1, i_2, \ldots, i_n}$.

Set $S = B \tup{\tup{i_1, i_2, \ldots, i_n}}$.
Thus,
$S = B \tup{\tup{i_1, i_2, \ldots, i_n}}
= \set{ k \in \ive{n} \mid i_k = 1 }$
(by the definition of $B$).
Now,
\begin{align}
% "\begin{align}" and "\end{align}" delimit multi-line equations.
\tup{A \circ B} \tup{\tup{i_1, i_2, \ldots, i_n}}
& =
% As before, "&" is for vertical alignment.
A \tup{ \underbrace{B \tup{\tup{i_1, i_2, \ldots, i_n}}}_{= S} } \nnn
% "\nnn" ends a line in the multi-line equation *without* giving it a label.
% If you do want to give it a label, use "\label{...} \\" instead.
& =
A \tup{S} \nnn
& = \tup{ \ive{1 \in S}, \ive{2 \in S}, \ldots, \ive{n \in S} }
\label{exe1.sol.a.AB.1}
\end{align}
(by the definition of $A$).
Now, we shall show that each $j \in \ive{n}$ satisfies
$\ive{j \in S} = i_j$.

Indeed, let $j \in \ive{n}$.
Recall that $S = \set{ k \in \ive{n} \mid i_k = 1 }$.
Hence, if $i_j = 1$, then $j \in S$ and therefore
$\ive{j \in S} = 1 = i_j$.
Therefore, we have proven $\ive{j \in S} = i_j$ in the
case when $i_j = 1$.
On the other hand, if $i_j \neq 1$, then
$i_j = 0$ (since $i_j \in \set{0, 1}$) and
$j \notin S$ (because $S = \set{ k \in \ive{n} \mid i_k = 1 }$
whereas $i_j \neq 1$) and therefore
$\ive{j \in S} = 0 = i_j$.
Thus, we have proven $\ive{j \in S} = i_j$ in the
case when $i_j \neq 1$.
We have now proven $\ive{j \in S} = i_j$ both in the
case when $i_j = 1$ and in the case when $i_j \neq 1$.
These two cases cover all possibilities; thus, we always
have $\ive{j \in S} = i_j$.

Forget that we fixed $j$.
We thus have shown that $\ive{j \in S} = i_j$ for each $j \in \ive{n}$.
Hence,
\[
\tup{ \ive{1 \in S}, \ive{2 \in S}, \ldots, \ive{n \in S} }
= \tup{i_1, i_2, \ldots, i_n} .
\]
Hence, \eqref{exe1.sol.a.AB.1} becomes
\begin{align}
\tup{A \circ B} \tup{\tup{i_1, i_2, \ldots, i_n}}
& = \tup{ \ive{1 \in S}, \ive{2 \in S}, \ldots, \ive{n \in S} }
  = \tup{i_1, i_2, \ldots, i_n} \nnn
& = \id \tup{\tup{i_1, i_2, \ldots, i_n}} .
\label{exe1.sol.a.AB.2}
\end{align}

Now, forget that we fixed $\tup{i_1, i_2, \ldots, i_n}$.
We thus have proven \eqref{exe1.sol.a.AB.2} for each \\
% The "\\" forces LaTeX to start a new line, like the "enter" key
% in a "normal" text editor.
% Unlike leaving an empty line, this does NOT start a new paragraph,
% so the new line will not start with an indent.
% Why are we using "\\" here? Well, try without -- you'll see
% that the next mathematical expression goes slightly over the
% margins, which is awkward. Though a new line is also awkward.
% Choose your poison.
$\tup{i_1, i_2, \ldots, i_n} \in \set{0, 1}^n$.
Hence, $A \circ B = \id$.

\item
In order to prove that $B \circ A = \id$, we fix
$S \in \set{\text{subsets of } \ive{n}}$.
We are going to show that $\tup{B \circ A} \tup{S} = S$.

We have
$A \tup{S} = \tup{ \ive{1 \in S}, \ive{2 \in S}, \ldots, \ive{n \in S} }$
by the definition of $A$.
Now,
\begin{align}
\tup{B \circ A} \tup{S}
& = B \tup{ \underbrace{A \tup{S}}_{= \tup{ \ive{1 \in S}, \ive{2 \in S}, \ldots, \ive{n \in S} }} }
\nnn
& = B \tup{ \tup{ \ive{1 \in S}, \ive{2 \in S}, \ldots, \ive{n \in S} } }
\nnn
& = \set{ k \in \ive{n} \mid \ive{k \in S} = 1 }
\qquad \explain{by the definition of $B$} \nnn
% We are using "\qquad \explain{...}" to put a justification of
% the equality sign after the equality. This is my style; you can do
% it in various other ways.
% 
% Note that we have used dollar signs inside the "\text{...}"
% to get back into math mode. That's perfectly fine, even if it
% looks like a math-in-text-in-math matryoshka doll.
& = \set{ k \in \ive{n} \mid k \in S } \nnn
& \qquad \explain{because for any $k \in \ive{n}$, we have
                  $\ive{k \in S} = 1$ if and only if $k \in S$}
\nnn
& = \ive{n} \cap S = S
\qquad \explain{since $S \subseteq \ive{n}$}
\nnn
& = \id\tup{S} .
\nonumber
% "\nonumber" is a way to NOT give a label to this line.
% This is like "\nnn", except that we don't also start a new line.
\end{align}
Since we have proven this for each
$S \in \set{\text{subsets of } \ive{n}}$,
we can thus conclude that $B \circ A = \id$.

\end{itemize}

We now know that $A \circ B = \id$ and $B \circ A = \id$.
Combining these equalities, we conclude that the maps $A$ and $B$
are mutually inverse.
Hence, the map $A$ is invertible, i.e., bijective.
In other words,
$A : \set{\text{subsets of } \ive{n}} \to \set{0, 1}^n$
is a bijection.
Thus, \eqref{exe1.sol.bij-size} (applied to
$X = \set{\text{subsets of } \ive{n}}$, $Y = \set{0, 1}^n$
and $f = A$)
% I'm saying precisely what I'm applying the bijection principle to.
% In cases as simple as this, you don't have to do that.
% But if the situation becomes more complicated and some
% rewriting is required, you should be explicit about this!
yields
\[
\abs{\set{\text{subsets of } \ive{n}}}
= \abs{\set{0, 1}^n} = 2^n
\qquad \explain{by \eqref{exe1.sol.pow-n.2}}.
\]
This proves \eqref{exe1.sol.a.claim}, thus solving
part \textbf{(a)} of the exercise.

It remains to solve part \textbf{(b)}.
If $n = 0$, then it demands us to prove that the number of all
compositions of $0$ is $1$.
This is easy enough:\footnote{... and can be left to the reader
in real homework}
Recall that a composition of $n$ is defined as a tuple of
positive integers whose sum is $n$.
Thus, the compositions of $0$ are the tuples of positive integers
whose sum is $0$.
Hence, the only composition of $0$ is the empty $0$-tuple $\tup{}$,
since any other tuple of positive integers would have a positive
sum.
Thus, the number of all compositions of $0$ is $1$.

Having thus dealt with the case $n = 0$, we can now
WLOG\footnote{``WLOG'' means
\href{https://en.wikipedia.org/wiki/Without_loss_of_generality}{``without loss of generality''}.}
assume that $n > 0$.
Thus, part \textbf{(b)} of the exercise claims that the number of
all compositions of $n$ is $2^{n-1}$.

Since $n > 0$, we have $n - 1 \in \NN$ (since $n$ is an integer).
Thus, we can apply part \textbf{(a)} of our exercise
to $n-1$ instead of $n$.
We thus obtain that the number of all subsets of
$\set{1, 2, \ldots, n-1}$ is $2^{n-1}$.
In other words, the number of all subsets of $\ive{n-1}$ is $2^{n-1}$
(since $\ive{n-1} = \set{1, 2, \ldots, n-1}$).
In other words,
\begin{equation}
\abs{\set{\text{subsets of } \ive{n-1}}} = 2^{n-1} .
\label{exe1.sol.b.subsets}
\end{equation}

This suggests finding a bijection from
$\set{\text{subsets of } \ive{n-1}}$ to
$\set{\text{compositions of } n}$.
And this is indeed what we shall do.

This time we will rely on the following principle:

\begin{proposition} \label{prop.intset.inclist}
% The "\label" here gives a label to this proposition.
% We can later refer to it by this label, using "\ref{prop.intset.inclist}".
Let $S$ be a finite set of integers.
Then, there exists a unique tuple $\tup{s_1, s_2, \ldots, s_k}$
of integers such that $\set{s_1, s_2, \ldots, s_k} = S$
and $s_1 < s_2 < \cdots < s_k$.
\end{proposition}

This proposition just says that if you have a finite set of
integers, you can list its elements in increasing order in exactly
one way.
Obvious, right?

I will not prove Proposition \ref{prop.intset.inclist} here,
nor would I require such a proof in homework solutions;
basic results like this can be taken for granted, as far as this
course is concerned.
Nevertheless, proving Proposition \ref{prop.intset.inclist} becomes
a necessity if one wants to fully understand the logical foundations
of mathematics or implement it in a proof assistant;
thus, I will give a few hints on how such a proof can be obtained:%
\footnote{For a complete detailed proof, see
\cite[Theorem 2.46]{detnotes}.}
% I have used the "\cite" command here. It yields a reference
% to a source (in this case, a set of notes).
% See the bibliography at the end of this TeX file for how it works.

\begin{fineprint}
% "\begin{fineprint}" starts a fine-print (smaller font) environment.
[\textit{Outline of a proof of Proposition \ref{prop.intset.inclist}.}
First, show that any nonempty finite set of integers has a
unique largest element.
Then, prove the existence part of
Proposition \ref{prop.intset.inclist} (that is, the claim that
there exists at least one tuple $\tup{s_1, s_2, \ldots, s_k}$
of integers such that $\set{s_1, s_2, \ldots, s_k} = S$
and $s_1 < s_2 < \cdots < s_k$)
by induction on $\abs{S}$
(start by picking the largest element $t$ of $S$, then apply the
induction hypothesis to $S \setminus \set{t}$).
Finally, it remains to prove the uniqueness part of
Proposition \ref{prop.intset.inclist}.
In other words, it remains to prove that if
$\tup{s_1, s_2, \ldots, s_k}$ and $\tup{t_1, t_2, \ldots, t_j}$
are two tuples of integers such that $\set{s_1, s_2, \ldots, s_k} = S$
and $\set{t_1, t_2, \ldots, t_j} = S$
and $s_1 < s_2 < \cdots < s_k$
and $t_1 < t_2 < \cdots < t_j$,
then
$\tup{s_1, s_2, \ldots, s_k} = \tup{t_1, t_2, \ldots, t_j}$.
Prove this by induction on $\abs{S}$ again:
First argue that both $s_k$ and $t_j$ equal the largest element of $S$
(and thus each other); then apply the induction hypothesis to the
rests of the lists (and the set $S \setminus \set{t}$,
where $t$ is the largest element of $S$).
Details are left to the reader.]
\end{fineprint}

Now, we define a map
\[
C : \set{\text{compositions of } n} \to \set{\text{subsets of } \ive{n-1}}
\]
by setting
\begin{align}
C \tup{ \tup{a_1, a_2, \ldots, a_k} }
& = \set{ a_1 + a_2 + \cdots + a_i \mid i \in \ive{k-1} }
\label{exe1.sol.B.defC} \\
& = \set{ a_1, \  a_1 + a_2, \  a_1 + a_2 + a_3, \  \ldots, \  a_1 + a_2 + \cdots + a_{k-1} }
% "\ " puts a space even when a normal whitespace would be ignored by LaTeX.
% We are doing this here for the sake of clarity.
\nnn
& \qquad \text{for all compositions } \tup{a_1, a_2, \ldots, a_k} \text{ of } n . \nonumber
\end{align}
\footnote{Note that every composition $\tup{a_1, a_2, \ldots, a_k}$ of $n$
satisfies $k \geq 1$.
Indeed, if it wouldn't, then it would satisfy $k = 0$ and therefore
$a_1 + a_2 + \cdots + a_k = a_1 + a_2 + \cdots + a_0
= \tup{\text{empty sum}} = 0$,
which would contradict
$a_1 + a_2 + \cdots + a_k = n > 0$.}
We first need to check that this $C$ is well-defined -- i.e., that
$\set{ a_1 + a_2 + \cdots + a_i \mid i \in \ive{k-1} }$ is actually
a subset of $\ive{n-1}$ for any composition
$\tup{a_1, a_2, \ldots, a_k}$ of $n$.
Before we do this, let us give a few examples of $C$:

\begin{itemize}

\item
If $n = 4$, then $C \tup{ \tup{1, 3} } = \set{1}$ and
$C \tup{ \tup{1, 1, 2} } = \set{1, 2}$ and
$C \tup{ \tup{2, 1, 1} } = \set{2, 3}$.

\item
If $n = 7$, then
$C \tup{ \tup{2, 1, 1, 2, 1} } = \set{2, 3, 4, 6}$.

\end{itemize}

Note that $C$ is called the ``partial-sums'' map, since it sends
a composition $\tup{a_1, a_2, \ldots, a_k}$
to the set of all (nonempty, proper) partial sums
$a_1 + a_2 + \cdots + a_i$ of the composition.

Let us now show that $C$ is well-defined:

\begin{fineprint}
[\textit{Proof of the well-definedness of $C$.}
Let $\tup{a_1, a_2, \ldots, a_k}$ be a composition of $n$.
We must show that
$\set{ a_1 + a_2 + \cdots + a_i \mid i \in \ive{k-1} }$ is actually
a subset of $\ive{n-1}$.
In other words, we must show that
$a_1 + a_2 + \cdots + a_i \in \ive{n-1}$ for each $i \in \ive{k-1}$.
So let us fix $i \in \ive{k-1}$.
Then, $i \geq 1$, so that
$a_1 + a_2 + \cdots + a_i$ is a nonempty sum of positive integers
(because $a_1, a_2, \ldots, a_k$ are positive integers).
Thus, $a_1 + a_2 + \cdots + a_i$ is itself a positive integer.
Also, from $i \in \ive{k-1}$, we obtain $i \leq k-1$.
Hence, $a_{i+1} + a_{i+2} + \cdots + a_k$ is a nonempty sum of
positive integers as well
(because $a_1, a_2, \ldots, a_k$ are positive integers).
Thus, $a_{i+1} + a_{i+2} + \cdots + a_k$ is itself a positive integer.
Hence, $a_{i+1} + a_{i+2} + \cdots + a_k \geq 1$.
But now,
\[
\tup{a_1 + a_2 + \cdots + a_i}
+ \tup{a_{i+1} + a_{i+2} + \cdots + a_k}
= a_1 + a_2 + \cdots + a_k = n
\]
(since $\tup{a_1, a_2, \ldots, a_k}$ is a composition of $n$).
Therefore,
\[
a_1 + a_2 + \cdots + a_i
= n - \underbrace{\tup{a_{i+1} + a_{i+2} + \cdots + a_k}}_{\geq 1}
\leq n - 1 .
\]
Since $a_1 + a_2 + \cdots + a_i$ is a positive integer, this shows
that $a_1 + a_2 + \cdots + a_i \in \ive{n-1}$.
But this is precisely what we wanted to show.
Hence, $C$ is well-defined.]
\end{fineprint}

Next, we define a map
\[
D : \set{\text{subsets of } \ive{n-1}} \to \set{\text{compositions of } n}
\]
as follows:
Let $S$ be a subset of $\ive{n-1}$.
Then, Proposition \ref{prop.intset.inclist} shows that
there exists a unique tuple $\tup{s_1, s_2, \ldots, s_k}$
of integers such that $\set{s_1, s_2, \ldots, s_k} = S$
and $s_1 < s_2 < \cdots < s_k$.
Consider this tuple, and extend it further by setting
$s_0 = 0$ and $s_{k+1} = n$.
Then, we have the following inequalities:
\begin{itemize}
 \item $s_1 < s_2 < \cdots < s_k$;
 \item $s_0 < s_i$ for each $i \in \ive{k}$ (because each $i \in \ive{k}$
       satisfies $s_i \in \set{s_1, s_2, \ldots, s_k} = S \subseteq \ive{n-1}$,
       so that $s_i > 0 = s_0$);
 \item $s_i < s_{k+1}$ for each $i \in \ive{k}$ (because each $i \in \ive{k}$
       satisfies $s_i \in \set{s_1, s_2, \ldots, s_k} = S \subseteq \ive{n-1}$,
       so that $s_i \leq n-1 < n = s_{k+1}$);
 \item $s_0 < s_{k+1}$ (since $s_{k+1} = n > 0 = s_0$).
\end{itemize}
Combining these inequalities, we obtain
$s_0 < s_1 < \cdots < s_{k+1}$.
Now, set
\[
D \tup{S}
= \tup{ s_1 - s_0, s_2 - s_1, \ldots, s_{k+1} - s_k } .
\]
This defines $D$.

\begin{fineprint}
In fact, we again need to prove that $D$ is well-defined --
i.e., that $\tup{ s_1 - s_0, s_2 - s_1, \ldots, s_{k+1} - s_k }$
is actually a composition of $n$.
But this is easy: The tuple
$\tup{ s_1 - s_0, s_2 - s_1, \ldots, s_{k+1} - s_k }$
consists of positive integers (since
$s_0 < s_1 < \cdots < s_{k+1}$), and the sum of these integers
is
\begin{align}
& \tup{ s_1 - s_0 } + \tup{ s_2 - s_1 } + \cdots + \tup{ s_{k+1} - s_k } \nnn
& = \underbrace{\tup{s_1 + s_2 + \cdots + s_{k+1}}}_{= \tup{s_1 + s_2 + \cdots + s_k} + s_{k+1}}
 - \underbrace{\tup{s_0 + s_1 + \cdots + s_k}}_{= s_0 + \tup{s_1 + s_2 + \cdots + s_k}}
\nnn
& = \tup{\tup{s_1 + s_2 + \cdots + s_k} + s_{k+1}} - \tup{s_0 + \tup{s_1 + s_2 + \cdots + s_k}}
\nnn
& = s_{k+1} - s_0
  = n - 0
\qquad \explain{since $s_{k+1} = n$ and $s_0 = 0$}
\nnn
& = n. \nonumber
\end{align}
Thus, $D$ is indeed well-defined.
\end{fineprint}

Note that the map $D$ depends on $n$.
For example, if $n = 5$, then $D \tup{ \set{1, 3} } = \tup{1, 2, 2}$,
but if $n = 7$, then $D \tup{ \set{1, 3} } = \tup{1, 2, 4}$.
But $n$ is fixed in our current setting, which allows us to
leave it out of our notation.

We now claim that the maps $C$ and $D$ are mutually inverse.

\begin{fineprint}
Proving this is again a fairly straightforward matter, so we
restrict ourselves to an outline:

\begin{itemize}

\item
In order to prove that $C \circ D = \id$, we fix some
subset $S$ of $\ive{n-1}$, and we try to show that
$\tup{C \circ D} \tup{S} = S$.

Proposition \ref{prop.intset.inclist} shows that
there exists a unique tuple $\tup{s_1, s_2, \ldots, s_k}$
of integers such that $\set{s_1, s_2, \ldots, s_k} = S$
and $s_1 < s_2 < \cdots < s_k$.
Consider this tuple, and extend it further by setting
$s_0 = 0$ and $s_{k+1} = n$.
The definition of $D$ shows that
\begin{equation}
D \tup{S}
= \tup{ s_1 - s_0, s_2 - s_1, \ldots, s_{k+1} - s_k } .
\label{exe1.sol.b.CD.1}
\end{equation}
Now,
\begin{align}
\tup{C \circ D} \tup{S}
& = C \tup{D \tup{S}}
= C \tup{ \tup{ s_1 - s_0, s_2 - s_1, \ldots, s_{k+1} - s_k } }
\qquad \explain{by \eqref{exe1.sol.b.CD.1}}
\nnn
& = \set{ \tup{s_1 - s_0} + \tup{s_2 - s_1} + \cdots + \tup{s_i - s_{i-1}} \mid i \in \ive{k+1-1} }
\nonumber
\end{align}
(by \eqref{exe1.sol.B.defC}, applied to $k+1$ and
$\tup{ s_1 - s_0, s_2 - s_1, \ldots, s_{k+1} - s_k }$
instead of $k$ and $\tup{a_1, a_2, \ldots, a_k}$).
Since
\begin{align}
& \tup{ s_1 - s_0 } + \tup{ s_2 - s_1 } + \cdots + \tup{ s_i - s_{i-1} } \nnn
& = \underbrace{\tup{s_1 + s_2 + \cdots + s_i}}_{= \tup{s_1 + s_2 + \cdots + s_{i-1}} + s_i}
 - \underbrace{\tup{s_0 + s_1 + \cdots + s_{i-1}}}_{= s_0 + \tup{s_1 + s_2 + \cdots + s_{i-1}}}
\nnn
& = \tup{\tup{s_1 + s_2 + \cdots + s_{i-1}} + s_i} - \tup{s_0 + \tup{s_1 + s_2 + \cdots + s_{i-1}}}
\nnn
& = s_i - \underbrace{s_0}_{= 0} = s_i
\nonumber
\end{align}
for each $i \in \ive{k+1-1}$, this becomes
\begin{align}
\tup{C \circ D} \tup{S}
& = \set{ \underbrace{\tup{s_1 - s_0} + \tup{s_2 - s_1} + \cdots + \tup{s_i - s_{i-1}}}_{= s_i} \mid i \in \ive{k+1-1} }
\nnn
& = \set{ s_i \mid i \in \ive{\underbrace{k+1-1}_{=k}} }
= \set{ s_i \mid i \in \ive{k} }
= \set{ s_1, s_2, \ldots, s_k } = S = \id\tup{S} .
\nonumber
\end{align}
Since we have proven this for each subset $S$ of $\ive{n-1}$,
we thus conclude that $C \circ D = \id$.

\item
In order to prove $D \circ C = \id$,
we fix some composition $\tup{a_1, a_2, \ldots, a_j}$ of $n$.
We shall show that
$\tup{D \circ C} \tup{ \tup{a_1, a_2, \ldots, a_j} }
= \tup{a_1, a_2, \ldots, a_j}$.

Let $S$ be the set $C \tup{\tup{a_1, a_2, \ldots, a_j}}$.
Then, $S$ is a subset of $\ive{n-1}$ (since $C$ is well-defined).

Recall that $\tup{a_1, a_2, \ldots, a_j}$ is a composition
of $n$.
Thus, $a_1, a_2, \ldots, a_j$ are positive integers whose
sum is $n$.
Hence, $a_1 + a_2 + \cdots + a_j = n > 0$, so that $j > 0$
(since otherwise, $a_1 + a_2 + \cdots + a_j$ would be an
empty sum and therefore equal to $0$).
Since $a_1, a_2, \ldots, a_j$ are positive integers, we
have
\[
a_1 < a_1 + a_2 < a_1 + a_2 + a_3 < \cdots < a_1 + a_2 + \cdots + a_{j-1} .
\]
Moreover,
\[
S = C \tup{ \tup{a_1, a_2, \ldots, a_j} }
= \set{ a_1, \  a_1 + a_2, \  a_1 + a_2 + a_3, \  \ldots, \  a_1 + a_2 + \cdots + a_{j-1} }
\]
(by the definition of $C$).
Hence, the $\tup{j-1}$-tuple
\[
\tup{ a_1, \  a_1 + a_2, \  a_1 + a_2 + a_3, \  \ldots, \  a_1 + a_2 + \cdots + a_{j-1} }
\]
is a tuple $\tup{s_1, s_2, \ldots, s_k}$
of integers such that $\set{s_1, s_2, \ldots, s_k} = S$
and $s_1 < s_2 < \cdots < s_k$.

But Proposition \ref{prop.intset.inclist} shows that
there is a \textbf{unique} tuple $\tup{s_1, s_2, \ldots, s_k}$
of integers such that $\set{s_1, s_2, \ldots, s_k} = S$
and $s_1 < s_2 < \cdots < s_k$.
This unique tuple must be the $\tup{j-1}$-tuple
$\tup{ a_1, \  a_1 + a_2, \  a_1 + a_2 + a_3, \  \ldots, \  a_1 + a_2 + \cdots + a_{j-1} }$
(because as we have just seen, the latter $\tup{j-1}$-tuple
is such a tuple).
Consider this tuple; thus,
\[
\tup{s_1, s_2, \ldots, s_k}
= \tup{ a_1, \  a_1 + a_2, \  a_1 + a_2 + a_3, \  \ldots, \  a_1 + a_2 + \cdots + a_{j-1} } .
\]
In other words, $k = j-1$ and
\begin{equation}
s_i = a_1 + a_2 + \cdots + a_i
\qquad \text{for each } i \in \ive{k} .
\label{exe1.sol.b.DC.1}
\end{equation}
Extend the $k$-tuple $\tup{s_1, s_2, \ldots, s_k}$ further by setting
$s_0 = 0$ and $s_{k+1} = n$.
The definition of $D$ then shows that
\begin{equation}
D \tup{S}
= \tup{ s_1 - s_0, s_2 - s_1, \ldots, s_{k+1} - s_k } .
\label{exe1.sol.b.DC.2}
\end{equation}
But $a_1 + a_2 + \cdots + a_0$ is an empty sum and thus equals $0$.
Also, $k = j-1$ leads to $k+1 = j$, so that
$a_1 + a_2 + \cdots + a_{k+1} = a_1 + a_2 + \cdots + a_j = n$.
Now, the equality \eqref{exe1.sol.b.DC.1} holds not only for each
$i \in \ive{k}$, but also for $i = 0$ (since
$s_0 = 0 = a_1 + a_2 + \cdots + a_0$) and for $i = k+1$
(since $s_{k+1} = n = a_1 + a_2 + \cdots + a_{k+1}$).
Hence, this equality holds for all $i \in \set{0, 1, \ldots, k+1}$.
In other words, we have
\begin{equation}
s_i = a_1 + a_2 + \cdots + a_i
\qquad \text{for each } i \in \set{0, 1, \ldots, k+1} .
\label{exe1.sol.b.DC.3}
\end{equation}
Hence, for each $i \in \ive{k+1}$, we have
\begin{align*}
% "align*" does the same as "align", but it doesn't label any of the lines.
\underbrack{s_i}{= a_1 + a_2 + \cdots + a_i \\ \text{(by \eqref{exe1.sol.b.DC.3})}}
% This is "\underbrack" in action.
-
\underbrack{s_{i-1}}{= a_1 + a_2 + \cdots + a_{i-1} \\ \text{(by \eqref{exe1.sol.b.DC.3}, applied to $i-1$ instead of $i$)}}
& =
\tup{a_1 + a_2 + \cdots + a_i}
- \tup{a_1 + a_2 + \cdots + a_{i-1}} \\
& = a_i .
\end{align*}
Thus,
\[
\tup{ s_1 - s_0, s_2 - s_1, \ldots, s_{k+1} - s_k }
= \tup{a_1, a_2, \ldots, a_{k+1}}
= \tup{a_1, a_2, \ldots, a_j}
\]
(since $k+1 = j$).
Thus, \eqref{exe1.sol.b.DC.2} becomes
\[
D \tup{S}
= \tup{ s_1 - s_0, s_2 - s_1, \ldots, s_{k+1} - s_k }
= \tup{a_1, a_2, \ldots, a_j} .
\]
Now,
\begin{align*}
\tup{D \circ C} \tup{ \tup{a_1, a_2, \ldots, a_j} }
& = D \tup{ \underbrace{C \tup{ \tup{a_1, a_2, \ldots, a_j} }}_{= S} }
  = D \tup{S} \\
& = \tup{a_1, a_2, \ldots, a_j} = \id \tup{ \tup{a_1, a_2, \ldots, a_j} } .
\end{align*}
This shows that $D \circ C = \id$.
\end{itemize}

Combining $C \circ D = \id$ with $D \circ C = \id$, we conclude
that the maps $C$ and $D$ are mutually inverse.
\end{fineprint}

Thus, the map
\[
C : \set{\text{compositions of } n} \to \set{\text{subsets of } \ive{n-1}}
\]
is invertible, i.e., is a bijection.
Hence, using \eqref{exe1.sol.bij-size} again\footnote{this time, applied to
$X = \set{\text{compositions of } n}$, $Y = \set{\text{subsets of } \ive{n-1}}$
and $f = C$}, we obtain
\[
\abs{\set{\text{compositions of } n}}
= \abs{\set{\text{subsets of } \ive{n-1}}}
= 2^{n-1}
\]
(by \eqref{exe1.sol.b.subsets}).
In other words, the number of all compositions of $n$ is $2^{n-1}$.
This completes our solution to part \textbf{(b)} of the exercise
(since this is what part \textbf{(b)} claims for $n > 0$).

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

\section{Exercise 2}

\subsection{Problem}

For any real number $x$ and any $k \in \NN$, we define a number $\lf{x}{k}$
by\footnote{Note that the letter $i$ does \textbf{not} stand for the imaginary
unit $\sqrt{-1}$ in combinatorics, unless we explicitly say that it does.}
% The "\lf{x}{k}" macro yields the k-th falling factorial of x.
% Note that you need to put the "x" in parentheses if it is
% longer than a single symbol.
\[
\lf{x}{k} = x \tup{x-1} \tup{x-2} \cdots \tup{x-k+1} = \prod_{i=0}^{k-1} \tup{x-i} .
\]
(Note that if $k = 0$, then the product on the right hand side of this
equality is an empty product, and thus equals $1$ by definition.
Hence, $\lf{x}{0} = 1$ for every real $x$. Also, $\lf{x}{1} = x$,
$\lf{x}{2} = x\tup{x-1}$, and so on.
The notation $\lf{x}{n}$ is called the \textit{$n$-th
\href{https://en.wikipedia.org/wiki/Falling_and_rising_factorials}{falling factorial}
of $x$}.)

Let $k \in \NN$ and $n \in \NN$. Prove that
\begin{equation}
\sum_{i=0}^n \lf{i}{k} = \dfrac{1}{k+1} \lf{\tup{n+1}}{k+1} .
\label{exe2.claim}
\end{equation}

\subsection{Remark}

\begin{remark}
This may remind you of the classical formula
\[
\int_0^n x^k dx = \dfrac{1}{k+1} n^{k+1}
\]
from calculus; in fact, \eqref{exe2.claim} is something like a ``discrete version''
of this formula (with the integral replaced by a finite sum, and the $k$-th
power $x^k$ replaced by the falling factorial $\lf{x}{k}$).

The equality \eqref{exe2.claim} rewrites as
\[
\lf{0}{k} + \lf{1}{k} + \cdots + \lf{n}{k} = \dfrac{1}{k+1} \lf{\tup{n+1}}{k+1} .
\]
For example, for $k = 1$, this simplifies to
\[
0 + 1 + \cdots + n = \dfrac{1}{2} \tup{n+1} n ,
\]
which is \href{https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF}{a famous formula}.
(It is common to start the sum at $1$ rather than $0$, but this doesn't matter.)
\end{remark}

\subsection{Solution}

There are several ways to solve this exercise;
the two simplest are probably the one by induction on $n$,
and the one using the telescope principle.
In truth they are ``essentially the same'' (i.e., you can easily
translate one into the other).
I shall show the second one only.

Let me state the telescope principle first:

\begin{proposition} \label{prop.sums.telescope}
Let $m \in \NN$.
Let $a_0, a_1, \ldots, a_m$ be $m+1$
real numbers\footnote{I am saying ``real numbers'' just for the
sake of saying something definite.
You could just as well say ``complex numbers'' or ``rational numbers''
or ``elements of an abelian group (where the operation of the
group is written as addition)''.
The telescope principle is a general property of sums and
differences; it does not depend on what exactly we are summing.}.
Then,
\[
\sum_{i=1}^m \tup{a_i - a_{i-1}} = a_m - a_0 .
\]
\end{proposition}

Proposition \ref{prop.sums.telescope} is known as
the ``telescope principle'' since it contracts the sum
$\sum_{i=1}^m \tup{a_i - a_{i-1}}$ to the single difference
$a_m - a_0$, like folding a telescope.

The simplest way to convince yourself that
Proposition \ref{prop.sums.telescope} is true is by expanding
the left hand side:
\[
\sum_{i=1}^m \tup{a_i - a_{i-1}}
= \tup{a_1 - a_0} + \tup{a_2 - a_1} + \tup{a_3 - a_2} + \cdots + \tup{a_m - a_{m-1}}
\]
and watching all the terms cancel each other out except for
the $-a_0$ and the $a_m$.
More formally, this argument can be emulated by an induction
on $m$.
Here is a different proof (which illustrates a few of the
basic rules for manipulating sums):

\begin{proof}[Proof of Proposition \ref{prop.sums.telescope}.]
% This is a "proof" environment. In general
% "\begin{proof}[...]" begins a proof; the "..." is written
% in italics at the beginning of the proof.
% If you just write "\begin{proof}" without the "[...]",
% then it just says "Proof.".
If $m = 0$, then
\[
\sum_{i=1}^m \tup{a_i - a_{i-1}}
= \sum_{i=1}^0 \tup{a_i - a_{i-1}}
= \tup{\text{empty sum}} = 0 = a_m - a_0
\]
(since $m = 0$ leads to $a_m = a_0$).
Thus, Proposition \ref{prop.sums.telescope} holds if $m = 0$.
Hence, for the rest of this proof, we can WLOG assume that
$m \neq 0$.
Let us assume this.\footnote{In actual homework, feel free
to just say ``Assume WLOG that $m \neq 0$'' without giving
the justification that we just gave. The reader can be trusted
to fill it in.}
Thus, $m \geq 1$.
Hence,
\[
\sum_{i=1}^m a_i
= \sum_{i=1}^{m-1} a_i + a_m
\]
and
\[
\sum_{i=1}^m a_{i-1}
= \underbrace{a_{1-1}}_{= a_0} + \sum_{i=2}^m a_{i-1}
= a_0 + \sum_{i=2}^m a_{i-1}
= a_0 + \sum_{i=1}^{m-1} a_i
\]
(here, we have substituted $i$ for $i-1$ in the sum).
Thus,
\[
\sum_{i=1}^m \tup{a_i - a_{i-1}}
= \underbrace{\sum_{i=1}^m a_i}_{= \sum_{i=1}^{m-1} a_i + a_m}
  - \underbrace{\sum_{i=1}^m a_{i-1}}_{= a_0 + \sum_{i=1}^{m-1} a_i}
= \tup{\sum_{i=1}^{m-1} a_i + a_m} - \tup{a_0 + \sum_{i=1}^{m-1} a_i}
= a_m - a_0 .
\]
This proves Proposition \ref{prop.sums.telescope}.
\end{proof}
% The "\end{proof}" ends the "proof" environment and automatically
% puts a black square at its end.

Now, let us come back to the problem at hand.
We want to prove \eqref{exe2.claim} using
Proposition \ref{prop.sums.telescope}.
The key turns out to be the following formula:

\begin{lemma} \label{lem.exe2.sol.key}
Let $i$ be a real number, and $k \in \NN$. Then,
\[
\lf{\tup{i-1}}{k} = \dfrac{1}{k+1} \lf{i}{k+1} - \dfrac{1}{k+1} \lf{\tup{i-1}}{k+1} .
\]
\end{lemma}

\begin{proof}[Proof of Lemma \ref{lem.exe2.sol.key}.]
The definition of $\lf{\tup{i-1}}{k}$ yields
\[
\lf{\tup{i-1}}{k} = \tup{i-1} \tup{\tup{i-1}-1} \tup{\tup{i-1}-2} \cdots \tup{\tup{i-1}-k+1}
= \tup{i-1} \tup{i-2} \cdots \tup{i-k} .
\]
But the definition of $\lf{i}{k+1}$ yields
\begin{align*}
\lf{i}{k+1}
& = i \tup{i-1} \tup{i-2} \cdots \tup{i-\tup{k+1}+1}
  = i \tup{i-1} \tup{i-2} \cdots \tup{i-k} \\
& = i \underbrace{\tup{\tup{i-1} \tup{i-2} \cdots \tup{i-k}}}_{= \lf{\tup{i-1}}{k}}
  = i \lf{\tup{i-1}}{k} .
\end{align*}
On the other hand, the definition of $\lf{\tup{i-1}}{k+1}$ yields
\begin{align*}
\lf{\tup{i-1}}{k+1}
& = \tup{i-1} \tup{\tup{i-1}-1} \tup{\tup{i-1}-2} \cdots \tup{\tup{i-1}-\tup{k+1}+1} \\
& = \tup{i-1} \tup{i-2} \cdots \tup{i-k-1} \\
& = \underbrace{\tup{\tup{i-1} \tup{i-2} \cdots \tup{i-k}}}_{= \lf{\tup{i-1}}{k}} \tup{i-k-1}
  = \lf{\tup{i-1}}{k} \tup{i-k-1} .
\end{align*}
Subtracting the preceding two equalities from each other, we find
\begin{align*}
\lf{i}{k+1} \ - \lf{\tup{i-1}}{k+1}
% We are using "\ " to summon extra whitespace; otherwise the
% underline from the falling factorial notation ends too close
% to the minus sign.
& = i \lf{\tup{i-1}}{k} \ - \lf{\tup{i-1}}{k} \tup{i-k-1} \\
& = \underbrace{\tup{i - \tup{i-k-1}}}_{= k + 1} \lf{\tup{i-1}}{k}
= \tup{k+1} \lf{\tup{i-1}}{k} .
\end{align*}
We can divide this equality by $k+1$ (since $k+1 > 0$), and thus obtain
\[
\dfrac{\lf{i}{k+1} \ - \lf{\tup{i-1}}{k+1}}{k+1} = \lf{\tup{i-1}}{k} .
\]
In other words,
\[
\lf{\tup{i-1}}{k}
= \dfrac{\lf{i}{k+1} \ - \lf{\tup{i-1}}{k+1}}{k+1}
= \dfrac{1}{k+1} \lf{i}{k+1} - \dfrac{1}{k+1} \lf{\tup{i-1}}{k+1} .
\]
This proves Lemma \ref{lem.exe2.sol.key}.
\end{proof}

We also note that the definition of $\lf{0}{k+1}$ yields
\[
\lf{0}{k+1} = 0 \tup{0-1} \tup{0-2} \cdots \tup{0-\tup{k+1}+1}
= 0 \tup{0-1} \tup{0-2} \cdots \tup{0-k}
= 0 .
\]

Now, let us substitute $i-1$ for $i$ in the sum $\sum_{i=0}^n \lf{i}{k}$.
Thus, we find
\begin{align*}
\sum_{i=0}^n \lf{i}{k}
& = \sum_{i=1}^{n+1}
      \underbrack{\lf{\tup{i-1}}{k}}{= \dfrac{1}{k+1} \lf{i}{k+1} - \dfrac{1}{k+1} \lf{\tup{i-1}}{k+1} \\
                                     \text{(by Lemma \ref{lem.exe2.sol.key})}}
  = \sum_{i=1}^{n+1} \tup{\dfrac{1}{k+1} \lf{i}{k+1} - \dfrac{1}{k+1} \lf{\tup{i-1}}{k+1}} \\
& = \dfrac{1}{k+1} \lf{\tup{n+1}}{k+1} - \dfrac{1}{k+1} \underbrace{\lf{0}{k+1}}_{=0} \\
& \qquad
  \explain{by Proposition \ref{prop.sums.telescope}, applied to $m = n+1$
           and $a_i = \dfrac{1}{k+1} \lf{i}{k+1}$} \\
& = \dfrac{1}{k+1} \lf{\tup{n+1}}{k+1} - \dfrac{1}{k+1} 0
  = \dfrac{1}{k+1} \lf{\tup{n+1}}{k+1} .
\end{align*}
This solves the exercise.

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

\section{Exercise 3}

\subsection{Problem}

Let $n$ be a positive integer.

An $n$-tuple $\tup{i_1, i_2, \ldots, i_n} \in \set{0, 1}^n$
is said to be \textit{even} if the sum $i_1 + i_2 + \cdots + i_n$ is even.
(For example, the $4$-tuple $\tup{1, 0, 0, 1}$ is even, whereas
$\tup{1, 0, 1, 1}$ is not.)

Prove that the number of all even $n$-tuples
$\tup{i_1, i_2, \ldots, i_n} \in \set{0, 1}^n$ is $2^{n-1}$.

\subsection{Solution}

Let $E_n$ be the set of all even $n$-tuples
$\tup{i_1, i_2, \ldots, i_n} \in \set{0, 1}^n$.
Then, the exercise wants us to show that
$\abs{E_n} = 2^{n-1}$.

We shall achieve this by finding a bijection from $E_n$
to $\set{0, 1}^{n-1}$.

Define a map $A : E_n \to \set{0, 1}^{n-1}$ by setting
\[
A \tup{\tup{i_1, i_2, \ldots, i_n}}
= \tup{i_1, i_2, \ldots, i_{n-1}}
\qquad \text{for each } \tup{i_1, i_2, \ldots, i_n} \in E_n .
\]
Thus, the map $A$ simply throws away the last entry of an even
$n$-tuple.

We want to prove that $A$ is bijective.
We can achieve this by proving that $A$ is injective and surjective:
\footnote{Again, there is much more detail in the following
argumentation than you need when writing up your homework.}

\begin{itemize}

\item
Let us first show that $A$ is injective.
This means showing that if
$\tup{i_1, i_2, \ldots, i_n}$ and $\tup{j_1, j_2, \ldots, j_n}$
are two elements of $E_n$
(that is, even $n$-tuples)
satisfying
\begin{equation}
A \tup{\tup{i_1, i_2, \ldots, i_n}}
= A \tup{\tup{j_1, j_2, \ldots, j_n}} ,
\label{exe3.sol.inj.ass}
\end{equation}
then
\begin{equation}
\tup{i_1, i_2, \ldots, i_n}
= \tup{j_1, j_2, \ldots, j_n} .
\label{exe3.sol.inj.goal}
\end{equation}
So let $\tup{i_1, i_2, \ldots, i_n}$ and $\tup{j_1, j_2, \ldots, j_n}$
be two elements of $E_n$ satisfying \eqref{exe3.sol.inj.ass}.
We must prove \eqref{exe3.sol.inj.goal}.

The definition of $A$ yields
\[
A \tup{\tup{i_1, i_2, \ldots, i_n}}
= \tup{i_1, i_2, \ldots, i_{n-1}}
\qquad \text{and} \qquad
A \tup{\tup{j_1, j_2, \ldots, j_n}}
= \tup{j_1, j_2, \ldots, j_{n-1}} .
\]
Thus, \eqref{exe3.sol.inj.ass} rewrites as
\[
\tup{i_1, i_2, \ldots, i_{n-1}}
= \tup{j_1, j_2, \ldots, j_{n-1}} .
\]
In other words,
\begin{equation}
i_k = j_k \qquad \text{for each } k \in \ive{n-1} .
\label{exe3.sol.inj.1}
\end{equation}
Hence,
$i_1 + i_2 + \cdots + i_{n-1} = j_1 + j_2 + \cdots + j_{n-1}$.

On the other hand, the $n$-tuple
$\tup{i_1, i_2, \ldots, i_n}$ is even (since
$\tup{i_1, i_2, \ldots, i_n} \in E_n$).
In other words, $i_1 + i_2 + \cdots + i_n$ is even.
In other words, $i_1 + i_2 + \cdots + i_n \equiv 0 \mod 2$.
Similarly, $j_1 + j_2 + \cdots + j_n \equiv 0 \mod 2$.
Now,
\begin{align*}
\underbrace{\tup{i_1 + i_2 + \cdots + i_{n-1}}}_{= j_1 + j_2 + \cdots + j_{n-1}} + j_n
& = \tup{j_1 + j_2 + \cdots + j_{n-1}} + j_n
  = j_1 + j_2 + \cdots + j_n
  \equiv 0 \\
& \equiv i_1 + i_2 + \cdots + i_n
  = \tup{i_1 + i_2 + \cdots + i_{n-1}} + i_n \mod 2.
\end{align*}
Subtracting $i_1 + i_2 + \cdots + i_{n-1}$ from both sides of
this congruence, we obtain $j_n \equiv i_n \mod 2$.
But $j_n$ and $i_n$ are two elements of $\set{0, 1}$,
and thus can only be congruent to each other modulo $2$ if they
are equal.
Hence, from $j_n \equiv i_n \mod 2$, we obtain $j_n = i_n$.
In other words, $i_n = j_n$.
Hence, $i_k = j_k$ holds not only for $k \in \ive{n-1}$
(as we have shown in \eqref{exe3.sol.inj.1}),
but also for $k = n$.
In other words, we have $i_k = j_k$ for all $k \in \ive{n}$.
In other words,
$\tup{i_1, i_2, \ldots, i_n}
= \tup{j_1, j_2, \ldots, j_n}$.
Thus, \eqref{exe3.sol.inj.goal} is proven.
So we have shown that $A$ is injective.

\item
Let us now prove that $A$ is surjective.
To do that, we need to show that for each
$\tup{j_1, j_2, \ldots, j_{n-1}} \in \set{0, 1}^{n-1}$,
there exists some $\tup{i_1, i_2, \ldots, i_n} \in E_n$
such that
\[
A \tup{\tup{i_1, i_2, \ldots, i_n}}
= \tup{j_1, j_2, \ldots, j_{n-1}} .
\]

So let us fix some
$\tup{j_1, j_2, \ldots, j_{n-1}} \in \set{0, 1}^{n-1}$.
We need to show that there
exists some $\tup{i_1, i_2, \ldots, i_n} \in E_n$
such that
$A \tup{\tup{i_1, i_2, \ldots, i_n}}
= \tup{j_1, j_2, \ldots, j_{n-1}}$.

Indeed, let us construct this $\tup{i_1, i_2, \ldots, i_n}$ as
follows:

We set $i_k = j_k$ for each $k \in \ive{n-1}$.
This defines $n-1$ elements $i_1, i_2, \ldots, i_{n-1}$
of $\set{0, 1}$.
Next, we define a further element $i_n$ of $\set{0, 1}$
by
\[
i_n
=
\begin{cases}
0, & \text{ if $i_1 + i_2 + \cdots + i_{n-1}$ is even;} \\
1, & \text{ if $i_1 + i_2 + \cdots + i_{n-1}$ is odd.} \\
\end{cases}
\]
Then, the number $i_1 + i_2 + \cdots + i_n$ is even (because
we can write it as the sum
$\tup{i_1 + i_2 + \cdots + i_{n-1}} + i_n$ of the two
numbers $i_1 + i_2 + \cdots + i_{n-1}$ and $i_n$, which
are either both even or both odd).
In other words, the $n$-tuple
$\tup{i_1, i_2, \ldots, i_n} \in \set{0, 1}^n$ is even.
In other words, $\tup{i_1, i_2, \ldots, i_n} \in E_n$.
Finally, the definition of $A$ yields
\[
A \tup{\tup{i_1, i_2, \ldots, i_n}}
= \tup{i_1, i_2, \ldots, i_{n-1}}
= \tup{j_1, j_2, \ldots, j_{n-1}}
\]
(since $i_k = j_k$ for each $k \in \ive{n-1}$).
Thus, we have constructed an
$\tup{i_1, i_2, \ldots, i_n} \in E_n$
such that
$A \tup{\tup{i_1, i_2, \ldots, i_n}}
= \tup{j_1, j_2, \ldots, j_{n-1}}$.
This completes our proof of the surjectivity of $A$.

\end{itemize}

We now know that the map $A$ is both injective and surjective.
Hence, $A$ is bijective.
In other words, $A : E_n \to \set{0, 1}^{n-1}$ is a bijection.
Hence, \eqref{exe1.sol.bij-size} (applied to
$X = E_n$, $Y = \set{0, 1}^{n-1}$ and $f = A$) yields
\[
\abs{E_n} = \abs{\set{0, 1}^{n-1}} = 2^{n-1}
\]
(where the last equality sign follows from \eqref{exe1.sol.pow-n.2},
applied to $n-1$ instead of $n$).
This solves the exercise.

\begin{thebibliography}{99999999}                                                                                         %

% This is the bibliography: The list of papers/books/articles/blogs/...
% cited. The syntax is: "\bibitem[name]{tag}Reference",
% where "name" is the name that will appear in the compiled
% bibliography, and "tag" is the tag by which you will refer to
% the source in the TeX file. For example, the following source
% has name "Grinbe16" (so you will see it referenced as
% "[Grinbe16]" in the compiled PDF) and tag "detnotes" (so you
% can cite it by writing "\cite{detnotes}").

\bibitem[Grinbe16]{detnotes}Darij Grinberg, \textit{Notes on the combinatorial
fundamentals of algebra}, 10 January 2019.\newline%
\url{http://www.cip.ifi.lmu.de/~grinberg/primes2015/sols.pdf} \newline The
numbering of theorems and formulas in this link might shift when the project
gets updated; for a \textquotedblleft frozen\textquotedblright\ version whose
numbering is guaranteed to match that in the citations above, see
\url{https://github.com/darijgr/detnotes/releases/tag/2019-01-10} .

\end{thebibliography}

\end{document}

% You can use the space after "\end{document}" as scratch paper --
% LaTeX stops compiling after it sees the "\end{document}"
% instruction, so everything that comes after it is ignored.
% For example, the following nonsense doesn't appear anywhere
% in the PDF file:

$aaaaaaaa$
