Counting and counting | Pete's World

One thing I am constantly on the lookout for, whenever I learn something new, or need to re-learn something forgotten, is the homework. Emphasis on the.

Good books, typically, offer many challenging exercises and quizzes, for the learner to practice the concepts. The better the book, the harder the exercises. It’s a reality, like it or not, that to move things forward we have to “overstress” the system: if one is very good at solving second order equations, she can only get better by solving very complicated second order equations; solving “normal” ones won’t help, and, in the long term, may even cause a decrease in her ability.

As an interesting aside, this somewhat surprising fact applies equally to the brain and to the muscles, and it’s known that top athletes follow finely-tuned programs even just to “maintain” their fitness. This makes me talk, on occasions, of “brain fitness”.

Leaving aside the aside, glancing at a great book makes it easy to see what I mean. Take your copy of TAOCP, dust it off, and see for yourself the copious amount of practice problems it contains. And, trust me, many of those are hard.

From an educational point of view there is an immense, and perhaps understated, value in knocking down as many practice homeworks as possible. But one thing that keeps happening to me is that, every now and again, I have to immerse myself in a domain that I thought I was fluent in, but of which I simply forgot many details. This happens specifically to me, most often, because I like to switch between projects that are only loosely related. In a minority of cases, it also happens in the form of “going back to the basics”, “don’t forget the basics”, “practice your foundations” kind-of-thing.

Whenever it happens, there should be no need for me to go again through the whole learning process for that subject — that is, assuming I did learn it well in the first place. It should suffice to collect my hard-learned pieces of memory from the back of my mind, metaphorically speaking, that is my long term memory.

To do that efficiently, I like to keep in mind what the perfect exercise is for that domain. For example, here’s another sport analogy: fifty meters bounding as a runner (but please, don’t injure yourself). Or, to stay on our track: determine if two binary trees have the same values and return the depth of the first level at which they differ, or -1 if they have indeed the same values all throughout. This is the perfect exercise to practice binary trees.

What are the qualities of that exercise that makes it, in my opinion, the perfect one? First of all, its statement is simple and quick to read. Secondly, it’s not galaxy hard: if I am coming back to something after a long enough time that I need to brush up, I probably don’t want a quiz that will take an entire week to solve. That’s actual work; this is supposed to be a refreshener. On the other hand, it’s hard enough that it will force me to recollect the key pieces of knowledge and apply them: binary search, recursive data structures, recursive functions. I know such things are really basic, and believe me when I say I’ve actually never needed to brush up on these, but, hey, this is my blog and I am trying to make a point here.

Another, and perhaps contingent, quality of that exercise is that it is simple enough that nobody wants to get it wrong. It’s a pride thing, really. So it’d force me to actually sit down and test the code and make sure it works on edge cases too. And lastly, it’s simple enough that I really do not want to ask a chatbot to do it for me.

Counting

As far as basics and foundational things go, counting is right there at the top of the list. Can you even call yourself an engineer if you can’t count?

And yet, counting is one of those things I keep coming back to, every now and then. Of course, I don’t mean enumerating things (c’mon!). Counting, here, means the ability to answer the question “How many?” without actually enumerating the objects.

Which means, you know, permutations, combinations, subsets, multisets, and the likes.

Still, I’d want to believe they belong to the basics, but for whatever reason they just won’t stick to my brain. So I’ve been looking for the perfect exercise for it. For as long as I have been able to read, textbooks always pick fancy stuff like playing card games (52-card decks, usually), some magic tricks, pigeons in pigeonholes, some good old Alice and Bob drama, total functions, bijections, and other stuff in various forms and shapes.

Here’s my take on it. Why don’t we just stick to a simple alphabet? I literally mean that, as a collection of symbols.

$$ S = \lbrace a_1, a_2, \dots, a_n \rbrace . $$

So the alphabet $S$ (ehm, a set) contains $n$ distinct symbols. Just like a real alphabet.

I hope I don’t need to convince you that every possible counting exercise that you’ll find in a book can be formulated as an equivalent exercise on counting strings (or subsets) of symbols with certain properties. But just in case, here are some of them:

How many ways of arranging ten books on a shelf are there? These are, of course, the permutations of the books, and they are as many as the non-repetitive strings made from an alphabet with ten symbols.
How many ways to choose six books among those ten are there? These are, of course, the 6-book combinations, and they are as many as the 6-symbol subsets made from an alphabet with ten symbols.
And so on.

