A combinatorial interpretation of the generalized Fibonacci numbers (Q1373439): Difference between revisions

The author considers the Fibonacci numbers of order \(k\), i.e., the numbers \(F^{(k)}_n\) defined by the recurrence relation \(F^{(k)}_{n+ k}= F_{n+k-1}^{(k)}+ F_{n+ k-2}^{(k)}+\cdots+ F_{n+1}^{(k)}+ F^{(k)}_n\) and, as in \textit{D. E. Knuth} [The art of computer programming, Vol. 3, Addison-Wesley (1974; Zbl 0302.68010)], by the initial conditions \(F^{(k)}_0=\cdots= F_{k-2}^{(k)}= 0\), \(F_{k-1}^{(k)}= 1\). He derives a combinatorial interpretation of them in the context of the linear species of \textit{A. Joyal} [Adv. Math. 42, 1-82 (1981; Zbl 0491.05007)] as the linear species of \(k\)-filtering partitions. He also proves a number of interesting identities.