0
$\begingroup$

All of the standard combinatorial functions have a trivial case involving empty sets, empty products, or empty sums; for example:

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?

$\endgroup$
8
  • 3
    $\begingroup$ Another: $0^0=1$ and also I would say ${n\choose 0}=1$ and $n^0=1$. Most of these can be thought of as the number of way of distributing nothing according to some rule, and there is precisely one way of doing that - do nothing. You might get cases where the answer is $0$ if the rule implicitly requires at least one positive event and so doing nothing does not satisfy the rule: e.g. number of ways of flipping a coin $k$ times so there are more heads than tails - this gives $0$ when $k=0$. $\endgroup$
    – Henry
    Commented Jul 21, 2021 at 8:18
  • $\begingroup$ "Are there any examples of combinatorial functions with trivial cases that are not 1?" Some will equal $n$ such as $\binom{n}{1}=\binom{n}{n-1}=n^1=n$. Some will equal $1$ such as ${n \brace 1}=1$. Some equal zero such as ${n\brace 0}=!1=0$ $\endgroup$
    – JMoravitz
    Commented Jul 21, 2021 at 12:38
  • $\begingroup$ Related: math.stackexchange.com/questions/1951490/… $\endgroup$ Commented Jul 21, 2021 at 15:40
  • $\begingroup$ Here’s an example where the trivial case is $2$. The Lucas numbers, $L_n$, enumerate the number of ways to tile a circular strip divided into $n$ sections numbered clockwise $1$ to $n$ with squares and dominoes (covering 1 and 2 sections respectively). These satisfy $L_n=L_{n-1}+L_{n-2}$ It turns out this implies $L_0=2$. (cont.) $\endgroup$ Commented Jul 21, 2021 at 15:46
  • $\begingroup$ The interpretation is that tilings of the $n$-annulus are either “in-phase” or “out-of-phase”, according to whether the border between spaces numbered $1$ and $n$ is covered by a domino. While this characterization does not literally apply to the empty tiling, it is natural to say there are two phases of empty tiling in order to make the recurrence work out when $n=2$. $\endgroup$ Commented Jul 21, 2021 at 15:49

1 Answer 1

2
$\begingroup$

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:

  • the existential quantifier ($\exists$) in the empty set gives False;
  • the universal quantifier ($\forall$) in the empty set gives True.

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .