\input lmacros
\documentstyle[12pt]{article}
\headheight 0in
\headsep 0in
\evensidemargin 1in
\oddsidemargin \evensidemargin
\textwidth 6.5in
\topmargin 1.25in
\textheight 8.7in
\begin{document}
\pagestyle{empty}

\begin{center}
{\bf Notes:  Counting functions.}
\end{center}

Let $f\colon K\rightarrow N$ denote a function from a set $K$ to a set
$N$: to each element $x\in K$ corresponds an element $f(x)\in N$.  We
say $f$ ``maps'' $x$ to $f(x)$; sometimes we leave the $f$ tacit
and say that $x$ maps to $f(x)$.

We call $f$ {\it injective} if distinct elements of $K$ map to
distinct elements of $N$:  for all $x,y\in K$ with $x \neq y$,
$f(x) \neq f(y)$.

We call $f$ {\it surjective} if every element of $N$ is mapped to by
some element (or elements) of $K$:  for all $y\in N$ there exists
$x\in K$ with $y = f(x)$.

We call $f$ {\it bijective} if it is both injective and surjective.
This says every element $y$ in $N$ is $f(x)$ for one and only one
element $x\in K$.  For $y\in N$ we may define $g(y)$ to be this unique
element $x$ and thus construct a function $g\colon N\rightarrow K$
which is a {\it left and right inverse} to $f$.  In other words
$g(f(x)) = x$ for all $x\in K$ {\it and} $f(g(y)) = y$ for all $y\in
N$.  Conversely if such an inverse exists then $f$ is bijective.
Indeed, if $g(f(x)) = x$ for all $x\in K$ then $f$ must be injective
since $f(x)$ determines $x$, while if $f(g(y)) = y$ for all $y\in N$
then $f$ must be surjective since $g(y)$ is an element that maps (via
$f$) to $y$.

One fundamental technique we use in combinatorics is to prove
that two sets have the same number of elements by finding a bijection
$f$ between them.  Frequently we will prove $f$ is a bijection by
finding its inverse $g$.  Keep in mind that in such a proof we must
check {\it both} directions: that $g$ is a left and also a right
inverse.

\medskip

In these notes we are going to count functions $f\colon K\rightarrow
N$ from a finite set $K$ with $|K| = k$ elements to $N$ with $|N| = n$
elements.  Our intention is to explain within one concise framework
the significance of the most basic enumeration problems of
combinatorics: enumeration of permutations and combinations of sets
and ``multisets'', as well as of partitions of sets and of numbers,
which we have already explored individually.

This framework is called the ``12-fold way'' and it uses two ideas to
get various types of enumeration problems from the counting of
functions $f\colon K\rightarrow N$.

The first idea is to consider different restrictions on the functions
$f$.  Thus we may count {\it all} functions, or only {\it injective}
functions, or only {\it surjective} functions.  Note that we don't
need to make a count of {\it bijective} functions separately.  For $f$
can only be bijective when $n = k$, and then $f$ is bijective iff $f$
is injective iff $f$ is surjective, so we can use enumerations of
injective or surjective functions to cover this case.

The second idea, subtler than the first, is not just to count functions
individually, but to group them together by regarding two functions as
``the same'' if they differ only by rearranging the elements of $K$,
or of $N$, or both.  Thus if we say that we consider the elelements of
$K$ {\it indistinguishable}, it means that two functions are to count
as the same if one can be converted into the other by permuting the
elements of $K$.  Otherwise we consider the elements of $K$ to be {\it
distinguished}.  We make similar definitions for $N$.

To understand these ideas it is best to consider their meaning more
informally.

If $K$ and $N$ both have distinguished elements, then we are just
counting functions individually.

If $K$ has indistinguishable elements, then the relevant information
about $f$ is just: {\it how many} elements of $K$ map to each element of $N$.
For instance, suppose $K = \{w,x,y,z \}$, $N = \{a,b \}$, and $f$ and
$g$ look like this:

\vspace{1in}

Then we are not to count $f$ and $g$ as different, for if we 
changed the names of $w,x,y,z$ to $w,z,x,y$, $g$ would now map the way $f$
did before.  What can't be changed by changing the names of elements
in $K$ is just the fact that $f$ and $g$ each map three elements to
$a$ and one to $b$.  If $N$ also had indistinguishable elements here,
it wouldn't even matter which of $a$ and $b$ got three elements and
which got one.  Then the only relevant information would be what
numbers occur and how often: here 3 once and 1 once.

If $N$ has indistinguishable elements, the relevant information about $f$
is how it {\it partitions} $K$, that is, which elements of $K$ map to
the same element of $N$ and which map to different ones.  For instance
these two functions would count as the same

\vspace{1in}

\noindent
because both partition $K$ into $\{w,y \}$ and $\{x,z \}$.

Now we have the 12 ``ways'' of counting functions in the 12-fold way.
Each of $K$ and $N$ can have either distinguished or indistinguishable
elements, for four possibilities.  Within each of these we may count
injective, surjective, or all functions, for a total of 12 different
enumeration problems.  Here is the table that results, followed by
some commentary.

