# Notation

## Rising and falling factorials

Write the rising factorial as

$x^\overline{n} = x(x+1)...(x+n-1)$

and the falling factorial as

$x^{\frac{n}{}} = x(x-1)...(x-n+1) .$

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

$D x^n = n x^{n-1}$

with

$\Delta x^\frac{n}{} = n x^\frac{n-1}{}$

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,

$[x = 0]$

is 1 when $$x = 0$$, and 0 otherwise (the impulse function). The Kronecker delta $$\delta_{i j}$$ is simply

$[i = j].$

A typical use is to pick out particular terms:

$\sum_k \frac{1}{k} [k \textrm{ is prime}]$

making expressions easier to manipulate. Other examples:

• $$\mathrm{sign}(x) = [x \gt 0] - [x \lt 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,

$\left[ {n \atop k} \right]$

will one day be the standard notation for the number of permutations of $$n$$ objects with $$k$$ disjoint cycles, and

$\left\{ {n \atop k} \right\}$

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 \lt 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

$p \perp q$

when $$\mathrm{gcd}(p,q) = 1$$.

## Coefficient extraction

When dealing with generating functions, it may help to define an expression such as

$[z + 2z^3]F(z)$

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:

$(x \vee y) \wedge z = (x \vee z) \wedge (y \vee z)$

## 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.

Ben Lynn blynn@cs.stanford.edu 💡