Tsiolkovsky Rocket Equation

In this note, we derive the so called Tsiolkovsky rocket equation or simply rocket equation. It is given by
\begin{equation}
\label{eq:rocket}
\Delta v=v_e\ln\frac{m_0}{m_f}=I_{\mathrm{sp}}g_0\ln\frac{m_0}{m_f}
\end{equation}
where

  • $\Delta v$ is the maximum change of velocity of the vehicle;
  • $v_e=I_{\mathrm{sp}}g_0$ is the effective exhaust velocity;
  • $g_0=9.8\ \mathrm{m}/\mathrm{s}^2$ is the gravitational acceleration of an object in a vacuum near the surface of the Earth;
  • $m_0$, called wet mass, is the initial mass, including propellant;
  • $m_f$, called dry mass, is the final total mass without propellant.

The equation \eqref{eq:rocket} is named after the Russian scientist Konstantin Eduardovich Tsiolkovsky (September 5, 1857 – September 19, 1935). He is dubbed the father of Russian rocket science. It is also called fuel equation.

By the Newton’s second law of motion, the net external force $\vec{F}$ to the change in linear momentum $\vec{P}$ of the whole system (including rocket and exhaust) is
$$\vec{F}=\frac{d\vec{P}}{dt}=\lim_{\Delta t\to 0}\frac{\Delta\vec{P}}{\Delta t}$$
$\Delta\vec{P}=\vec{P}_2-\vec{P}_1$, where $\vec{P}_1=m\vec{V}$ is the momentum of the rocket at time $t=0$ and $\vec{P}_2=(m-\Delta m)(\vec{V}+\Delta\vec{V})+\Delta m\vec{V}_e$ is the momentum of the rocket and exhausted mass at $t=\Delta t$. Here, with respect to the observer, $\vec{V}$ is the velocity of the rocket at time $t=0$, $\vec{V}$ is the velocity of the rocket at time $t=\Delta t$, $\vec{V}_e$ is the velocity of the mass added to the exhaust and lost by the rocket during tim $\Delta t$, $m$ is the mass of the rocket at time $t=0$, and $m-\Delta m$ is the mass of the rocket at time $t=\Delta t$. The velocity of the exhaust $\vec{V}_e$ in the observer frame is related to the velocity of the exhaust in the rocket $\vec{v}_e$ by $$\vec{v}_e=\vec{V}_e-\vec{V}$$ or $$\vec{V}_e=\vec{V}+\vec{v}_e$$ Now, $\Delta\vec{P}$ can be written as $$\Delta\vec{P}=m\Delta\vec{V}+\vec{v}_e\Delta m-\Delta m\Delta\vec{V}$$ Since $\Delta m\to 0$ as $\Delta t\to 0$, we have \begin{equation}\label{eq:rocket2}\vec{F}=m\frac{d\vec{V}}{dt}+\vec{v}_e\frac{dm}{dt}\end{equation} If there are no external forces, then $\vec{F}=0$ i.e. $\frac{d\vec{P}}{dt}=0$ (conservation of linear momentum). \eqref{eq:rocket2} then becomes the separable differential equation \begin{equation}\label{eq:rocket3}-m\frac{d\vec{V}}{dt}=\vec{v}_e\frac{dm}{dt}\end{equation} Assuming that $\vec{v}_e$ is constant (Tsiolkovsky’s hypothesis) $v_e$, and integrating \eqref{eq:rocket3} we have $$\int_v^{v+\Delta v}dv=-v_e\int_{m_0}^{m_f}\frac{dm}{m}$$
where $v=|\vec{V}|$, $\Delta v=|\Delta\vec{V}|$, $m_0$ is the initial total mass and $m_f$ is the final mass. Finally, evaluating the integral yields the rocket equation \eqref{eq:rocket}.

From \eqref{eq:rocket}, we obtain
\begin{equation}
\label{eq:rocket4}
\frac{m_0-m_f}{m_0}=1-\frac{m_f}{m_0}=1-e^{-\frac{\Delta v}{v_e}}
\end{equation}
The equation \eqref{eq:rocket4} gives rise to the percentage of the initial total mass which has to be propellant. This tells us how efficient the rocket engine is as shown in the following example.

