Selected functions

Factorial The factorial function, written \(n!\) for \(n\) an integer greater than 0, is the product of the integers between 1 and \(n\), inclusive. Thus, \(5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120\). As a special case, \(0! = 1\).

\[\begin{split}\begin{aligned} && 0! = 1 \\ && n! = n \cdot (n-1)!\end{aligned}\end{split}\]

Note

Factorial is usually denoted with the symbol \(!\), which is not to be confused with the C++ logical operator ! which means NOT.

Notice that when used to negate a boolean, the ! appears before the operand, while factorial appears after the operand.

The factorial function grows quickly as \(n\) becomes larger. Because computing the factorial function directly is a time-consuming process, it can be useful to have an equation that provides a good approximation. Stirling’s approximation states that \(n! \approx \sqrt{2\pi n}(\frac{n}{e})^n\), where \(e \approx 2.71828\) (\(e\) is the base for the system of natural logarithms) [1]. Thus we see that while \(n!\) grows slower than \(n^n\) (because \(\sqrt{2\pi n}/e^n < 1\)), it grows faster than \(c^n\) for any positive integer constant \(c\).

Logic notation We will occasionally make use of the notation of symbolic or boolean logic. \(A \Rightarrow B\) means “\(A\) implies \(B\)” or “If \(A\) then \(B\)”. \(A \Leftrightarrow B\) means “\(A\) if and only if \(B\)” or “\(A\) is equivalent to \(B\)”. \(A \vee B\) means “\(A\) or \(B\)” (useful both in the context of symbolic logic or when performing a boolean operation). \(A \wedge B\) means “\(A\) and \(B\)”. \(\sim\!A\) and \(\overline{A}\) both mean “not \(A\)” or the negation of \(A\) where \(A\) is a boolean variable.

Floor and ceiling The floor of \(x\) (written \(\lfloor x \rfloor\)) takes real value \(x\) and returns the greatest integer \(\leq x\). For example, \(\lfloor 3.4 \rfloor = 3\), as does \(\lfloor 3.0 \rfloor\), while \(\lfloor -3.4 \rfloor = -4\) and \(\lfloor -3.0 \rfloor = -3\). The ceiling of \(x\) (written \(\lceil x \rceil\)) takes real value \(x\) and returns the least integer \(\geq x\). For example, \(\lceil 3.4 \rceil = 4\), as does \(\lceil 4.0 \rceil\), while \(\lceil -3.4 \rceil = \lceil -3.0 \rceil = -3\).

More to Explore

You have attempted of activities on this page