a broad context for Möbius functions

This post is about the Möbius function, which is not something I have had to think about very often. It has come up in some combinatorial problems I’ve been working on recently, and so I’ve been reading about it bit by bit. One particular presentation I have found especially helpful, and that’s what I’m going to share here.

The “classical” Möbius function \(\mu\) is defined on the positive integers by \[ \mu(n) = \begin{cases} 1 & \text{if}\ n = 1 \\ (-1)^r & \text{if}\ n=p_1\cdots p_r,\ \text{a product of \(r\) distinct primes} \\ 0 & \text{otherwise.} \end{cases} \] I have never particularly understood this function. Its definition is simple, but to me opaque. Why would this function be of interest? (I’m not interested in answers such as “because it works.”) Maybe it’s just because I’m not a number theorist at heart.

For independent reasons, I recently read the monograph Commutation and Rearrangements by Pierre Cartier and Dominique Foata, and therein they demonstrate the existence of a Möbius function for any monoid \(M\) with finite factorization: that is, given any \(x\in M\), there are only finitely many sequences \((x_1,\dots,x_n)\) of non-identity elements \(x_i\) such that \(x=x_1\cdots x_n\). If \(1_M\) is the identity element of \(M\), then it is assumed to be the product of the empty sequence.

As two examples, think of the positive integers with multiplication as the operation, or strings over a given alphabet with concatenation as the operation. In a sense, these are two “extreme” examples, because the positive integers form a commutative monoid with an infinite set of generators (the primes), while the only elements that commute in the monoid of strings are powers of a single generator (the elements of the alphabet being the generators).

One consequence of the assumption that every element of \(M\) has finitely many factorizations is that \(1_M\) has only the empty factorization, because otherwise if \(1_M=x_1\cdots x_n\) for some nonempty sequence \((x_1,\dots,x_n)\), then this could be used to produce infinitely many factorizations of every element of \(M\).

Here is the definition that Cartier and Foata give for the Möbius function \(\mu_M\) of M: given \(x\in M\),

• \(d_+(x)\) is the number of ways \(x\) can be written as a product of an even number of factors;
• \(d_-(x)\) is the number of ways \(x\) can be written as a product of an odd number of factors;
• \(\mu_M(x) = d_+(x)-d_-(x)\).

This is a definition I can get behind! Now the Möbius function is revealed as the difference between two natural counting functions. Note that for any \(M\), because the identity \(1_M\) has only the empty factorization, with zero factors, \(d_+(1_M)=1\) and \(d_-(1_M)=0\), which means \(\mu_M(1_M)=1\) always.

Let’s see how the rest of the values of \(\mu_M\) work out for the two examples we have in mind.

First suppose that \(M\) is the monoid of strings over an alphabet \(A\). (This will turn out to be the easier of the two cases.) If \(x\in A\) is a string with only one letter, then it can only be written as \(x\), so \(\mu_M(x) = -1\). If \(x\in M\) has \(n>1\) letters, then it can be factored in \(2^{n-1}\) ways, by introducing “breaks” between adjacent letters. Half of these factorizations have an even number of factors, and half have an odd number of factors, so \(d_+(x)=d_-(x)=2^{n-2}\), which means \(\mu_M(x) = 0\). For example, we can factor the string \(acbb\) in eight ways:

\((acbb)\)	\((a)(c)(bb)\)	\((a)(cb)(b)\)	\((ac)(b)(b)\)
\((a)(cbb)\)	\((ac)(bb)\)	\((acb)(b)\)	\((a)(c)(b)(b)\)

The top row shows the factorizations with an odd number of factors, and the bottom row shows the factorizations with an even number of factors.

Now suppose \(M = \mathbb{Z}_+\) is the monoid of positive integers. If \(p\) is a prime, then it can only be written as the product \(p\), so \(d_+(p)=0\) and \(d_-(p)=1\), which means \(\mu_M(p) = -1\). If \(p\) and \(q\) are distinct primes, then we have \(pq = (pq) = (p)(q) = (q)(p)\), so \(d_+(pq) = 2\) and \(d_-(pq) = 1\), which means \(\mu_M(pq) = 2-1 = 1\). On the other hand, \(p^2 = (p^2) = (p)(p)\), so \(d_+(p^2)=d_-(p^2)=1\), which means \(\mu_M(p^2)=0\). More generally, if \(x=p_1\cdots p_n\) with \(p_1,\dots,p_n\) all distinct primes, then any factorization of \(x\) is given by choosing \(k_1\) prime factors, then \(k_2\) prime factors, and so on, until \(x\) is expressed as a product of \(m\) factors as \[x=(p_1\cdots p_{k_1})(p_{k_1+1}\cdots p_{k_1+k_2})\cdots(p_{k_1+\cdots+k_{m-1}+1}\cdots p_{k_1+\cdots+k_m})\] where \(k_1+\cdots+k_m=n\). Within each parenthetical factor, the order of the primes doesn’t matter, but the order of the parenthetical factors does matter. This is an ordered partition of the prime factors of \(x\).