And look, already at this point I feel like there’s been an improvement. I don’t need to recall playing card decks, or pigeonholes, or whatnot. I just need to remember symbols’ and alphabets’ tricks. It’s less of a burden on my mind.

Now, for the exercise. How many non-repetitive strings, of any length, can we make from an alphabet with n symbols? Non-repetitive means without repetitions of any symbol.

As far as simplicity of statements go, how about that one! Before looking for complicated combinations of cards and pigeons, can you just tell me how many valid strings can you make at all from an alphabet? Plain and simple.

OK, we are going to look at what the number is, but first I want to mention again what I am looking for here: the educational power of the exercise. Not all drills are the same: I am looking for the drill that maximises the learning in the least amount of time (because in this case it really is re-learning). To solve this counting quiz, we are going to have to remind ourselves of what permutations are, then what k-permutations are, then why are they different from combinations, what’s a binomial, and a few more things. That’s the solid foundation that everyone needs for counting. Of course, that doesn’t suddenly make me an expert in probability, but … one step at the time.

So let’s count them

Remember, we are looking for non-repetitive strings of any length. That includes strings of length $k=0$, of which we obviously have only one, the empty string $()$. As for length $k=1$, how many non-repetitive strings can we make? Clearly, we can make $n$ of them, because a 1-symbol string is the symbol itself, and there are only $n$ of them.

$$ \begin{aligned} k=0 &\to () \\ k=1 &\to a_1, a_2, \dots, a_n \end{aligned} $$

So far, so good. Now let’s think about length $k=2$, where we want to make all possible non-repetitive strings with two symbols. $ab$ is one such string, and because strings are not sets (that is, order does matter), $ba$ is also one such string, and we have to count them both. If we were instead looking for subsets of symbols, also called combinations, then $ab$ and $ba$ would be the same subset (combination) and we would have to exclude one of the two from the total count.

We can think of $k=2$ as it follows. We pick the first symbol in the string, and then we can put next to it any of the remaining $n-1$ symbols. That will give us $n-1$ strings. Then we change the first symbol, and put any of the remaining $n-1$ symbols next to it, and that will give us other $n-1$ strings. Clearly, we can keep doing this for all of the $n$ symbols that can be the first one, and every time we will have generated $n-1$ strings. Hence, for $k=2$, we can make $n(n-1)$ strings.

But wait a minute! $n(n-1)$ rings a bell. Oh sure, it looks like an incomplete $n$ factorial. It’s missing the terms $(n-2)$, $(n-3)$, etc., as if someone had divided it by $(n-2)!$.

So we could also say that at $k=2$ we can generate $n!/(n-2)!$ Strings. That also rings a bell. Oh yes, hold on a second, I got my math book here … ah, there it is, it’s the k-permutations of $n$ elements: $n!/(n-k)!$.

Nevermind the naming of things, right? Let’s think about $k=3$ now. We can apply the same reasoning recursively, where we first pick the first two symbols and then put next to them any of the remaining $n-2$ symbols. This way, every time we pick the first two we will generate $n-2$ strings. In how many different ways can we pick the first two symbols? Clearly, we can pick the first one in $n$ ways, and the second one in $n-1$ ways. So that gives us $n(n-1)(n-2)$, which (pretend you’re surprised) is just the same formula again, having increase $k$, that is, $n!/(n-3)!$.

OK, we’re nearly finished. For every length $k=0,\dots,n$ we know how many non-repetitive strings we are able to generate. Therefore the total is

$$ \sum_{k=0}^n \frac{n!}{(n-k)!} $$

It’s nice to notice that the formula works even for $k=0$ because $n!/n! = 1$ and we indeed have one string of length zero, the empty string $()$.

There’s still something about this formula that strikes my attention. That number, $n!/(n-k)!$ looks familiar. I still have my book open, let me check … It looks almost like the binomial ${n \choose k} = n!/(k!(n-k)!)$. My book says that the binomial gives the number of k-subsets (also called k-combinations), not that of k-permutations.

Ah that’s why I remembered it. Because $2^n$ is just about the only number computer science students remember, I knew that

$$ 2^n = \sum_{k=0}^n {n \choose k} = \sum_{k=0}^n \frac{n!}{k!(n-k)!} $$