Example. Let us consider an SSTO (Single-Stage-To-Orbit) rocket. (Most rockets we are seeing are two-stage-to-orbit or three-stage-to-orbit ones.) The rocket uses liquid hydrogen/liquid oxygen for its propellant, so specific impulse is about $I_{\mathrm{sp}}=350$ s. The exhaust velocity is then given by $v_e=3.43$ km/s. $\Delta v$ needed to get the rocket to a 322 km high LEO (Low Earth Orbit) is 8 km/s. With these values \eqref{eq:rocket4} is evaluated to be
$$1-e^{-\frac{\Delta v}{v_e}}=0.9$$
This means that 90% of the initial total mass has to be propellant. The remaining 10% is for the engines, the fuel tank, and the payload. The payload would account for only about 1% of the initial total mass. This kind of rocket is obviously very inefficient and expensive.

In the Sci-Fi novella The Wandering Earth by Liu Cixin (there is also a movie of the same title on Netflix), the Sun will soon become a supernova and facing the ultimate cataclysmic extinction event, people on Earth turns their entire planet into a spaceship and attempt to relocate it to Proxima Centauri which is the closest star to the Sun (about 4.2 light-years). This is an extremely bold idea even in Chinese scale. (Well, they built the Great Wall!) Disappointingly though, in here, I showed using the rocket equation that it is not even possible for startship Earth to break away from its orbit around the Sun.

Counting and Combinations: Permutations and Combinatorics

Let us begin with the following example.

Example. In how many ways can 8 horses finish in a race? Here, we assume that there are no ties.

Solution. $8\times 7\times 6\times 5\times 4\times 3\times 2\times 1=40,320$ ways.

The example above shows an ordered arrangement. Such an ordered arrangement is called a permutation.

Definition. $n$ factorial $n!$ is defined by
\begin{align*} n!&=n(n-1)(n-2)\cdots 3\cdot 2\cdot 1,\ n\geq 1\\ 0!&=1 \end{align*}

The number of permutation of $n$ objects is $n!$.

Example. There are $6!$ permutations of the six letters of the word “square”. In how may of them is $r$ the second letter?

Solution. $5\times 1\times 4!=5!=120$.

Example. Five different books are on a shelf. In how many different ways can you arrange them?

Solution. $5!=120$.

We now consider the permutation of a set of objects taken from a larger set. Suppose we have $n$ items. The number of ordered arrangements of $k$ items from the $n$ items can be then found by
$$n(n-1)(n-2)\cdots (n-k+1)=\frac{n!}{(n-k)!}$$
Denote this by ${}_nP_k$.

Example. How many license plates are there that starts with three letters followed by 4 digits (no repetitions)?

Solution. \begin{align*} {}_{26}P_3\times {}_{10}P_4&=\frac{26!}{23!}\times\frac{10!}{6!}\\
&=26\cdot 25\cdot 24\cdot 10\cdot 9\cdot 8\cdot 7\\
&=78,624,000
\end{align*}

Example. How many five-digit zip codes can be made where all digits are different? The possible digits are 0-9.

Solution. ${}_{10}P_5=\frac{10!}{5!}=30,240$.

Circular permutations are ordered arrangements of objects in a circle. Suppose that circular permutations such as

are considered as different. Under this assumption, let us consider seating $n$ different objects in a circle. There are $n!$ ways to arrange $n$ seats in a circle depending on where we start and there are $n$ different ways to start seating, so there are $\frac{n!}{n}=(n-1)!$ circular permutations. If the orientation does not matter, i.e. if we consider clockwise and counterclockwise directions are the same, there are $\frac{(n-1)!}{2}$ circular permutations.

Example. In how many ways can you seat 6 persons at a circular dinner table?

Solution. $(6-1)!=5!=120$.

Suppose that we are interested in counting the number of ways to choose $k$ objects from $n$ distinct objects without regard to order. It can be calculated as
$$\frac{{}_nP_k}{k!}=\frac{n!}{k!(n-k)!}$$
This is denoted by ${}_nC_k$ or $\begin{pmatrix}n\\k\end{pmatrix}$ and is read “$n$ choose $k$”.

Example. From a group of 5 women and 7 men, how many different committees consisting of 2 women and 3 men can be formed? What if two of the men are feuding and refuse to serve on the committee together?

Solution. For the first question, there are
\begin{align*} {}_5C_2\times {}_7C_3&=\frac{5!}{2!3!}\times\frac{7!}{3!4!}\\ &=350 \end{align*}
such committees. For the second question, the number of ways to two feuding men and another man is ${}_2C_2\times {}_5C_1=5$. So, the number of selecting male committee members that do not include the two feuding men together is ${}_7C_3-5=30$. Consequently, the number of possible committees in this case is ${}_5C_2\times 30=300$.