It is possible to compute \(d_+(x)\) and \(d_-(x)\) directly, based on the ordered partitions of the prime factors of \(x\). (See OEIS A000670 for the total number of ordered partitions of \(n\) elements, A089677 for the number of ordered partitions with an odd number of blocks, and A052841 for the number of ordered partitions with an even number of blocks.) However, here we will instead use induction to show the simpler result we need, that if \(p_1,\dots,p_n\) are \(n\) distinct primes, then \[ d_+(p_1\dots p_n) - d_-(p_1\dots p_n) = (-1)^n \] which recovers the classical Möbius function on numbers of this form. We have already shown the cases \(n=1\) and \(n=2\) in the previous paragraph, so suppose the result is true for some arbitrary value of \(n\), and let \(q\) be a prime distinct from \(p_1,\dots,p_n\). Set \(x=p_1\cdots p_n\). A factorization of \(xq\) can be obtained from a factorization of \(x\) in three ways:

1. by inserting \(q\) into one of the existing factors;
2. by introducing \(q\) as a new factor immediately before one of the existing factors;
3. by introducing \(q\) as a new factor at the end.

The first operation preserves the parity of the number of factors, while the second operation switches the parity of the number of factors. Because there are the same number of these two types of operations, in computing the difference \(d_+(xq)-d_-(xq)\), they cancel out. The third operation also switches the parity of the number of factors, and it is only applied once to each of the factorizations of \(x\). Thus \[ d_+(xq)-d_-(xq) = d_-(x)-d_+(x) = -(-1)^n = (-1)^{n+1} \] and the result follows.

On the other hand, if \(x\in\mathbb{Z}_+\) is divisible by a prime power \(p^k\) with \(k>1\), then we can first examine the ways to split up this power. By treating \(p^k\) as a string over the alphabet \(\{p\}\), we see that there are the same number of factorizations having an even number of factors as an odd number of factors, and so \(d_+(p^k)-d_-(p^k)=0\). Introducing the rest of the prime factors of \(x\) one at a time, the same argument as in the previous paragraph shows that \(d_+(x)-d_-(x)=d_+(p^k)-d_-(p^k)=0\). (The case where more than one prime factor of \(x\) appears with multiplicity higher than \(1\) is left as an exercise to the reader.)

The purpose of the Möbius function of \(M\) is mainly to enable Möbius inversion, a way of transforming between related complex-valued functions on \(M\). I won’t go into that process now, because this post has taken long enough already, but I encourage anyone interested to read Cartier and Foata’s monograph (which has a load of other great ideas!).

I will observe that in the original paper where Möbius introduced his eponymous function ( “Über eine besondere Art von Umkehrung der Reihen”, 1832), he derived the expression \[ x = \frac{x}{1-x} - \frac{x^2}{1-x^2} - \frac{x^3}{1-x^3} - \frac{x^5}{1-x^5} + \frac{x^6}{1-x^6} - \frac{x^7}{1-x^7} + \frac{x^{10}}{1-x^{10}} \cdots \] which can be written more succinctly as \[ x = \sum_{n=1}^\infty \frac{\mu(n)x^n}{1-x^n} \] (the expression on the right is a Lambert series). In this context the definition of \(\mu(n)\) also makes sense to me, as a collection of coefficients, as it can be derived by an application of the inclusion–exclusion principle. Recall that the summation formula for the geometric series yields \[ \frac{x^n}{1-x^n} = \sum_{k=1}^\infty x^{nk}\text. \] So if you start with the series \(x+x^2+x^3+\cdots = x/(1-x)\) and you want to reduce it to \(x\), you can remove all the powers that are multiples of \(2\), then remove all powers that are multiples of \(3\), then add back in all powers that are multiples of \(6\) because they got removed twice, then remove all powers that are multiples of \(5\), then add back powers that are multiples of \(10\) or \(15\), then remove powers that are multiples of \(30\) because they got removed three times and added back in three times, and so on…

