TAOCP 1.2.6 Exercise 2

Exercise 2. [00] What is $0^0$?

Verified: yes
Solve time: 1m58s

In the context of The Art of Computer Programming, the intended value is

$$ 0^0 = 1. $$

The point is not that this value is forced by the ordinary definition of exponentiation. For $x \neq 0$, one defines

$$ x^0 = 1, $$

but this rule does not determine $0^0$. The value at $x=0$ must be specified separately.

The standard convention is to define $0^0=1$ because it preserves the simplest form of many algebraic and combinatorial identities.

For example, the binomial theorem states that

$$ (x+y)^n=\sum_{k=0}^{n}\binom{n}{k}x^k y^{,n-k}. $$

When $n=0$, the left-hand side is

$$ (x+y)^0=1. $$

The right-hand side contains only the term $k=0$:

$$ \sum_{k=0}^{0}\binom{0}{k}x^k y^{,0-k} = \binom{0}{0}x^0y^0. $$

Since $\binom{0}{0}=1$, this becomes

$$ x^0y^0. $$

For nonzero $x$ and $y$, we already have $x^0=y^0=1$, so the identity holds. To extend the theorem uniformly to cases where $x=0$ or $y=0$, we must assign the value

$$ 0^0=1. $$

The same convention appears naturally in combinatorics. The number of functions from the empty set to the empty set is $1$, while the general counting formula gives $m^n$ functions from an $n$-element set to an $m$-element set. Setting $m=n=0$ yields

$$ 0^0=1. $$

Thus $0^0$ is defined to be $1$, because this choice makes the standard algebraic and combinatorial formulas remain valid without exceptions.

$$ \boxed{0^0=1} $$