Theorem. Suppose that $n$ and $k$ are integers such that $0\leq k\leq n$. Then

  1. ${}_nC_0={}_nC_n=1$ and ${}_nC_1={}_nC_{n-1}=n$.
  2. ${}_nC_k={}_nC_{n-k}$.
  3. Pascal’s identity: ${}_{n+1}C_k={}_nC_{k-1}+{}_nC_k$.

Proof. 2. $${}_nC_{n-k}=\frac{n!}{(n-k)!(n-(n-k))!}=\frac{n!}{(n-k)!k!}={}_nC_k$$

  1. \begin{align*} {}_nC_{k-1}+{}_nC_k&=\frac{n!}{(k-1)!(n-k+1)!}+\frac{n!}{k!(n-k)!}\\ &=\frac{n!k}{k!(n+1-k)!}+\frac{n!(n+1-k)}{k!(n+1-k)!}\\ &=\frac{(n+1)!}{k!(n+1-k)!}\\ &={}_{n+1}C_k
    \end{align*}
    The Pascal’s identity allows us to construct the Pascal’s triangle.
    $$\begin{array}{cccccccccc}
    n & & & & & & & & &\\
    0 & & & & & 1 & & & &\\
    1 & & & & 1 & & 1 & & &\\
    2 & & & 1 & & 2 & & 1 & &\\
    3 & & 1 & & 3 & & 3 & & 1 &\\
    4 & 1 & & 4 & & 6 & & 4 & & 1
    \end{array}$$

Example. The chess club has six members. In how many ways

  1. can all six members line up for a picture?
  2. can they choose a president and a secretary?
  3. can they choose three members to attend a regional tournament with no regard to order?

Solution.

  1. ${}_6P_6=6!=720$.
  2. ${}_6P_2=\frac{6!}{4!}=30$.
  3. ${}_6C_3=\frac{6!}{3!3!}=20$.

Theorem. (Binomial Theorem) Let $n$ be a nonnegative integer. Then
$$(x+y)^n=\sum_{k=0}^n{}_nC_k x^{n-k}y^k$$

Proof. We prove it by induction on $n$. For $n=0$,
$$(x+y)^0=1=\sum_{k=0}^0 {}_0C_k x^{-k}y^k$$ For $n=1$, $$\sum_{k=0}^1 {}_1C_k x^{1-k}y^k=x+y$$ Suppose the statement is true up to $n$, i.e. $$(x+y)^n=\sum_{k=0}^n{}_nC_k x^{n-k}y^k$$ \begin{align*} (x+y)^{n+1}&=(x+y)^n(x+y)\\ &=\sum_{k=0}^n {}_nC_k x^{n-k}y^k\\ &=\sum_{k=0}^n {}_nC_kx^{n+1-k}y^k+\sum_{k=0}^n {}nC_k x^{n-k}y^{k+1}\\ &=\sum_{k=0}^n {}_nC_kx^{n+1-k}y^k+\sum_{k=1}^{n+1} {}_nC{k-1} x^{n+1-k}y^k\ (\mbox{replaing $k$ by $k-1$ in the second sum})\\ &={}_nC_0x^{n+1}+\sum_{k=1}^n[{}_nC_k+{}_nC{k-1}]x^{n+1-k}y^k+{}_nC_n y^{n+1}\\ &={}_{n+1}C_0 x^{n+1}+\sum_{k=1}^n {}_{n+1}C_k x^{n+1-k}y^k+{}_{n+1}C_{n+1} y^{n+1}\ (\mbox{Pascal’s identity})\\
&=\sum_{k=0}^{n+1}{}_{n+1}C_k x^{n+1-k}y^k
\end{align*}
This completes the proof.

Example. Expand $(x+y)^6$ using the Binomial Theorem.

Solution.
$$(x+y)^6=x^6+6x^5y+15x^4y^2+20x^3y^3+15x^2y^4+6xy^5+y^6$$

Example. How many subsets are there of a set with $n$ elements?

Solution. There are ${}nC_k$ subsets of $k$ elements, $0\leq k\leq n$. Hence, the total number of subsets of a set of $n$ elements is $$\sum_{k=0}^n {}_nC_k=(1+1)^n=2^n$$