more on poetry and partitions (sort of)

In my previous post I defined the ordered Virahanka numbers $V_{m,n}$ and the unordered Virahanka numbers $U_{m,n}$ recursively by \[ \begin{array}{rl} V_{m,n} = U_{m,n} = 0 &\qquad \text{for $n < 0$ or $m < 0$} \\ V_{m,0} = U_{m,0} = 1 &\qquad \text{for $m \ge 0$} \\ V_{m,n} = \displaystyle\sum_{k=1}^m V_{m,n-k} &\qquad \text{for $n > 0$} \\ U_{m,n} = \displaystyle\sum_{k=1}^m U_{k,n-k} &\qquad \text{for $n > 0$} \\ \end{array} \] The value of $V_{m,n}$ counts the number of compositions of $n$ with no term greater than $m$, and the value of $U_{m,n}$ counts the number of partitions of $n$ with no part greater than $m$. (Following a standard convention, I consider the “empty sum” having no terms to be equal to $0$, which is why $V_{m,0} = U_{m,0} = 1$; moreover, $V_{0,n} = U_{0,n} = 0$ for $n > 0$, because the recursive formulas above become empty sums.) Some special cases:

• $V_{2,n}$ is the sequence of Virahanka–Fibonacci numbers $1,1,2,3,5,8,\dots$.
• $V_{n,n}$ is the total number of compositions of $n$ (which equals $2^{n-1}$ for $n \ge 1$).
• $U_{n,n}$ is the total number of partitions of $n$ (which has no known closed-form expression).

For later reference, here are partial tables of values for $V_{m,n}$ and $U_{m,n}$. \[ V_{m,n}: \begin{array}{c|c|c|c|c|c|c|c|c|c} m\backslash n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline 2 & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 & 89 \\ \hline 3 & 1 & 1 & 2 & 4 & 7 & 13 & 24 & 44 & 81 & 149 & 274 \\ \hline 4 & 1 & 1 & 2 & 4 & 8 & 15 & 29 & 56 & 108 & 208 & 401 \\ \hline 5 & 1 & 1 & 2 & 4 & 8 & 16 & 31 & 61 & 120 & 236 & 464 \\ \hline 6 & 1 & 1 & 2 & 4 & 8 & 16 & 32 & 63 & 125 & 248 & 492 \\ \hline 7 & 1 & 1 & 2 & 4 & 8 & 16 & 32 & 64 & 127 & 253 & 504 \\ \hline 8 & 1 & 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 255 & 509 \\ \hline 9 & 1 & 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256 & 511 \\ \hline 10 & 1 & 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256 & 512 \end{array} \] \[ U_{m,n}: \begin{array}{c|c|c|c|c|c|c|c|c|c} m\backslash n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline 2 & 1 & 1 & 2 & 2 & 3 & 3 & 4 & 4 & 5 & 5 & 6 \\ \hline 3 & 1 & 1 & 2 & 3 & 4 & 5 & 7 & 8 & 10 & 12 & 14 \\ \hline 4 & 1 & 1 & 2 & 3 & 5 & 6 & 9 & 11 & 15 & 18 & 23 \\ \hline 5 & 1 & 1 & 2 & 3 & 5 & 7 & 10 & 13 & 18 & 23 & 30 \\ \hline 6 & 1 & 1 & 2 & 3 & 5 & 7 & 11 & 14 & 20 & 26 & 35 \\ \hline 7 & 1 & 1 & 2 & 3 & 5 & 7 & 11 & 15 & 21 & 28 & 38 \\ \hline 8 & 1 & 1 & 2 & 3 & 5 & 7 & 11 & 15 & 22 & 29 & 40 \\ \hline 9 & 1 & 1 & 2 & 3 & 5 & 7 & 11 & 15 & 22 & 30 & 41 \\ \hline 10 & 1 & 1 & 2 & 3 & 5 & 7 & 11 & 15 & 22 & 30 & 42 \end{array} \]

There are so many fun ways to play with these collections of numbers, it’s hard to know when to stop! To limit the scope of this post, I will only consider two related notions, and those only in part: first differences, and generating functions.