(Note: ``$N$ dist.'' means the elements of $N$ are distinguishable
from one another; ``$N$ ind.'' means that they are not.  Similarly
for $K$.)

\vspace{0.5in}

\noindent
Part I: $f: K \rightarrow N$ injective:
$$
\begin{array}{ccc}
	& \mbox{$N$ dist.} & \mbox{$N$ indist.} \\
\mbox{$K$ dist.} & (n)_k & \begin{array}{ll}
	1 & \mbox{if $k \leq n$} \\
	0 & \mbox{if $k > n$} \end{array} \\
\mbox{$K$ ind.} & {n \choose k} & \begin{array}{ll}
	1 & \mbox{if $k \leq n$} \\
	0 & \mbox{if $k > n$} \end{array} \end{array}
$$

$K$ dist., $N$ dist.:
$(n)_k = n(n-1) \cdots (n-k+1)$
is the {\it falling factorial\/};
in Brualdi it is written as
$[n]_k$ or $P(n,k)$.
Injections from a $k$-element set
of indistinguishable elements
to the set $N$
are really the same thing as
$k$-permutations of the set $N$.

$K$ ind., $N$ dist.:
${n \choose k} = \frac{(n)_k}{k!} = \frac{n!}{k!(n-k)!}$
is the binomial coefficient ``$n$ choose $k$''.
Brualdi also writes it as $C(n,k)$.
Since $K$ has indistinguishable elements,
the order of the values of $f$
(call them $f_1, f_2, ..., f_k$)
is immaterial
and we are counting $k$-combinations from $N$,
that is, subsets of $N$ with $k$ elements.

$K$ dist., $N$ ind.:
If $k > n$, there are no such functions.
If $k \leq n$, then such functions exist,
but they may all be obtained from one another
by re-labelling.

$K$ ind., $N$ ind.:
Ditto.

\vspace{0.5in}

\noindent
Part II: $f: K \rightarrow N$ unconstrained:
$$
\begin{array}{ccc}
	& \mbox{$N$ dist.} & \mbox{$N$ indist.} \\
\mbox{$K$ dist.} & n^k & S(k,1)+S(k,2)+...+S(k,n) \\
\mbox{$K$ ind.} & {n \choose k} & p_1(k)+p_2(k)+...+p_n(k) \end{array}
$$

$K$ dist., $N$ dist.:
$n^k$ is the number of functions from $K$ to $N$
since each of the $k$ values $f(x)$ for $x \in K$
can be chosen independently in $n$ ways.
Such functions are essentially the same as
$k$-permutations from $N$ with unlimited repetition.

$K$ ind., $N$ dist.:
${n \choose k}$ is read ``$n$ multichoose $k$''.
This is the number of $k$-combinations with unlimited repetition from $N$,
since when $K$ has indistinguishable elements the order in which
$f_1,f_2,...,f_k$ occur is immaterial.
Brualdi Theorem 3.5.1 expresses ${n \choose k}$
as ${n+k-1 \choose k}$.
It is equal to the number of $n$-tuples of non-negative integers
summing to $k$.

For explanations of the other two entries in the table, see below.

\vspace{0.5in}

\noindent
Part III: $f: K \rightarrow N$ surjective:
$$
\begin{array}{ccc}
	& \mbox{$N$ dist.} & \mbox{$N$ indist.} \\
\mbox{$K$ dist.} & n!\,S(k,n) & S(k,n) \\
\mbox{$K$ ind.} & {n \choose k-n} & p_n (k) \end{array}
$$

$K$ dist., $N$ ind.:
$S(k,n)$ is a Stirling number of the second kind,
and equals the number of partitions of a $k$-element set into $n$ blocks.
That's what we're counting here with $N$ having indistinguishable elements.
When $f$ is not surjective,
as in Part II,
not all elements of $N$ correspond to blocks --
only those that actually are mapped to by $f$.
Then we are counting partitions with
{\it at most} $n$ blocks,
giving the entry $S(k,1)+...+S(k,n)$ in Part II.

$K$ ind., $N$ ind.:
$p_n(k)$ is defined as the number of partitions
of the {\it integer} $k$ into $n$ positive parts:
they are the sizes of the blocks of the partition of the {\it set} $K$.
Since $K$ has indistinguishable elements the actual set-partition is lost;
only the block sizes count.
The reasoning for $p_1(k)+...+p_n(k)$ in Part II
is like that for $S(k,1)+...+S(k,n)$ given above.

$K$ dist., $N$ dist.:
Since $f$ is surjective,
each partition of $N$ into $k$ blocks
gives rise to $n!$ {\it different} functions,
by permuting the elements of $N$.
Therefore the number of such functions is $n!\,S(k,n)$.
Note that this reasoning does not apply in Part II;
for there, $f$ need not be surjective,
and if there are elements of $N$ not mapped to by $f$,
permuting such elements does not affect $f$.

$K$ ind., $N$ dist.:
Such maps correspond to $n$-tuples of {\it positive} integers
summing to $k$ (cf.\ the corresponding case in Part II).
By subtracting 1 from each part,
we obtain a $n$-tuple of non-negative integers summing to $k-n$,
and the number of such $n$-tuples is ${n \choose k-n}$.

\end{document}