References:

Marcel B. Finan, A Probability Course for the Actuaries

Sheldon Ross, A First Course in Probability, Fifth Edition, Prentice Hall, 1997

Fermat Factorization

Proposition. Let $n$ be a positive odd integer. There is a one-to-one correspondence between factorizations of $n$ in the form $n=ab$ , where $a\geq b>0$, and the representations of $n$ in the form $t^2-s^2$, where $s$ and $t$ are nonnegative integers. The correspondence is given by the equation
$$t=\frac{a+b}{2},\ s=\frac{a-b}{2};\ a=t+s,\ b=t-s$$

Proof. Given $n=ab$, we can write
$$n=ab=\left(\frac{a+b}{2}\right)^2-\left(\frac{a-b}{2}\right)^2$$
Conversely, given $n=t^2-s^2$, $n$ can be factored as $n=(t+s)(t-s)$.

If $n=ab$ with $a$ and $b$ close together, then $s=\frac{a-b}{2}$ is small, and so $t=\frac{a+b}{2}$ is slightly larger than $\sqrt{n}$. In that case, we can find $a$ and $b$ by trying all values of $t$ starting with $[\sqrt{n}]+1$, until we find one for which $t^2-n=s^2$ is a perfect square. This method is called the Fermat factorization.

Example. Factor $200819$.

Solution. $[\sqrt{200819}]+1=449$.
\begin{align*} 449^2-200819&=782,\ \mbox{not a perfact square}\\ 450^2-200819&=1681=41^2 \end{align*}
Hence,
$$200819=450^2-41^2=(450+41)(450-41)=491\cdot 409$$

If $a$ and $b$ are not close together for $n=ab$, although the Fermat factorization method will eventually find $a$ and $b$, one will have to try a large number of $t=[\sqrt{n}]+1, [\sqrt{n}]+2,\cdots$. There is a generalization of Fermat factorization. Choose small $k$, successively set $t=[\sqrt{kn}]+1, [\sqrt{kn}]+2,\cdots$, etc. until we find a $t$ for which $t^2-kn=s^2$ is a perfect square. Then $(t+s)(t-s)=kn$ and a nontrivial common factor of $n$ can be found by calculating $(t+s,n)$.

Example. Factor 141467.

Solution. First we factor 141467 by simple Fermat factorization. Since $\sqrt{141467}\approx 376.1209911717239$, we successively try $t=377,378,\cdots$ until we find $t^2-141467$ is a perfect square. We find
$$t^2-141467=414^2-141467=29929=173^2$$
Thus,
$$141467=414^2-173^2=(414+173)(414-173)=587\cdot 241$$
Now, this time we factor 141467 by generalized Fermat factorization with $k=3$. We try $t=[\sqrt{3n}]+1=652, 653,\cdots$ and find
$$t^2-3n=655^2-3\cdot 141467=4624=68^2=s^2$$
$(t+s,n)=(723,141467)=241$ and so $141467=241\cdot 587$.

The following two propositions tell us that it is not a good idea to choose an even number for $k$ in generalized Fermat factorization.

Proposition. If $k=2$, or if $k$ is any integer divisible by 2 but not by 4, then we cannot factor a large odd $n$ using generalized Fermat factorization with this choice of $k$.

Proof. $n$ is an odd integer, so $n=2m+1$ for some $m\in\mathbb{Z}$. For $k=2$, $kn=4m+2\equiv 4\mod 4$. If $k$ is an integer divisible by 2 but not by 4, $k=2(2l+1)=4l+2$ for some $l\in\mathbb{Z}$ and $kn\equiv 2\mod 4$. $t^2-s^2=kn\equiv 2\mod 4$, but the difference of two squares cannot be 2 modulo 4. (Each of the integers $t$ and $s$ is one of the forms $4u$, $4u+1$, $4u+2$, or $4u+3$ for some $u\in\mathbb{Z}$, so there are 16 different cases of $t$ and $s$ and in each case you can easily check if $t^2-s^2$ can be 2 modulo 4. For instance if $t=4u_1+1$ and $s=4u_2+2$, then
$t^2-s^2\equiv 1^2-2^2\equiv 1\mod 4$.)

Proposition. If $k=4$, and if generalized Fermat factorization works for a certain $t$, then simple Fermat factorization (with $k=1$) would have worked equally well.