First differences

Given a collection of numbers $S_{m,n}$ indexed by integers $m$ and $n$, and a pair $(p,q) \in \mathbb{Z}^2$, let \[ S_{m,n}^{(p,q)} = S_{m,n} - S_{m-p,n-q}\text. \]

From the definitions, we have for $n > 1$ \[ \begin{array}{rl} V_{m,n}^{(0,1)} &= V_{m,n} - V_{m,n-1} \\ &= \sum_{k=1}^m V_{m,n-k} - \sum_{k=1}^m V_{m,(n-1)-k} \\ &= \sum_{k=1}^m \big(V_{m,n-k} - V_{m,(n-k)-1}\big) \\ &= \sum_{k=1}^m V_{m,n-k}^{(0,1)} \end{array} \] and so the first differences $V_{m,n}^{(0,1)}$ satisfy the same recurrence relation as the original numbers $V_{m,n}$ when $n\ge 2$. Here is the table of values for $V_{m,n}^{(0,1)}$. \[ V_{m,n}^{(0,1)}: \begin{array}{c|c|c|c|c|c|c|c|c|c} m\backslash n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline 0 & 1 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 2 & 1 & 0 & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 \\ \hline 3 & 1 & 0 & 1 & 2 & 3 & 6 & 11 & 20 & 37 & 68 & 125 \\ \hline 4 & 1 & 0 & 1 & 2 & 4 & 7 & 14 & 27 & 52 & 100 & 193 \\ \hline 5 & 1 & 0 & 1 & 2 & 4 & 8 & 15 & 30 & 59 & 116 & 228 \\ \hline 6 & 1 & 0 & 1 & 2 & 4 & 8 & 16 & 31 & 62 & 123 & 244 \\ \hline 7 & 1 & 0 & 1 & 2 & 4 & 8 & 16 & 32 & 63 & 126 & 251 \\ \hline 8 & 1 & 0 & 1 & 2 & 4 & 8 & 16 & 32 & 64 & 127 & 254 \\ \hline 9 & 1 & 0 & 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 255 \\ \hline 10 & 1 & 0 & 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256 \end{array} \] We see that the “initial conditions” of the recurrence $V_{m,n}^{(0,1)} = \sum_{k=1}^m V_{m,n-k}^{(0,1)}$ have shifted, so that before beginning to apply the recurrence relation, we insert one term equal to $0$. But what are these numbers counting? Well, $V_{m,n}$ is the number of compositions of $n$ with no term greater than $m$, and $V_{m,n-1}$ is the number of compositions of $n-1$ with no term greater than $m$. Any composition of $n-1$ can be converted to a composition of $n$ by adding a $1$ at the end. So $V_{m,n}^{(0,1)}$ equals the number of compositions of $n$ that do not end with $1$. Perhaps not the most interesting quantity to count, although having the recurrence formula is nice. (The same principle will lead to other interesting quantities, so don’t go away yet!)

On the other hand, $V_{m,n}^{(1,0)} = V_{m,n} - V_{m-1,n}$ does have an interesting interpretation. Because $V_{m-1,n}$ counts all compositions of $n$ whose largest term is at most $m-1$, $V_{m,n}^{(1,0)}$ equals the number of compositions of $n$ whose largest term is exactly $m$. Here’s a partial table of values. \[ V_{m,n}^{(1,0)}: \begin{array}{c|c|c|c|c|c|c|c|c|c} m\backslash n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline 2 & 0 & 0 & 1 & 2 & 4 & 7 & 12 & 20 & 33 & 54 & 88 \\ \hline 3 & 0 & 0 & 0 & 1 & 2 & 5 & 11 & 23 & 47 & 94 & 185 \\ \hline 4 & 0 & 0 & 0 & 0 & 1 & 2 & 5 & 12 & 27 & 59 & 127 \\ \hline 5 & 0 & 0 & 0 & 0 & 0 & 1 & 2 & 5 & 12 & 28 & 63 \\ \hline 6 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 2 & 5 & 12 & 28 \\ \hline 7 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 2 & 5 & 12 \\ \hline 8 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 2 & 5 \\ \hline 9 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 2 \\ \hline 10 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{array} \] One interesting feature of this table is that the entries stabilize below the line $n = 2m$: when $n < 2m$, we see that $V_{m+1,n+1}^{(1,0)} = V_{m,n}^{(1,0)}$. The sequence $V_{m,2m-1}^{(0,1)}$ begins (starting with $m = 1$) \[ 1,\;2,\;5,\;12,\;28,\;64,\;144,\;320,\;704,\;\dots \] The OEIS says that this sequence comes from counting all the $1$s that appear in all compositions of $m$. Why should that sequence arise here? I guess that’s a mystery that will have to wait for later…

