Abstract

Consider the following problems:

  1. If $S$ and $T$ are finite sets, how many mappings $\alpha:S\rightarrow T$ are possible? (Durbin 10)
  2. How many ways are there to place $r\gt0$ distinguishable balls into $n\gt0$ urns? (Ross 12)
  3. How many interpretations are there of a truth-functional sentence $\mathscr{P}$ containing $n$ atomic sentences? (Bergmann 70)
    For example, how many interpretations of the sentence $\unicode{x201C}(A\lor B)\land(A\lor C)"$ are possible? $(n=3).$
  4. How many truth functions of $n$ arguments are possible? (Bergmann 221)
    For example, two such functions with two arguments are 'and' and 'or', and one with one argument is 'not'.
  5. How many functions defined on $n$ points are possible if each functional value is either $0$ or $1?$ (Ross 3)
  6. How many strings of length $r$ from an alphabet of length $n$ can be composed?
    Example, how many license plates of 6 alphanumeric characters are possible if repetition of characters is allowed?

The answers to these questions have a lot in common. In probability, they are examples of sampling with replacement. Let's begin by developing a theorem we will need.

Preliminaries

According to the Basic Principle of Counting, a.k.a. the Multiplication Principle, if $|S_i|=n_i$ for all $i\in[1,r],$ $i$ and $r$ positive integers, $S_i$ any set, then \begin{equation} \label{mult_princ} \abs{S_1\times\cdots\times S_r}= \abs{S_1}\cdots\abs{S_r}=n_1\cdots n_r. \end{equation} For a set $S$ with $\abs{S}=n,$ it follows that \begin{equation} \label{mult_cor} \abs{S^r}=\abs{S}^r=n^r \end{equation} (Let $S_i=S$ and $n_i=n$ for all $i\in[1,r].$)

Problem (i)

If $S$ and $T$ are finite sets, how many mappings $\alpha:S\rightarrow T$ are possible? (Durbin 10)

Informal Solution

Consider a mapping $\alpha:S\rightarrow T$ where $\abs{S}=r,$ $\abs{T}=n,$ and $S=\{x_1,\ldots,x_r\}.$ To indicate that $\alpha$ maps $x\mapsto\alpha(x)$ for each $x\in S,$ we may write: \begin{equation} \label{alpha_map} (x_1,\ldots,x_r)\mapsto(\alpha(x_1),\ldots,\alpha(x_r)). \end{equation} However, $(\alpha(x_1),\ldots,\alpha(x_r))\in T^r.$ Therefore, there are $\abs{T^r}=\abs{T}^r=n^r$ possible mappings $\alpha$ by Equation \eqref{mult_cor}. (See "Formal Solution" next for more precision in how this conclusion is drawn.) We state this result formally as a theorem.

Theorem 1. If $\abs{S}=r$ and $\abs{T}=n$ then there are $n^r$ possible mappings $\alpha:S\rightarrow T.$

This count includes all possible maps, such as those that are

  • one-to-one but not onto (injection but not surjection)
  • onto but not one-to-one (surjection but not injection)
  • one-to-one and onto (bijection)
  • neither one-to-one nor onto

For example, there are fewer injections.

Formal Solution

Define the set of all maps from $S$ to $T$ by \begin{equation} M(S,T)=\{\alpha\mid\alpha:S\rightarrow T\} \end{equation} and let $S$ and $T$ be finite sets with $\abs{S}=r,$ $\abs{T}=n,$ and $S=\{x_1,\ldots,x_r\}.$ Consider the function $f: M(S,T)\rightarrow T^r$ defined by \[ f(\alpha)=(\alpha(x_1),\ldots,\alpha(x_r)). \]

If $\alpha,\beta\in M(S,T)$ and $\alpha\ne\beta,$ then $\alpha(x)\ne\beta(x)$ for some $x\in S.$ Therefore, $f(\alpha)=(\alpha(x_1),\ldots,\alpha(x_r))$ $\ne(\beta(x_1),\ldots,\beta(x_r))$ $=f(\beta),$ establishing $f$ is an injection.

If $(y_1,\ldots,y_r)\in T^r$ then $y_i\in T$ for all $i\in[1,r].$ Consider the mapping $\alpha\in M(S,T)$ defined by $\alpha(x_i)=y_i$ for all $i\in[1,r].$ For this mapping, $f(\alpha)=(y_1,\ldots,y_r).$ Therefore, $f$ is a surjection.

