Notation
Rising and falling factorials
Write the rising factorial as
and the falling factorial as
The position of the horizontal line immediately identifies the type of factorial. The superscript reminds us these operations are akin to exponentiation. Alternatives often employ parenthesess. Avoiding them here reduces clutter and confusion.
Additionally, similarities between finite calculus and infinite calculus are emphasized. Compare
with
where \(\Delta\) is the difference operator, that is, \(\Delta f(x) = f(x+1)-f(x)\). We also have:
-
\((x + y)^n = \sum \binom{n}{k} x^k y^{n-k}\)
-
\((x + y)^\overline{n} = \sum \binom{n}{k} x^\overline{k} y^\overline{n-k}\)
-
\((x + y)^\frac{n}{} = \sum \binom{n}{k} x^\frac{k}{} y^\frac{n-k}{}\)
Iverson brackets
The first subject of Knuths’s "Two Notes on Notation" is this simple yet powerful idea.
We place a logical statement inside square brackets, and the whole expression evaluates to 1 when the statement is true, and 0 otherwise. This is similar to the logical and comparison operators of the C language.
For example,
is 1 when \(x = 0\), and 0 otherwise (the impulse function). The Kronecker delta \(\delta_{i j}\) is simply
A typical use is to pick out particular terms:
making expressions easier to manipulate. Other examples:
-
\(\mathrm{sign}(x) = [x > 0] - [x < 0]\)
-
\([A \wedge B] + [A \vee B] = [A] + [B]\) for any logical statements \(A, B\).
Stirling numbers
This is also the second subject of Knuth’s "Two Notes on Notation".
Writing \(\binom{n}{k}\) for the number of ways of picking \(k\) objects from a set of size \(n\) has triumphed over other schemes, such as an awkward concoction involving a "C", a subscript and a superscript. Hopefully,
will one day be the standard notation for the number of permutations of \(n\) objects with \(k\) disjoint cycles, and
will be recoginzed as the number of ways to partition \(n\) into \(k\) subsets.
Incidentally, these are known as the Stirling numbers of the first and second kind.
Our notation yields memorable formulas:
-
\(x^\overline{n} = \sum_k \left[ {n \atop k} \right] x^k\)
-
\(x^n = \sum_k \left\{ {n \atop k} \right\} x^\frac{k}{}\)
-
\(\binom{n+1}{k} = \binom{n}{k}+ \binom{n}{k-1}\)
-
\(\left[ {n+1}\atop{k} \right] = n\left[ {n}\atop{k} \right] + \left[ {n}\atop{k-1} \right] \)
-
\(\left\{ {n+1}\atop{k} \right\} = k\left\{ {n}\atop{k} \right\} + \left\{ {n}\atop{k-1} \right\} \)
-
\( \left[ {m \atop n} \right] = \left\{ {-n \atop -m} \right\} \) where we extend the functions to negative numbers via the recurrence relations. (So all these numbers are really Stirling numbers of the only kind.)
Intervals
An interval such as \({x : a \le x < b\}\) would often be denoted \([a,b)\), but what if both ends are open? Does \((5,7)\) mean a pair of coordinates? Or the greatest common divisor? Or an interval?
We circumvent ambiguity by replacing the comma with two dots: \((5..7)\).
Coprimes
Number theorists talk about coprime integers so much that we ought to adopt succint notation for two integers that are coprime. We borrow a symbol from geometry and write
when \(\mathrm{gcd}(p,q) = 1\).
Coefficient extraction
When dealing with generating functions, it may help to define an expression such as
to mean the coefficient of \(z\) in \(F\) plus 2 times the coefficient of \(z^3\) in \(F\).
In praise of infix
If we write \(\max(\min(x,y),z)\) with infix notation, it is much easier to apply distributivity:
Inverses
Why not write \(x^{-}\) for the multiplicative inverse of \(x\)? In fields such as group theory, the 1s in terms such as \(x^{-1}\) waste time and space.