Turning to first differences of the unordered Virahanka numbers, let’s start with $U_{m,n}^{(1,0)}$. \[ U_{m,n}^{(1,0)}: \begin{array}{c|c|c|c|c|c|c|c|c|c} m\backslash n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline 2 & 0 & 0 & 1 & 1 & 2 & 2 & 3 & 3 & 4 & 4 & 5 \\ \hline 3 & 0 & 0 & 0 & 1 & 1 & 2 & 3 & 4 & 5 & 7 & 8 \\ \hline 4 & 0 & 0 & 0 & 0 & 1 & 1 & 2 & 3 & 5 & 6 & 9 \\ \hline 5 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 2 & 3 & 5 & 7 \\ \hline 6 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 2 & 3 & 5 \\ \hline 7 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 2 & 3 \\ \hline 8 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 2 \\ \hline 9 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ \hline 10 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{array} \] It looks like no new numbers have appeared in this table; each row has simply been shifted to right, with the $m$th row having $m$ new $0$s at the start. Indeed, using the recurrence formula for $U_{m,n}$, we calculate that \[ \begin{array}{rl} U_{m,n}^{(1,0)} &= U_{m,n} - U_{m-1,n} \\ &= \sum_{k=1}^m U_{k,n-k} - \sum_{k=1}^{m-1} U_{k,n-k} \\ &= U_{m,n-m} \end{array} \] Why should this be true, from a counting perspective? Reasoning as we did with $V_{m,n}^{(1,0)}$, we see that $U_{m,n}^{(0,1)}$ counts the number of partitions of $m$ whose largest part is exactly $m$. But if the largest part is exactly $m$, then it only remains to partition $n-m$ using parts no greater than $m$, which is exactly what $U_{m,n-m}$ counts! So $U_{m,n}^{(0,1)} = U_{m,n-m}$.

Ok, now for taking first differences of $U_{m,n}$ within rows. \[ U_{m,n}^{(0,1)}: \begin{array}{c|c|c|c|c|c|c|c|c|c} m\backslash n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 2 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ \hline 3 & 1 & 0 & 1 & 1 & 1 & 1 & 2 & 1 & 2 & 2 & 2 \\ \hline 4 & 1 & 0 & 1 & 1 & 2 & 1 & 3 & 2 & 4 & 3 & 5 \\ \hline 5 & 1 & 0 & 1 & 1 & 2 & 2 & 3 & 3 & 5 & 5 & 7 \\ \hline 6 & 1 & 0 & 1 & 1 & 2 & 2 & 4 & 3 & 6 & 6 & 9 \\ \hline 7 & 1 & 0 & 1 & 1 & 2 & 2 & 4 & 4 & 6 & 7 & 10 \\ \hline 8 & 1 & 0 & 1 & 1 & 2 & 2 & 4 & 4 & 7 & 7 & 11 \\ \hline 9 & 1 & 0 & 1 & 1 & 2 & 2 & 4 & 4 & 7 & 8 & 11 \\ \hline 10 & 1 & 0 & 1 & 1 & 2 & 2 & 4 & 4 & 7 & 8 & 12 \end{array} \] Hmm, that’s curious: this is the first time we’ve seen any cases (outside of the $0$th row or the $1$st column) where the entries occasionally decrease moving left to right. What exactly are we seeing? Well, any partition of $n-1$ can be converted to a partition of $n$ by adjoining a $1$, so the difference between $U_{m,n}$ and $U_{m,n-1}$ is the number of partitions of $n$ that do not include $1$ as a part and whose largest part is at most $m$. So,

• In row $2$, we are only allowing partitions using $2$, so every even number has one partition, and every odd number has zero.
• In row $3$, we are only allowing partitions using $2$ and $3$. By hand, we find that $2$, $3$, $4$, and $5$ have one partition each, but $6$ has two: $6 = 2 + 2 + 2 = 3 + 3$. However, $7$ only has one: $7 = 3 + 2 + 2$. From this point, each time we add $6$, we increase the number of possible partitions by $1$, so $U_{3,n+6} = U_{3,n}+1$.

