Counting and Combinatorics: The Fundamental Principle of Counting

Example. A lottery allows to select a two-digit number. Each digit may be either 1, 2, or 3. Show all possible out comes. Show all possible outcomes.

Solution. There are three different ways to choose the first digit. For each choice of the first digit, there are three different ways of choosing the second digit (a tree diagram would visually show this). Hence, there are nine possible outcomes of the two-digit numbers and they are
$${11,12,13,21,22,23,31,32,33}$$

Theorem [The Fundamental Principle of Counting]. If a choice consists of $k$ steps, of which the fist can be made in $n_1$ ways, for each of these the second can be made in $n_2$ ways, …, and for each of these the $k$th can be made in $n_k$ ways, then the whole choice can be made in $n_1n_2\cdots n_k$ ways.

Proof. Let $S_i$ denote the set of outcomes for the $i$th task, $i=1,\cdots,k$, and let $n(S_i)=n_i$. Then the set of outcomes for the entire job is
$$S_1\times S_2\times\cdots\times S_k={(s_1,s_2,\cdots,s_k)| s_i\in S_i,\ 1\leq i\leq k}$$
Now, we show that
$$n(S_1\times S_2\times\cdots\times S_k)=n(S_1)n(S_2)\cdots n(S_k)$$
by induction on $k$. Let $k=2$. For each element in $S_1$, there are $n_2$ choices from the set $S_2$ to pair with the element. Thus, $n(S_1\times S_2)=n_1n_2$. Suppose that
$$n(S_1\times S_2\times\cdots\times S_m)=n(S_1)n(S_2)\cdots n(S_m)$$
For each $m$-tuple in $S_1\times S_2\times\cdots\times S_m$, there are $n_{m+1}$ choices of elements in the set $S_{m+1}$ to pair with the $m$-tuple. Thus,
\begin{align*} n(S_1\times S_2\times\cdots\times S_{m+1})&=n(S_1\times S_2\times\cdots\times S_m)n(S_{m+1})\\ &=n(S_1)n(S_2)\cdots n(S_{m+1})\ (\mbox{by the induction hypothesis}) \end{align*}
Therefore, by the induction principle,
$$n(S_1\times S_2\times\cdots\times S_k)=n(S_1)n(S_2)\cdots n(S_k)$$

Example. In designing a study of the effectiveness of migraine medicines, 3 factors were considered.

  1. Medicine (A, B, C, D, Placibo)
  2. Dosage Level (Low, Medium, High)
  3. Dosage Frequency (1, 2, 3, 4 times/day)

In how many possible ways can a migraine patient be given medicine?

Solution. $5\cdot 3\cdot 4=60$ different ways.

Example. How many license-plates with 3 letters followed by 3 digits exist?

Solution. There are $10\cdot 10\cdot 10=1000$ ways to choose 3 digits. For each $3$ digit, there are $26\cdot 26\cdot 26=17,576$ ways to choose 3 letters. Hence, the number of ways to make license-plates is $17,270,576,000$.

Example. How many numbers in the range $1000-9999$ have no repeated digits?

Solution. There are 9 different ways to choose the first digit. For each choice of the first digit, there are 9 different ways to choose the second digit without repeating the first digit. For each choice of the first and the second digits, there are 8 different ways to choose the third digit without repeating the first and the second digits. For each choice of the first, second and third digits, there are 7 different ways to choose the fourth digit without repeating the first, second, third digits repeated. Therefore, the answer is $9\cdot 9\cdot 8\cdot 7=4,536$ ways.

Example. How many license-plates with 3 letters followed by 3 digits if exactly one of the digits is 1.

Solution. \begin{align*} 26\cdot 26\cdot 26\cdot(1\cdot 9\cdot 9+9\cdot 1\cdot 9+9\cdot 9\cdot 1)&=26\cdot 26\cdot 26\cdot 3\cdot 9\cdot 9\\ &=4,270,968 \end{align*}
ways.

References:

  1. Marcel B. Finan, A Probability Course for the Actuaries
  2. Sheldon Ross, A First Course in Probability, Fifth Edition, Prentice Hall, 1997

System of Linear Equations and Determinant

