Advanced counting

This learning module has many interactive demos. It is easier to work with them on a larger screen. Bookmark and revisit if you are currently on a small screen device.

\(\DeclareMathOperator*{\argmax}{arg\,max} \DeclareMathOperator*{\argmin}{arg\,min} \DeclareMathOperator*{\asterisk}{\ast} \newcommand{\sup}{\text{sup}} \newcommand{\inf}{\text{inf}} \newcommand{\min}{\text{min}\;} \newcommand{\max}{\text{max}\;} \newcommand{\maxunder}[1]{\underset{#1}{\max}} \newcommand{\minunder}[1]{\underset{#1}{\min}} \newcommand{\real}{\mathbb{R}} \newcommand{\natural}{\mathbb{N}} \newcommand{\integer}{\mathbb{Z}} \newcommand{\rational}{\mathbb{Q}} \newcommand{\irrational}{\mathbb{I}} \newcommand{\complex}{\mathbb{C}} \newcommand{\cardinality}[1]{|#1|} \newcommand{\vec}[1]{\mathbf{#1}} \newcommand{\mat}[1]{\mathbf{#1}} \newcommand{\star}[1]{#1^*} \newcommand{\inv}[1]{#1^{-1}} \newcommand{\indicator}[1]{\mathcal{I}(#1)} \renewcommand{\BigO}[1]{\mathcal{O}(#1)} \renewcommand{\BigOsymbol}{\mathcal{O}} \renewcommand{\smallo}[1]{\mathcal{o}(#1)} \renewcommand{\smallosymbol}[1]{\mathcal{o}} \newcommand{\set}[1]{\mathbb{#1}} \newcommand{\complement}[1]{#1^c} \newcommand{\powerset}[1]{\mathcal{P}(#1)} \newcommand{\setdiff}{\setminus} \newcommand{\setsymmdiff}{\oplus} \newcommand{\dash}[1]{#1^{'}} \newcommand{\permutation}[2]{{}_{#1} \mathrm{ P }_{#2}} \newcommand{\combination}[2]{{}_{#1} \mathrm{ C }_{#2}} \newcommand{\prob}[1]{P(#1)} \newcommand{\pmf}[1]{P(#1)} \newcommand{\pdf}[1]{p(#1)} \newcommand{\cdf}[1]{F(#1)} \newcommand{\expect}[2]{E_{#1}\left[#2\right]} \newcommand{\entropy}[1]{\mathcal{H}\left[#1\right]} \newcommand{\expe}[1]{\mathrm{e}^{#1}} \newcommand{\textexp}[1]{\text{exp}\left(#1\right)} \def\independent{\perp\!\!\!\perp} \def\notindependent{\not\!\independent} \newcommand{\yhat}{\hat{y}} \newcommand{\vs}{\vec{s}} \newcommand{\vt}{\vec{t}} \newcommand{\vu}{\vec{u}} \newcommand{\vv}{\vec{v}} \newcommand{\vw}{\vec{w}} \newcommand{\vx}{\vec{x}} \newcommand{\vy}{\vec{y}} \newcommand{\vz}{\vec{z}} \newcommand{\va}{\vec{a}} \newcommand{\vb}{\vec{b}} \newcommand{\vc}{\vec{c}} \newcommand{\vd}{\vec{d}} \newcommand{\ve}{\vec{e}} \newcommand{\vg}{\vec{g}} \newcommand{\vh}{\vec{h}} \newcommand{\vi}{\vec{i}} \newcommand{\vk}{\vec{k}} \newcommand{\vo}{\vec{o}} \newcommand{\vp}{\vec{p}} \newcommand{\vq}{\vec{q}} \newcommand{\vr}{\vec{r}} \newcommand{\vs}{\vec{s}} \newcommand{\vmu}{\vec{\mu}} \newcommand{\vsigma}{\vec{\sigma}} \newcommand{\vphi}{\vec{\phi}} \newcommand{\vtau}{\vec{\tau}} \newcommand{\vtheta}{\vec{\theta}} \newcommand{\mA}{\mat{A}} \newcommand{\mB}{\mat{B}} \newcommand{\mC}{\mat{C}} \newcommand{\mD}{\mat{D}} \newcommand{\mE}{\mat{E}} \newcommand{\mH}{\mat{H}} \newcommand{\mK}{\mat{K}} \newcommand{\mP}{\mat{P}} \newcommand{\mQ}{\mat{Q}} \newcommand{\mR}{\mat{R}} \newcommand{\mS}{\mat{S}} \newcommand{\mU}{\mat{U}} \newcommand{\mV}{\mat{V}} \newcommand{\mW}{\mat{W}} \newcommand{\mX}{\mat{X}} \newcommand{\mY}{\mat{Y}} \newcommand{\mZ}{\mat{Z}} \newcommand{\mI}{\mat{I}} \newcommand{\mLambda}{\mat{\Lambda}} \newcommand{\mSigma}{\mat{\Sigma}} \newcommand{\mTheta}{\mat{\theta}} \newcommand{\setsymb}[1]{#1} \newcommand{\sA}{\setsymb{A}} \newcommand{\sB}{\setsymb{B}} \newcommand{\sC}{\setsymb{C}} \newcommand{\sO}{\setsymb{O}} \newcommand{\sP}{\setsymb{P}} \newcommand{\sQ}{\setsymb{Q}} \newcommand{\sH}{\setsymb{H}} \newcommand{\sX}{\setsymb{X}} \newcommand{\sY}{\setsymb{Y}} \newcommand{\norm}[2]{||{#1}||_{#2}} \newcommand{\infnorm}[1]{\norm{#1}{\infty}} \newcommand{\fillinblank}{\text{ }\underline{\text{ ? }}\text{ }} \newcommand{\lbrace}{\left\{} \newcommand{\rbrace}{\right\}} \newcommand{\set}[1]{\lbrace #1 \rbrace} \newcommand{\seq}[1]{\left( #1 \right)} \newcommand{\ndim}{N} \newcommand{\ndimsmall}{n} \newcommand{\dataset}{\mathbb{D}} \newcommand{\ndata}{D} \newcommand{\ndatasmall}{d} \newcommand{\labeledset}{\mathbb{L}} \newcommand{\nlabeled}{L} \newcommand{\nlabeledsmall}{l} \newcommand{\unlabeledset}{\mathbb{U}} \newcommand{\nunlabeled}{U} \newcommand{\nunlabeledsmall}{u} \newcommand{\nclass}{M} \newcommand{\nclasssmall}{m} \newcommand{\loss}{\mathcal{L}} \newcommand{\sign}{\text{sign}} \newcommand{\Gauss}{\mathcal{N}} \newcommand{\hadamard}{\circ} \newcommand{\doh}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\dox}[1]{\doh{#1}{x}} \newcommand{\doy}[1]{\doh{#1}{y}} \newcommand{\doxx}[1]{\doh{#1}{x^2}} \newcommand{\doyy}[1]{\doh{#1}{y^2}} \newcommand{\doxy}[1]{\frac{\partial #1}{\partial x \partial y}} \newcommand{\doyx}[1]{\frac{\partial #1}{\partial y \partial x}} \newcommand{\qed}{\tag*{$\blacksquare$}}\)

        Advanced counting
        Foundations of mathematics
      

Introduction

In this article, we continue to expand our understanding of counting by studying advanced counting concepts involving recurrence relations, onto functions, and derangements.

Recurrence relations

A formula that defines the terms of a sequence $ \set{a_n} $ as some function of one or more of the previous terms of the sequence, namely $ a_0, a_1, \ldots, a_{n-1} $ for all integers $ n $ such that $ n \ge n_0 $, is known as a recurrence relation.

A sequence is known as a solution to a recurrence relation if its terms satisfy the recurrence relation.

Example

Consider a sequence indicating the population of bacteria in some experiment. Every instant, the bacteria in the petri dish double. Then, this can be expressed as a recurrence relation $ a_n = 2 a_{n-1} $. If we set some initial condition, say the starting number of bacteria $ a_0 = 1 $, then we can calculate the total number of bacteria at any instant given the recurrence relation.

Linear homogeneous recurrence relation

A linear homogeneous recurrence relation of degree $ k $ with constant coefficients is a recurrence relation of the form

$$ a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{n-k} $$

where $ c_1, c_2, \ldots, c_k $ are real numbers and $ c_k \ne 0 $.

Thus, the degree defines the farthest backward dependency in describing the recurrence relation. The relationship is linear because all the past terms of the sequence appear in a sum. Finally, it is considered homogeneous, because there are no terms in the relation which do not involve some past term $ a_j $.

Fibonacci sequence

In 13th century, Fibonacci (Leonardo of Pisa) posed an interesting problem in his book Liber Abaci.

A pair of young rabbits (one of each gender) is placed on an uninhabited island. Rabbits cannot reproduce until they are two months old, but once they are two months old, each reproducing pair breeds on pair of rabbits per month! What will be the number of rabbits on the island after $ n $ months? Assume that the rabbits are immortal and genders are equally represented in each brood.

We present this scenario in the following figure. We have marked each pair with an identifier to show the movement of a pair from the pool of young rabbits to those who are capable of reproducing.

Month	Reproducing pairs	Young pairs	Total pairs
0	0	1	1
1	0	1	1
2	1	1	2
3	1	2	3
4	2	3	5
5	3	5	8

Note the total pairs at each month. They follow a recurrence relation! The total pair of rabbits in any month is the sum of total pairs in the prior two months.

Thus, the sequence of total number of rabbits after $ n $ months can be described as the recurrence relation below.

$$ f_n = f_{n-1} + f_{n-2} $$

with the initial conditions $ f_0 = 1 $ and $ f_1 = 1 $.

It is a linear homogeneous recurrence relation of degree $ 2 $. Stay tuned through this article to figure out how to calculate the value of $ f_n $ for any value of $ n $.

Characteristic equation of a recurrence relation

Consider a linear homogeneous recurrence relation of degree $ k $ with constant coefficients

$$ a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{n-k} $$

where $ c_1, c_2, \ldots, c_k $ are real numbers and $ c_k \ne 0 $.

When solving recurrence relations of this form, it is usually the case that we wish to find solutions of the form $ a_n = r^n $ where $ r $ is some constant real number.

Note that if such a solution is possible, then it must be the case that

$$ r^n = c_1 r^{n-1} + c_2 r^{n-2} + \ldots + c_k r^{n-k} $$

Rearranging these terms to the left side and dividing by $ r^{n-k} $ we get,

$$ r^k - c_1 r^{k-1} - c_2 r^{k-2} - \ldots - c_{k-1} r - c_k = 0 $$

This equation is known as the characteristic equation of the recurrence relation. The solutions of the characteristic equation are known as characteristic roots of the recurrence relations. Solving linear homogeneous recurrence relations with constant coefficients involves finding their characteristic roots.

Solving linear homogeneous recurrence relations of degree 2 with 2 characteristic roots

Consider a recurrence relation $ a_n = c_1 a_{n-1} + c_2 a_{n-2} $ where $ c_1 $ and $c_2 $ are constant real numbers. Suppose that the characteristic equation of this recurrence relation $ r^2 - c_1 r - c_2 = 0 $ has two distinct roots $ r_1 $ and $r_2$.

Then, it is the case that $ a_n = \alpha_1 r_1^n + \alpha_2 r_2^n $ for $ n = 1, 2, \ldots, $ where $ \alpha_1 $ and $ \alpha_2 $ are real constants.

Example

Consider the recurrence relation $ a_n = a_{n-1} + 6 a_{n-2} $, with the initial conditions $ a_0 = 1 $ and $ a_1 = 2 $. The characteristic equation of this relation is $ r^2 - r - 6 = 0 $. Its roots are $ r = 3 $ and $ r = -2 $.

Then, using the result above, it must be the case that $ a_n = \alpha_1 3^n + \alpha_2 (-2)^n $, for some constants $ \alpha_1 $ and $ \alpha_2 $.

Because $ a_0 = 1 $, it follows that $ \alpha_1 + \alpha_2 = 1 $. Also, because $ a_1 = 2 $, it is also the case that $ 3\alpha_1 - 2\alpha_2 = 2 $

Solving this system of linear equations, it is easy to find that $ \alpha_1 = \frac{4}{5} $ and $ \alpha_2 = \frac{1}{5} $.

Thus, the sequence is $ a_n = \frac{4}{5} \cdot 3^n + \frac{1}{5} \cdot (-2)^n $.

Solving linear homogeneous recurrence relations of degree 2 with 1 characteristic root

Consider a recurrence relation $ a_n = c_1 a_{n-1} + c_2 a_{n-2} $ where $ c_1 $ and $c_2 $ are constant real numbers, such that $ c_2 \ne 0$. Suppose that the characteristic equation of this recurrence relation $ r^2 - c_1 r - c_2 = 0 $ has only one root $ r_0 $.

Then, it is the case that $ a_n = \alpha_1 r_0^n + \alpha_2 n r_0^n $ for $ n = 1, 2, \ldots, $ where $ \alpha_1 $ and $ \alpha_2 $ are real constants.

Example

Consider the recurrence relation $ a_n = 2 a_{n-1} - 4 a_{n-2} $, with the initial conditions $ a_0 = 1 $ and $ a_1 = 3 $. The characteristic equation of this relation is $ r^2 - 2 r + 4 = 0 $. It has only one root $ r = 2 $.

Then, using the result above, it must be the case that $ a_n = \alpha_1 2^n + \alpha_2 n 2^n $, for some constants $ \alpha_1 $ and $ \alpha_2 $.

Because $ a_0 = 1 $, it follows that $ \alpha_1 + \alpha_2 \times 0 = 1 $. This implies that $ \alpha_1 = 1 $.

Also, because $ a_1 = 3 $, it is also the case that $ 2\alpha_1 + 2\alpha_2 = 3 $. Substituting the value of $ \alpha_1 $, we can find that $ \alpha_2 = \frac{1}{2} $.

Thus, the sequence is $ a_n = 2^n + \frac{1}{2} \cdot 2^n $.

Solving linear homogeneous recurrence relations of degree k with k distinct characteristic roots

Consider a recurrence relation $ a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{n-k} $ where $ c_1, c_2, \ldots, c_k $ are real constants. Suppose that the characteristic equation of this recurrence relation $ r^k - c_1 r^{k-1} - \ldots - c_{k-1} r - c_k = 0 $ has $ k $ distinct roots $ r_1, r_2, \ldots, r_k $.

Then, it is the case that $ a_n = \alpha_1 r_1^n + \alpha_2 r_2^n + \ldots + \alpha_k r_k^n $ for $ n = 1, 2, \ldots, $ where $ \alpha_1, \alpha_2, \ldots, \alpha_k $ are real constants.

Divide-and-conquer relations

Divide-and-conquer strategies work by splitting a large problem into smaller ones and then accumulating the results of the sub-tasks into the final solution of the original problem.

For example, a large problem of size $ n $ may be split into $ a $ sub-tasks, where each sub-problem is approximately of size $ n/b $. Suppose $ g(n) $ is the additional work needed to split the problem into its sub-problems. If $ f(n) $ represents the effort to solve a problem of size $ n $, then $ f $ satisfies the recurrence relation

$$ f(n) = a f(n/b) + g(n) $$

This is called a divide-and-conquer recurrence relation.

Example

Consider the problem of binary search over a list of $ n $ sorted elements.

Starting at the middle element the problem is split into the relevant path (the path that might contain the query) and the irrelevant path by comparing the search term to the current element. Additionally, one more comparison is needed to figure out if there are any more elements left to search against. So, $ g(n) = 2 $. Since the binary search algorithm only follows the relevant path, only one sub-task of the two need followed.

Thus, binary search satisfies the following divide-and-conquer recurrence relation, when $ n $ is even.

$$ f(n) = f(n/2) + 2 $$

Solving divide-and-conquer recurrence relations with constant split function

Let $ f $ be an increasing function that satisfies the following divide-and-conquer recurrence relation

$$ f(n) = a f(n/b) + c $$

where, $ a \ge 1 $ is the number of tasks the problem is split into, $ b $ is an integer greater than 1, and $ c $ is a positive real number indicating the constant number of operations needed to split the problem at each division.

Then,

$$ f(n) = \begin{cases} \BigO{n^{\log_b a}} \text{ if } a > 1 \\\\ \BigO{\log n} \text{ if } a = 1 \end{cases} $$

Example

We saw earlier that the number of operations in binary search satisfy the divide-and-conquer recurrence relation $ f(n) = f(n/2) + 2 $, if $ n $ is even. Since $ a = 1 $ in this case, we can use the result above to identify that $ f(n) = \BigO{\log n} $.

Solving divide-and-conquer recurrence relations with dynamic split function

There are scenarios when the splitting function is dependent on the size of the input $ n $.

Let $ f $ be such an increasing function that satisfies the following divide-and-conquer recurrence relation

$$ f(n) = a f(n/b) + cn^d $$

where, $ a \ge 1 $ is the number of tasks the problem is split into, $ b $ is an integer greater than 1, and $ c $ and $ d $ are positive real numbers.

Whenever $ n = b^k $, for some positive integer $ k $

Then,

$$ f(n) = \begin{cases} \BigO{n^d} \text{ if } a < b^d \\\\ \BigO{n^d \log n} \text{ if } a = b^d \\\\ \BigO{n^{\log_b a}} \text{ if } a > b^d \end{cases} $$

Counting elements in the union of finite sets

Let $ A_1, A_2, \ldots, A_n $ be finite sets. Then,

\begin{align} |A_1 \cup A_2 \cup \ldots \cup A_n| = & \left(\sum_{i=1}^n |A_i|\right) \\\\ & - \left(\sum_{1 \le i < j \le n} |A_i \cap A_j| \right) \\\\ & + \left(\sum_{1 \le i < j < k \le n} |A_i \cap A_j \cap A_k| \right)\\\\ & ~~~~~~~ \vdots \\\\ & + (-1)^{n+1}|A_1 \cap A_2 \cap \ldots \cap A_n| \end{align}

We show this result visually in the following Venn diagram. Note how the element $ 7 $ is first included 3 times, then excluded 3 times, and finally reintroduced due to $ |A \cap B \cap C| $.

Note how the inclusion-exclusion principle requires including and excluding cardinalities of set intersections alternately.

Counting elements that do not satisfy any property

Sometimes, given several properties $ P_1, P_2, \ldots, P_n $, we are required to identify the number of elements in a set that do not satisfy any of these properties. Suppose $ N $ is the total number of elements. Also, let $N(P_i) $ denote the number of elements satisfying a property $ P_i $. Elements that satisfy multiple properties, say $ k $, are written as $ N(P_{i_1} P_{i_2} \ldots P_{i_k}) $

Then, by the principle of inclusion-exclusion, it can be proven that the number of elements that do not satisfy any property, that is $ N(P_1' P_2' \ldots P_n') $ is

\begin{align} N(P_1' P_2' \ldots P_n') = & N \\\\ & - \left(\sum_{1 \le i \le n} N(P_i) \right) \\\\ & + \left(\sum_{1 \le i < j \le n} N(P_i P_j)\right) \\\\ & - \left(\sum_{1 \le i < j < k \le n} N(P_i P_j P_k) \right)\\\\ & ~~~~~~~ \vdots \\\\ & + (-1)^n N(P_1 P_2 \ldots P_n) \end{align}

Basically, in this case, we are computing the union of all properties and subtracting it from the universal set of all $ N $ elements. We demonstrate this visually with the Venn diagram below. We are interested in finding elements that are not divisible by 2, 3, and 4. Clearly, we need to exclude the set of elements in the union of the sets $ A $, $ B $, and $ C $. The remaining elements in $ U $ are the answer to our query.

Number of onto functions from a set to another

You remember onto functions from our article on functions.

If $ a $ and $ b $ are positive integers such that $ a \ge b $, then how many onto functions are there from a set with $ a $ elements (domain) to a set with $ b $ elements (codomain).

This can be derived from the method for counting number of elements that do not satisfy given properties.

Note that the total number of functions from a domain with $ a $ elements to a codomain with $ b $ elements is $ b^a $.

Now, for each of the $ b $ elements in the codomain, define a property $ P_i $ such that if a function satisfies $ P_i $, then the $ i $-th element is not in the range of the function.

Thus, $ N(P_i) $ is the number of functions that do not have the $ i $-th element in their range. For each $ P_i $ there will be $ (b-1)^a $ functions because the codomain is restricted to only $ b - 1 $ elements. Since each of the $ b $ elements of the codomain will have one such count, we are looking at $ C(b,1)(b-1)^a $ total functions that have some element missing from range.

Similarly, $ N(P_iP_j) $ is the number of functions that do not have the $ i $-th as well as the $ j $-th element in their range. Analogous to before, the total such functions will be $ C(b,2)(b-2)^a $.

Assigning this way, and using the formula for calculating the number of elements that do not satisfy properties $ P_1, P_2, \ldots, P_b $, we get the total number of onto functions.

$$ b^a - C(b,1)(b-1)^a + C(b,2)(b-2)^a - \ldots + (-1)^{b-1} C(b,b-1) 1^a $$

Example application

This general formulation is quite useful. For example, consider the task of assigning $ 6 $ balls to $ 3 $ containers such that each container receives at least one ball. How many ways can this be achieved in?

Essentially, we are counting the number of onto functions from the set of balls to the set of containers, since each container is associated with at least one ball.
In this case, the size of the domain is $ a = 6 $ and the size of the codomain is $ b = 3 $. Substituting, we get $ 540 $ different ways.

Check out the handy calculator in the next section to understand how fast these values grow as $ a $ and/or $ b $ grow.

Number of onto functions calculator

Calculate the total number of onto functions from a domain with $ a $ elements to a codomain with $ b $ elements. Note that it must be the case that $ a > b $.

Derangements

A derangement is a permutation of objects that does not leave any object in its original position. In the following figure we show potential derangements of an initial ordering of an oval, star, and a pentagon. The disqualifying element, the one that causes the permutation to not be a derangement, is marked with an "x".

You should get the hint that counting derangements starts with listing out all possible permutations and then removing those that have any elements in their original position. This is based on our previous section on counting elements that do not satisify given properties.

We know that for $ n $ objects, the total number of arrangements or permutations is $ n! $.

Let $ P_i $ denote the property that the $ i $-th element is in its original position. Since the $i$-th element is fixed, there are only $ n - 1 $ spots for the remaining elements. There would be $ (n-1)! $ such permutations which fix the $ i $-th element. And there would be $ C(n,1) $ such properties. So total number of such permutations with at least one element in its original spot are $ \sum_{1 \le n \le n} N(P_i) = C(n,1)(n-1)! $.

Analogously, the total number of permutations such that two elements $ i $ and $ j $ are in their original spot are $ \sum_{1 \le i < j \le n } N(P_i, P_j) = C(n,2)(n-2)! $. And so on.

Using the formula for counting the number of elements that do not satisfy given properties and substituting, we get the number of derangements $ D_n $ of $ n $ objects as

$$ D_n = n! - C(n,1)(n-1)! + C(n,2)(n-2)! - \ldots + (-1)^n C(n,n)(n-n)! $$

Re-arranginng the terms, we get the equation,

$$ D_n = n! \left[ 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \ldots + (-1)^n \frac{1}{n!} \right] $$

Example

Consider the set of first 3 positive integers $ \set{1, 2, 3} $ and a permutation $ 123 $. The permutation $ 312 $ is a derangement of the given permutation, but $ 321 $ is not since $ 2 $ is still in the original position. The number of such possible derangements are

\begin{align} D_3 =~ & 3! \left[1 - 1 + \frac{1}{2!} - \frac{1}{3!} \right] \\\\ =~ & 6 \left[ \frac{1}{2} - \frac{1}{6} \right] \\\\ =~ & 2 \end{align}

Derangements calculator

Calculate the number of derangements of $ n $ objects, such that $ 1 \le n \le 100 $.

Derangements as a recurrence relation

Derangements of $ n $ objects follow the recurrence relation, for $ n \ge 1 $

$$ D_n = n D_{n-1} + (-1)^n $$

The proof can be derived using the inclusion-exclusion formula for derangements that we derived in the previous section.

\begin{align} D_n &= n! \left[ 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \ldots + (-1)^n \frac{1}{n!} \right] \\\\ &= n (n-1)! \left[1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \ldots + (-1)^{n-1} \frac{1}{(n-1)!} + (-1)^n \frac{1}{n!} \right] \\\\ &= n (n-1)! \left[1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \ldots + (-1)^{n-1} \frac{1}{(n-1)!} \right] + n(n-1)! ((-1)^n \frac{1}{n!} \\\\ &= n D_{n-1} + ((-1)^n \end{align}

Next-article

With a sound understanding of counting and advanced counting concepts in this article, you are now well prepared to tackle complex ideas such as probability.

Please support us

Help us create more engaging and effective content and keep it free of paywalls and advertisements!

Please donate

Let's connect

Please share your comments, questions, encouragement, and feedback.