Sagan and Savage gave a combinatorial interpretation of a polynomial generalization of Fibonomial coefficients. Their proof uses the recurrence relation for the Lucas polynomials that generalize the Fibonacci numbers, namely $\{0\}=0$, $\{1\}=1$, $\{n\}=s\{n-1\}+t\{n-2\}$ for $n\ge 2$. Define $s$ as a weight of a monomino, $t$ is a weight of a domino, and extend the weight function multiplicatively as usual. Then the $s,t$-Fibonacci number $\{n+1\}$ is the sum of all possible weights of an $n\times 1$ strip of cells. Subsequently, $\{n\}!=\{n\}\{n-1\}\dots\{1\}$, $\{0\}!=1$, and the $s,t$-Fibonomial coefficient $$ {m+n \brace m}=\frac{\{m+n\}!}{\{m\}!\{n\}!} $$ is the sum of weights of fillings of an $m\times n$ rectangle by pairs of complementary partitions $(\lambda,\lambda^*)$ so that rows of $\lambda$ and columns of $\lambda^*$ are filled by monominos and dominos, and every column of $\lambda^*$ starts with a domino (see Figure 2 in the paper).

The proof that ${m+n \brace n}$ is a combinatorial interpretation of the $s,t$-Fibonomial coefficients is recursive, using the identity $$ {m+n \brace m}=\{n+1\}{m+n-1 \brace m-1} + t\{m-1\}{m+n-1 \brace m}. $$

However, I am wondering if there have since been any direct bijections, using this combinatorial interpretation of $s,t$-Fibonomials, corresponding to the following identities: $$ \begin{split} {m+n \brace m}&={m+n \brace n}\\ {m+n+1 \brace m+1}\{m+1\}&={m+n+1 \brace m}\{n+1\}={m+n \brace m}\{m+n+1\}\\ {m+n \brace m}\{m\}!&=\{m+n\}\{m+n-1\}\dots\{m+1\} \end{split} $$


I'm glad to see you're interested in this question. A number of people have thought about it including Art Benjamin and myself. The person who seems to have gotten the furthest is Curtis Bennett who came up with a new way to view the rectangular tilings in terms of tilings of a triangle with a lattice path through it which explains those special dominoes in an intuitive way. Last I heard he and a student were trying to prove identities like the ones you state using their interpretation.

If you are looking for other open problems involving the Fibonomials, see my paper with Xi Chen, The fractal nature of the Fibonomial triangle, Integers, 14 (2014), A3, 12 pp., as well as the article Generalized Fibonacci polynomials and Fibonomial coefficients (with Tewodros Amdeberhan, Xi Chen and Victor H. Moll), Ann. Combin., 18 (2014), 541-562.

Finally, one can play the same game (replacing n by F_n or an appropriate polynomial) with Catalan numbers and even with Catalan analogues for Coxeter groups. The resulting fractions always give integers (or polynomials in the weighted case) and nobody really understands why. See the slides for my talk Open Problems for Catalan Number Analogues at http://users.math.msu.edu/users/sagan/Slides/OpcH.pdf

| cite | improve this answer | |
  • 1
    $\begingroup$ Thanks, Bruce, and welcome to MO! I actually started by thinking about FiboCatalan polynomials and then realized that to prove $\frac{1}{\{n+1\}}{2n \brace n}={2n-1 \brace n-1}+t{2n-1 \brace n-2}$ combinatorially from your recurrence, I would need to show $\{n-1\}{2n-1 \brace n}=\{n+1\}{2n-1 \brace n+1}$. This implied looking at the identities I listed. $\endgroup$ – Alexander Burstein Jan 11 '18 at 21:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.