As the rows go on, the jumps down become harder to predict, in my view. But we could plug them into the OEIS and see what comes up! Here’s what row 4 yields.

Evidently, there is more fun to be had, looking at first differences $V_{(m,n)}^{(p,q)}$ and $U_{m,n}^{(p,q)}$ for other values of $(p,q)$, second differences, and so on. But for now let’s turn to a new game.

Generating functions

Given a sequence of numbers $\{a_n\}$, the generating function of the sequence is the formal power series \[ g(x) = \sum a_n x^n\text. \] I have not included a starting or ending index in order to allow for whatever values of $n$ make sense. In cases where the power series converges to an analytic function on some neighborhood of $0$, this function is also called the generating function of the sequence, and the terms of the sequence are the Taylor coefficients of the function.

The Virahanka–Fibonacci numbers $V_{2,n}$ produce the generating function \[ g_2(x) = \sum_{n=0}^\infty V_{2,n}x^n\text. \] Because $V_{2,0} = 1$, $V_{2,n} = 0$ for $n < 0$, and $V_{2,n} = V_{2,n-1} + V_{2,n-2}$ for $n \ge 1$, we can rewrite the power series as \[ \begin{array}{rl} g_2(x) &= \displaystyle 1 + \sum_{n=1}^\infty (V_{2,n-1} + V_{2,n-2}) x^n \\ &= \displaystyle 1 + \sum_{n=1}^\infty V_{2,n-1} x^n + \sum_{n=1}^\infty V_{2,n-2} x^n \\ &= \displaystyle 1 + x\sum_{n=1}^\infty V_{2,n-1} x^{n-1} + x^2\sum_{n=1}^\infty V_{2,n-2} x^{n-2} \\ &= \displaystyle 1 + x\sum_{n=0}^\infty V_{2,n} x^n + x^2\sum_{n=0}^\infty V_{2,n} x^n \\ &= 1 + xg_2(x) + x^2g_2(x) \end{array} \] and therefore $g_2(x) = 1 + xg_2(x) + x^2g_2(x)$. Solving this equation, we find \[ g_2(x) = \frac{1}{1 - x - x^2}\text. \] By a similar process, if we set \[ g_m(x) = \sum_{n=0}^\infty V_{m,n}x^n \] then using $V_{m,0} = 1$ and $V_{m,n} = V_{m,n-1} + \cdots + V_{m,n-m}$ for $n > 0$, we get \[ g_m(x) = \frac{1}{1 - x - \cdots - x^m}\text. \] As $m \to \infty$, the series $x + x^2 + \dots + x^m$ that is subtracted in the denominator converges to $x/(1-x)$, so the generating functions converge to \[ g_{\infty}(x) = \frac{1}{1 - x/(1 - x)} = \frac{1 - x}{1 - 2x}\text. \] This is precisely equivalent to \[ g_{\infty}(x) = 1 + \sum_{n=1}^\infty 2^{n-1} x^n \] which is the generating function of the sequence $V_{n,n}$ to which the terms of $V_{m,n}$ stabilize as $m$ grows.

Now let’s find the generating functions of the $U_{m,n}$ sequences. For each $m \ge 0$, set \[ f_m(x) = \sum_{n=0}^\infty U_{m,n}x^n \] By inspection, we have \[ f_0(x) = 1 \qquad\text{and}\qquad f_1(x) = 1 + x + x^2 + \cdots = \frac{1}{1 - x}\text. \] (These are the same as $g_0(x)$ and $g_1(x)$.) We know that $U_{2,n} = U_{1,n-1} + U_{2,n-2}$ for $n \ge 1$, and so \[ \begin{array}{rl} f_2(x) &= \displaystyle 1 + \sum_{n=1}^\infty (U_{1,n-1} + U_{2,n-2}) x^n \\ &= \displaystyle 1 + x\sum_{n=1}^\infty U_{1,n-1}x^{n-1} + x^2\sum_{n=1}^\infty U_{2,n-2} x^{n-2} \\ &= \displaystyle 1 + x\sum_{n=0}^\infty U_{1,n}x^n + x^2\sum_{n=0}^\infty U_{2,n} x^n \\ &= 1 + xf_1(x) + x^2f_2(x) \end{array} \] This implies $(1 - x^2) f_2(x) = 1 + xf_1(x)$, or \[ f_2(x) = \left(1 + \frac{x}{1 - x} \right) \frac{1}{1 - x^2} = \frac{1 - x + x}{1 - x} \frac{1}{1 - x^2} = \frac{1}{(1 - x)(1 - x^2)}\text. \] Proceeding inductively, a similar process shows that \[ f_m(x) = 1 + xf_1(x) + x^2f_2(x) + \cdots + x^mf_m(x) \] and therefore \[ f_m(x) = \frac{1}{(1-x)(1-x^2)\cdots(1-x^m)} \] for all $m \ge 2$. On compact subsets of $(-1,1)$, $x^m$ converges uniformly to $0$, and so $f_m$ converges uniformly on compact subsets of $(-1,1)$ to \[ f_\infty(x) = \prod_{k=1}^\infty \frac{1}{1 - x^k} \] which is the generating function of $U_{n,n}$, the sequence that counts all partitions of $n$.

