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$.
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).
No comments:
Post a Comment