Having found a bijection $f:M(S,T)\rightarrow T^r$ it follows that \begin{equation} M(S,T)\sim T^r. \end{equation} Therefore, \begin{equation} \abs{M(S,T)}=\abs{T^r}=n^r=\abs{T}^{\abs{S}}. \end{equation} We restate Theorem 1 accordingly.

Theorem 1 (alternative form). If $S$ and $T$ are finite sets, then $\abs{M(S,T)}=\abs{T}^{\abs{S}}.$

Problem (ii)

How many ways are there to place $r\gt0$ distinguishable balls into $n\gt0$ urns? (Ross 12)

Solution

An arrangement of balls in urns is a map $\alpha:S\rightarrow T,$ where $S$ is the set of $r$ balls, $T$ the set of $n$ urns, and $\alpha(s)=t$ the urn containing ball $s$. The set of all such arrangements is the set of all mappings $M(S,T).$ Since $\abs{S}=r$ and $\abs{T}=n,$ then there are $n^r$ such arrangements by Theorem 1.

Since balls are distinguished, two maps that assign different balls to different urns but the same number of balls to each urn are still counted as distinct maps.

Explanation

The solution rests on the equivalence of the possible arrangements of balls in urns and the elements of $M(S,T).$ This section tries to convice the reader that this equivalence is real.

First, we number each ball and urn in such a way that $s_i$ names the $i\text{th}$ ball for $i\in \{1,\ldots,r\},$ and $t_j$ names the $j\text{th}$ urn for $j\in \{1,\ldots,n\}.$ This establishes the correspondence of $S=\{s_1,\ldots,s_r\}$ as the set of balls, and $T=\{t_1,\ldots,t_n\}$ as the set of urns. As expected, $|S|=r$ and $|T|=n.$

That an arrangement is a map is given by the problem: each ball is distinguished, each ball is placed in an urn, and by physical limit, a ball cannot be in two urns at once. Let $\alpha$$=\{(s,t)\in S\times T\ \mid\ \text{ball}$ $s \text{ is in urn } t\}.$ Thus, we are told that if $(s,x)\in \alpha$ and $(s,y)\in \alpha$ then $x=y.$ Therefore, $\alpha:S\rightarrow T$ is a function (Gaughan 9).

This map can be an injection, surjection, both, or neither, since nothing in the problem says otherwise. For example, if $n=r$ then each urn could contain exactly one ball for a bijection. If $n>r$ then at least $n-r$ urns will be empty and the remaining $r$ urns could contain exactly one ball each for an injection. If $n\lt r$ then an injection is not possible because some urns will contain more than one ball, but a surjection is possible since every urn can contain at least one ball. In most cases, maps which are neither one-to-one nor onto are possible. A notable exception is when $n=r=1$ in which case only a bijection is possible. Similarly, if $n=1$ and $r>n$ then all maps will be onto but none will be one-to-one.

The balls placed in urn $t$ are given by the preimage of $t$ under $\alpha$, namely, the set $\alpha^{-1}(t)$ $=\{s\in S\mid \alpha(s)=t\in T\}.$ This preimage is simply $s$ when $\alpha$ is invertible (a bijection).

Let $X=\{\alpha_i\}$ denote the set of all such arrangements. If $\alpha\in X$ then $\alpha:S\rightarrow T,$ so $\alpha\in M(S,T)$. Conversely, if $\alpha\in M(S,T)$ then $\alpha:S\rightarrow T.$ Suppose $\alpha\not\in X.$ Then for some ball $s\in S$ and urn $t\in T,$ we have $(s,t)\not\in\alpha,$ meaning the ball is left out of an urn. Thus, $S$ is not the domain of $\alpha,$ a contradiction. Thus, $\alpha\in X.$ Therefore, $X\sim M(S,T)$ and $|X|=n^r.$

Problem (iii)

How many interpretations are there of a truth-functional sentence $\mathscr{P}$ containing $n$ atomic sentences? (Bergmann 70)

An interpretation is a mapping that assigns a value of 'true' or 'false' to each atomic sentence occurring in $\mathscr{P}.$ Such an interpretation corresponds to a single row of the truth table of $\mathscr{P}.$ Therefore, the problem can also be stated as, "How many rows are in the truth table of a sentence $\mathscr{P}$ containing $n$ atomic components?"

Solution