Now that we have the generating functions $g_m(x)$ and $f_m(x)$ in hand, we can have more fun! Note that \[ x\sum a_n x^n = \sum a_n x^{n+1} = \sum a_{n-1} x^n \] and so multiplying a generating function by $x$ shifts all the terms of the sequence to the right by one position. (We have already used this fact above; it’s just worth making the general principle explicit.) This allows us to find the generating functions of the first differences calculated in the previous section. We’ll consider these in the reverse order from what we did previously.

For $U_{m,n}^{(1,0)}$, the generating function is \[ \begin{array}{rl} f_m(x) - f_{m-1}(x) &= \dfrac{1}{(1 - x)\cdots(1 - x^m)} - \dfrac{1}{(1 - x)\cdots(1 - x^{m-1})} \\ &= \dfrac{x^m}{(1 - x)\cdots(1 - x^m)} = x^mf_m(x) \end{array} \] Hey, that’s great! This matches what we just saw: the coefficients of $f_m(x) - f_{m-1}(x)$ are the same as those of $f_m(x)$, but shifted $m$ places to the right.

For $U_{m,n}^{(0,1)}$, the generating function is \[ \begin{array}{rl} f_m(x) - xf_m(x) &= \dfrac{1}{(1 - x)\cdots(1 - x^m)} - \dfrac{x}{(1 - x)\cdots(1 - x^m)} \\ &= \dfrac{1 - x}{(1 - x)\cdots(1 - x^m)} = \dfrac{1}{(1 - x^2)\cdots(1 - x^m)} \end{array} \] Oh, neat—we wanted a function that counts the number of partitions that don’t contain $1$ as a part, and the factor $1-x$ vanished! This suggests that if we want to count partitions that only allow $a_1,\dots,a_N$ then perhaps we should use the generating function $[(1-x^{a_1})\cdots(1-x^{a_N})]^{-1}$? Something to explore further…

Now for $V_{m,n}^{(1,0)}$, the generating function is \[ \begin{array}{rl} g_m(x) - g_{m-1}(x) &= \dfrac{1}{1 - x - \cdots - x^m} - \dfrac{1}{1 - x - \cdots - x^{m-1}} \\ &= \dfrac{x^m}{(1 - x - \cdots - x^m)(1 - x - \cdots - x^{m-1})} \\ &= x^m g_m(x) g_{m-1}(x)\text. \end{array} \] Hmm, this definitely tells us something interesting. Multiplying out the power series for $g_m$ and $g_{m-1}$, and equating coefficients, we find \[ V_{m,n}^{(1,0)} = \sum_{k=0}^{n-m} V_{m,k} V_{m-1,n-m-k}\text. \] Recall from our interpretation of $V_{m,n}^{(1,0)}$ that it counts the number of compositions of $n$ whose largest term is exactly equal to $m$. Indeed, since we know the largest term is $m$, we can sort the compositions by the last term that equals $m$. The sum of the terms before this will be equal to some $k \le n - m$, for which there are $V_{m,k}$ compositions with no terms greater than $m$. After the last term equal to $m$, the remaining terms will sum to $n - k - m$, for which there are $V_{m-1,n-k-m}$ compositions whose terms are all less than $m$. We thus could have found this equality earlier in our study, but the generating function suggested it immediately! (I had hoped that looking at the generating functions would also help explain why $V^{(1,0)}_{m,2m-1}$ equals the number of $1$s in all compositions of $m$, as observed above, but I haven’t quite got there yet… possible update to come!)

