Enumerating Flat Fubini Rankings

Kenny Barrese, Jennifer Elder, Pamela E. Harris, Anthony Simpson · 2025

Read Enumerating Flat Fubini Rankings by Kenny Barrese, Jennifer Elder, Pamela E. Harris, Anthony Simpson (2025) 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-2504-06466.txt.

Introduction

When a contest allows ties, the possible final rankings of the players can be coded as lists of numbers called Fubini rankings. Barrese, Elder, Harris, and Simpson study rankings whose rising runs appear in a flattened order. They define two flattened families, one using strict rises and one allowing level steps, each with its own ordering rule for the runs.

The main results give exact counting formulas for both families: how many flattened rankings exist for any number of competitors. Such counts are rarely simple, since ties multiply the possibilities quickly. The authors also pose conjectures for further study, inviting others to extend the patterns. The work adds to combinatorics, the branch of math that counts structured arrangements, and may help analyze contests and voting systems where ties are common.

Catalog record

CREATORKenny Barrese, Jennifer Elder, Pamela E. Harris, Anthony Simpson
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE67 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-06466

Browse the full library · About the Tower of Babel

Full text

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

Enumerating Flat Fubini Rankings Kenny Barrese, Jennifer Elder, Pamela E. Harris, Anthony Simpson Abstract . Recall that the set of Fubini rankings on n n competitors consists of the n n -tuples that encode the possible rankings of n n competitors in a competition allowing ties. Moreover, recall that a run (weak run) in a tuple is a subsequence of consecutive ascents (weak ascents). If the leading terms of the set of maximally long runs (weak runs) of a tuple are in increasing (weakly increasing) order, then the tuple is said to be flattened (weakly flattened). We define the set of strictly flattened Fubini rankings, which is the subset of Fubini rankings with runs of strict ascents whose leading term are strictly increasing. Analogously, we define the set of weakly flattened Fubini rankings, which is the subset of Fubini rankings with runs of weak ascents whose leading terms are in weakly increasing order. Our main results give formulas for the enumeration of strictly flattened Fubini rankings and weakly flattened Fubini rankings. We also provide some conjectures for further study. † † footnotetext: 2020 Mathematics Subject Classification . Primary 05A05; Secondary 05A10, 05A15, 05A17, 05A18. † † footnotetext: Key words and phrases . Fubini ranking, flattened word, flattened Fubini ranking, content of a word 1. Introduction Let \mathbb{N} denote the set of positive integers and let [n]=\{1,2,\ldots,n\} whenever n\in\mathbb{N} . Throughout we let \mathfrak{S}_{n} denote the set of permutations which we write in one-line notation \pi=\pi_{1}\pi_{2}\cdots\pi_{n} . We recall that a set partition \beta of [n] is a collection of subsets (also called blocks) \beta_{1},\beta_{2},\ldots,\beta_{k} satisfying the conditions that \cup_{i=1}^{k}\beta_{i}=\beta and \beta_{i}\cap\beta_{j}=\emptyset for all i\neq j . In [ 5 ] , Callan studied the Mathematica Flatten function, which we denote by flat , whose input is an ordered set partition (where the order of the blocks matter) and returns a permutation by deleting the block notation and concatenating the numbers in a single row. For example, under the flatten operation, the set partition \Pi=1|36|524|8|79 will become \text{Flatten}(\Pi)=136524879. One way to uniquely order the blocks of a set partition is to order blocks by their minimal elements, and then order the elements within a block in increasing order. Whenever this ordering is implemented, the flattened function returns a permutation whose runs of ascents have the property that the leading terms of those runs are in increasing order. Using the previous example, we would reorder the blocks and elements in the blocks as \Pi=1|245|36|79|8 , which produces \text{Flatten}(\Pi)=124536798. A permutation with this property is often referred to as a flattened permutation or flattened partition [ 5 ] . Callan considered the set of flattened permutations which also avoid certain patterns of length three, whose enumerations involve powers of 2, Fibonacci numbers, Catalan numbers, and binomial transforms of Catalan numbers. Nabawanda, Rakotondrajao, Bamunoba [ 11 ] and Beyene, Mantaci [ 2 ] , independently gave formulas for the number of flattened permutations of length n with k runs. They showed multiple recursive identities, including f_{n,k}=\sum_{m=1}^{n-2}\left(\binom{n-1}{m}-1\right)f_{m,k-1}. This work has since been expanded to a subset of parking functions which consist of a permutation on the multiset \{1^{r+1},2,3,4,\ldots,n\} , where r+1 denotes the multiplicity of 1 [ 9 ] . Baril, Harris, and Ramírez studied flattened Catalan words and some related statistics [ 1 ] , and Buck, Elder, Figueroa, Harris, Harry, and Simpson studied flattened Stirling permutations [ 4 ] , giving enumerative formulas and bijections to other combinatorial objects such as type B set partitions. We consider the analogous problem of enumerating flattened Fubini rankings. We recall that a Fubini ranking of length n is a tuple r=(r_{1},r_{2},\ldots,r_{n})\in[n]^{n} that records a valid ranking over n competitors with ties allowed (i.e., multiple competitors can be tied and have the same rank). However, if k competitors are tied and rank i th, then the k-1 subsequent ranks i+1,i+2,\ldots,i+k-1 are disallowed. We let \mathrm{\mathrm{FR}}_{n} denote the set of all Fubini rankings on n competitors and let \mathrm{fr}_{n}=|\mathrm{\mathrm{FR}}_{n}| denote its cardinality. If n=3 , then \mathrm{\mathrm{FR}}_{3}=\left\{\begin{matrix}(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1),\\ (1,1,1),(1,1,3),(1,3,1),(3,1,1),(1,2,2),(2,1,2),(2,2,1),\end{matrix}\right\} and \mathrm{fr}_{3}=13 . It was shown by Cayley [ 6 ] that the number of Fubini rankings is given by the n th Fubini number [ 12 , A000670 ] \mathrm{fr}_{n}=\sum_{{k=0}}^{n}\sum_{{j=0}}^{k}(-1)^{{k-j}}{\binom{k}{j}}j^{n}. We remark that Fubini rankings have received recent attention in the literature due to their connection to parking functions. Harris and Haddaway established that Fubini rankings are in bijection with unit interval parking functions, see [ 10 ] , thereby establishing that the number of unit interval parking functions is also a Fubini number. Utilizing the connection between unit interval parking functions and Fubini rankings, Brandt, Elder, Harris, Rojas Kirby, Reutercrona, Wang, and Whidden [ 3 ] gave an identity for the Fubini numbers as a sum of multinomials over compositions. They also considered a generalization of Fubini rankings, called the r -Fubini rankings of length n+r , whose first r values are distinct. Their main result established a bijection between r -Fubini rankings and unit interval parking functions of length n+r where the first r cars have distinct preferences. This showed that those parking functions are also enumerated by the r -Fubini numbers. In other work, Elder, Harris, Kretschmann, and Martìnez Mori [ 8 ] studied the subset of Fubini rankings called unit Fubini rankings , which satisfy that at most two competitors tie for any single rank. A main contribution of Elder, Harris, Kretschman, and Martínez Mori [ 8 ] , established that the unit Fubini rankings with exactly n-k distinct ranks are in bijection with Boolean intervals of rank k in the weak (Bruhat) order of the symmetric group \mathfrak{S}_{n} . In our work, we consider the natural question lying at the intersection of these themes: How many Fubini rankings on n competitors are flattened? Given that Fubini rankings are a super set of the set of permutations, we first note that defining a word to be flattened requires two inequality conditions: a condition on the definition of the runs as strict ascents or weak ascents, and a condition on the leading terms to either be strictly increasing or weakly increasing. We follow the definitions in [ 9 ] , and define weakly flattened Fubini rankings with runs of weak ascents to be a Fubini ranking with runs of weak ascents and whose leading terms are in weakly increasing order. For example, (1,3,3,1) is a weakly flattened Fubini ranking with runs of weak ascents that contains two runs: 1,3,3 and 1 . The run 1,3,3 is allowed because we are dealing with runs of weak ascents and the two runs are allowed to both begin with 1 because the leading terms are required to be in weakly increasing order. We also define flattened Fubini rankings with runs of ascents , which are Fubini rankings whose runs are made of strict ascents and whose leading terms are in strictly increasing order. For example, (1,2,2,4) contains two runs of (strict) ascents, 1,2 and 2,4 , whose leading terms are in (strictly) increasing order. Note that in this way all strictly flattened Fubini rankings are weakly flattened, but the converse is not true. For the rest of this paper, if the flattness condition or the runs are not specified

Read the complete text