In this note, we discuss the relationship between a system of linear equations and the determinant of its coefficients. For simplicity, I am considering only a system of two linear equations with two variables. But a similar argument can be used for more general cases. Let us consider the system of linear equations $$\left\{\begin{aligned}ax+by&=e\\cx+dy&=f\end{aligned}\right.,$$ where none of $a,b,c,d,e,f$ is zero. The two linear equations are equations of lines in the plane, so we know there are three possibilities: There is no solution of the system in which case the two lines are parallel (so they do not meet), the system has a unique solution in which case the two lines meet at exactly one point, or the system has infinitely many solutions in which case the two lines are identical. This system can be written in terms of matrices as $$\begin{pmatrix}a & b\\c & d\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}=\begin{pmatrix}e\\f\end{pmatrix}$$ Let $A=\begin{pmatrix}a & b\\c & d\end{pmatrix}$. If $\det A\ne 0$, then the system has a unique solution and it can be found using the Cramer’s rule as follows: $$x=\frac{\begin{vmatrix}e & b\\f & d\end{vmatrix}}{\det A},\ y=\frac{\begin{vmatrix}a & e\\c & f\end{vmatrix}}{\det A}$$ Note that $\det A=0$ if and only if the two lines have the same slope. Suppose that $\det A=0$. Then one can easily show that $\begin{vmatrix}e & b\\f & d\end{vmatrix}=0$ if and only if $\begin{vmatrix}a & e\\c & f\end{vmatrix}=0$. From $\det A=0$ and $\begin{vmatrix}e & b\\f & d\end{vmatrix}=0$, we have the system of equations: \begin{align}\label{eqn1}ad-bc&=0\\\label{eqn2}ed-fc&=0\end{align} Subtracting $a$ times \eqref{eqn2} from $e$ times \eqref{eqn1} yields $b(af-ec)=0$. Since $b\ne 0$, $af-ec=\begin{vmatrix}a & e\\c & f\end{vmatrix}=0$ which means that the two lines have the same $y$-intercept. This is the case when the two lines coincide and hence the system has infinitely many solutions (all the points on the line are solutions). Lastly, we know $\begin{vmatrix}e & b\\f & d\end{vmatrix}\ne0$ if and only if $\begin{vmatrix}a & e\\c & f\end{vmatrix}\ne0$. If $\begin{vmatrix}a & e\\c & f\end{vmatrix}\ne0$ while $\det A=0$, from the Cramer’s rule the system does not have a solution. $\begin{vmatrix}a & e\\c & f\end{vmatrix}\ne0$ means that the two lines have different $y$-intercepts, so this is the case when the two lines are parallel i.e. they do not meet. A system of homogeneous linear equations $$\left\{\begin{aligned}ax+by&=0\\cx+dy&=0\end{aligned}\right.$$ comes down to only two cases: the system has a unique solution $x=y=0$ (if $\det A\ne 0$) or has infinitely many solutions (if $\det A=0$). This is also obvious from considering two lines passing through the origin.

Should the sign of Coulomb potential be positive or negative?

In classical physics, the sign of a potential (say, gravitational potential or electric potential) is merely a convention. For example, since the electric field $\mathbb{E}$ is conservative, it is the gradient of some potential, which we call the electric potential or Coulomb potential $V$, so it can be written as $\mathbb{E}=\nabla V$ or $\mathbb{E}=-\nabla V$. Mathematically, it doesn’t matter whichever you use. If you choose $\mathbb{E}=\nabla V$, Coulomb potential should be $V=-\frac{1}{4\pi\epsilon_0}\frac{Q}{r}$ and if you choose $\mathbb{E}=-\nabla V$, $V=\frac{1}{4\pi\epsilon_0}\frac{Q}{r}$. In physics, the usual convention is $\mathbb{E}=-\nabla V$ and it is interpreted as electric field pointing downhill towards lower voltages.

On the other hand, in quantum mechanics the sign of Coulomb potential matters and it does depend on the problem that you are studying. In a hydrogen atom or a hydrogen-like atom (for example, an ionized helium atom $\mathrm{He}^+$) an electron is trapped in the atom by Coulomb force between proton and electron. In this case, we say the electron is in a bound state. The bound state with the minimum energy is called the ground state and the minimum energy is called the ground state energy. A bound state with energy higher than the ground state energy is said to be unstable and the electron in an unstable bound state always tend to move to the ground state by emitting photons. Modeling bound state of a hydrogen atom or a hydrogen-like atom requires negative Coulomb potential $V(r)=-\frac{Z\alpha}{r}$ as seen in the following figure.

Coulomb potential (in red) with bound state energy (in blue)

In this simple figure, the electron is trapped in the region $0<r<1$. The figure also clearly shows you that bound state energy must be negative. By drawing a picture, one can easily see that bound state cannot be modeled with positive Coulomb potential, but positive Coulomb potential is used to model scattering of a particle.

The Momentum Representation

This note is based on my friend Khin Maung’s short lecture.

Let us begin with Schrödinger equation
$$\left(\frac{\hat p^2}{2m}+\hat V(r)\right)|\psi\rangle=E|\psi\rangle$$
Use the completeness relation
$$1=\int|\vec{p}\rangle\langle\vec{p}|d\vec{p}$$
to get the momentum space representation of the Schrödinger equation
\begin{equation}
\label{eq:schrodingerms}
\frac{p^2}{2m}\psi(\vec{p})+\int\langle\vec{p}|\hat V(r)|\vec{p’}\rangle\psi(\vec{p’})d\vec{p’}=E\psi(\vec{p})
\end{equation}
where $\psi(\vec{p}):=\langle\vec{p}|\psi\rangle$. \eqref{eq:schrodingerms} is called the Schrödinger equation in momentum space. Using the completeness relation
$$1=\int|\vec{r}\rangle\langle\vec{r}|d\vec{r}$$
we obtain
$$\langle\vec{p}|\hat V(r)|\vec{p’}\rangle=\frac{1}{(2\pi\hbar)^3}\int e^{\frac{i}{\hbar}(\vec{p’}-\vec{p})\cdot\vec{r}}V(r)d\vec{r}$$
Here, recall that $\langle\vec{p}|\vec{r}\rangle=\frac{1}{(2\pi\hbar)^{\frac{3}{2}}}e^{-\frac{i}{\hbar}\vec{p}\cdot\vec{r}}$. Let $\vec{q}=\vec{p’}-\vec{p}$ and $V(\vec{q})=\langle\vec{p}|\hat V(r)|\vec{p’}\rangle$. Then we have
$$V(\vec{q})=\frac{1}{(2\pi\hbar)^3}\int e^{\frac{i}{\hbar}\vec{q}\cdot\vec{r}}V(r)d\vec{r}$$
This is just the Fourier transform of $V(r)$. For the Yukawa potential
$$V(r)=V_0\frac{e^{-\mu r}}{r}$$
\begin{align*} V(\vec{q})&=\frac{1}{(2\pi\hbar)^3}\int e^{\frac{i}{\hbar}qr\cos\theta}\int_0^{2\pi}\int_0^\pi\int_0^\infty V(r)r^2dr\sin\theta d\theta d\phi\\ &=\frac{1}{(2\pi)^2\hbar^3}\int_0^\infty V(r)r^2\int_{-1}^1e^{\frac{i}{\hbar}qru}dudr\\ &=\frac{1}{(2\pi\hbar)^2iq}\int_0^\infty V(r)r(e^{\frac{i}{\hbar}qr}-e^{-\frac{i}{\hbar}qr})dr\\ &=\frac{V_0}{(2\pi\hbar)^2iq}\int_0^\infty e^{-\mu r}(e^{\frac{i}{\hbar}qr}-e^{-\frac{i}{\hbar}qr})dr\\ &=\frac{V_0}{2\pi^2\hbar^3}\frac{1}{\mu^2+\frac{q^2}{\hbar^2}} \end{align*}
From here on, we assume that $\hbar=1$ for simplicity.

Let
$$\psi(\vec{p})=\psi_l(p)Y_l^m(\hat p)$$
Here, $\hat p$ stands for the unit vector in the momentum space in spherical coordinates $\hat p=\frac{\vec{p}}{p}=(\theta_l,\phi_p)$ where $\theta_l$ is the polar angle and $\phi_p$ is the azimuth angle corresponding to the momentum vector $\vec{p}$. $V(\vec{q})$ can be written as the series
\begin{align*} V(\vec{q})&=\sum_{l=0}^\infty\sum_{m=-l}^lV_l(p,p’)Y_l^m(\hat p)Y_l^{m}(\hat p’)\\
&=\sum_{l=0}^\infty\frac{2l+1}{4\pi}V_l(p,p’)P_l(x)
\end{align*} The last line is obtained by the addition theorem for spherical harmonics $$\frac{4\pi}{2l+1}\sum_{m=-l}^lY_l^m(\hat p)Y_l^{m}(\hat p’)=P_l(x)$$
where $x=\cos\theta_{pp’}$.
By the orthonormality of spherical harmonics
$$\int_0^{2\pi}\int_0^\pi Y_{l_1}^{m_1}(\hat p)Y_{l_2}^{m_2}(\hat p)\sin\theta d\theta d\phi=\delta_{l_1l_2}\delta_{m_1m_2}$$
the Schrödinger equation in momentum space \eqref{eq:schrodingerms} yields
$$\frac{p^2}{2m}\psi_l(p)+\int_0^\infty V_l(p,p’)\psi_l(p’)p’^2dp’=E\psi_l(p)$$
Using the orthogonality of Legendre polynomials
$$\int_{-1}^1P_{l’}(x)P_l(x)dx=\frac{2}{2l+1}\delta_{ll’}$$
we obtain
$$V_l(p,p’)=2\pi\int_{-1}^1V(\vec{q})P_l(x)dx$$
For the Yukawa potential, we have
$$V(\vec{q})=\frac{V_0}{2\pi^2}\frac{1}{\mu^2+q^2}=\frac{V_0}{2\pi^2}\frac{1}{p^2+p’^2+\mu^2-2pp’x}$$
The Neumann’s formula yields then
$$V_l(p,p’)=\frac{V_0}{pp’\pi}Q_l\left(\frac{p^2+p’^2+\mu^2}{2pp’}\right)$$
Note here that we require $\left|\frac{p^2+p’^2+\mu^2}{2pp’}\right|>1$. Recall that
$$Q_0(z)=\frac{1}{2}\ln\frac{z+1}{z-1}$$
for $|z|>1$. Hence for the Yukawa potential, $V_0(p,p’)$ can be written as
$$V_0(p,p’)=\frac{V_0}{2pp’\pi}\ln\frac{(p+p’)^2+\mu^2}{(p-p’)^2+\mu^2}$$
With $V_0=Z\alpha$ and $\mu=0$, the Yukawa potential reduces to the Coulomb potential $V(r)=\frac{Z\alpha}{r}$. $V_l(p,p’)$ is then given by$$V_l(p,p’)=\frac{Z\alpha}{pp’\pi}Q_l\left(\frac{p^2+p’^2}{2pp’}\right)$$
and accordingly,$$V_0(p,p’)=\frac{Z\alpha}{pp’\pi}\ln\left|\frac{p+p’}{p-p’}\right|$$

Neumann’s Formula

Today I learned a pretty cool formula called Neumann’s formula while reading a paper by Maurice Lévy, Wave equations in momentum space, Proceedings of the Royal Society of London. Series A, Vol. 204, No. 10 (7 December 1950), pp. 145-169. When $n$ is a positive integer and $|z|>1$, the Legendre function of the second kind $Q_n(z)$ can be expressed in terms of the Legendre function of the first kind $P_n(x)$ as
$$Q_n(z)=\frac{1}{2}\int_{-1}^1\frac{P_n(x)}{z-x}dx$$
A derivation of this formula can be found on p. 320 of E. T. Whittaker and G. N. Watson, A Course in Modern Analysis, 4th edition, Cambridge University Press, 1927 as cited in the Lévy’s paper (the page number is incorrectly cited as p. 330). The formula is originally appeared in a paper by J. Neumann (the author’s name is incorrectly cited as F. Neumann in Whittaker & Watson), Entwicklung der in elliptischen Coordinaten ausgedrückten reciproken Entfernung zweier Puncte in Reihen, welche nach den Lalace’schen $Y^{(n)}$ fortschreiten; und Anwendung dieser Reihen zur Bestimmung des magetischen Zustandes eines Rotations-Ellipsoïds, welcher durch vertheilende Kräfte erregt ist. pp. 21-50 (the formula appears on page 22), Journal für die reine und angewandte Mathematik (Crelle’s journal), de Gruyter, 1848. The title is unusually long. It reads like an abstract rather than a title. Maybe it was not unusual back then.

The formula can be used to evaluate the following integral
$$I=2\pi\int_0^\pi\frac{P_l(\cos\theta)\sin\theta d\theta}{|\vec{p}-\vec{p’}|^2+\mu^2}$$
which appears in the momentum representation of Schrödinger equation with Yukawa potential. With $x=\cos\theta$, the integral $I$ can be written as
\begin{align*} I&=2\pi\int_{-1}^1\frac{P_l(x)dx}{p^2+p’^2-2pp’x+\mu^2}\\ &=\frac{2\pi}{pp’}\frac{1}{2}\int_{-1}^1\frac{P_l(x)dx}{\frac{p^2+p’^2+\mu^2}{2pp’}-x}\\ &=\frac{2\pi}{pp’}Q_l\left(\frac{p^2+p’^2+\mu^2}{2pp’}\right) \end{align*}