4
$\begingroup$

Something that has been bothering me for a while is the formula for the maximum amount of nodes of a tree with height d and branching factor of b.

$$(b^{d+1}-1)/(b-1)$$

This holds true for all positive integer values of b, including 0, with the exception of b=1.

If b = 1, we would be dividing by 0. Which, well, we all know is not a "legal mathematical move". However, if b = 1, the number of nodes would be equal to the height of the tree + 1.

I'm not sure exactly what my question is. I just feel like it's weird that a tree with branching factor 0 would have 0 nodes, a tree with branching factor 2 would have $$(b^{d+1}-1)/(b-1)$$ nodes , but calculating the number of nodes of a tree with branching factor 1 would be impossible using the same formula.

I don't know what I'm missing. Why isn't there a formula that calculates all nodes in a tree that includes branching factor 1 (or rather, why doesn't this formula include b = 1?)? Or does a tree need a branching factor that is anything else than 1 (but larger than -1?) to qualify as a tree? I'm a bit confused. Help is greatly appreciated.

(Not sure if I got all the facts right here. Please forgive me if I didn't)

$\endgroup$
3
$\begingroup$

The formula you state follows from summing a geometric series: $$ 1 + b + b^2 + \cdots + b^d = \frac{b^{d+1}-1}{b-1}. $$ When $b=1$, the series sums to $d+1$, which is also the limit of the expression above as $b\to1$.

As you mention, the formula is only meaningful when $b \neq 1$, though the correct value can still be recovered by taking a limit. This is perhaps the simplest example of a curious phenomenon in combinatorics, that of the "field with one element". Consider the following two quantities:

  1. The number of subsets of size $k$ of a set of size $n$. These are counted by binomial coefficients $\binom{n}{k}$.
  2. The number of $k$-dimensional subspaces of an $n$-dimensional vector space over the finite field with $q$ elements. These are counted by Gaussian binomial coefficients $\binom{n}{k}_q$, which are rational functions (ratios of two polynomials) in $q$.

The curious thing is that if we substitute $q=1$ in the expression for $\binom{n}{k}_q$, we get back $\binom{n}{k}$ in the limit. (Just as in your case, when $q=1$ the denominator vanishes.) So a set is similar to a vector space over "the field with one element".

More generally, there are other formulas involving "$q$-analogs" (sets replaced with vector spaces over the field with $q$ elements) which degenerate to the correct values when taking the limit $q\to1$. There are some explanations for this phenomenon but it is still somewhat mysterious.

$\endgroup$
  • $\begingroup$ It amazes me that you wrote this within 13 minutes of me asking the question. I'm not a math person, so this will take me a few days to digest. Anyway, thanks for the response. I'm always looking to improve. $\endgroup$ – Lobs001 Sep 18 '17 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.