For $V_{m,n}^{(0,1)}$, the generating function is \[ \begin{array}{rl} g_m(x) - xg_m(x) &= \dfrac{1}{1 - x - \cdots - x^m} - \dfrac{x}{1 - x - \cdots - x^m} \\ &= \dfrac{1 - x}{1 - x - \cdots - x^m} \end{array} \] Oh, so changing the initial conditions of the sequence just corresponds to changing the numerator of the generating function. That’s neat! (Indeed, the Lucas numbers $L_n$ famously satisfy the same recursive formula as the Virahanka–Fibonacci numbers, $L_n = L_{n-1} + L_{n-2}$, and their generating function is $(2-x)/(1-x-x^2) = g_2(x) + (g_2(x)-xg_2(x))$.)

I can’t help doing one more thing with these generating functions, especially since we haven’t seen much interaction between the numbers $V_{m,n}$ and $U_{m,n}$. Let’s try dividing their generating functions. We know that $V_{m,n}$ is at least as large as $U_{m,n}$, so we’ll divide $g_m$ by $f_m$: \[ \frac{g_m}{f_m} = \frac{(1-x)\cdots(1-x^m)}{1-x-\cdots-x^m}\text. \] What could the coefficients of this generating function represent? Loosely speaking, they carry the information about the number of compositions (with no part greater than $m$) that is not contained in the number of partitions. That’s fairly vague, so let’s consider the case $m = 2$. We calculate \[ \frac{g_2}{f_2} = \frac{(1-x)(1-x^2)}{1-x-x^2} = 1 + \frac{x^3}{1-x-x^2} = 1 + x^3 g_2 \] which gives us the factorization $g_2 = f_2\big(1 + x^3 g_2\big)$, or $g_2 = f_2 + x^3 f_2 g_2$. Equating coefficients of the power series yields the relation \[ V_{2,n} = U_{2,n} + \sum_{k=0}^{n-3} U_{2,k} V_{2,n-3-k}\text. \] This equation has a sensible meaning. Recall that a partition of $n$ can be thought of as a composition (a sum of positive integers summing to $n$) in which the terms are non-increasing. (For example, $2 + 2 + 1 + 1 + 1$ is a partition of $7$, but $2 + 1 + 1 + 2 + 1$ is not.) The right-hand side of the last equation splits the number of compositions into the number of partitions $U_{2,n}$ and the number of non-partitions. If we are only allowing terms equal to $1$ or $2$, then a composition that is not a partition must have a $1$ followed by a $2$ somewhere in its expression. In poetic terms, we can think of $1$ and $2$ as short and long syllables, and $n$ as the number of beats in a line. We sort compositions by where the first appearance of $1 + 2$ occurs. Everything before that in the sum is non-increasing; say this takes $k$ beats (this is the $U_{2,k}$ factor in the sum on the right). Then we have $1 + 2$, which accounts for $3$ more beats, and finally the remaining $n-3-k$ beats can be subdivided in any manner using shrot and long syllables (which is what the $V_{2,n-3-k}$ factor counts).

The sequence of coefficients for $g_4(x)/f_4(x)$ begins \[ 1,\;0,\;0,\;1,\;2,\;5,\;8,\;16,\;30,\;58,\;113,\;217,\;418,\;\dots\text. \] As of this writing (May 2022) this sequence does not appear in the OEIS (should I submit it?). However, the sequence of coefficients for \[ \frac{g_\infty}{f_\infty} = 1 + x^3 + 2x^4 + 5x^5 + 9x^6 + 19x^7 + 37x^8 + 74x^9 + 148x^{10} + \cdots \] does appear, as A178841, which counts “the number of pure inverting compositions of $n$.” These seem to be related to a basis for the algebra of quasisymmetric functions as a module over the symmetric functions. So there’s something deep and important going on with these quotients!

In case it isn’t obvious from this post, I’m still learning about generating functions, and I’m kind of in awe of them. It’s entirely possible that everything in this post appears among the exercises of some book on combinatorics. (Certainly most of them are mild generalizations of facts that can be found in the OEIS.) One of my summer activities may be to finally get through Herbert Wilf’s book generatingfunctionology (the second edition is available for free download at the link).