🔢 mathematics

An identity relating $n$ -nacci numbers, partitions, and products of binomial coefficients

This paper establishes a combinatorial identity expressing $n$ -nacci numbers as sums of products of binomial coefficients over specific partitions derived from "final types," thereby generalizing the classical Fibonacci identity and analyzing the associated partial order structures.

Original authors: Dušan Dragutinović

Published 2026-01-27

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Dušan Dragutinović

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a mathematician trying to organize a chaotic pile of LEGO bricks. You want to find hidden patterns in how these bricks can be stacked, grouped, and counted. This paper by Dušan Dragutinović is exactly that: a guide to finding order in the chaos of numbers, specifically focusing on three main characters: Final Types, Partitions, and n-nacci Numbers.

Here is the story of the paper, broken down into simple concepts.

1. The Characters: What are we talking about?

The "Final Types" (The Staircase Builders)
Imagine a staircase that goes up from the ground (0) to a certain height ( $g$ ). A "Final Type" is a specific rule for building this staircase. The rule is simple: at every step, you can either stay at the same height or go up by exactly one step. You can never jump two steps at once.

The Analogy: Think of a video game character climbing a ladder. They can stand still or climb one rung. They cannot teleport. The paper studies all the different ways this character can climb from the bottom to the top.

The "Partitions" (The Grouping Game)
Now, imagine you have a pile of $g$ identical coins. A "Partition" is just a way of splitting that pile into smaller piles. For example, if you have 6 coins, you could split them into piles of 3, 2, and 1. Or maybe 2, 2, and 2.

The Analogy: It's like breaking a chocolate bar into pieces. You can break it into 3 big chunks, or 6 tiny crumbs. The total amount of chocolate stays the same, but the arrangement changes.

The "n-nacci Numbers" (The Family Tree of Fibonacci)
You probably know the Fibonacci numbers (1, 1, 2, 3, 5, 8...), where each number is the sum of the previous two.
The n-nacci numbers are the "cousins" of Fibonacci.

2-nacci: Sum of the previous 2 (Fibonacci).
3-nacci (Tribonacci): Sum of the previous 3.
4-nacci (Tetranacci): Sum of the previous 4.
The Analogy: Imagine a family where every child is born based on how many parents they have. In the 2-nacci family, you need 2 parents. In the 3-nacci family, you need 3 parents. The paper looks at how these families grow.

2. The Big Discovery: Connecting the Dots

The author found a magical bridge connecting these three characters.

The Bridge:
The paper proves that if you take a specific number (let's call it $g$ ) and look at the n-nacci number for that position, you can calculate it by adding up a bunch of "products of binomial coefficients" (which are just fancy math ways of counting combinations) over all the possible Partitions of that number.

The Metaphor: Imagine you want to know the total population of a city (the n-nacci number). Instead of counting people one by one, you realize that the population is exactly equal to the sum of all possible ways you can arrange a specific set of furniture (Partitions) in a room, where each arrangement has a specific "weight" (the binomial coefficients).
The Result: The author gives a formula that says:

"The n-nacci number is the sum of these specific counting products over all possible ways to split the number $g$ ."

This is a big deal because it generalizes a famous old trick. For a long time, mathematicians knew this trick worked for the standard Fibonacci numbers (where $n=2$ ). This paper says, "Hey, this trick works for all versions of the Fibonacci family, not just the original!"

3. The "Ordering" Game: Who is bigger?

The second half of the paper is like a game of "Who is more organized?" The author looks at the different ways to split the coins (Partitions) and asks: "Can we say one arrangement is 'smaller' or 'less complex' than another?"

They compare three different ways of ranking these arrangements:

The "Grouping" Order ( $\le_{pp}$ ): One arrangement is "smaller" if it can be made by gluing together pieces of the other. (e.g., A pile of 2+2 is "smaller" than a pile of 1+1+1+1 because you just glued the 1s together).
The "Dominance" Order ( $\le_{do}$ ): One arrangement is "smaller" if its biggest piles are smaller than the other's. (e.g., A pile of 3+1 is "bigger" than 2+2 because 3 is a bigger top pile).
The "Final Type" Order ( $\le_{ft}$ ): This is the new, tricky one. It's based on the "Staircase Builders" (Final Types) mentioned earlier. If you can build the staircase for arrangement A using a "lower" or "slower" staircase than arrangement B, then A is "smaller."

The Main Finding on Ordering:
The author discovered that the "Final Type" order sits right in the middle of the other two.

If Arrangement A is "smaller" by the Grouping rules, it is also "smaller" by the Final Type rules.
If Arrangement A is "smaller" by the Final Type rules, it is also "smaller" by the Dominance rules.
But: The reverse isn't always true. Just because A is "smaller" by the Dominance rules doesn't mean it's "smaller" by the Final Type rules.
The Metaphor: Imagine three judges rating a dance routine.
- Judge 1 (Grouping) is very strict: "You must have glued your moves together perfectly."
- Judge 3 (Dominance) is very loose: "As long as your biggest move wasn't huge, you're fine."
- Judge 2 (Final Type) is the middle ground. The paper proves that if Judge 1 likes you, Judge 2 will too. And if Judge 2 likes you, Judge 3 will too. But Judge 3 might like someone that Judge 2 rejects.

4. Why does the author care? (The "Real World" Connection)

The paper mentions that this isn't just a game with numbers. The "Final Types" and "Partitions" come from a very advanced field called Algebraic Geometry, specifically studying shapes called Abelian Varieties in a world with a specific type of math called "characteristic p" (which relates to prime numbers).

The Analogy: Think of these shapes as complex, multi-dimensional donuts. Mathematicians want to know how these donuts behave when you zoom in very closely (looking at their "p-torsion"). The "Final Types" are like the unique fingerprints of these donuts, and the "Partitions" describe how their internal gears (operators) turn.
The paper shows that by understanding the simple combinatorial rules (the LEGO stacking and coin splitting), we can understand the complex behavior of these high-level geometric shapes.

Summary

In short, this paper does two main things:

It found a new formula: It showed how to calculate a whole family of number sequences (n-nacci) by adding up specific combinations of number partitions. It's like finding a universal key that opens the lock for Fibonacci and all its cousins.
It mapped the relationships: It organized the different ways to split numbers into a hierarchy, proving that a new way of ordering them (based on "Final Types") sits perfectly between two old, well-known ways of ordering them.

The author didn't invent these numbers to build a new app or cure a disease; they did it because the mathematical structure itself is beautiful and reveals deep connections between counting, geometry, and algebra.

Technical Summary: An Identity Relating n-Nacci Numbers, Partitions, and Products of Binomial Coefficients

Problem Statement
The paper investigates the combinatorial properties of "final types," defined as non-decreasing sequences of integers with a maximal step of 1, and their associated partitions. The primary objective is to establish a precise correspondence between these final types and integer partitions to derive new identities involving $n$ -nacci numbers (generalizations of Fibonacci numbers) and products of binomial coefficients. Additionally, the work seeks to clarify the relationship between the partial order induced by final types and two classical partial orders on the set of integer partitions: the "partial partition" order ( $\le_{pp}$ ) and the dominance order ( $\le_{do}$ ).

Methodology
The author employs a combinatorial approach rooted in the structural analysis of functions $\nu: \{0, 1, \dots, g\} \to \{0, 1, \dots, g\}$ satisfying $\nu(0)=0$ and $\nu(i) \le \nu(i+1) \le \nu(i)+1$ .

Correspondence Construction: For a given final type $\nu$ of length $g$ , a partition $\delta_\nu$ is defined by the differences $\delta_\nu(i) = \nu_{i-1}(g) - \nu_i(g)$ , where $\nu_i$ denotes the $i$ -fold composition of $\nu$ .
Counting Argument: The paper calculates the number of final types $N(\delta)$ that map to a specific partition $\delta$ . This is achieved by analyzing the constraints on the values of $\nu$ between the fixed points determined by the partition parts, leading to a product of binomial coefficients.
Recursive Derivation: By summing these counts over all partitions of a fixed integer, the author derives a recurrence relation for the number of final types satisfying specific conditions ( $\nu_n(g)=0$ ). This recurrence is shown to match the definition of $n$ -nacci numbers.
Order Comparison: The study defines a partial order $\le_{ft}$ on partitions induced by the lexicographical ordering of their corresponding final types. This order is then compared against $\le_{pp}$ (where one partition is obtained by grouping parts of another) and the dominance order $\le_{do}$ (based on partial sums of parts).

Key Contributions and Results

Generalized Identity for n-Nacci Numbers:
The central result is an identity expressing the $n$ -nacci numbers as a sum of products of binomial coefficients over specific partitions. For any $g \ge 1$ and $n \ge 1$ , the paper proves:
$\tilde{F}_n(g+n) = \sum_{\substack{0 \le \delta_n \le \dots \le \delta_1 \le g \\ \delta_1 + \dots + \delta_n = g}} \binom{\delta_1}{\delta_2} \binom{\delta_2}{\delta_3} \dots \binom{\delta_{n-1}}{\delta_n}$
Here, $\tilde{F}_n$ denotes the $n$ -nacci sequence defined by $\tilde{F}_n(k) = \sum_{j=1}^n \tilde{F}_n(k-j)$ with specific initial conditions. This generalizes the classical Lucas identity for Fibonacci numbers ( $n=2$ ).
Combinatorial Identity for Partitions:
A corollary of the main theorem provides a purely combinatorial identity for the sum of products of binomial coefficients over all partitions of $g$ :
$\sum_{\delta \vdash g} \prod_{i=1}^{|\delta|-1} \binom{\delta_i}{\delta_{i+1}} = 2^{g-1}$
The paper offers two proofs for this: one derived from the main theorem and an alternative, purely combinatorial proof based on counting final types with $f(\nu)=0$ .
Hierarchy of Partial Orders:
The paper establishes a strict hierarchy among three partial orders on the set of partitions of a fixed integer $g$ :
$\delta \le_{pp} \delta' \implies \delta \le_{ft} \delta' \implies \delta \le_{do} \delta'$
The author demonstrates that the reverse implications do not hold in general. Specifically, $\le_{ft}$ is shown to be a partial order that lies strictly between the "partial partition" order and the dominance order. The paper provides counterexamples (e.g., partitions of $g=6$ ) to show that $\le_{ft}$ is distinct from both $\le_{pp}$ and $\le_{do}$ .
Motivation from Algebraic Geometry:
The study of these combinatorial objects is motivated by the classification of $p$ -torsion of principally polarized abelian varieties in characteristic $p$ . The final types correspond to isomorphism classes of polarized Dieudonné modules (specifically the Ekedahl-Oort type), while the associated partitions encode the action of the Verschiebung operator $V$ . The combinatorial results, such as the criterion for when a partition uniquely determines a final type, have direct interpretations in this geometric context.

Significance
The paper claims significance primarily in providing a unified combinatorial framework that connects $n$ -nacci numbers, binomial coefficient products, and integer partitions. While the case $n=2$ (Fibonacci numbers) is a classical result attributed to Lucas, the generalization to arbitrary $n$ is presented as an elegant formula that appears to be absent from standard references. Furthermore, the identification of the $\le_{ft}$ order as an intermediate structure between two well-studied partial orders offers a new perspective on the lattice of integer partitions. The work bridges abstract combinatorics with the specific needs of algebraic geometry regarding the classification of abelian varieties, providing explicit counting formulas and structural insights relevant to the study of $p$ -torsion.

1. The Characters: What are we talking about?

2. The Big Discovery: Connecting the Dots

3. The "Ordering" Game: Who is bigger?

4. Why does the author care? (The "Real World" Connection)

Summary

More like this