and that’s the total number of subsets that we can make from a set with $n$ elements, or, equivalently, an alphabet with $n$ distinct symbols. But that’s nothing to do with what we are counting here, does it? I mean, there’s an extra $k!$ in every term of the summation.

The extra $k!$ is at the denominator, so it means our number is greater than $2^n$. What? I thought $2^n$ was the greatest number ever! But, in effect, we are counting strings, where order of symbols matter, so $ab$ and $ba$ are counted twice, whereas there’s only one subset $\lbrace a, b\rbrace$ in $2^S$. So, OK, that checks out.

But why is it exactly $k!$? That’s too odd to be a coincidence!

Of course, it’s not a coincidence. At length $k$, to make non-repetitive strings, we arrange $k$ elements among $n$, minding their order, so, in the “strings world”, $abc \ne bac$ (at $k=3$). But in the “sets world”, $\lbrace a, b, c \rbrace = \lbrace b, a, c \rbrace$, so they are two copies of the same set. How many copies are there? Clearly, for a k-symbol string such as $abc$ there are $k!$ copies of it in the sets world, because these “copies” are the re-arrangements of the same $k$ symbols. To conclude, at length $k$ we generate $n!/(n-k)!$ k-permutations, but each of these is one of $k!$ copies, if we look at them as sets. Therefore, the effective number of subsets, if we wanted to count them, would be $n!/(k!(n-k)!)$.

How do you like that, for a brush up?

A surprise

Believe it or not: the total number of non-repetitive strings of any length, $\sum_{k=0}^n n!/(n-k)!$, is exactly equal to

$$ \lfloor n! \cdot e \rfloor, $$

where $e$ is Euler’s number. I know you want to prove that all by yourself, so I won’t spoil the fun.

Cheatsheet

One could, admittedly, also just memorize a limited set of rules. I don’t like to brute force my memory, but here are some.

Given an alphabet with $N$ distinct symbols (or a set with $N$ elements):

The number of ways to arrange the $N$ symbols is $N!$ (permutations).
The number of non-repetitive strings of exactly $N$ symbols is also $N!$.
The number of ways to arrange $k$ symbols among $N$ is $N!/(N-k)!$ (k-permutations).
The number of non-repetitive strings of exactly $k$ symbols is the same as in the previous point.
The number of ways to select $k$ symbols among $N$ is ${N \choose k}$ (k-combinations or k-subsets).

A multiset is like a set where elements can be repeated, and therefore each element $a_i$ has a multiplicity $p_i$ that is the number of times it occurs in the multiset. Let $N$ be the total number of elements in the multiset, and $m$ be the number of distinct elements ($m \le N$).

The numbers of ways to arrange the elements of a multiset is $N!/(p_1! \hspace{5mu} p_2! \cdots p_m!)$ (also called permutations).

And a few important rules:

The number of ways to make a 2-symbol string picking the first symbol from alphabet $A$ and the second from alphabet $B$ is $|A| \times |B|$ (product rule).
The number of ways to pick a symbol from alphabet $A$ or alphabet $B$, when they do not have any symbol in common, is $|A| + |B|$ (sum rule).
If there exists a k-to-1 total function from alphabet $A$ to alphabet $B$, then $|A| = k |B|$ (division rule).
The product rule and the sum rule generalize to operations on any number of alphabets (not just two).

One more thing

Variety is good in exercise; it’s almost like a requirement of any good learning process. That’s why our math books contain exercises on pigeons, poker hands, Alice and Bob, and so on. That’s good and we should solve all of them when learning the concepts for the first time. The main points of this article are meant for the times when we have to re-learn something, under the assumption that we did do a fairly good job the first time.

Bonus

Some code for the quiz I mentioned, optimized for clarity.

from __future__ import annotations
from dataclasses import dataclass

@dataclass
class Tree:
    value: int
    left: Tree | None
    right: Tree | None

# Return -1 if trees a’s and b’s values are the same, in the same positions.
# Return the minimum depth at which trees a’s and b’s values are different.
# Root has depth zero.
def equal(a: Tree, b: Tree) -> int:
    return _equal(a, b, 0)

def _equal(a, b, l):
    if a is None and b is None:
        return -1
    if a is None or b is None or a.value != b.value:
        return l
    lside = _equal(a.left, b.left, l+1)
    rside = _equal(a.right, b.right, l+1)
    if lside == -1:
        return rside
    if rside == -1:
        return lside
    return min(lside, rside)