Let $\Gamma$ be the set of $n$ atomic sentences in $\mathscr{P},$ $\Lambda$ the set of values 'true' and 'false', and $\mathbf{I}:\Gamma\rightarrow \Lambda.$ That is, $\mathbf{I}$ is the interpretation that maps $\mathscr{Q}\mapsto\mathbf{I}(\mathscr{Q})\in\Lambda$ for each atomic sentence $\mathscr{Q}$ in $\mathscr{P}.$ Since $\abs{\Gamma}=n$ and $\abs{\Lambda}=2,$ there are $2^n$ possible interpretations of $\mathscr{P}$ by Theorem 1.

Example

Let $\mathscr{P}$ be the sentence $\unicode{x201C}(A\lor B)\land(A\lor C)"$ and $\Lambda=\{\mathbf{T}, \mathbf{F}\}$ where $\mathbf{T}$ denotes the value 'true' and $\mathbf{F}$ denotes the value 'false'. This sentence has three atomic components, $\Gamma=\{ \unicode{x2018}A\unicode{x2019}, \unicode{x2018}B\unicode{x2019}, \unicode{x2018}C\unicode{x2019} \}.$ Therefore, $n=\abs{\Gamma}=3,$ $r=\abs{\Lambda}=2,$ and there are $n^r=2^3=8$ interpretations of $\mathscr{P},$ or $8$ rows in it's truth table. One such interpretation $\mathbf{I}:\Gamma\rightarrow\Lambda$ assigns \[ \mathbf{I}(\unicode{x2018}A\unicode{x2019})=\mathbf{T}\\ \mathbf{I}(\unicode{x2018}B\unicode{x2019})=\mathbf{F}\\ \mathbf{I}(\unicode{x2018}C\unicode{x2019})=\mathbf{T} \] or, written in the form of Equation \eqref{alpha_map}, \[ ( \unicode{x2018}A\unicode{x2019}, \unicode{x2018}B\unicode{x2019}, \unicode{x2018}C\unicode{x2019} ) \mapsto( \mathbf{T}, \mathbf{F}, \mathbf{T} ), \] the third row of the truth table of $\mathscr{P}$ in standard form.

Problem (iv)

How many truth functions of $n$ arguments are possible? (Bergmann 221)

Solution

Let $\Lambda$ be the set of values 'true' and 'false' and $\alpha:\Lambda^n\rightarrow\Lambda$ be a truth function of $n$ arguments. Then $\abs{\Lambda}=2$ and $\abs{\Lambda^n}$$=\abs{\Lambda}^n$$=2^n$ by Equation \eqref{mult_cor}. Therefore, there are $2^{(2^n)}$ truth functions of $n$ arguments by Theorem 1. Since $\alpha$ is an $n$-ary operation on $\Lambda,$ the answer can be restated. There are $2^{(2^n)}$ $n$-ary operations on $\Lambda.$

Problem (v)

How many functions defined on $n$ points are possible if each functional value is either $0$ or $1?$ (Ross 3)

Solution

This problem is equivalent to Problem (iii) by letting $\Gamma=\{p_1,\ldots,p_n\},$ a set of $n$ points instead of $n$ atomic sentences, and $\Lambda=\{0,1\}$ instead of 'true' or 'false'. Therefore, there are $2^n$ functions defined on $n$ points if each functional value is $0$ or $1.$

Problem (vi)

How many strings of length $r$ from an alphabet of length $n$ can be composed?

Solution

This problem is equivalent to Problem (i) by letting $S$ be the set of $r$ positions in the string and $T$ the alphabet of $n$ characters to draw from. Referring to Equation \eqref{alpha_map}, the expression $(\alpha(x_1),\ldots,\alpha(x_r))$ is the string given by $\alpha$ that assigns the alphabet character $\alpha(x_i)$ to position $x_i.$ That is, $x_i\mapsto\alpha(x_i)$ for each $i\in[1,r].$ Therefore, the number of strings is $n^r.$

Works Cited

Bergmann, Merrie, James Moor and Jack Nelson. The Logic Book. Third Edition. New York: McGraw Hill. 1998. Print.

Durbin, John R. Modern Algebra, An Introduction. Fourth Edition. New York: John Wiley & Sons, Inc. 2000. Print.

Gaughan, Edward D. Introduction to Analysis. Fifth Edition. Providence: American Mathematical Society, 1998. Print.

Ross, Sheldon M. A First Course in Probability. Sixth Edition. Prentice Hall, Upper Saddle River, New Jersey 07458. 2002. Print.