Tree with branching factor 1

Question

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)

Answer 1

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.

• Lobs001: 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.