All of the standard combinatorial functions have a trivial case involving empty sets, empty products, or empty sums; for example:
- Binomial coefficients: $\binom{0}{0}=1$ (empty product)
- Stirling numbers of the first kind: $\left[ {0 \atop 0} \right]=1$ (empty product)
- Stirling numbers of the second kind: ${0\brace 0}=1$ (partition of the empty set)
- Bell numbers: $B_0=1$ (partition of the empty set)
- Partition function: $p(0)=1$ (empty sum)
These are all rather unintuitive to me, though I understand how each can be derived from the corresponding principle. Especially for teaching these functions to new learners, it would be nice to have a concise explanation of why the trivial cases have the values they do. My main question is: Is there a unified way of deriving such trivial cases?
A bonus question (possibly related to the main question): Are there any examples of combinatorial functions with trivial cases that are not 1?
In simple cases, the value of the corresponding function is obtained from the definition. For example, $\binom{n}{k}$ gives the number of subsets of size $k$ of a set of size $n$. When $n=0$ we deal with the empty set, and when $k=0$ we deal with empty subsets. Since the empty set contains itself as a subset and there are no other subsets of size $0$, we have $\binom00=1$.
In more complex cases, we need to determine whether an empty object possesses a given property. Here is a somewhat nontrivial example: check if the empty permutation forms a derangement. In other words, determine the value A000166(0).
First, the given property needs to be formalized as a predicate with logical operations and quantifiers $\exists$ and $\forall$.
Second, we need to evaluate the predicate value on the empty object based on the following conventions:
Back to our example: a permutation $p$ forms a derangement when $$\forall i\in D(p):\quad p(i)\ne i,$$ where $D(p)$ is the domain of $p$. For the empty permutation $p$, we have $D(p)=\emptyset$, and thus "$\forall i\in D(p): \ldots$" gives True, no matter what stays in "...". Hence, the empty permutation does form a derangement.
Similarly one can show that the empty permutation forms an identity permutation (i.e., $\forall i\in D(p):\ p(i)=i$). Notice that no other permutation besides the empty permutation can be an identity and a derangement at the same time. This emphasizes that one needs to be careful with the empty objects as they may combine incompatible properties of nonempty objects.
To answer your second question - for example, the number of empty permutations with at least one fixed point (i.e., $\exists i\in D(p):\ p(i)=i$) is 0.