Proof. $t^2-s^2=kn=4n\equiv 4\mod 8$ which can hold only if both $s$ and $t$ are even. In that case, $\left(\frac{s}{2}\right)^2=\left(\frac{t}{2}\right)^2-n$, so simple Fermat factorization would have worked equally well.

Factoring by the Monte Carlo Method

The Monte Carlo method is a computational simulation scheme, originally introduced by Stanisław Ulam, that solves a wide variety of problems arising in chemistry, economics, finance, mathematics, physics, etc. In this note, we discuss an application of the Monte Carlo method in factoring of integers. It is also called rho method and was introduced by J. M. Pollack.

The first step is to choose an easily evaluated map from $\mathbb{Z}_n$ to itself. A popular choice is $f(x)=x^2+1$. Next, one chooses an initial value $x=x_0$, and then computes the successive iterates of $f$: $x_1=f(x_0)$, $x_2=f(x_1)$, $x_3=f(x_2)$, etc. i.e. $x_{j+1}=f(x_j)$, $j=0,1,2,\cdots$. Compare the $x_j$’s, hoping to find two which are different modulo $n$ but the same modulo some divisor of $n$. Once we find such $x_i$, $k_k$, we have $(x_k-x_j,n)$ equal to a proper divisor of $n$

Example. Let us factor $91$ by choosing $f(x)=x^2+1$, $x_0=1$.
\begin{align*} x_1&=f(x_0)=2\\ x_2&=f(2)=5\\ x_3&=f(5)=26\\ &\vdots \end{align*}
Since $(x_3-x_2,n)=(21,91)=7$, 7 is a factor.

The method works by successively computing $x_k=f(x_{k-1})$ and comparing $x_k$ with the earlier $x_j$ until we find a pair satisfying $(x_k-x_j,n)=r>1$. But as $k$ gets larger, it becomes more time consuming to compute $(x_k-x_j,n)$ for each $j<k$. Note that once there is a pair $(k_0,j_0)$ such that $x_{k_0}\equiv x_{j_0} \mod r|n$, we have the same relation $x_k\equiv x_j\mod r$ for any pair $(j,k)$ such that $k-j=k_0-j_0$: Set $k=k_0+m$ and $j=j_0+m$, and apply $f$ to both sides of the congruence $x_{k_0}\equiv x_{j_0}\mod r$ repeatedly $m$ times.

The previous algorithm can be modified so that we need to calculate the gcd only once for each $k$. This significantly reduces the required computational burden. Here is the modified algorithm.

We successively compute the $x_k$. For each $k$, we proceed as follows. Suppose $k$ is an $(h+1)$-bit integer, i.e. $2^h\leq k<2^{h+1}$. Let $j$ be the largest $h$-bit integer: $j=2^h-1$. We compare $x_k$ with this particular $x_j$, i.e. compute $(x_k-x_j,n)$. If this gcd gives a nontrivial factor of $n$, stop. Otherwise continue on to $k+1$.

Example. $n=91$, $f(x)=x^2+1$, $x_0=1$.
\begin{align*} x_1&=f(1)=2\\ x_2&=f(2)=5;\ (x_2-x_1,n)=(5-2,91)=1\\ x_3&=f(5)=26;\ (x_3-x_1,n)=(24,91)=1\\ x_4&=f(26)=26^2+1\equiv 40\mod 91;\ (x_4-x_3,n)=(14,91)=7 \end{align*}

Example. Factor 4087 using $f(x)=x^2+x+1$ and $x_0=2$.
\begin{align*} x_1&=f(2)=7;\ (x_1-x_0,n)=(7-2,4087)=1\\ x_2&=f(7)=57;\ (x_2-x_1,n)=(57-7,4087)=1\\ x_3&=f(57)=3307;\ (x_3-x_1,n)=(3307-7,4087)=1\\ x_4&=f(3307)\equiv\mod 4087;\ (x_4-x_3,n)=(2745-3307,4087)=1\\ x_5&=f(2745)\equiv 1343\mod 4087; (x_5-x_3,n)=(1343-3307,4087)=1\\ x_6&=f(1343)\equiv 2626\mod 4087;\ (x_6-x_3, n)=(2626-3307,4087)=1\\ x_7&=f(2626)\equiv 3734\mod 4087;\ (x_7-x_3,n)=(3734-3307,4087)=61 \end{align*}
Hence, $61$ is a factor of $4087$ and $4087=61\cdot 67$.

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