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](http://oeis.org/A000085), [A001475](https://oeis.org/A001475), [A005425](https://oeis.org/A005425), and [A000898](https://oeis.org/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$)?
> 
> 
> 



A common combinatorial description for a certain type of recurrences
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$)


