5
$\begingroup$

For integer-valued sequences $(x_n)_{n=0}^\infty$, consider recurrences of the form $$x_n=ax_{n-1}+(bn+c)x_{n-2} \tag{$*$}\label{star}$$ for $n\ge2$, where $a,b,c$ are integers. There seem to be many such sequences in the OEIS — see e.g. A000085, A001475, A005425, and A000898 — with various combinatorial descriptions.

Question: Is there a common combinatorial description for all integer-valued sequences $(x_n)_{n=0}^\infty$ satisfying recurrences of the form \eqref{star} — at least for natural $a$, $b$ ,$c$ and for some initial conditions (on $x_0$, $x_1$, depending on $a$, $b$, $c$)?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ The solutions to the differential equation $y''=ay'+bxy'+cy$ around the origin are precisely the functions of the form $\sum_{k=0}^{\infty}a_{k}\frac{x^{k}}{k!}$ there the coefficients satisfy the recurrence relation $a_{n+2}=a\cdot a_{n+1}+(bn+c)a_{n}$. According to WolframAlpha, this is a Strum-Liouville equation (the solution is written in terms of Hermite polynomials and hypergeometric functions). $\endgroup$
    – Joseph Van Name
    Commented Jan 3, 2022 at 5:41
  • $\begingroup$ @JosephVanName : Thank you for your comment. $\endgroup$
    – Iosif Pinelis
    Commented Jan 3, 2022 at 16:26

1 Answer 1

Reset to default
5
$\begingroup$

So, the Fibonacci numbers can be constructed from this recursion, so it is natural to look for generalizations of those (and combinatorial models for the Fibonacci numbers). The Fibonacci number $f_n$ (up to some index shift), can be seen as the number of integer compositions of $n$ (list of numbers summing to $n$), using only the numbers $1$ and $2$.

Now, the recursion above, $x_n = a x_{n-1} + (bn+c)x_{n-2}$ hints that we also look at integer compositions using $1$ and $2$, but the $1$ comes in $a$ different colors. Moreover, the 2s have two types, either, one of $c$ colors, or it is a 'special' 2, with one of $b$ colors and a label. The label is between 1 and the total sum of entries up to that point.

For example, $a=3$, $b=3$, $c=2$ $n=8$ has the object $$ 1_3, \; 2_{1, 1}, \; 2_{3, 5}, \; 2_{2}, \; 1_{1}. $$ The numbers sum to $n$, and subscripts of the $1$ is between $1$ and $a$. The $2's$ with only one subscript has the subscript between $1$ and $c$. Finally, each $2$ with two substripts, has the first subscript (color) between $1$ and $b$. The second subscript must be between $1$ and the sum of all numbers in the list up to that point. For example, for $2_{3, 5}$, the 5 is the maximum allowed since $1+2+2=5$.

Below is Mathematica code for generating such compositions:

a = 3;
b = 3;
c = 2;
Clear[f];
f[0] := {{}};
f[1] := Table[{{1, j}}, {j, a}];
f[n_] := f[n] = Join[
    Join @@ Table[
      Append[f, {1, aa}],
      {f, f[n - 1]}, {aa, a}]
    ,
    Join @@ Table[
      Append[f, {2, bb}],
      {f, f[n - 2]}, {bb, b}]
    ,
    Join @@ (Join @@ Table[
        Append[f, {2, cc, j}],
        {f, f[n - 2]}, {cc, c}, {j, n}])
    ];

The natural initial condition is $x_0 =0$ and $x_1 = a$. (In the code above, I use $f$ instead of $x$)

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thank you very much for your answer. I have a question, though: f[n] is a list of lists of lists, whereas $x_n$ is a number; how is then f[n] related to $x_n$, and why? Also, I have taken a liberty to fix a typo. $\endgroup$
    – Iosif Pinelis
    Commented Jan 3, 2022 at 15:45
  • 1
    $\begingroup$ $x_n$ counts the sets enumerated by these lists, so is equal to their length. $\endgroup$
    – Ben Barber
    Commented Jan 3, 2022 at 16:42
  • $\begingroup$ @BenBarber : Thank you for your comment. $\endgroup$
    – Iosif Pinelis
    Commented Jan 3, 2022 at 17:41
  • 1
    $\begingroup$ With $a=z+w $, $b=1$ and $c=0$, there is the generalization of the recurrence relation to the bivariate Hermite polynomials of oeis.org/A344678 $$H_{n}(z+w) = (z+w) H_{n-1}(z+w) + n H_{n-2}(z+w).$$ Per, I wonder if you could add another combinatorial model to that entry. $\endgroup$
    – Tom Copeland
    Commented Jan 3, 2022 at 21:12
  • 1
    $\begingroup$ @PerAlexandersson, it's a specialization in the sense that $a,b,c$ have been restricted and a generalization in that it deals with a sequence of bivariate polynomials rather than a sequence of numbers. $\endgroup$
    – Tom Copeland
    Commented Jan 3, 2022 at 21:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .