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

Dušan Dragutinović · 2026

Read An identity relating n n -nacci numbers, partitions, and products of binomial coefficients by Dušan Dragutinović (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-17401.txt.

Introduction

Dušan Dragutinović studies links between number sequences and partitions. He looks at final types, certain non-decreasing integer sequences. Each such sequence pairs with partitions in a natural way. From that link, he proves an identity for n-nacci numbers. Those numbers extend the Fibonacci rule to longer sums. The identity writes them as sums of products of binomial coefficients.

The sums run over the partitions tied to final types. The result extends a classical identity to the full family. Such identities help counters check formulas in two ways at once. They also show hidden order in fast-growing sequences. Pure counters gain a new bridge between sequences and splits.

Catalog record

CREATORDušan Dragutinović
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE44 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-17401

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An identity relating n n -nacci numbers, partitions, and products of binomial coefficients Dušan Dragutinović Abstract . We study the combinatorial properties of final types, which are certain non-decreasing sequences of integers, together with the partitions naturally associated with them. As a consequence, we obtain an identity expressing the n n -nacci numbers as sums of products of binomial coefficients over these partitions, generalizing the classical identity for n = 2 n=2 that expresses Fibonacci numbers in this way. We also examine how the partial order on the set of all partitions of a fixed integer induced by the ordering of final types compares with two natural partial orders on the same set. 1. Introduction In this note, we study the relations between final types \nu , which are certain non-decreasing sequences of length g\geq 1 with maximal step 1 , and the partitions \delta=\delta_{\nu} of g that are defined from them; see Section 2 for more details. Our aim is to highlight several combinatorial features of this correspondence and to draw attention to some consequences that seem to be of independent interest. As a first consequence of this relation, we obtain identities involving products of binomial coefficients and the n -nacci numbers, generalizing a well-known result for n=2 concerning the representation of Fibonacci numbers as sums of specific binomial coefficients. More precisely, given g\geq 1 and n\geq 1 , let \tilde{F}_{n}(g) be the sequence of n -nacci numbers, that is, \tilde{F}_{n}(g)=\tilde{F}_{n}(g-1)+\ldots+\tilde{F}_{n}(g-n),\quad g\geq n+1 with initial conditions \tilde{F}_{n}(1)=\ldots=\tilde{F}_{n}(n-1)=0\quad\text{and}\quad\tilde{F}_{n}(n)=1. In the special case n=2 , recall that \tilde{F}_{2}(g) is equal to the g -th Fibonacci number. Namely, \tilde{F}_{2}(g)=\mathrm{Fibonacci}(g), where \mathrm{Fibonacci}(g)=\mathrm{Fibonacci}(g-1)+\mathrm{Fibonacci}(g-2)\text{ for }g\geq 2 with \mathrm{Fibonacci}(1)=0\quad\text{and}\quad\mathrm{Fibonacci}(2)=1. It is a classical identity, already observed by Lucas in [ Luc91 ] , that \tilde{F}_{2}(g)=\mathrm{Fibonacci}(g) can be expressed as a sum of binomial coefficients for any g\geq 2 . For example, 5=\tilde{F}_{2}(6)={4\choose 0}+{3\choose 1}+{2\choose 2}\text{ and }144=\tilde{F}_{2}(13)={11\choose 0}+{10\choose 1}+{9\choose 2}+{8\choose 3}+{7\choose 4}+{6\choose 5}. More generally, as noted in [ Luc91 , p. 7] , one has \mathrm{Fibonacci}(g+2)=\sum_{i=0}^{\left\lfloor{g}/{2}\right\rfloor}{g-i\choose i} , i.e., (1.1) \tilde{F}_{2}(g+2)=\sum_{i=0}^{\left\lfloor\frac{g}{2}\right\rfloor}{g-i\choose i}\text{ for any }g\geq 0. Below we observe the following identity, which generalizes ( 1.1 ) from n=2 to all n\geq 2 . Although we expect that the case n\geq 3 is known in at least some instances, the lack of a suitable reference leads us to include this elegant formula here. For some similar identities, including the generating function of generalized Fibonacci and n -nacci numbers and partitions, we refer to [ Yan08 ] , [ HL09 ] , [ Sil11 ] , and [ Kom14 ] . Theorem . For any g\geq 1 and n\geq 1 , the following identity holds: \tilde{F}_{n}(g+n)=\sum_{\begin{subarray}{c}0\leq\delta_{n}\leq\ldots\leq\delta_{2}\leq\delta_{1}\leq g\\ \delta_{1}+\delta_{2}+\ldots+\delta_{n}=g\end{subarray}}{\delta_{1}\choose\delta_{2}}{\delta_{2}\choose\delta_{3}}\ldots{\delta_{n-1}\choose\delta_{n}}. A partition \delta=\delta_{1}\ldots\delta_{n} of g consists of 1\leq\delta_{n}\leq\delta_{n-1}\leq\ldots\leq\delta_{1}\leq g such that \delta_{1}+\ldots+\delta_{n}=g . In this case, we write \delta\vdash g and denote the length of \delta , that is, the number of elements appearing in this partition, by |\delta|=n . For example, if \delta=3111 and \delta^{\prime}=832 , then \delta\vdash 6, |\delta|=4,\delta^{\prime}\vdash 13 , and |\delta^{\prime}|=3 . A consequence of the preceding theorem for {n=g} provides a neat connection between several combinatorial notions, as shown in the corollary below. Corollary . For any g\geq 1 , the following identity holds: \sum_{\delta\vdash g}\prod_{i=1}^{|\delta|-1}{\delta_{i}\choose\delta_{i+1}}=2^{g-1}. In Corollary 2.3 , we offer an alternative, purely combinatorial proof of the previous corollary, which does not rely on the preceding theorem. In addition to the material mentioned above, we continue our discussion of the relationship between final types and the partitions defined from them by studying three partial orderings on the set of all partitions of a fixed integer: the order induced by the lexicographic order on final types, \leq_{ft} , the order defined in terms of partial partitions, \leq_{pp} , and the dominance order, \leq_{do} ; see Section 4 for more details. In particular, we obtain the following result in Proposition 4.12 , which shows an interesting property of \leq_{ft} , placing it between the two classically studied orders. Proposition . For any two partitions \delta\vdash g and \delta^{\prime}\vdash g , it holds that \delta\leq_{pp}\delta^{\prime}\implies\delta\leq_{ft}\delta^{\prime}\implies\delta\leq_{do}\delta^{\prime}. In general, \delta\leq_{ft}\delta^{\prime}\not\implies\delta\leq_{pp}\delta^{\prime} and \delta\leq_{do}\delta^{\prime}\not\implies\delta\leq_{ft}\delta^{\prime} . Outline. In Section 2 , we present initial results relating final types and partitions. Furthermore, in Subsection 2.4 , we briefly explain our motivation for studying these combinatorial invariants, which comes from algebraic geometry and the study of p -torsion of abelian varieties in characteristic p . In Section 3 , we prove the theorem stated above. Finally, in Section 4 , we consider another viewpoint motivated by the discussion in Subsection 2.4 , concerning the three partial orders on the set of all partitions, and we compare them. 2. Final types and partitions Let g\geq 1 be an integer. We first introduce the basic notions of the final types and partitions we will use throughout this article. Final types are non-decreasing sequences of integers with a maximum step of 1 with some initial properties; see below for the precise definition we will use. We say that \delta=\delta_{1}\delta_{2}\ldots\delta_{n} is a partition of g if \delta_{i}\in\mathbb{Z} and 1\leq\delta_{n}\leq\delta_{n-1}\leq\ldots\leq\delta_{2}\leq\delta_{1}\leq g\quad\text{and}\quad\delta_{1}+\delta_{2}+\ldots+\delta_{n}=g. In this case, we write \delta\vdash g\quad\text{and}\quad|\delta|=n. 2.1. Final types Consider a function \nu:\{0,1,\ldots,g\}\to\{0,1,\ldots,g\} such that \nu(0)=0\quad\text{and}\quad\nu(i)\leq\nu(i+i)\leq\nu(i)+1. We say that \nu is a final type of length g and write \nu\vdash g. Taking into account that \nu is determined by the values of \nu(i) with 1\leq i\leq g , we also write \nu=(\nu(1),\nu(2),\ldots,\nu(g)), and think of \nu as of sequence of g numbers. Furthermore, let us denote \nu^{i}(j)=\underbrace{\nu\circ\ldots\circ\nu}_{i}(j)\quad\text{with}\quad\nu^{0}(j)=j,\quad\text{for any}\quad 0\leq i,j\leq g. Lastly, we denote f(\nu)=\nu^{g}(g); equivalently, f(\nu) is the largest f\geq 0 such that \nu(i)=i for every {0\leq i\leq f} . Remark 2.1 . In total, there are 2^{g} final types \nu\vdash g ; namely, this count follows from the property that \nu(i)=\nu(i-1) or \nu(i)=\nu(i-1)+1 for any 1\leq i\leq g . 2.2. Partitions defined by final types Given a final type \nu\vdash g , let (2.1) \delta_{\nu}(i)=\nu^{i-1}(g)-\nu^{i}(g)\quad\text{for all}\quad 1\leq i\leq g. Note that \delta_{\nu}(i+1)\leq\delta_{\nu}(i)\quad\text{for all}\quad 1\leq i<g. If n is the largest number such that \delta_{\nu}(n)\neq 0 , then \delta_{\nu}=\delta_{\nu}(1)\delta_{\nu}(2)\ldots\delta_{\nu}(n) is a partition of g-f(\nu) , i.e., \delta_{\nu}(1)+\ldots+\delta_{\nu}(n)=g-f(\nu). On the other hand, let 0\leq f\leq g and let \delta=\delta_{1}\delta_{2}\ldots\delta_{n}\vdash g-f be a partition with \delta=|n| . By the defining property ( 2.1 ), final type \nu\vdash g satisfies \delta_{\nu}=\delta if and only if \nu(f+\sum_{i=j}^{n}\delta_{i})=f+\sum_{i=j+1}^{n}\delta_{i},\quad\text{for all}\quad j=1,\ldots,n, or, in other words, (2.2) \nu=(\underbrace{1,2,\ldots,f}_{f},\underbrace{*,\ldots,*,f}_{\delta_{n}},\underbrace{*,\ldots,*,f+\delta_{n}}_{\delta_{n-1}},\underbrace{*,\ldots,*,f+\sum_{i=n-1}^{n}\delta_{i}}_{\delta_{n-2}},\ldots,\underbrace{*,\ldots,*,f+\sum_{i=2}^{n}\delta_{i}}_{\delta_{1}}), where each entry * can be any integer as long as \nu(i)\leq\nu({i+1})\leq\nu(i)+1 for 0\leq i\leq g-1 with \nu(0)=0 . 2.3. Relations between final types and partitions The natural question is: given a partition \delta\vdash g-f for some g\geq 1 and 0\leq f\leq g , what is the number N(\delta) of final types \nu\vdash g such that \delta=\delta_{\nu} . We compute this in the following proposition. Proposition 2.2 . Let g\geq 1 , 0\leq f\leq g and let \delta=\delta_{1}\delta_{2}\ldots\delta_{n}\vdash g-f be a partition of g-f with |\delta|=n . Then, there are exactly N(\delta)=\prod_{i=1}^{n-1}{\delta_{i}\choose\delta_{i+1}} final types \nu\vdash g such that \delta=\delta_{\nu} . Proof. The number of sequences (\nu^{\prime}(1),\ldots,\nu^{\prime}(k)) such that \nu^{\prime}(0)=m,\quad\nu^{\prime}(k)=M,\quad\text{and}\quad\nu^{\prime}(i-1)\leq\nu^{\prime}(i)\leq\nu^{\prime}(i-1)+1,\text{ }1\leq i\leq k equals {k\choose M-m} : out of k indices 1\leq i\leq k , we choose M-m for which \nu^{\prime}(i-1)<\nu^{\prime}(i) . Let \delta=\delta_{1}\delta_{2}\ldots\delta_{n}\vdash g-f . As we noted in Subsection 2.2 , the final types \nu\vdash g such that \delta_{\nu}=\delta must

Read the complete text