# Lexicographic unranking algorithms for the Twentyfold Way

Amaury Curiel, Antoine Genitrini

<figure><img src="image_1.png" /></figure>

To cite this version:

Amaury Curiel, Antoine Genitrini. Lexicographic unranking algorithms for the Twentyfold Way. 2026. [hal-05486059]

HAL Id: hal-05486059

https://hal.science/hal-05486059v1

Preprint submitted on 30 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Lexicographic unranking algorithms for the Twentyfold Way

Amaury Curiel

Antoine Genitrini

Submitted: 2026; Accepted: ; Published:

© The authors. Released under the CC BY-ND license (International 4.0).

## Abstract

The Twelvefold Way, introduced by Rota, provides a fundamental framework for classifying and counting functions between finite sets. While counting formulas for these cases are well-established, efficient lexicographic unranking algorithms (which map an integer to its corresponding combinatorial structure) remain missing for several key cases, most notably those related to set partitions. In this paper, we extend the study of combinatorial generation to the Twentyfold Way, a broader classification that incorporates more complex combinatorial objects. Our primary contribution is the development of the first lexicographic unranking algorithms for the cases that had previously remained unaddressed, specifically set partitions and their ordered counterparts. The core of our approach lies in the derivation of new counting formulas based on shared prefixes. By decomposing the combinatorial space according to lexicographical prefixes, we establish a direct bridge between recursive counting and unranking. We further provide efficient algorithmic implementations capable of handling the very large integers inherent in these problems. Our complexity analysis and experimental results demonstrate that these algorithms offer a robust and efficient solution for unranking and uniform random generation.

**Mathematics Subject Classifications:** 05A17, 05A18, 05A19

**Keywords:** Twelvefold Way, Twentyfold Way, Thirtyfold Way, Unranking, Combinatorial generation, Lexicographic order.

<footnote>Sorbonne Université, CNRS, LIP6 - UMR 7606 (Amaury.Curiel@lip6.fr, Antoine.Genitrini@lip6.fr).</footnote>
# 1 Introduction

In the 1960s, Rota sought to classify the simplest combinatorial objects and to link each of these classes to explicit counting formulas. This systematic approach culminated in the Twelvefold Way, a unifying framework for the most fundamental enumeration problems. Generating these objects systematically is central to applying this framework. Lexicographical ordering is the primary method for translating abstract counting into concrete sequences.

These simple objects serve as the foundational building blocks for numerous combinatorial models; consequently, mastering their generation is essential for analyzing complex systems and conducting accurate simulations. The transition from mere counting to generation, especially random generation, necessitates a formal organization of the combinatorial space. To pick an object at random from a set of billions of billions, one must ensure that every element is reachable and that none are over-represented. This leads to the fundamental requirement of ordering structures.

As Nijenhuis and Wilf establish in their work on combinatorial algorithms [17], uniform random generation is possibly achieved through a bijection between the set of objects and an interval of the first integers. Assigning an integer to an object automatically induces a total order on the combinatorial set. Without such an underlying order, randomness remains a heuristic process with no mathematical guarantee of completeness or uniformity.

Once the necessity of an order is established, the lexicographical order emerges as an interesting candidate for several reasons. In the context of recursive decompositions, Knuth [11] demonstrates that most combinatorial objects are defined by a sequence of choices (e.g., *does this item go into box A or B?*). The lexicographical order is simply the natural unfolding of these choices in a decision tree. From a computational efficiency perspective, unlike Gray codes (essentially where only one building atom changes from one object to the next one), the lexicographical order allows for divide-and-conquer strategies. It enables us to skip large blocks of the search space or to target a specific lexicographical rank efficiently using combinatorial numbering systems. The process of mapping an integer to its corresponding combinatorial object is known as *unranking*.

Flajolet and Sedgewick, in Analytic Combinatorics [8], view combinatorial classes as languages. Just as words in a language are naturally sorted in a dictionary, combinatorial objects are naturally sorted by their construction rules. They argue that the systematic ordering of structures is a prerequisite for any symbolic analysis. Hence, generating at random amounts to navigating an ordered tree where the lexicographical path defines the object's identity.

In [5], we cataloged all known lexicographic unranking algorithms for the structures described in the Twelvefold Way, to unify fundamental sampling problems and their associated counting formulas. However, to the best of our knowledge, lexicographic unranking algorithms for the three problems related to set partitions remained conspicuously absent from the literature. Existing unranking algorithms for set partitions are typically lexicographic with respect to restricted growth sequences [13, 21]. While these sequences are in bijection with set partitions, the bijection does not preserve lexicographic order over the
combinatorial objects.

In this paper, corresponding to a largely extended version of [5], we introduce such algorithms for all structures within an extension of the Twelvefold Way: the Twentyfold Way, proposed by Bogart in 2004 [3]. While Rota's framework classifies functions from an n-set to a k-set based on distinguishability and mappings constraints (injective, surjective, or arbitrary), Bogart shifts the perspective to the allocation of k objects to n recipients. This broader framework accounts for the distinguishability of both objects and recipients, the nature of the recipients (viewed as boxes or queues), and the constraints on occupancy. Rota's Twelvefold Way is a subset of Bogart's Twentyfold Way; the latter adds four cases where each recipient may receive exactly one object (effectively bijections) and four cases where the internal order of elements within each recipient matters. These latter cases describe ordered set partitions, where the sequence of elements within each block is significant. Specifically, problems 5.a, 5.b, 6.a, and 6.b in Table 1 are the ordered counterparts to problems 1, 7, 3, and 9 of the Twelvefold Way, with their counting formulas expressed via Lah numbers [20].

<table><caption>Table 1: The Twentyfold Way by Bogart*</caption><thead><tr><th rowspan="2">k objects and conditions on how they are received</th><th colspan="2">n recipients and mathematical model for distribution</th></tr><tr><th>a. Distinct</th><th>b. Identical</th></tr></thead><tbody><tr><td>1. Distinct<br>no conditions</td><td>n<sup>k</sup><br>functions</td><td>&Sigma;<sup>n</sup><sub>i=1</sub> {{k<sub>i</sub>}</sub><br>Bell partitions</td></tr><tr><td>2. Distinct<br>Each gets at most one</td><td>n<sup>k</sup><br>n-permutations</td><td>[k &le; n]<br>1,2,...,k</td></tr><tr><td>3. Distinct<br>Each gets at least one</td><td>n!{{k<sub>n</sub>}</sub><br>ordered Stirling partitions</td><td>{k<sub>n</sub>}</sub><br>Stirling partitions</td></tr><tr><td>4. Distinct<br>Each gets exactly one</td><td>k![n = k]<br>bijective functions</td><td>[k = n]<br>1,2,...,k</td></tr><tr><td>5. Distinct<br>order matters</td><td>(k + n - 1)<sup>k</sup><br>ordered Lah partitions with empty blocks</td><td>&Sigma;<sup>n</sup><sub>i=1</sub> [k<sub>i</sub>]<br>Lah partitions in &le; n parts</td></tr><tr><td>6. Distinct<br>order matters, each gets at least one</td><td>k! &middot; [k<sub>n</sub>]<br>ordered Lah partitions</td><td>[k<sub>n</sub>]<br>Lah partitions</td></tr><tr><td>7. Identical<br>no conditions</td><td>(n+k-1)<sub>k</sub><br>multisets</td><td>&Sigma;<sup>n</sup><sub>i=1</sub> p(k, i)<br>partitions of k into &le; n parts</td></tr><tr><td>8. Identical<br>Each gets at most one</td><td>(n)<sub>k</sub><br>subsets</td><td>[k &le; n]<br>1,1,...,1</td></tr><tr><td>9. Identical<br>Each gets at least one</td><td>(k-1)<sub>n-1</sub><br>compositions of k</td><td>p(k, n)<br>partitions of k</td></tr><tr><td>10. Identical<br>Each gets exactly one</td><td>[k = n]<br>1,1,...,1</td><td>[k = n]<br>1,1,...,1</td></tr></tbody></table>

The challenge of unranking combinatorial objects is a cornerstone of combinatorial generation [23], with applications spanning software testing [16], deep neural network compression [22], video compression [24], cryptography [6], and complex structural modeling in phylogenetics [2] and bioinformatics [1]. Crucially, any unranking procedure, and

<footnote>* The notation $k^n$ corresponds to the product $k \cdot (k-1) \cdots (k-n+1)$; $[p]$ is the Iverson bracket returning 1 when the predicate $p$ is true and 0 otherwise; $\{\cdot\}$, $(\cdot)$ and $[\cdot]$ stand respectively for the Stirling numbers of the second kind, binomial coefficients and Lah numbers; and $p_k(n)$ is the number of integer partitions of $n$ into $k$ positive integers.</footnote>
by extension, any uniform random generation, requires the establishment of a total order
over the object set. The lexicographic order is the most widely utilized due to its intuitive
nature and alignment with recursive definitions, however, as Ruskey points out [21, p.
59], lexicographic generation is often not the most computationally efficient, necessitating
sophisticated algorithmic care during the unranking process.

Typically, constructing structures through a recursive decomposition schema involves
leveraging the structural definition to build larger objects from smaller sub-components.
In this work, we apply these principles to bridge the gap for Lah partitions and their
lexicographical representations.

**Main results.** To develop an efficient unranking generator for set partitions, we first establish a lexicographic order over collections of integers. This requires particular care, as these collections are inherently unordered. To address this, we define a canonical representation based on a standard normalized string of integers, ensuring a unique and consistent ordering. We then introduce a decomposition grounded in new counting formulas, which leads directly to efficient lexicographic unranking algorithms. All the proofs we provide for counting structures sharing a given prefix are based on combinatorial interpretations, giving clear intuition behind the formulas, and helping to establish the correctness of the unranking algorithms.

Given that the algorithms must handle very large integers, we pay specific attention
to the computational overhead of high-precision arithmetic and the efficient delivery of
these values within the generation process. The correctness and complexity of our ap-
proach are established through specific combinatorial properties derived throughout this
study. Finally, we provide empirical results by evaluating several implementations of our
algorithm, comparing their performance against existing state-of-the-art methods, which
often rely on alternative combinatorial orderings when a direct lexicographical approach
is unavailable.

**Organization of the paper.** The remainder of this paper is organized as follows. Section 2 establishes the theoretical foundation by formally defining the Twentyfold Way framework, expanding upon Rota's classical Twelvefold Way. We introduce the necessary combinatorial structures, notably the ordered set partitions and their connection to Lah numbers. Section 3 is dedicated to the core of our contribution: the development of lexicographical unranking algorithms. We first define the canonical representation for unordered collections of integers to impose a total order. Then, we derive the recursive counting formulas that underpin our decomposition schema, specifically tailored for set partitions and their ordered counterparts. We then address the algorithmic implementation details. We discuss the challenges associated with the manipulation of large integers of order present the complexity analysis of our approach. Then we provide experimental results comparing our lexicographical unranking generators with existing state-of-the-art methods that rely on alternative combinatorial orderings.
# 2 Preliminaries

## 2.1 Basic combinatorial concepts

We first provide three generic definitions to define collections of elements with different properties regarding order and repetition. They are classical in the context of combinatorial structures.

**Definition 1.** We say that a collection $\mathcal{C}$ is a set of elements if $\mathcal{C}$ is an unordered collection of distinct elements. We denote by $\mathbf{set}_p$ such a collection satisfying the cardinality constraint expressed by the property $p$.

**Definition 2.** We say that a collection $\mathcal{C}$ is a sequence of elements if $\mathcal{C}$ is an ordered collection of elements where repetitions are allowed. We denote by $\mathbf{sequence}_p$ such a collection satisfying the cardinality constraint expressed by the property $p$.

**Definition 3.** We say that a collection $\mathcal{C}$ is a multiset of elements if $\mathcal{C}$ is an unordered collection of elements where repetitions are allowed. We denote by $\mathbf{MSet}_p$ such a collection satisfying the cardinality constraint expressed by the property $p$.

## 2.2 From Stirling partitions to ordered Lah partitions

**Definition 4.** Let $\mathcal{N}$ be a set of $n$ distinguishable elements. A Stirling partition $\pi$ of $\mathcal{N}$ in $k$ blocks is a set $\{B_1, B_2, \dots, B_k\}$ of disjoint non-empty subsets of $\mathcal{N}$ such that every element from $\mathcal{N}$ belongs to exactly one $B_i$, for $i \in \{1, \dots, k\}$. In the rest of the paper, we will denote by block the elements of $\pi$.

As an example let $\mathcal{N}$ be the set of elements $\{1, \alpha, 2, 3, 4, \beta, 6, 12\}$. The collection $\{\{2, 3\}, \{4, 6, 12\}, \{\beta, 1, \alpha\}\}$ is a partition of $\mathcal{N}$ in 3 blocks.

**Notation 1.** Let $\mathcal{N}$ be a set of $n$ distinguishable elements. All along this paper, we will denote by $k$-partition of $\mathcal{N}$ a partition of $\mathcal{N}$ into exactly $k$ blocks. The context will make clear if we are considering Stirling partitions, or other kinds of partition we will define later on. Furthermore, since the set $\mathcal{N}$ will always be countable, we assume without loss of generality that $\mathcal{N} = \lfloor n \rfloor$, i.e. the subset of consecutive integers from 1 to $n$.

For example $\{\{1\}, \{2, 3, 5\}, \{4, 6\}\}$ is a Stirling 3-partition of $\lfloor 6 \rfloor$.

**Proposition 5.** A Stirling partition in $k$ blocks is as an instance of

$$ \mathit{set}_k(\mathit{set}_{\ge 1}(\mathit{Integer})). $$

**Notation 2.** Let $1 \le k \le n$ be two positive integers. The set of Stirling $k$-partitions of $\lfloor n \rfloor$ is denoted by $\mathcal{P}_k^n$.

**Fact 6.** Let $1 \le k \le n$ be two positive integers. The number of partitions in $\mathcal{P}_k^n$ is the Stirling number of the second kind denoted by $\begin{Bmatrix} n \\ k \end{Bmatrix}$. It satisfies the following recurrence:

$$ \begin{Bmatrix} n \\ k \end{Bmatrix} = \begin{cases} 1 & \text{when } k = 1 \text{ or } k = n; \\ \begin{Bmatrix} n-1 \\ k-1 \end{Bmatrix} + k \cdot \begin{Bmatrix} n-1 \\ k \end{Bmatrix} & \text{otherwise, i.e. when } 1 < k < n. \end{cases} \quad (1) $$
Proof. Let $1 \le k \le n$ be two positive integers. Let us introduce a combinatorial interpretation of the formulas.

* If $k = 1$ or $k = n$, then there is only one way to partition the set: either all elements are in one block (if $k = 1$) or each element is in its own block (if $k = n$). Thus, in these cases, we have $\binom{n}{k} = 1$.

* Otherwise, when $1 < k < n$, to build a $k$-partition of $\lfloor n \rfloor$, we can either:

- Build a $(k-1)$-partition of $\lfloor n-1 \rfloor$ and add $n$ as a new block. In this case, there are as much possibilities as the number of $(k-1)$-partition of $\lfloor n-1 \rfloor$.

- Build a $k$-partition of $\lfloor n-1 \rfloor$ and add $n$ to one of the existing blocks. In this case, there are $k$ possibilities for the block to which $n$ is added multiplied by the number of $k$-partitions of $\lfloor n-1 \rfloor$.

The later two disjoint cases naturally lead to the recurrence relation $\binom{n}{k} = \binom{n-1}{k-1} + k \cdot \binom{n-1}{k}$, concluding the proof. $\square$

This sequence is stored in OEIS A008277¹ and the following table shows the first values of $\binom{n}{k}$:

<table><thead><tr><th>k<br>n</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th></tr></thead><tbody><tr><th>1</th><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>2</th><td>1</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>3</th><td>1</td><td>3</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>4</th><td>1</td><td>7</td><td>6</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>5</th><td>1</td><td>15</td><td>25</td><td>10</td><td>1</td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>6</th><td>1</td><td>31</td><td>90</td><td>65</td><td>15</td><td>1</td><td></td><td></td><td></td><td></td></tr><tr><th>7</th><td>1</td><td>63</td><td>301</td><td>350</td><td>140</td><td>21</td><td>1</td><td></td><td></td><td></td></tr><tr><th>8</th><td>1</td><td>127</td><td>966</td><td>1701</td><td>1050</td><td>266</td><td>28</td><td>1</td><td></td><td></td></tr><tr><th>9</th><td>1</td><td>255</td><td>3025</td><td>7770</td><td>6951</td><td>2646</td><td>462</td><td>36</td><td>1</td><td></td></tr><tr><th>10</th><td>1</td><td>511</td><td>9330</td><td>34105</td><td>42525</td><td>22827</td><td>5880</td><td>750</td><td>45</td><td>1</td></tr></tbody></table>

**Fact 7.** Let $1 \le n$ be a positive integer. The sequence $(\binom{n}{k})_{1 \le k \le n}$ is unimodal and its maximum is reached when $k = k_n \sim n/\ln n$. Around this value, we have $2^2 \log \binom{n}{k_n} = \Theta(n \log n)$. Furthermore, we have an upper bound valid for all $1 \le k \le n$:

$$ \log \binom{n}{k} \le (n-k) \log k + \log \binom{n}{k} \le (n-k) \log k + k \log \left( \frac{n \cdot e}{k} \right). $$

<footnote n="1">¹OEIS stands for the On-line Encyclopedia of Integer Sequences.</footnote>

<footnote n="2">²In this paper we use the notation log for the logarithm in basis 2.</footnote>
See the fundamental paper of Rennie and Dobson [19] to get a proof for these results.
The next structures that we are interested in are the ordered Stirling partitions. An ordered Stirling partition is a Stirling partition where the blocks are ordered. Formally, we define it as follows:

**Definition 8.** Let $\mathcal{N}$ be a set of $n$ distinguishable elements. An ordered Stirling partition $\pi$ of $\mathcal{N}$ in $k$ blocks is a sequence $(B_1, B_2, \dots, B_k)$ of disjoint non-empty subsets of $\mathcal{N}$ such that every element from $\mathcal{N}$ belongs to exactly one $B_i$, for $i \in \{1, \dots, k\}$.

**Proposition 9.** An ordered Stirling partition in $k$ blocks is an instance of

$$ sequence_k(\text{set}_{\ge 1}(\text{Integer})). $$

**Notation 3.** Let $1 \le k \le n$ be two positive integers. The set of ordered Stirling $k$-partitions of $\mathcal{N}$ is denoted by $O_k^n$.

**Fact 10.** Let $1 \le k \le n$ be two positive integers. The number of ordered Stirling partitions in $O_k^n$ is the ordered Stirling number of the second kind which is denoted by $O_k^n$. It satisfies the following recurrence:

$$ O_k^n = k! \cdot \begin{Bmatrix} n \\ k \end{Bmatrix} = \begin{cases} k! & \text{when } k = 1 \text{ or } k = n; \\ k \cdot (O_{k-1}^{n-1} + O_k^{n-1}) & \text{otherwise, i.e. when } 1 < k < n. \end{cases} \quad (2) $$

*Proof.* Let $1 \le k \le n$ be two positive integers. Let us introduce a combinatorial interpretation of the formulas.

* If $k = 1$, then all elements are in one block, and there is a single ordered Stirling partition.

* If $k = n$, then each element is in its own block, and every permutation of these $k$ blocks represent a different partition; thus, there are $k!$ such partitions.

* Otherwise, when $1 < k < n$, to build a $k$-partition of $\llbracket n \rrbracket$, we can either:

- Build a $(k-1)$-partition of $\llbracket n-1 \rrbracket$ and add $n$ as a new block. In this case, there are as much possibilities as the number of $(k-1)$-partitions of $\llbracket n-1 \rrbracket$ multiplied by $k$ since we can add the new block in any of the $k$ possible positions.

- Build a $k$-partition of $\llbracket n-1 \rrbracket$ and add $n$ to one of the existing blocks. In this case, there are as much possibilities as the number of $k$-partitions multiplied by $k$ possibilities for the block to which $n$ is added.

The later two disjoint cases naturally lead to the recurrence relation $O_k^n = k \cdot (O_{k-1}^{n-1} + O_k^{n-1})$, concluding the proof.

<figure><img src="image_3.png" /></figure>

This sequence is stored in OEIS A131689 and the following table shows the first values of $O_k^n$:
<table><thead><tr><th>k<br>n</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th></tr></thead><tbody><tr><th>1</th><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>2</th><td>1</td><td>2</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>3</th><td>1</td><td>6</td><td>6</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>4</th><td>1</td><td>14</td><td>36</td><td>24</td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>5</th><td>1</td><td>30</td><td>150</td><td>240</td><td>120</td><td></td><td></td><td></td><td></td></tr><tr><th>6</th><td>1</td><td>62</td><td>540</td><td>1560</td><td>1800</td><td>720</td><td></td><td></td><td></td></tr><tr><th>7</th><td>1</td><td>126</td><td>1806</td><td>8400</td><td>16800</td><td>15120</td><td>5040</td><td></td><td></td></tr><tr><th>8</th><td>1</td><td>254</td><td>5796</td><td>40824</td><td>126000</td><td>191520</td><td>141120</td><td>40320</td><td></td></tr><tr><th>9</th><td>1</td><td>510</td><td>18150</td><td>186480</td><td>834120</td><td>1905120</td><td>2328480</td><td>1451520</td><td>362880</td></tr></tbody></table>

**Fact 11.** Let $1 \le n$ be a positive integer. The sequence $(O_k^n)_{1 \le k \le n}$ is unimodal, its maximum is reached when $k = k_n \sim \frac{n}{2\ln(2)}$. Around this value, we calculate that $\log O_{k_n}^n \sim \Theta(n \log(n))$, and, the following upper bound is valid for all $1 \le k \le n$:

$$ \log O_k^n \le (n-k) \log k + \log \binom{n}{k} + \log(k!). $$

*Proof.* The proof for unimodality and the modes of the ordered Stirling numbers can be found in [15]. Furthermore, we have that

$$ \log \binom{n}{k} \le (n-k) \log k + \log \binom{n}{k}, $$

and we directly deduce the stated upper bound. By applying $k = k_n = \frac{n}{2\ln(2)}$, we get $\log O_{k_n}^n = \Theta(n \log(n))$. $\square$

**Definition 12.** Let $\mathcal{N}$ be a set of $n$ distinguishable elements. A Lah partition of $\mathcal{N}$ in $k$ blocks is a set $\{B_1, B_2, \dots, B_k\}$ of disjoint non-empty sequences of elements of $\mathcal{N}$ such that every element from $\mathcal{N}$ belongs to exactly one $B_i$, for $i \in \{1, \dots, k\}$.

**Proposition 13.** A Lah partition in $k$ blocks is an instance of

$$ \text{set}_k(\text{sequence}_{\ge 1}(\text{Integer})). $$

*Notation 4.* Let $1 \le k \le n$ be two positive integers. The set of Lah partitions of $\llbracket n \rrbracket$ is denoted by $\mathcal{L}_k^n$.

**Fact 14.** Let $1 \le k \le n$ be two positive integers. The number of Lah partitions in $\mathcal{L}_k^n$ is the Lah number denoted by $\lfloor n \rfloor$. It satisfies the following recurrence:

$$ \lfloor n \rfloor = \begin{cases} n! & \text{when } k=1; \\ 1 & \text{when } k=n; \\ \lfloor n-1 \rfloor + (n-1+k) \cdot \lfloor n-1 \rfloor & \text{otherwise, i.e. when } 1 < k < n. \end{cases} \quad (3) $$
Proof. Let $1 \le k \le n$ be two positive integers.

* If $k = 1$, then all elements are in one block, and there are as many possibilities to arrange them as there are $n$-permutations; thus, there are $n!$ such partitions.

* If $k = n$, then each element is in its own block, and every arrangement of these blocks represent the same partition; thus, there is only one such partition.

* Finally, in the other cases, we can either:

- Build a $(k-1)$-partition of $\lfloor n-1 \rfloor$ and add $n$ as a new block. In this case, there are as much possibilities as the number of $(k-1)$-partitions of $\lfloor n-1 \rfloor$.

- Build a $k$-partition of $\lfloor n-1 \rfloor$ and add $n$ to one of the existing blocks. In this case, we insert $n$ in any of the $k$ blocks after any of the existing elements or at the beginning of the block. Thus, there are $n-1+k$ possibilities to add $n$ to one of the existing blocks and as much possibilities as the number of $k$-partitions of $\lfloor n-1 \rfloor$ for choosing the partition to which we add $n$.

The later two disjoint cases naturally lead to the recurrence relation $\lfloor n \rfloor = \lfloor n-1 \rfloor + (n-1+k) \cdot \lfloor n-1 \rfloor$, concluding the proof. $\square$

This sequence is stored in OEIS A271703 and the following table shows the first values of $\lfloor n \rfloor$:

<table><thead><tr><th>k<br>n</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th></tr></thead><tbody><tr><th>1</th><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>2</th><td>2</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>3</th><td>6</td><td>6</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>4</th><td>24</td><td>36</td><td>12</td><td>1</td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>5</th><td>120</td><td>240</td><td>120</td><td>20</td><td>1</td><td></td><td></td><td></td><td></td></tr><tr><th>6</th><td>720</td><td>1800</td><td>1200</td><td>300</td><td>30</td><td>1</td><td></td><td></td><td></td></tr><tr><th>7</th><td>5040</td><td>15120</td><td>12600</td><td>4200</td><td>630</td><td>42</td><td>1</td><td></td><td></td></tr><tr><th>8</th><td>40320</td><td>141120</td><td>141120</td><td>58800</td><td>11760</td><td>1176</td><td>56</td><td>1</td><td></td></tr><tr><th>9</th><td>362880</td><td>1451520</td><td>1693440</td><td>846720</td><td>211680</td><td>28224</td><td>2016</td><td>72</td><td>1</td></tr></tbody></table>

**Fact 15.** Let $1 \le n$ be a positive integer. The sequence $(\lfloor n \rfloor)_{1 \le k \le n}$ is unimodal and its maximum is reached when

$$k = k_n = \begin{cases} \sqrt{n+1}-1 & \text{and } \sqrt{n+1} & \text{ if } n+1 \text{ is a perfect square, i.e. } \exists \tilde{n} \mid n+1 = \tilde{n}^2; \\ \lfloor \sqrt{n+1} \rfloor & & \text{otherwise.} \end{cases}$$

Around this value, we have $\log \lfloor n \rfloor_{k_n} \sim \Theta(n \log n)$. Furthermore, we have an asymptotic equivalence valid for all $1 \le k < n$:

$$\log \lfloor n \rfloor_{k_n} = 2n \log n - (n-k) \log(n-k) - 2k \log(k) - O(n-k).$$
*Proof.* The proofs for unimodality and for the modes of the Lah numbers are given in [18]. Furthermore, an other form of $\lfloor n \rfloor$ is given by $\lfloor n \rfloor = \frac{n!(n-1)!}{k!(n-k)!(k-1)!}$. By applying Stirling asymptotic formula for factorials, we get the stated asymptotic equivalence for $k = f(n)$ with $f$ any strictly growing function. If $k = O(1)$, the result is straightforward. $\square$

**Definition 16.** Let $\mathcal{N}$ be a set of $n$ distinguishable elements. An ordered Lah partition of $\mathcal{N}$ in $k$ blocks is a sequence $(B_1, B_2, \dots, B_k)$ of disjoint non-empty sequences of elements of $\mathcal{N}$ such that every element from $\mathcal{N}$ belongs to exactly one $B_i$, for $i \in \{1, \dots, k\}$.

**Proposition 17.** An ordered Lah partition in $k$ blocks is an instance of

$$ sequence_k(sequence_{\ge 1}(Integer)). $$

*Notation 5.* Let $1 \le k \le n$ be two positive integers. The set of ordered Lah partitions of $\mathcal{N}$ is denoted by $Q_k^n$.

**Proposition 18.** Let $1 \le k \le n$ be two integers. The number of ordered Lah partitions in $Q_k^n$ is the ordered Lah number denoted by $\lfloor n \rfloor$. It satisfies the following recurrence:

$$ \begin{bmatrix} n \\ k \end{bmatrix} = \begin{cases} n! & \text{if } k = n \text{ or } k = 1. \\ k \cdot \begin{bmatrix} n-1 \\ k-1 \end{bmatrix} + (n-1+k) \cdot \begin{bmatrix} n-1 \\ k \end{bmatrix} & \text{otherwise, i.e. when } 1 < k < n. \end{cases} \quad (4) $$

*Proof.* Let $1 \le k \le n$ be two positive integers.

* If $k = 1$, then the interpretation is the same as for Lah partitions.

* If $k = n$, then each element is in its own block, and every permutation of these blocks represent a different partition; thus, there are $n!$ such partitions.

* Finally, in the other cases, we can either:

- Build a $(k-1)$-partition of $\lfloor n-1 \rfloor$ and add $n$ as a new block. In this case, as for ordered Stirling partitions, we add $n$ as a new block but in this case, we need to choose among the $k$ possible positions for this new block.

- Build a $k$-partition of $\lfloor n-1 \rfloor$ and add $n$ to one of the existing blocks. In this case, we insert $n$ in any of the $k$ blocks after any of the existing elements or at the beginning of the block. Thus, there are $n-1+k$ possibilities to add $n$ to one of the existing blocks.

The later two disjoint cases naturally lead to the recurrence relation $\begin{bmatrix} n \\ k \end{bmatrix} = k \cdot \begin{bmatrix} n-1 \\ k-1 \end{bmatrix} + (n-1+k) \cdot \begin{bmatrix} n-1 \\ k \end{bmatrix}$, concluding the proof. $\square$

This sequence seems not be stored in the OEIS. The following table shows the first values of $\begin{bmatrix} n \\ k \end{bmatrix}$:
<table><thead><tr><th>k<br>n</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th></tr></thead><tbody><tr><th>1</th><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>2</th><td>2</td><td>2</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>3</th><td>6</td><td>12</td><td>6</td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>4</th><td>24</td><td>72</td><td>72</td><td>24</td><td></td><td></td><td></td><td></td></tr><tr><th>5</th><td>120</td><td>480</td><td>720</td><td>480</td><td>120</td><td></td><td></td><td></td></tr><tr><th>6</th><td>720</td><td>3600</td><td>7200</td><td>7200</td><td>3600</td><td>720</td><td></td><td></td></tr><tr><th>7</th><td>5040</td><td>30240</td><td>75600</td><td>100800</td><td>75600</td><td>30240</td><td>5040</td><td></td></tr><tr><th>8</th><td>40320</td><td>282240</td><td>846720</td><td>1411200</td><td>1411200</td><td>846720</td><td>282240</td><td>40320</td></tr></tbody></table>

**Proposition 19.** Let $1 \le n$ be a positive integer. The sequence $\begin{bmatrix} n \\ k \end{bmatrix}_{1 \le k \le n}$ is unimodal. Furthermore, if $n$ is even, then the maximum is reached at $k = k_n = \lfloor \frac{n+1}{2} \rfloor$ and at $k = k'_n = \lfloor \frac{n+1}{2} \rfloor + 1$ while if $n$ is odd, then the maximum is reached at $k = k_n = \frac{n+1}{2}$. Around this value, we have $\log \begin{bmatrix} n \\ k_n \end{bmatrix} = \Theta(n \log n)$. Furthermore, we have an asymptotic equivalence valid for all $n$ and $k$ satisfying $1 \le k \le n$:

$$ \log \begin{bmatrix} n \\ k \end{bmatrix} \underset{n \to \infty}{=} 2n \ln(n) - (n-k) \ln(n-k) - k \ln(k) - O(n). $$

*Proof.* Let $f$ be the function defined on $\mathbb{R}_+^* \times [1, n]$ by

$$ f(n, k) = \frac{n^{n+\frac{1}{2}} \left(\frac{1}{e}\right)^{2n-k} (k-1)^{\frac{1}{2}-k} (n-1)^{n-\frac{1}{2}} \left(\frac{n-k}{e}\right)^{k-n}}{\sqrt{n-k}}. $$

The study of the variation of $f(n, k)$ with respect to $k$ gives that $\partial_k f(n, k) = 0$ if and only if $k = \frac{n+1}{2}$.

Thus the unique critical point of $f(n, k)$ is at $k = \frac{n+1}{2}$. Furthermore, by applying Stirling asymptotic formula for factorials, we get $\begin{bmatrix} n \\ k \end{bmatrix} \underset{n \to \infty}{\sim} f(n, k)$. $\square$

## 2.3 Extension to integer partitions

We now turn to integer partitions, another class of partitions central to this paper. While set partitions distribute the elements of a set into disjoint subcollections, integer partitions decompose an integer into positive parts and group them into subcollections. We consider partitions of an integer $n$ into exactly $k \ge 1$ parts.

**Definition 20.** Let $1 \le k \le n$ be two positive integers. A partition of $n$ into $k$ parts is a set $\{\alpha_1, \dots, \alpha_k\}$ of strictly positive integers summing to $n$.

**Proposition 21.** An integer partition in $k$ blocks is an instance of

$$ MSet_k(\mathbf{Integer}). $$

*Notation 6.* Let $1 \le k \le n$ be two positive integers. The set of partitions of $n$ into $k$ parts is denoted by $\mathcal{P}_k^n$.
**Proposition 22.** Let $0 \le k \le n$ be two positive integers. The number of partitions in $\mathcal{P}_k^n$ is denoted by $p(n, k)$. We have

$$p(n, k) = \begin{cases} 0 & \text{if } n < 1; \\ 1 & \text{if } n = k \text{ or } k = 1; \\ p(n-1, k-1) + p(n-k, k) & \text{otherwise, i.e. when } 1 < k < n. \end{cases}$$

*Proof.* Let $1 \le k \le n$ be two positive integers.

* If $n = k$ or $k = 1$, the only possible $k$-partition of $n$ is respectively $\{1, 1, \dots, 1\}$ or $\{n\}$. Thus, in these cases, we have $p(n, k) = 1$.

* Otherwise, if we want to build a $k$-partition of $n$, we can either:

- Build a $(k-1)$-partition of $n-1$ and add 1 as a new part. In this case, there are as much possibilities as the number of $(k-1)$-partitions of $n-1$.

- Build a $k$-partition of $n-k$ and add 1 to each of the existing part. In this case, there are as much possibilities as the number of $k$-partitions of $n-k$.

The later two disjoint cases naturally lead to the recurrence relation $p(n, k) = p(n-1, k-1) + p(n-k, k)$, concluding the proof. $\square$

This sequence is stored in OEIS A008284. The following table shows the first values of $p(n, k)$:

<table><thead><tr><th>k<br>n</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th></tr></thead><tbody><tr><th>1</th><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>2</th><td>1</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>3</th><td>1</td><td>1</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>4</th><td>1</td><td>2</td><td>1</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>5</th><td>1</td><td>2</td><td>2</td><td>1</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>6</th><td>1</td><td>3</td><td>3</td><td>2</td><td>1</td><td>1</td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>7</th><td>1</td><td>3</td><td>4</td><td>3</td><td>2</td><td>1</td><td>1</td><td></td><td></td><td></td><td></td></tr><tr><th>8</th><td>1</td><td>4</td><td>5</td><td>5</td><td>3</td><td>2</td><td>1</td><td>1</td><td></td><td></td><td></td></tr><tr><th>9</th><td>1</td><td>4</td><td>7</td><td>6</td><td>5</td><td>3</td><td>2</td><td>1</td><td>1</td><td></td><td></td></tr><tr><th>10</th><td>1</td><td>5</td><td>8</td><td>9</td><td>7</td><td>5</td><td>3</td><td>2</td><td>1</td><td>1</td><td></td></tr><tr><th>11</th><td>1</td><td>5</td><td>10</td><td>11</td><td>10</td><td>7</td><td>5</td><td>3</td><td>2</td><td>1</td><td>1</td></tr></tbody></table>

**Proposition 23.** Let $1 \le k \le n$ be two positive integers. The sequence $(p(n, k))_{1 \le k \le n}$ is unimodal and its maximum is reached when $k = k_n = \frac{\sqrt{6n}}{\pi} (\log(\frac{\sqrt{6n}}{\pi}) + O(1))$. Around this value, we have $\log p(n, k_n) = \Theta(\sqrt{n})$.

**Lemma 24.** Let $1 \le k \le n$ be two positive integers. Let $\mathcal{P}_{\le k}^n = \bigcup_{i=1}^k \mathcal{P}_i^n$ be the set of partitions of $n$ into at most $k$ parts. The set $\mathcal{P}_{\le k}^n$ is in one-to-one correspondence with the set $\mathcal{P}_k^{n+k}$.
*Proof.* Let $\alpha = \{\alpha_1, \alpha_2, \dots, \alpha_k\}$ and $\beta = \{\beta_1, \beta_2, \dots, \beta_k\}$ be two distinct partitions of $n$ into $k$ non negative parts given in increasing order (here we allow some parts equal to zero). Obviously, $\alpha$ and $\beta$ are two different partitions in $\mathcal{P}_{\le k}^n$ by removing all the parts equal 0. We denote by $i$ the smallest index such that $\alpha_i \ne \beta_i$.

Let us now consider the two partitions $\alpha' = \{\alpha_1 + 1, \alpha_2 + 1, \dots, \alpha_k + 1\}$ and $\beta' = \{\beta_1 + 1, \beta_2 + 1, \dots, \beta_k + 1\}$. Since $\alpha'_i \ne \beta'_i$, we get $\alpha' \ne \beta'$ partitions $\alpha'$ and $\beta'$ are two distinct integer partitions of $n+k$ in $k$ (positive) parts.

Conversely, the same reasoning is applied to show that any two different partitions in $\mathcal{P}_k^{n+k}$ can be bijectively transformed into two different partitions in $\mathcal{P}_{\le k}^n$ by removing 1 from each part. $\square$

*Proof of Proposition 23.* In [7], the authors prove that the sequence $(p(n, k))_{1 \le k \le n}$ is uni-modal and that its maximum is reached when $k = k_n = \frac{\sqrt{6n}}{\pi} \left( \log\left(\frac{\sqrt{6n}}{\pi}\right) + O(1) \right)$ by studying the ratio $\frac{p(n, \le k)}{p(n)}$ where $p(n, \le k) = \sum_{i=1}^k p(n, i)$ is the number of partitions of $n$ into at most $k$ parts. Using Lemma 24 in Theorem 1.1 of [7], we get that around $k_n$, the value $p(n, k_n) = \Theta(1/(n-k_n) \exp(\pi\sqrt{2(n-k_n)/3}))$. We thus get $\log p(n, k_n) = \Theta(\sqrt{n})$. $\square$

## 2.4 Canonical representation of partitions

Every object defined above is specified using the constructors **set**, **MSet** and **sequence**. However, the objects specified with the constructors **MSet** and **set** can be represented in several ways. For instance, the Lah partition $\{(3, 1), (2), (5, 4)\}$ can also be represented in 5 other different ways depending on the order of the blocks: $\{(2), (3, 1), (5, 4)\}$, $\{(2), (5, 4), (3, 1)\}$, $\{(5, 4), (2), (3, 1)\}$, $\{(5, 4), (3, 1), (2)\}$, $\{(3, 1), (5, 4), (2)\}$. In the following, we define a canonical representation for all the objects defined above. This canonical representation allows us to define a total order over such objects classes.

**Definition 25.** Let **CAN** be a function taking as input an object decomposable into **set**, **MSet** and **sequence** and returning a canonical representation of this object only using sequences. **CAN** is defined as follows:

* if the object is a terminal object then return the object;

* if the object is a sequence then apply **CAN** to each element of the sequence and return the concatenation of the results;

* if the object is a set or a multiset then apply **CAN** to each element of the set and return the sequence of the results sorted regarding their minimal element.

If an object $x$ satisfies $\text{CAN}(x) = x$, we say that $x$ is in canonical form. For Stirling partitions, the canonical form corresponds to the sequential form defined by Mansour in [13].

The context allows us to determine the type of object we are dealing with; in the remainder of this paper, we will represent the different objects in their canonical form while omitting the set-theoretic notations. Thus, the Stirling partition $\{{\{2, 5, 3\}}, \{1\}, \{4, 6\}}$ will be represented 1/235/46.
**Notation 7.** Let $A$ and $B$ be sequences of elements.

• We denote by $|A|$ the length of $A$.

• We denote by $A_i$ the $i^{th}$ element of $A$.

• We denote by $A.B$ the concatenation of $A$ and $B$. By abuse of notation, $A.b$ is the concatenation of $A$ with the element $b$.

• Let $a, b \in \mathbb{N}$ satisfying $a < b$. We denote by $A.[[a, b]]$ the set of sequences obtained by appending an element $x$ to $A$ for all $x \in [[a, b]]$.

**Definition 26.** We say that a sequence of integers $A$ is a prefix of a sequence of integers $B$ if for all index $i \in [[|A|]]$, we have $A_i = B_i$.

In the same way, we say that a sequence $A$ is a prefix of a partition $B$ if $A$ is a prefix of the first block of $B$ represented in canonical form.

For example, the four possible prefixes of the 3-ordered Lah partition 642/1/35 are $\emptyset$, 6, 64 and 642.

**Definition 27.** Let $A$ and $B$ be two sequences of positive integers. We denote $A \prec_{lex} B$ if either

• $A = B$, or

• $A$ is a strict prefix of $B$ (i.e. $A$ is a prefix of $B$ and $A \neq B$), or

• $\exists i \leqslant |A|$ such that $A_i < B_i$ and $\forall j < i, A_j = B_j$

The relation $\prec_{lex}$ is a total order on the set of sequences of positive integers.

For example, $(1, 3) \prec_{lex} (1, 3, 4)$, $(1, 3) \prec_{lex} (1, 4)$ and $(1, 3, 4) \prec_{lex} (1, 4)$. This order is different from the lexicographic order defined by Martinez and Molinero in [14], because in our context a shorter sequence may be greater than a longer one. Indeed, we make the choice to be as close as possible to the dictionary order.

**Definition 28.** Let $A$ and $B$ be two $k$-partitions of $\mathcal{N}$. We denote $A \prec_{lex} B$ if either

• $A = B$, or

• $\exists i \leqslant |A|$ such that $A_i \prec_{lex} B_i$ but $A_i \neq B_i$ and $\forall j < i, A_j = B_j$.

The relation $\prec_{lex}$ is a total order on the set of $k$-partitions of $\mathcal{N}$. Abusively, we will always use the same notation $\prec_{lex}$ when comparing integer sequences or all kinds of partitions, since the context makes it clear.

This total order will be called the lexicographic order on $k$-partitions and is used for all the kinds of partitions defined before as long as they are expressed in their canonical form.
**Definition 29.** Using the lexicographic order over the canonical form for *k*-partitions (for all possible partition kinds), we define a ranking function assigning to each partition its rank corresponding to the number of *k*-partitions smaller than it in the lexicographic order.

<table><caption>Table 2: The 31 first 3-Stirling partitions of [[5]], 3-ordered Stirling partitions of [[4]], 2-Lah partitions of [[4]], 2-ordered Lah partitions of [[4]], and 5-integer partitions of 15 in canonical form in lexicographic order.</caption><thead><tr><th>Rank</th><th>Partition</th><th>Ord. Part.</th><th>Lah Part.</th><th>Ord. Lah Part.</th><th>Int. Part.</th></tr></thead><tbody><tr><td>0</td><td>1/2/345</td><td>1/2/34</td><td>1/234</td><td>1/234</td><td>1 1 1 1 1 1</td></tr><tr><td>1</td><td>1/23/45</td><td>1/23/4</td><td>1/243</td><td>1/243</td><td>1 1 1 2 10</td></tr><tr><td>2</td><td>1/234/5</td><td>1/24/3</td><td>1/324</td><td>1/324</td><td>1 1 1 3 9</td></tr><tr><td>3</td><td>1/235/4</td><td>1/3/24</td><td>1/342</td><td>1/342</td><td>1 1 1 4 8</td></tr><tr><td>4</td><td>1/24/35</td><td>1/34/2</td><td>1/423</td><td>1/423</td><td>1 1 1 5 7</td></tr><tr><td>5</td><td>1/245/3</td><td>1/4/23</td><td>1/432</td><td>1/432</td><td>1 1 1 6 6</td></tr><tr><td>6</td><td>1/25/34</td><td>12/3/4</td><td>12/34</td><td>12/34</td><td>1 1 2 2 9</td></tr><tr><td>7</td><td><b>12/3/45</b></td><td>12/4/3</td><td>12/43</td><td>12/43</td><td>1 1 2 3 8</td></tr><tr><td>8</td><td><b>12/34/5</b></td><td>13/2/4</td><td>123/4</td><td>123/4</td><td>1 1 2 4 7</td></tr><tr><td>9</td><td><b>12/35/4</b></td><td>13/4/2</td><td>124/3</td><td>124/3</td><td>1 1 2 5 6</td></tr><tr><td>10</td><td><b>123/4/5</b></td><td>14/2/3</td><td>13/24</td><td>13/24</td><td>1 1 3 3 7</td></tr><tr><td>11</td><td><b>124/3/5</b></td><td>14/3/2</td><td>13/42</td><td>13/42</td><td>1 1 3 4 6</td></tr><tr><td>12</td><td><b>125/3/4</b></td><td>2/1/34</td><td>132/4</td><td>132/4</td><td>1 1 3 5 5</td></tr><tr><td>13</td><td>13/2/45</td><td>2/13/4</td><td>134/2</td><td>134/2</td><td>1 1 4 4 5</td></tr><tr><td>14</td><td>13/24/5</td><td>2/14/3</td><td>14/23</td><td>14/23</td><td>1 2 2 2 8</td></tr><tr><td>15</td><td>13/25/4</td><td>2/3/14</td><td>14/32</td><td>14/32</td><td>1 2 2 3 7</td></tr><tr><td>16</td><td>134/2/5</td><td>2/34/1</td><td>142/3</td><td>142/3</td><td>1 2 2 4 6</td></tr><tr><td>17</td><td>135/2/4</td><td>2/4/13</td><td>143/2</td><td>143/2</td><td>1 2 2 5 5</td></tr><tr><td>18</td><td>14/2/35</td><td>23/1/4</td><td>21/34</td><td>2/134</td><td>1 2 3 3 6</td></tr><tr><td>19</td><td>14/23/5</td><td>23/4/1</td><td>21/43</td><td>2/143</td><td>1 2 3 4 5</td></tr><tr><td>20</td><td>14/25/3</td><td>24/1/3</td><td>213/4</td><td>2/314</td><td>1 2 4 4 4</td></tr><tr><td>21</td><td>145/2/3</td><td>24/3/1</td><td>214/3</td><td>2/341</td><td>1 3 3 3 5</td></tr><tr><td>22</td><td>15/2/34</td><td>3/1/24</td><td>231/4</td><td>2/413</td><td>1 3 3 4 4</td></tr><tr><td>23</td><td>15/23/4</td><td>3/12/4</td><td>241/3</td><td>2/431</td><td>2 2 2 2 7</td></tr><tr><td>24</td><td>15/24/3</td><td>3/14/2</td><td>31/24</td><td>21/34</td><td>2 2 2 3 6</td></tr><tr><td>25</td><td></td><td>3/2/14</td><td>31/42</td><td>21/43</td><td>2 2 2 4 5</td></tr><tr><td>26</td><td></td><td>3/24/1</td><td>312/4</td><td>213/4</td><td>2 2 3 3 5</td></tr><tr><td>27</td><td></td><td>3/4/12</td><td>314/2</td><td>214/3</td><td>2 2 3 4 4</td></tr><tr><td>28</td><td></td><td>34/1/2</td><td><b>321/4</b></td><td>23/14</td><td>2 3 3 3 4</td></tr><tr><td>29</td><td></td><td>34/2/1</td><td><b>341/2</b></td><td>23/41</td><td>3 3 3 3 3</td></tr><tr><td>30</td><td></td><td>4/1/23</td><td>41/23</td><td>231/4</td><td></td></tr></tbody></table>

## 2.5 On the number of partitions sharing the same prefix

Lexicographic order is fundamentally defined through the notion of prefixes. This section therefore addresses a central problem: counting partitions that share a common prefix. This is a core building block for our lexicographic unranking algorithms.
A secondary but important goal is to provide intuition about how structure in parti-
tions affects counting efficiency. Specifically, we show that more ordered partition classes
admit simpler prefix-counting formulas, which in turn lead to more efficient unranking
algorithms. To illustrate this principle, we progress from the least structured partition
class (Stirling partitions) to the most structured one (ordered Lah partitions).

**2.5.1 Normalization of a partition**

**Definition 30.** Let $1 \le k \le n$ be two positive integers. Let $p$ be a set $k$-partition written in canonical form (whatever the kind of set partition). The normalization of $p$, denoted by $\bar{p}$ consists in the collection $\bar{B}_1/\bar{B}_2/\dots/\bar{B}_k$, such that each element $\bar{B}_{i,j}$ is equal to $B_{i,j}$ shifted by $-|\{\ell \mid \exists i_0 \le i \text{ and } B_{i_0,\ell} \le B_{i,j}\}|$. Abusively, we say that $\bar{B}_i$ is the normalization of $B_i$.

For example, for *p* the Stirling partition from 10 elements in 3 blocks, written in
canonical form: *p* = 13/25679/4810, we get *p* = 01/01112/000. Intuitively, using the
normalization of a set partition is such that, once the first blocks have been computed,
the rest of the partition can be constructed without considering the elements appearing
in the previous blocks. The intuition behind this transformation is the following: at the
beginning take the list of [[*n*]]. Reading the normalization from left to right, when seeing a
coefficient *i*, you just extract the *i*th smallest element from the remaining elements. We
obtain some kind of independence between the blocks. Obviously this is only a relative
independence.

*Notation* 8. Let *E* be a set of set partitions. We denote by *E* the set containing the normalizations of the set partitions in *E*.

**Proposition 31.** *Let E be a set of set partitions. The normalization is a one-to-one correspondence between E and Ē.*

**2.5.2 Stirling-related partitions**

We now focus on Stirling partitions, the least constrained set partition structures intro-
duced so far. In this section, we first study classical Stirling partitions, then their ordered
variants. Since both classes consist of structurally similar combinatorial objects, they
naturally yield related counting formulas.

Stirling-related partitions do not impose any order on elements within blocks, nor any
order among blocks themselves. This lack of structure creates significant challenges when
counting partitions with a given prefix, as we must account for intricate dependencies
between blocks and their elements. These dependencies arise from the use of the canon-
ical form to represent partitions. Notably, counting Stirling partitions by prefix requires
tracking information about the prefix itself, especially its last element.

*Notation* 9. Let $1 \le k \le n$ be two positive integers. Let $p$ be a prefix of a Stirling partition of $\llbracket n \rrbracket$. We denote by $\mathcal{P}_k^n(p)$ the set of Stirling partitions in $\mathcal{P}_k^n$ accepting $p$ as a prefix and by $S_k^n(p)$ its cardinality. By abuse of notation, if $P$ is a set of prefixes, we will denote by $\mathcal{P}_k^n(P) = \bigcup_{p \in P} \mathcal{P}_k^n(p)$ and $S_k^n(P) = |\mathcal{P}_k^n(P)|$.
**Proposition 32.** Let $1 \le k \le n$ be two positive integers. Let $p'$ be a length $\ell - 1 \ge 0$ prefix of a Stirling partition in $\mathcal{P}_k^n$. Let $\alpha \in [n] \setminus p'$ such that $p = p' \cdot \alpha$. We have:

$$S_k^n(p) = \sum_{u=0}^{\min(n-k-\ell+1, n-\alpha)} \binom{n-\alpha}{u} \left\{ \begin{array}{l} n-\ell-u \\ k-1 \end{array} \right\}. \qquad (5)$$

For example, the number of 3-Stirling partitions of $[5]$ starting with the prefix 12 is given by $S_3^5(1.2) = 5$. They are written in bold in the Table 2.

*Proof.* First if $\ell = \alpha = 1$, then in the canonical form the first block necessarily contains 1. Thus $S_k^n(1) = |\mathcal{P}_k^n| = \binom{n}{k} = \sum_{u=0}^{n-k} \binom{n-1-u}{k-1} \binom{n-1}{u}$. The latter equality is given e.g. in [10, p. 251, Table 251].

In the second case when $1 < \ell \le \alpha$, we aim at counting the number of partitions in $\mathcal{P}_k^n$ accepting $p' \cdot \alpha$ as a prefix. In order to exhibit a combinatorial interpretation, we rewrite $S_k^n(p)$ as

$$\sum_{u=0}^{\min((n-\ell)-(k-1), n-\alpha)} \binom{n-\alpha}{u} \left\{ \begin{array}{l} n-(\ell+u) \\ k-1 \end{array} \right\}.$$

Once the prefix is given, it remains to complete the first block $B_1$ from the partition, and then to calculate how we can further complete the partition using the remaining elements in the next blocks. The index $u$ in the sum corresponds to the number of elements that are appended to the prefix to complete $B_1$. Its value ranges from 0 up to the maximal number of elements that we append i.e. $(n-\ell) - (k-1)$ because at least $k-1$ among the remaining $n-\ell$ elements must be assigned to the other $k-1$ blocks. Obviously the number of possible elements $u$ is also upper bounded by the number of remaining elements, i.e. $n-\alpha$. Once the number $u$ of elements for the completion of $B_1$ is given, we choose $u$ elements greater than $\alpha$: the number of possibilities is given by the binomial coefficient. Finally it remains to build the other blocks of the partition: we partition $n-(\ell+u)$ elements into $k-1$ blocks. Hence the formula is proved. $\square$

Let us take another perspective for the value $S_k^n(p)$. As the reader may have noticed in the proof, only two parameters about the prefix $p$ are necessary: its length $\ell$ and its last component $\alpha$. In fact, for two distinct prefixes $p_1$ and $p_2$ of same length $\ell$ and same last component $\alpha$, there corresponding values $S_k^n(p_1)$ and $S_k^n(p_2)$ are equal. The reason is the following: in order to complete the first block (starting by $p_1$ or $p_2$), we have to choose elements greater than $\alpha$. Once done, it remains to partition the other elements (including) the one smaller than $\alpha$ and which do not occur in the prefix into $k-1$ blocks. But in fact, their exact value is not important, only there number is important. Interestingly, we note that the values $S_k^n(p)$ depends on four parameters $(n, k, \ell, \alpha)$, but there are not completely independent: indeed in Equation 5, we could substitute $n-\ell$ by $\tilde{n}$ and also $\alpha-\ell$ by $\tilde{\alpha}$, then we note that the new sum depends only on the triplet $(\tilde{n}, k, \tilde{\alpha})$. This proves other counting results. In fact, for two distinct prefixes $p_1$ and $p_2$ of respective length $\ell$ and $\ell+l$ and last components $\alpha$ and $\alpha+l$, we have $S_k^n(p_1) = S_k^{n+l}(p_2)$.
Counting formulas for ordered Stirling partitions closely parallel those for unordered Stirling partitions (compare the recursive definitions in Facts [6, 10]). The key difference lies in the ordering constraint: within each block, elements must appear in a specific linear order. Consequently, when extending a prefix of an ordered Stirling partition, we must track the last element to preserve the correct internal order of each block.

**Notation 10.** Let $1 \le k \le n$ be two positive integers. Let $p$ be a prefix of a $k$-ordered Stirling partition of $\llbracket n \rrbracket$. We denote by $O_k^n(p)$ the set of $k$-ordered Stirling partitions in $O_k^n$ accepting $p$ as a prefix and by $T_k^n(p)$ its cardinality. By abuse of notation, if $P$ is a set of prefixes, we will denote by $O_k^n(P) = \bigcup_{p \in P} O_k^n(p)$ and $T_k^n(P) = |O_k^n(P)|$.

**Proposition 33.**$^3$ Let $1 \le k \le n$ be two positive integers. Let $p'$ be a length $\ell - 1$ prefix of an ordered Stirling partition in $O_k^n$. Let $\alpha \in \llbracket n \rrbracket \setminus p'$ and $p = p' \cdot \alpha$. We have:

$$T_k^n(p) = \sum_{u=0}^{\min(n-k-\ell+1, n-\alpha)} \binom{n-\alpha}{u} \cdot O_{k-1}^{n-\ell-u}.$$

*Proof.* The proof of the above proposition is similar to the proof of Proposition 32. Given a prefix $p = p' \cdot \alpha$, we complete the first block by appending until $u \le \min(n-k-\ell+1, n-\alpha)$ elements to the prefix in order to have no empty block and to ensure that the first block is ordered. Once the value of $u$ is fixed, we choose $u$ elements among the elements that are greater than $\alpha$. Finally, we build the other $k-1$ blocks by partitioning the remaining $n-\ell-u$ elements into the $k-1$ blocks (obvioulsy these blocks are ordered). $\square$

We now consider a family of prefixes that are identical except for their last element, which varies within a given range. Our goal is to count the total number of partitions starting with any prefix in this family.

**Proposition 34.** Let $1 \le k \le n$ and $\ell \ge 2$ be three positive integers. Let $p'$ be a length $\ell - 1$ prefix of a Stirling partition in $\mathcal{P}_k^n$. Let $\alpha, \beta \in \llbracket n \rrbracket \setminus p'$ with $\alpha < \beta$. The number of partitions constrained to have a prefix in $p' \cdot \gamma$, with $\gamma \in \llbracket \alpha, \beta \rrbracket$ is given by:

$$S_k^n(p' \llbracket \alpha, \beta \rrbracket) = \sum_{u=0}^{\min(n-k-\ell+1, n-\alpha)} \left( \binom{n-\alpha+1}{u+1} - \binom{n-\beta}{u+1} \right) \cdot \left\{ \begin{matrix} n-\ell-u \\ k-1 \end{matrix} \right\}.$$

*Proof.* Let $1 \le k \le n$ and $\ell \ge 1$ be three positive integers. Let $p'$ be a length $\ell - 1$ prefix of a Stirling partition in $\mathcal{P}_k^n$. We are interested in the number of partitions constrained to have a prefix in $p' \cdot \gamma$, with $\gamma \in \llbracket \alpha, \beta \rrbracket$.

As mentioned before, for distinct prefixes $p_1$ and $p_2$ of the same length $\ell - 1$; both numbers $S_k^n(p_1 \cdot a)$ and $S_k^n(p_2 \cdot a)$ are equal. So we define the prefix $p''$ whose $\ell - 2$ first components are the same as $p'$ and whose last component is $\alpha - 1$. The number $S_k^n(p'')$ counts the partitions whose first block is exactly $p''$ plus the partitions whose first block is

<footnote>$^3$This revised statement replaces Proposition 15 in [5] due to a typographical error in the original wording.</footnote>
starting with $p''$. $\gamma$ with $\gamma \ge \alpha$. We now define the prefix $p'''$ whose $\ell-2$ first components are the same as $p'$ and whose last component is $\beta$. The number $S_k^n(p'')$ counts the partitions whose first block is exactly $p'''$ plus the partitions whose first block is starting with $p''$. $\gamma$ with $\gamma \ge \beta+1$. Thus the difference $S_k^n(p'') - S_k^n(p''')$ counts exactly the partitions whose first block is starting with $p'$. $\gamma$ with $\gamma \in [\alpha, \beta]$, since partitions whose first block is $p''$ are equal to those whose first block is $p''$. Proposition 32 gives the counts, it remains to collect equal terms in both sums to obtain the stated formula.

Note that in the case when the index $u$ is larger than $n - \beta - 1$, then the second binomial coefficient is equal to 0. $\square$

**Proposition 35.** Let $1 \le k \le n$ and $\ell \ge 2$ be three positive integers. Let $p'$ be a length $\ell-1$ prefix of an ordered Stirling partition in $O_k^n$. Let $\alpha, \beta \in [n] \setminus p'$ with $\alpha < \beta$. The number of partitions constrained to have a prefix in $p'$. $\gamma$, with $\gamma \in [\alpha, \beta]$ is given by:

$$T_k^n(p'.[\alpha, \beta]) = \sum_{u=0}^{\min(n-k-\ell+1, n-\alpha)} \left( \binom{n-\alpha+1}{u+1} - \binom{n-\beta}{u+1} \right) \cdot O_{k-1}^{n-\ell-u}.$$

*Proof.* Again, in order to get the combinatorial proof of this result, a direct adaptation of the proof of Proposition 34 is obtained by substituting classical Stirling numbers by the ordered ones. $\square$

### 2.5.3 Lah partitions

Having analyzed prefix counting for Stirling-related partitions, we now develop analogous results for Lah partitions. Like Stirling partitions, we first study the unordered case before extending to ordered Lah partitions (in the next section).

The canonical form introduces similar complexity: the first block must contain the element 1, requiring us to distinguish cases based on whether the prefix already includes 1. However, unlike Stirling partitions, the order of elements within blocks plays a role, which yields more tractable formulas.

*Notation 11.* Let $1 \le k \le n$ be two positive integers. Let $p$ be a prefix of a Lah partition of $[n]$. We denote by $\mathcal{L}(p)$ the set of Lah partitions in $\mathcal{L}_k^n$ accepting $p$ as a prefix and by $L_k^n(p)$ its cardinality.

**Proposition 36.** Let $1 \le k \le n$ be two positive integers. Let $p$ be a length $\ell$ prefix of a partition in $\mathcal{L}_k^n$.

$$L_k^n(p) = \begin{cases} L_{1k}^n(p) = \sum_{u=0}^{n-k-\ell+1} \left\lfloor \frac{n-\ell-u}{k-1} \right\rfloor \binom{n-\ell}{u} u! & \text{if } 1 \in p \\ L_{2k}^n(p) = \sum_{u=0}^{n-k-\ell} \left\lfloor \frac{n-\ell-u-1}{k-1} \right\rfloor \binom{n-\ell-1}{u} (u+1)! & \text{otherwise.} \end{cases}$$

*Proof.* Let $1 \le k \le n$ be two positive integers. Let $\ell \ge 1$ be an integer and $\alpha_1 \alpha_2 \dots \alpha_\ell$ be a prefix of a Lah partition in $\mathcal{L}_k^n$.
* If one of the $\alpha_i$ is equal to 1, then, we complete the first block by appending until $u \le n-k-\ell+1$ elements to the prefix in order to have no empty block. We choose $u$ elements among the remaining $n-\ell$ elements, choose the order in which we will insert them and build the others blocks by partitioning the remaining $n-\ell-u$ elements into $k-1$ blocks.

* If none of the $\alpha_i$ is equal to 1, then we add a mandatory 1 to the first block and we follow the same logic as before. However, we must shuffle the 1 with the elements that we append to the prefix. $\square$

The formulas established in Proposition 36 are expressed as a sum which make the calculations longer. The rest of the section is dedicated to finding a more efficient formula to calculate $L_{1k}^n(p)$ and $L_{2k}^n(p)$. Indeed, let $\alpha \in [n] \setminus p$, finding a recurrence relation allowing to go from $L_{1k}^n(p)$ to $L_{1k}^n(p.\alpha)$ and from $L_{2k}^n(p)$ to $L_{2k}^n(p.\alpha)$ may allow us to compute the values of $L_{1k}^n(p)$ and $L_{2k}^n(p.\alpha)$ in constant time.

**Proposition 37.** Let $1 \le k \le n$ be two positive integers. Let $p'$ be a length $\ell-1$ prefix of a Lah partition in $\mathcal{L}_k^n$. Let $\alpha \in [n] \setminus p'$ and $p = p'.\alpha$. We have

$$ \left\{ \begin{array}{l} L_{1k}^n(p) = \frac{L_{1k}^n(p') - \left\lfloor \frac{n-(\ell-1)}{k-1} \right\rfloor}{(n - (\ell - 1))} = \left\lfloor \frac{n-\ell}{k-1} \right\rfloor + k \left\lfloor \frac{n-\ell}{k} \right\rfloor; \\ \\ L_{2k}^n(p) = \frac{L_{2k}^n(p') - L_{1k}^n(p)}{(n-\ell)} = \left\lfloor \frac{n-\ell}{k} \right\rfloor. \end{array} \right. $$

*Proof.* Let $1 \le k \le n$ be two positive integers. Let $1 \le \ell \le n-k-1$.

* Let $p'$ be a length $\ell-1$ prefix of a Lah partition in $\mathcal{L}_k^n$. Let $\alpha \in [n] \setminus p'$ and $p = p'.\alpha$. We suppose that $1 \in p'$. To extract $\overline{\mathcal{L}}_k^n(p)$ from $\overline{\mathcal{L}}_k^n(p')$, we remove from $\overline{\mathcal{L}}_k^n(p')$ the partitions that have $p'$ as their whole first block. This kind of partitions are counted by $\overline{\mathcal{L}}_k^n(p') - \left\lfloor \frac{n-\ell-1}{k-1} \right\rfloor$ and select among them those that have $\alpha$ as their $\ell^{th}$ element. Now, suppose that $1 \notin p'$ and $\alpha = 1$. We assume the second equality of the proposition for the moment. It will be proved in the next paragraph. We express $\mathcal{L}_{1k}^n(p)$ as $\mathcal{L}_{2k}^n(p')$ where we remove the partitions of the form $p'.\beta$ where $\beta \in [n] \setminus p', \beta \ne 1$. Hence, $L_{1k}^n(p) = L_{2k}^n(p') - \sum_{\beta \in [n] \setminus p', \beta \ne 1} L_{2k}^n(p'.\beta) = L_{1k}^n(p)$.

We are going to prove the second equality by working on $\overline{\mathcal{L}}_k^n(p)$ which is the set of Lah partitions in normal form accepting $\overline{p}$ as a prefix. Given the $\ell$ first elements of a partition in $\overline{\mathcal{L}}_k^n$, we complete the partition in two ways:

- Either $\overline{p}$ is the whole first block of the partition. In this case, we complete the partition by appending to the first block a $(k-1)$-partition of the remaining $n-\ell$ elements. The number of such partitions is counted by $\left\lfloor \frac{n-\ell}{k-1} \right\rfloor$.
- Or $\bar{p}$ is not the whole first block of the partition. In this case, we choose a block of a partition in $\overline{\mathcal{L}}_k^{n-\ell}$ and choose among the $k$ blocks of this partition the one that we will append to the first block. The number of such partitions is counted by $k \cdot \lfloor n-\ell \rfloor$.

Hence, by proposition 31, we have that $L_{1k}^n(\ell) = \lfloor n-\ell \rfloor + k \lfloor n-\ell \rfloor$.

* Let $p'$ be a length $\ell-1$ prefix of a Lah partition in $\mathcal{L}_k^n$. Let $\alpha \in [[n]] \setminus p'$ and $p = p' \cdot \alpha$. We suppose that none of the elements of $p$ is equal to 1. To extract $\mathcal{L}_{2k}^n(p)$ from $\mathcal{L}_{2k}^n(p')$, we remove from $\mathcal{L}_{2k}^n(p')$ the partitions that have 1 as their $\ell^{th}$ element and choose among the remaining partitions those that have $\alpha$ as their $\ell^{th}$ element.

The second equality can be shown by decomposing a partition in $\mathcal{L}_k^n$ with a length $\ell$ prefix that does not contain 1 into two parts: the first part is the prefix and the second part is a partition of the remaining $n-\ell$ elements into $k$ blocks. $\square$

### 2.5.4 Ordered Lah partitions

**Proposition 38.** There exists a bijection between $Q_k^n$ and the pair $\tilde{Q}_k^n = (C_{k-1}^{n-1}, \Sigma_n)$ where $C_{k-1}^{n-1}$ is the set of the $(k-1)$-combinations of $[[n-1]]$ and $\Sigma_n$ is the set of permutations of $[[n]]$.

Intuitively, $\Sigma$ specifies the order in which elements appear across all blocks, while $C$ marks the positions of cuts separating successive blocks. For instance, let $C = (2, 4)$ and $\Sigma = (5, 1, 3, 2, 4, 6)$. The associated partition is $(B_1, B_2, B_3) = ((5, 1), (3, 2), (4, 6))$.

*Proof.* Let $C = (c_1, \dots, c_{k-1})$ be a $(k-1)$-combination of $[[n-1]]$ in canonical form and $\Sigma = (\sigma_1, \dots, \sigma_n)$ be a permutation of $[[n]]$. We construct a partition $A = (B_1, \dots, B_k) \in Q_k^n$ as follows:

* Let $\tilde{C} = \{\tilde{c}_0 = 0, \tilde{c}_1 = c_1, \dots, \tilde{c}_{k-1} = c_{k-1}, \tilde{c}_k = n\}$;

* $\forall i \in [[k]], B_i = \{\sigma_j \in \Sigma \mid \tilde{c}_{i-1} < j \le \tilde{c}_i\}$.

Doing the reverse operation, we obtain a $k-1$-combination $C$ and a permutation $\Sigma$ from a partition $A$ in $Q_k^n$. $\square$

**Notation 12.** Let $1 \le k \le n$ be two positive integers. Let $p$ be a prefix of a $k$-ordered Lah partition of $[[n]]$. We denote by $Q(p)$ the set of $k$-ordered Lah partitions in $Q_k^n$ accepting $p$ as a prefix and by $Q_k^n(p)$ its cardinality.

**Corollary 39.** Let $1 \le k \le n$ be two positive integers. Let $\alpha, \beta \in [[n]]$ with $\alpha \ne \beta$. We have $Q_k^n(\alpha) = Q_k^n(\beta) = \lfloor n \rfloor / n$.

**Proposition 40.** Let $1 \le k \le n$ be two positive integers. For a given prefix $p = \alpha_1 \alpha_2 \dots \alpha_\ell$, we define $Q_k^n(p)$ to be the number of partitions in $Q_k^n$ accepting $p$ as a prefix. We have $Q_k^n(p) = \lfloor n-\ell \rfloor + \lfloor n-\ell \rfloor = \lfloor n+1-\ell \rfloor / (n+1-\ell)$.
Notation 13. Let $A$ be a sequence of elements of a finite set $E$ without repetition. We denote by $A.$ the set of sequences obtained by appending an element $x \in E \setminus A$ to $A$.

*Proof.* The first equality can be proved combinatorially: Let $1 \le k \le n$ be two positive integers. Let $p = \alpha_1 \alpha_2 \dots \alpha_\ell$ be a prefix of a partition in $Q_k^n$. To obtain a partition in $Q_k^n(p)$, we can either:

* Take a partition from $\bar{Q}_{k-1}^{n-\ell}$ and add $\bar{p}$ as a new first block;

* Take a partition from $\bar{Q}_k^{n-\ell}$ and add $\bar{p}$ at the beginning of the first block.

Once this is done, we unnormalize the partition to obtain a partition in $Q_k^n(p)$. The second equality can be proved by recurrence on the length of $p$. If $|p| = 1$, then, by Corollary 39, we have $Q_k^n(p) = \left\lfloor \frac{n}{k} \right\rfloor / n$. Now we assume that the result is true for a prefix $p$ of length $\ell$ and we want to prove it for a prefix of the form $p' = p.\alpha_{\ell+1}$. Let $Q_k^n(p.)$ be the set of partitions in $Q_k^n(p)$ whose first block is $p$ followed by at least one other element. We express $Q_k^n(p.)$ as $Q_k^n(p)$ minus the partitions whose first block is exactly $p$. Hence $|Q_k^n(p.)| = Q_k^n(p) - \left\lfloor \frac{n-\ell}{k-1} \right\rfloor$ and by recurrence hypothesis, we have that $|Q_k^n(p.)| = \left\lceil \frac{n+1-\ell}{k} \right\rceil / (n+1-\ell) - \left\lfloor \frac{n-\ell}{k-1} \right\rfloor$. After remarking that $|p.?| = (n-\ell)$ we deduce

$$|Q_k^n(p')| = \frac{|Q_k^n(p.)|}{(n-\ell)} = \frac{\frac{\left\lfloor \frac{n+1-\ell}{k} \right\rfloor}{n+1-\ell} - \left\lfloor \frac{n-\ell}{k-1} \right\rfloor}{(n-\ell)} = \frac{\left\lfloor \frac{n-\ell}{k} \right\rfloor}{n-\ell}. \quad \square$$

### 2.5.5 Integer partitions

We now derive analogous prefix-counting formulas for integer partitions. These formulas are computationally simpler than their counterparts for Stirling-related partitions due to a fundamental structural difference. In set partitions (written in canonical form), a smaller element may precede a larger one if they belong to different blocks. In contrast, integer partitions are always sorted in non-decreasing order, ensuring that the last element of a prefix provides a global lower bound for all subsequent parts. To be coherent with literature for integer partition we use the term part instead of block along the paper.

Notation 14. Let $1 \le k \le n$ be two positive integers. Let $p$ be a prefix of an integer partition of the integer $n$. We denote by $\mathcal{I}_k^n(p)$ the set of integer partitions in $\mathcal{I}_k^n$ accepting $p$ as a prefix and by $\mathcal{I}_k^n(p)$ its cardinality. By abuse of notation, if $P$ is a set of prefixes, we will denote by $\mathcal{I}_k^n(P) = \bigcup_{p \in P} \mathcal{I}_k^n(p)$ and $\mathcal{I}_k^n(P) = |\mathcal{I}_k^n(P)|$.

**Proposition 41.** Let $1 \le k' \le k$, and $n' \le n$ be integers. Let $p'$ be in $\mathcal{I}_{k'-1}^{n'}$. Let $\alpha \in \left\lfloor \frac{n-n'-k+k'+1}{2} \right\rfloor$ and $p = p'.\alpha$. We denote by $\Delta_n$ the quantity $n-n'$ and by $\Delta_k$ the quantity $k-k'$. We have:

$$I_k^n(p) = \sum_{j=\alpha}^{\Delta_n - (\Delta_k - 1)} p(\Delta_n - \Delta_k(j-1) + 1, \Delta_k - 1).$$
**Proof.** Let $1 \le k \le n$ be two positive integers. Let $p' \in \mathcal{I}_{k'-1}^{n'}$. Let $\alpha \in [n-n'-k+k'+1]$ and $p = p' \cdot \alpha$. We count the number of ways to extend $p$ into a complete partition of $n$ into $k$ parts. Since integer partitions are sorted in non-decreasing order, all remaining parts must be at least $\alpha$. Additionally, to ensure $k$ parts in total, no appended element can exceed $\Delta_n - (\Delta_k - 1)$. We therefore adjoin an element $j \in [\alpha, \Delta_n - (\Delta_k - 1)]$ to the prefix. Once $j$ is fixed, we extend the partition by appending the value $j$ exactly $\Delta_k$ times, yielding an intermediate partition $i$ with all $\Delta_k$ remaining parts initialized to $j$. Finally, we partition the residual weight $\Delta_n - \Delta_k(j-1) + 1$ into $\Delta_k - 1$ parts and distribute these among the last $\Delta_k - 1$ parts of $i$. $\square$

**Proposition 42.** Let $1 \le k' \le k$, and $n' \le n$ be integers. Let $p'$ be in $\mathcal{I}_{k'-1}^{n'}$. Let $\alpha > \beta \in [n-n'-k+k'+1]$. We denote by $\Delta_n$ the quantity $n-n'$ and by $\Delta_k$ the quantity $k-k'$. We have:

$$I_k^n(p'.[\alpha, \beta]) = p(\Delta_n - \Delta_k(\alpha - 1), \Delta_k) - p(\Delta_n - \Delta_k\beta, \Delta_k).$$

**Proof.** Let $1 \le k \le n$ be two positive integers. Let $p' \in \mathcal{I}_{k'-1}^{n'}$. Let $\alpha > \beta \in [n-n'-k+k'+1]$. The quantity $p(\Delta_n - \Delta_k(\alpha - 1), \Delta_k)$ counts the number of partitions of $\Delta_n$ into $\Delta_k$ parts where the first part is at least $\alpha$.

* The quantity $p(\Delta_n - \Delta_k(\alpha - 1), \Delta_k)$ counts the number of partitions of $\Delta_n$ into $\Delta_k$ parts where the first part is at least $\alpha$.

* The quantity $p(\Delta_n - \Delta_k\beta, \Delta_k)$ counts the number of partitions of $\Delta_n$ into $\Delta_k$ parts where the first part is at least $\beta + 1$.

Thus, the difference counts partitions of $\Delta_n$ into $\Delta_k$ parts where the first part lies in $[\alpha, \beta]$. Concatenating $p'$ with each such partition yields precisely the partitions in $\mathcal{I}_k^n$ that admit $p'.[\alpha, \beta]$ as a prefix. $\square$

Note, in [21], the author provides other formulas for counting integer partitions that leads to colexicographic unranking algorithms for integer partitions.

# 3 Lexicographic unranking of partitions

## 3.1 Combinatorial interpretation and unranking algorithms

As a first approach, we develop a systematic method for constructing unranking algorithms for a combinatorial class $C$ based on a combinatorial decomposition of its counting formula. However, the resulting order is not necessarily lexicographic.

**Definition 43.** Let $C$ be a combinatorial class containing $n$ elements and $\prec$ a total order on $C$. We define a pair of functions $\text{RANK}: C \to [0, n-1]$ and $\text{UNRANK}: [0, n-1] \to C$ inverse of each other as follows.

* $\forall c \in C$, $\text{RANK}(c) = |\{c' \in C | c' \prec c\}|$.

* $\forall i \in [0, n-1]$, $\text{UNRANK}(i) = c \in C$ such that $\text{RANK}(c) = i$.
Algorithms implementing these functions are respectively called ranking and unranking algorithm.

**Definition 44.** A finite combinatorial class $\mathcal{C}$ is said admissible if either

* $\mathcal{C}$ is constituted of integers, or

* $\mathcal{C}$ is the disjoint union of two admissible classes.

**Definition 45.** Let $\mathcal{C}$ be a finite admissible combinatorial class decomposable into $\mathcal{C} = \mathcal{A} \uplus \mathcal{B}$, with $\mathcal{A}$ and $\mathcal{B}$ totally-ordered admissible classes. Let $\prec_C$ be the total recursive order on $\mathcal{C}$ satisfying:

* $\forall \alpha \in \mathcal{A}$ and $\forall \beta \in \mathcal{B}, \alpha \prec_C \beta$;

* $\forall \alpha_1, \alpha_2 \in \mathcal{A}, \alpha_1 \prec_C \alpha_2 \iff \alpha_1 \prec_C \alpha_2$;

* $\forall \beta_1, \beta_2 \in \mathcal{B}, \beta_1 \prec_C \beta_2 \iff \beta_1 \prec_C \beta_2$.

The total order $\prec_C$ is called the combinatorial order on $\mathcal{C}$.

**Corollary 46.** Let $\mathcal{C}$ be a finite admissible combinatorial class decomposable into $\mathcal{C} = \mathcal{A} \uplus \mathcal{B}$, with $\mathcal{A}$ and $\mathcal{B}$ totally-ordered admissible classes. The combinatorial order $\prec_C$ is such that

$$ \forall c \in \mathcal{C}, \mathrm{RANK}_{\mathcal{C}}(c) = \begin{cases} \mathrm{RANK}_{\mathcal{A}}(c) & \text{if } c \in \mathcal{A} \\ |\mathcal{A}| + \mathrm{RANK}_{\mathcal{B}}(c) & \text{if } c \in \mathcal{B}. \end{cases} $$

Here the notation $\mathrm{RANK}_S$ represents the ranking function over set $S$. When there is no ambiguity, the set is omitted. The corollary is proved by using a structural induction on $\mathcal{C}$.

In practice, a natural decomposition of a combinatorial class $\mathcal{C}$ is given by the combinatorial interpretation of a constructive counting formula. For instance, the Stirling $k$-partitions of $\llbracket n \rrbracket$ are counted by $\binom{n}{k}$, and the proof of Fact 6 provides a way to decompose $\mathcal{P}_k^n$ into $k+1$ subclasses based on the position of element $n$ in the partition:

* partitions where $n$ is alone in the last block;

* partitions where $n$ is in the first block but not alone;

* partitions where $n$ is in the second block but not alone;

* ...

* and finally partitions where $n$ is in the last block but not alone.
In Appendix A, we provide a complete example for the combinatorial order over Stirling partitions of $\llbracket 5 \rrbracket$ into 3 blocks.

Since the combinatorial order arises naturally from how objects in a combinatorial class are constructed and reflects their enumeration formula, we can readily derive an unranking algorithm for any admissible combinatorial class. Given the decomposition $C = A \uplus B$ and a rank $r$, the algorithm computes the cardinality of $A$ and recursively generates an object from either $A$ or $B$ based on the value of $r$.

Implementations for Stirling-related partitions, Lah-related partitions, and integer partitions are available in the accompanying repository [4]. These implementations prioritize pedagogical clarity over efficiency, providing reference implementations based on the combinatorial interpretation of counting formulas.

These algorithms serve as benchmarks when evaluating our lexicographic unranking algorithms, which will be presented in the next section. Intuitively, the complexity of an unranking algorithm reflects the complexity of the underlying combinatorial decomposition. A key practical consideration is that arithmetic operations on large integers are computationally expensive in both time and space, which significantly affects the efficiency of these algorithms.

## 3.2 Lexicographic unranking algorithms

This section develops new recurrence relations for the combinatorial classes introduced in Section 2.1 and derives, from their combinatorial interpretation, decompositions compatible with the lexicographic order. These decompositions naturally lead to lexicographic unranking algorithms following the principles of Section 3.1. Unlike Section 3.1, where a decomposition $C = A \uplus B = B \uplus A$ admits multiple combinatorial orders on $C$, we focus exclusively on the unique decomposition that is lexicographically compatible.

**Definition 47.** Let $C$ be a combinatorial class. We say that a decomposition of $C = A \uplus B$ is compatible with the lexicographic order if for all $\alpha \in A$ and $\beta \in B$, we have $\alpha \prec_{lex} \beta$. In the rest of this article, we will denote

$$C = A \succ B$$

such a decomposition.

### 3.2.1 Stirling partitions

Let us start with the case of Stirling partitions corresponding to the least constrained set partitions studied in this paper.

**Proposition 48.** Let $1 \le k \le n$ be two positive integers. Let $p'$ be a length $\ell - 1$ prefix of a partition in $P_k^n$. Let $\alpha, \beta \in \llbracket n \rrbracket \setminus p'$, satisfying $\alpha < \beta$. We have:

$$S_k^n(p'.\llbracket \alpha, \beta \rrbracket) = \sum_{i=\alpha}^{\beta} S_k^n(p'.i).$$
*Proof.* By definition of $\mathcal{P}_k^n(p'.[[\alpha, \beta]])$, we have

$$ \mathcal{P}_k^n(p'.[[\alpha, \beta]]) = \bigcup_{i=\alpha}^{\beta} \mathcal{P}_k^n(p'.i). $$

Since the set union is disjoint in this case, the result follows. □

**Proposition 49.** Let $1 \le k \le n$ be two positive integers. Let $p'$ be a length $\ell - 1$ prefix of a partition in $\mathcal{P}_k^n$. Let $\alpha, \beta \in [[n]] \setminus p'$, satisfying $\alpha < \beta$. We have

$$ \mathcal{P}_k^n(p'.[[\alpha, \beta]]) = \triangleright_{i=\alpha}^{\beta} \mathcal{P}_k^n(p'.i). $$

While this decomposition is compatible with the lexicographic order, it is insufficient for constructing a lexicographic unranking algorithm. Indeed, it induces only a partial order on $\mathcal{P}_k^n(p'.[[\alpha, \beta]])$, since any two elements with equal $\ell^{th}$ elements remain incomparable under this order.

**Proposition 50.** Let $1 \le k \le n$ be two positive integers. Let $p'$ be a length $\ell - 1$ prefix of a partition in $\mathcal{P}_k^n$. Let $\alpha, \beta \in [[n]] \setminus p'$, satisfying $\alpha < \beta$. Two partitions in $\mathcal{P}_k^n(p'.[[\alpha, \beta]])$ are incomparable regarding the order described in Proposition 49 if and only if they have the same $\ell^{th}$ element.

The next propositions establish a recurrence relation linking sets of the form $\mathcal{P}_k^n(p'.i)$ with sets of the form $\mathcal{P}_k^n(p'.i.[i + 1, n])$. This relation enables us to order elements of $\mathcal{P}_k^n(p'.i)$ according to their $(\ell + 1)^{th}$ component.

**Proposition 51.** Let $1 \le k \le n$ be two positive integers. Let $p'$ be a length $\ell - 1$ prefix of a partition in $\mathcal{P}_k^n$. Let $\alpha \in [[n]] \setminus p'$ and $p = p'.\alpha$. We obtain

$$ S_k^n(p) = \left\{ \begin{array}{l} n - \ell \\ k - 1 \end{array} \right\} + S_k^n(p.[[\alpha + 1, n]]). $$

*Proof.* Let $x \in \mathcal{P}_k^n(p)$ be a partition with prefix $p$. There are two possibilities whose interpretation leads to the equality: Either the first block of $x$ is exactly $p$, or $p$ is followed by at least one element in the first block of $x$. □

**Proposition 52.** Let $1 \le k \le n$ be two positive integers. Let $p'$ be a length $\ell - 1$ prefix of a partition in $\mathcal{P}_k^n$. Let $\alpha \in [[n]] \setminus p'$ and $p = p'.\alpha$. We have

$$ \mathcal{P}_k^n(p) = N^{-1}(\bar{p} :: \overline{\mathcal{P}_{k-1}^{n-\ell}}) \triangleright \mathcal{P}_k^n(p.[[\alpha + 1, n]]), $$

where $N^{-1}$ is the inverse of the normalization function defined in Definition 30.

*Proof.* By definition, $N^{-1}(\bar{p} :: \overline{\mathcal{P}_{k-1}^{n-\ell}})$ contains all partitions in $\mathcal{P}_k^n(p)$ with first block exactly $p$, while $\mathcal{P}_k^n(p.[[\alpha + 1, n]])$ contains those with first block starting with $p$ and including at least one additional element. Consequently, any partition in the first set has a first block that is a strict prefix of the first block of any partition in the second set, ensuring compatibility with the lexicographic order. □
Notably, the equality described in Proposition 51 allows us to directly compute the cardinality of the sets involved in the decomposition described in Proposition 52.

**Proposition 53.** Let $1 \le k \le n$ be two positive integers. Let $p'$ be a length $\ell-1$ prefix of a partition in $\mathcal{P}_k^n$. Let $\alpha \in [n] \setminus p'$ and $p = p' \cdot \alpha$. Two elements of $\mathcal{P}_k^n(p)$ are incomparable regarding the order described in Proposition 52 if and only if either both have first block exactly $p$, or both have first blocks containing at least $\ell+1$ elements.

**Theorem 54.** Let $1 \le k \le n$ be two positive integers. We denote by $\prec_{49}$ and $\prec_{52}$ the orders described in Propositions 49 and 52 respectively. We define the relation $\prec$ over $\mathcal{P}_k^n$ as follows: Let $p_1, p_2 \in \mathcal{P}_k^n$,

$$p_1 \prec_{49} p_2 \text{ or } p_1 \prec_{52} p_2 \iff p_1 \prec p_2.$$

The relation $\prec$ is a total order over $\mathcal{P}_k^n$ corresponding to the lexicographic order.

*Proof.* Let $1 \le k \le n$ be two positive integers. The relation $\prec$ is a total order over $\mathcal{P}_k^n$ is deduced as a direct consequence of the Propositions 53 and 50. In fact, the relation $\prec_{49}$ puts in relationship partitions whose first block is of size at least $\ell$ and sharing the same length $\ell-1$-prefix $p'$ followed by two distinct elements while the relation $\prec_{52}$ puts in relationship partitions sharing the same first length $\ell$-prefix $p$ such that $p$ is either exactly the first block, or it is a strict prefix that is followed by at least one additional element, and thus $\prec_{49}$ will be applied again. $\square$

Let us introduce some auxilliary ideas before presenting the unranking algorithm. It will highlight the intuition under the unranking algorithm we will describe. Let $\mathcal{M}$ be a sequence of distinct partitions in $\mathcal{P}_k^n$. We are going to show that the following algorithm will sort $\mathcal{M}$ regarding the lexicographic order:

* With one traversal of $\mathcal{M}$, we partition $\mathcal{M}$ into $n$ subsets $\mathcal{M}_1, \mathcal{M}_2, \dots, \mathcal{M}_n$ such that $m_i \in \mathcal{M}_j$ if and only if the first element of $m_i$ is equal to $j$. The lexicographic compatibility of the order $\prec_{49}$ ensures that for all $i < j$, for all $m_i \in \mathcal{M}_i$ and for all $m_j \in \mathcal{M}_j$, we have $m_i \prec_{lex} m_j$.

* Given a set $\mathcal{M}_j$, we partition it into two subsets $\mathcal{M}_{j,1}$ and $\mathcal{M}_{j,2}$ such that $m \in \mathcal{M}_{j,1}$ if and only if the first block of $m$ is exactly $j$. The lexicographic compatibility of the order $\prec_{52}$ ensures that for all $m_1 \in \mathcal{M}_{j,1}$ and for all $m_2 \in \mathcal{M}_{j,2}$, we have $m_1 \prec_{lex} m_2$.

* We sort $\mathcal{M}_{j,1}$ and $\mathcal{M}_{j,2}$ recursively by applying the same procedure, elements by elements until each subset is reduced to a singleton.

* Finally, we concatenate all the sorted subsets to obtain the sorted sequence $\mathcal{M}$.

The unranking algorithm we present searches for the partition with rank $r$ in $\mathcal{P}_k^n$ within the sorted sequence of all such partitions. It follows the same principles as the algorithms used in the proof of Theorem 54, but for unranking we only need the sizes of the subsets known to precede the partition of rank $r$, not the entire sequence. To improve
the time complexity, we replace the linear search over each element of the partition with a binary search. In practice, we rely on the following decomposition instead of the one in Proposition 49.

**Proposition 55.** Let $1 \le k \le n$ be two positive integers. Let $p'$ be a length $\ell - 1$ prefix of a partition in $\mathcal{P}_k^n$. Let $\alpha, \beta \in [[n]] \setminus p'$, satisfying $\alpha < \beta$. We have:

$$ \mathcal{P}_k^n(p'.[[\alpha, \beta]]) = \mathcal{P}_k^n(p'.[[\alpha, \lfloor(\alpha + \beta)/2\rfloor]]) \triangleright \mathcal{P}_k^n(p'.[[\lfloor(\alpha + \beta)/2\rfloor + 1, \beta]]). $$

These decompositions lead us to the following lexicographic unranking algorithm for Stirling partitions.

<table><caption>**Algorithm 1** Lexicographic unranking of the partition with rank $r$ in $\mathcal{P}_k^n$</caption><thead><tr><th></th><th></th><th></th></tr></thead><tbody><tr><td>1:</td><td>function UNRANKING(n, k, r, Cf, Rf)</td><td>1: function NEXTBLOCK(n, k, r, Cf, Rf)</td></tr><tr><td>2:</td><td>n' := n</td><td>2: ret := []</td></tr><tr><td>3:</td><td>Res := []</td><td>3: acc, d_0 := 0, 0</td></tr><tr><td>4:</td><td>while k > 1 do</td><td>4: pos := 1</td></tr><tr><td>5:</td><td>(B, acc) := NEXTBLOCK(n, k, r, Cf, Rf)</td><td>5: inf, sup := 1, n</td></tr><tr><td>6:</td><td>Append(Res, B)</td><td>6: complete := false</td></tr><tr><td>7:</td><td>r := r - acc</td><td>7: while not complete do</td></tr><tr><td>8:</td><td>n := n - len(B)</td><td>8: while inf < sup do</td></tr><tr><td>9:</td><td>k := k - 1</td><td>9: mid := ⌊(inf + sup)/2⌋</td></tr><tr><td>10:</td><td>Append(Res, [0, 0, ..., 0])</td><td>10: rMid := Rf(n, k, pos, d<sub>0</sub>, mid) + acc</td></tr><tr><td>11:</td><td>Res:= EXTRACT(n', Res)</td><td>11: if r ≥ rMid then</td></tr><tr><td>12:</td><td>return Res</td><td>12: inf := mid + 1</td></tr><tr><td>1:</td><td>function EXTRACT(n, R)</td><td>13: else</td></tr><tr><td>2:</td><td>L := [1, 2, ..., n]</td><td>14: sup := mid</td></tr><tr><td>3:</td><td>P := []</td><td>15: mid := inf</td></tr><tr><td>4:</td><td>for r in R do</td><td>16: rMid := Rf(n, k, pos, d<sub>0</sub>, mid-1) + acc</td></tr><tr><td>5:</td><td>p := []</td><td>17: Append(ret, mid - pos)</td></tr><tr><td>6:</td><td>for i in r do</td><td>18: acc := rMid</td></tr><tr><td>7:</td><td>Append(p, L[i])</td><td>19: stirling := Cf(n - pos, k - 1)</td></tr><tr><td>8:</td><td>Remove(L, i)</td><td>20: if r < stirling + acc then</td></tr><tr><td>9:</td><td>Append(P, p)</td><td>21: complete := true</td></tr><tr><td>10:</td><td>return P</td><td>22: else</td></tr><tr><td></td><td>Remove(L, i) removes element with index i in L.</td><td>23: pos := pos + 1</td></tr><tr><td></td><td>Append(L, e) appends element e to L.</td><td>24: d<sub>0</sub> := mid</td></tr><tr><td></td><td></td><td>25: inf, sup := d<sub>0</sub> + 1, n</td></tr><tr><td></td><td></td><td>26: acc := stirling + acc</td></tr><tr><td></td><td></td><td>27: return (ret, acc)</td></tr></tbody></table>

The function **Unranking** constructs partitions block by block and element by element, taking three integer parameters $(n, k, r)$ and two auxiliary functions $(Cf$ and $Rf)$:

* $Cf$ computes the total number of partitions of $[[n]]$ into $k$ blocks.

* $Rf$ counts partitions of $[[n]]$ into $k$ blocks with a specified prefix and $\ell^{th}$ element within given bounds.
Specifically, Unranking(n, k, r, Stirling, R) (instantiating Cf with Stirling number computation via memoization and Rf with $S_k^n(p'.[[a, b]])$) returns the $r^{th}$ lexicographic partition of $[[n]]$ into k blocks.

Algorithm 1 operates through three steps: (1) Line 3 (right column) tests whether the current block is complete using Proposition 52; (2) The while loop (line 8) performs binary search to identify each element by applying Proposition 55; (3) Line 17 implements the termination condition from Proposition 52.

### 3.2.2 Ordered Stirling partitions

The problem of the lexicographic unranking for ordered Stirling partitions is very similar to the one of Stirling partitions. Indeed, the set of ordered Stirling partitions can be decomposed in the same way as Stirling partitions.

**Proposition 56.** Let $1 \le k \le n$ be two positive integers. Let $p'$ be a length $l-1$ prefix of a partition in $O_k^n$. Let $\alpha, \beta \in [[n]] \setminus p'$, satisfying $\alpha < \beta$. Let $\alpha \in [[n]] \setminus p'$ and let $p = p'.\alpha$. We have

$$T_k^n(p'.[[\alpha, \beta]]) = \sum_{i=\alpha}^{\beta} T_k^n(p'.i) \quad \text{and} \quad T_k^n(p) = O_{k-1}^{n-\ell} + T_k^n(p.[[\alpha + 1, n))).$$

*Proof.* Each of these equalities can be proved using the same arguments as those used in the proofs of Propositions 48 and 51. $\square$

**Theorem 57.** The total order over $O_k^n$ induced by the decompositions of Proposition 56 is the lexicographic order over $O_k^n$.

The lexicographic unranking algorithm for ordered Stirling partitions is identical to Algorithm 1. The same decompositions are used as for Stirling partitions; only the counting formulas differ. Using both functions OrderedStirling(n,k) that returns the number of ordered Stirling partitions of $[[n]]$ into k blocks and T(n,k,l,α,β) that returns $T_k^n(p'.[[\alpha, \beta]])$ for a length l prefix $p'$. Then Unranking(n, k, r, OrderedStirling, T), produces the $r^{th}$ ordered partition of $[[n]]$ into k blocks in lexicographic order. An illustration of the unranking algorithm is provided in Appendix B.

### 3.2.3 Lah partitions

The lexicographic unranking algorithm for Lah partitions follows the same principles as for Stirling-related partitions. However, for Lah partitions the two counting formulas associated with the same prefix depend only on the prefix's length and not on its content. Consequently, an element of a block in a Lah partition can be determined with a constant number of calls to the counting formulas. By contrast, for Stirling-related partitions, determining a block element requires a logarithmic number of such calls.
**Proposition 58.** Let $1 \le k \le n$ be two positive integers. Let $p$ be a length $\ell$ prefix of a partition in $\mathcal{L}_k^n$.

$$ egin{cases} \mathcal{L}_k^n(p) = \triangleright_{i=1, i \notin p}^n \mathcal{L}_k^n(p.i) & \text{if } 1 \notin p; \\ \mathcal{L}_k^n(p) = N^{-1}(\bar{p} :: \overline{\mathcal{L}_{k-1}^{n-\ell}}) \triangleright \mathcal{L}_k^n(p.([1, n] \setminus p)) & \text{if } 1 \in p. \end{cases} $$

Furthermore, for all $\alpha, \beta \in [n] \setminus p$ satisfying $\alpha < \beta$, if $1 \notin p$, we have

$$ \mathcal{L}_k^n(p.([\alpha, \beta] \setminus p)) = \triangleright_{\substack{i=\alpha \\ i \notin p}}^{\beta} \mathcal{L}_k^n(p.i). $$

**Theorem 59.** The total order over $\mathcal{L}_k^n$ induced by the decomposition of Propositions 58 is the lexicographic order over $\mathcal{L}_k^n$.

Decompositions for Lah partitions coincide with Stirling partitions ones, Algorithm 1 hence lexicographic unranking algorithm for Stirling partitions can be adapted for Lah partitions. Concretely, calling **Unranking**(n,k,r,Lah,U) (where Lah(n,k) returns $\lfloor n \rfloor$ and U(n,k,l,α,β) returns the appropriate value among $L_{1k}^n(p'.[[\alpha, \beta]])$ and $L_{2k}^n(p'.[[\alpha, \beta]])$) produces the unranking of Lah partitions. Moreover, because the counting formulas for Lah partitions depend essentially on the prefix length rather than its precise content, we can replace the binary search performed by **nextBlock** in Algorithm 1 with a constant-time selection. (See lines 20 and 25 of the following algorithm and the while loop starting at line 8 of Algorithm 1.) Substituting **nextBlock** with **nextBlockLah** therefore yields a specialized and more efficient lexicographic unranking algorithm for Lah partitions.

<caption>**Algorithm 2** Function NextBlock for the Lah Partitions</caption>

1: **function** NBPREFIXEDLAH(n, k, size)
2:     **return** $\lfloor \frac{n-(size-1)}{k} \rfloor$ - (n - size) $\lfloor \frac{n-size}{k} \rfloor$
3: **function** NEXTBLOCKLAH(n, k, r)
4:     block := [] 20: else
5:     size := 1 21: r := r - s₁
6:     contains1 := false 22: sᵢ₁ := $\lfloor \frac{n-size}{k} \rfloor$
7:     s₁ := NBPREFIXEDLAH(n, k, size) 23: elt, r := DivMod(r, sᵢ₁)
8:     **while** true **do** 24:         Append(block, elt + 2)
9:     if not contains1 **then** 25:         size := size + 1
10:    if r < s₁ **then** 26:         s₁ := NBPREFIXEDLAH(n, k, size)
11:    L := $\lfloor \frac{n-size}{k-1} \rfloor$ 27: else
12:    Append(block, 1) 28:         elt, r := DivMod(r, s₁)
13:    if r < L **then** 29:         Append(block, elt + 1)
14:    **return** (block, r) 30:         L := $\lfloor \frac{n-size}{k-1} \rfloor$
15:    **else** 31:         if r < L **then**
16:        r := r - L 32:             return (block, r)
17:        size := size + 1 33:             r := r - L
18:        contains1 := true 34:             size := size + 1
19:    s₁ := NBPREFIXEDLAH(n, k, size) 35:         s₁ := NBPREFIXEDLAH(n, k, size)

<footnote>DivMod(n, p) returns the quotient and remainder of dividing n by p.</footnote>
### 3.2.4 Ordered Lah partitions

The lexicographic unranking algorithm for ordered Lah partitions is identical to that for Lah partitions. However, whereas the lexicographic counting formulas for classical Lah partitions depend only on the prefix length and whether it contains 1, the formulas for ordered Lah partitions are independent of the prefix content entirely. Consequently, calling `Unranking(n,k,r,OrderedLah,U)` (where `OrderedLah(n,k)` returns `[n]` and `U(n,k,l,α,β)` returns the value of $Q_k^n(p'.[α,β])$ for a prefix $p'$ of length 1) produces the lexicographic unranking of ordered Lah partitions.

### 3.2.5 Integer partitions

The lexicographic unranking algorithm for integer partitions relies on Proposition 41, whose proof directly yields the following lexicographically compatible decomposition.

**Proposition 60.** Let $1 \le k' \le k$, and $n' \le n$ be integers. Let $p = p'.\alpha \in \mathcal{I}_{k'}^{n'}. We denote by $\Delta_n$ the quantity $n - n'$ and by $\Delta_k$ the quantity $k - k'$. We have

$$ \bar{\mathcal{I}}_k^n(p) = \mathrel{\triangleright}_{i=\alpha}^{\Delta_n-(\Delta_k-1)} \bar{p} :: \bar{\mathcal{I}}_{\Delta_k-1}^{\Delta_n-\Delta_k(\alpha-1)}(i). $$

This decomposition allows us to build an integer partition from left to right by determining each part one by one.

<caption>**Algorithm 3** LEXICOGRAPHIC UNRANKING ALGORITHM FOR INTEGER PARTITIONS</caption>

1: **function** UNRANKINGINTPART(n, k, r)
2: acc := []
3: last_elt := 2
4: **if** k = n **then** return [1, 1, ..., 1] (k times)
5: **if** k = 1 **then** return [n]
6: **if** r < p(n - 1, k - 1) **then**
7: acc := [1]
8: last_elt := 1
9: n := n - 1
10: k := k - 1
11: **else**
12: r := r - p(n - 1, k - 1)
13: **for** i = 1 to k **do**
14: **for** j = last_elt to n - k + 1 **do**
15: s := p(n - j - (k - 1)(j - 1), k - 1)
16: **if** r < s **then**
17: Append(acc, j)
18: n := n - j
19: k := k - 1
20: last_elt := j
21: **break**
22: **else**
23: r := r - s
24: **return** acc

## 3.3 Implementation, experiments and complexity analysis

In this section, we discuss optimizations and implementation choices for the unranking algorithms presented in the previous section. For each family of partitions, we compare different implementations experimentally and theoretically analyze the time and space complexity of the best implementation. Furthermore, we compare the performance of our lexicographic unranking algorithms with that of the unranking algorithms based on combinatorial orders. We conduct these experiments on a MacBook Air with an Apple
M3 CPU at 4.05 GHz and 24 GB of RAM LPDDR5 at 6400 MT/s<fnref n="4" />. Our first idea was to implement our unranking algorithm in Python since in this language, the int type supports arbitrary-precision integers natively. However, preliminary experiments revealed that for the Lah and Stirling partitions, we needed to implement efficient caching mechanisms to save as much memory as possible. Indeed, for implementing the unranking algorithms for Stirling-related partitions, we relied on multicore parallelism to compute the Stirling numbers. However the Global Interpreter Lock (GIL) in Python allows concurrency but not true parallelism in multithreaded programs. Consequently, we opted for Go, which provides efficient support for concurrent and parallel programming, along with the Big.Int library. For Lah-related partitions, the unranking algorithms are much faster than the ones for Stirling-related partitions so we could handle bigger inputs. However, Python recursion limits made our algorithm crash for n = 12000 even after increasing the recursion limit. Thus, we also implemented the unranking algorithm for Lah partitions in Go to handle larger inputs. For integer partitions, none of these issues arose, so we kept the Python implementation for its readability and the cache management provided by the functools library. The interpreter used is PyPy 7.3.17, which significantly improves execution time compared to the standard Python interpreter.

### 3.3.1 Stirling-related partitions

The core of the unranking algorithm for Stirling-related partitions cannot be modified without altering the overall behavior of the algorithm. However, some flexibility remains in implementing certain parts of the algorithm. The Stirling numbers of the second kind are used extensively in the unranking algorithms for Stirling-related partitions, and there are several ways to compute them, each with its own advantages and disadvantages.

1. The first approach is to use the explicit formula for Stirling numbers of the second kind: $\binom{n}{k} = \frac{1}{k!} \sum_{j=0}^{k} (-1)^{k-j} \binom{k}{j} j^n$ each time one is needed. The main drawback of this method is that it adds an extra linear factor (in k, for arithmetic operations on big integers) to the time complexity of the unranking algorithm.

2. The second approach is to store all Stirling numbers in a dynamic programming matrix using the recurrence relation stated in Fact 6. This method sacrifices memory efficiency to provide the best execution time for the unranking algorithm.

Another degree of freedom in implementing the algorithms for Stirling-related partitions concerns the implementation of the counting formulas $S_k^n(p'.[[\alpha, \beta]])$ and $T_k^n(p'.[[\alpha, \beta]])$.

Indeed, there exists another way to compute the value of $S_k^n(p'.[[\alpha, \beta]])$ using a sum that involves a different number of terms than the one presented in Proposition 34:

*Remark 61.* Let $1 \le k \le n$ be two positive integers. Let $p'$ be a length $\ell - 1$ prefix of a

<footnote n="4">⁴Since Apple does not provide official specifications on RAM or CPU frequencies, the specifications listed above are based on independent experimental measurements.</footnote>
partition in $\mathcal{P}_k^n$. Let $\alpha \in [n] \setminus p'$. We have:

$$S_k^n(p) = \sum_{u=0}^{\min(n-\ell-k+1, \alpha)} (-1)^u \binom{n-\ell+1-u}{k} \binom{\alpha-\ell}{u}.$$

The proof of this remark is straightforward by recurrence.

Each of these formulas is a sum of big integers with a different number of terms. We pick the formula with fewer terms to optimize the unranking algorithm's time complexity. From preliminary experiments, the best way to implement Algorithm 1 for Stirling-related partitions is to use method 2 for computing Stirling numbers, paired with the counting formula of Proposition 34 or 61, whichever yields the shorter sum.

This choice increases memory usage because it stores many Stirling numbers. We reduce memory by caching only the Stirling numbers actually needed during execution in a hash map instead of a full dynamic programming (DP) matrix. A further memory improvement, without harming runtime, comes from noting that generating the $k^{th}$ block of a Stirling-related partition requires only the $(k-1)^{th}$ column of the Stirling DP matrix. We therefore keep only two columns at a time and compute the $k^{th}$ column in parallel while unranking the $k^{th}$ block.

In Figure 1, the first curve depicts execution time for these implementations as $n$ increases, with $k = \lfloor n/\ln(n) \rfloor$ held fixed, while the second curve shows execution time when supplying $S_k^n$ values, with Stirling numbers computed in parallel as described above.

<figure><img src="image_4.png" /><figcaption>Figure 1: Average execution time for unranking Stirling partitions using different methods to provide Stirling numbers.</figcaption></figure>

In practice, we unranked a Stirling partition of size $n = 3000$ into $k = 375 \approx n/\ln(n)$ blocks and measured memory consumption for different implementations:

* The dynamic-programming-matrix approach consumes about 20 GB of RAM.

* The hash-map approach consumes about 2.5 GB of RAM.
• The two-column parallel approach consumes only about 30 MB of RAM.

Figure 2 takes advantage from the second formula for $S_k^n(p)$ established in Proposition 61.

<figure><img src="image_5.png" /><figcaption>Figure 2: Average execution time for unranking Stirling partitions using different methods to provide $S_k^n$.</figcaption></figure>

In the rest of the section, we will analyze the worst case time and space complexity using the parallel implementation of the unranking algorithm for Stirling-related partitions.

**Theorem 62.** For the time complexity, the algorithm UNRANKING, of a set-partition of $n$ in $k$ blocks, has a bit-complexity bounded by

$$O\left(\frac{(n-k)^3 M(n)}{n} \ln n \log k + \frac{k(n-k)^2 M(n)}{n} \ln n \log\left(\frac{n \cdot e}{k}\right)\right),$$

where $M(n)$ is the bit complexity for the multiplication of two numbers, each one containing $n$ bits.

Recall the naïve multiplication algorithm satisfies $M(n) = \Theta(n^2)$. But using, for example, Karatsuba algorithm, we obtain $M(n) = \Theta(n^{\log 3})$ for the time complexity. In Go<fnref n="5" />, as soon as integers are greater than $2^{40}$, Karatsuba multiplication algorithm is used. In our context, almost all cases are thus based on the latter algorithm.

*Proof.* We study the worst case with large $n$ and $k$ ranging over $\llbracket n \rrbracket$, using the bit-complexity approach of [9, Section 4.3]. We bound the cost in the central range of Stirling numbers of the second kind, which occurs when $k = \Theta(n/\ln n)$ as $n \to \infty$ (see also [12]). Storing one Stirling number requires $\log \binom{n}{k}$ bits, and it is multiplied by binomial coefficients with at most $n$ bits. We therefore group Stirling numbers into $n$-bit blocks so multiplications involve operands of similar size, yielding a time bound of $\log \binom{n}{k}/n \cdot M(n)$. Repeated binary searches make $O((n-k) \ln n)$ calls to $S$. Finally combining these bounds gives the stated bit-complexity. □

<footnote n="5">⁵Go documentation for `big integers` manipulations.</footnote>
**Theorem 63.** For the space complexity, the parallel algorithm UNRANKING, of a set-partition of $n$ in $k$ blocks, has a bit-complexity bounded by

$$O((n-k)(kn \ln(n) + n(n-4k+1) \ln(k))).$$

*Proof.* At each step of the unranking algorithm, we store a constant number of columns of the Stirling dynamic-programming matrix. In our implementation in Go, this constant is less than 4. Each column contains at most $n-k$ Stirling numbers. Fact 7 gives an upper bound on the size of each Stirling number. Summing this bound over $n$ gives the stated bit complexity. □

### 3.3.2 Lah-related partitions

As with Stirling-related partitions, the main implementation choice for Lah-related partitions is how to supply the Lah numbers. We evaluated four approaches:

1. Compute $\lfloor n/k \rfloor = \left(\frac{(n-1)!}{k!}\right)^2 \cdot nk \cdot \frac{1}{(n-k)!}$ on demand. This is memory efficient but slows the unranking algorithm because nothing is cached.

2. Compute $\lfloor n/k \rfloor = \binom{n-1}{k-1} \cdot \frac{n!}{k!}$ on demand, caching binomial coefficients. This uses more memory, but runtime improves by a factor of about 2.5 compared with method 1.

3. Cache every Lah number actually needed during execution via the recurrence in Fact 14. This maximizes speed at the cost of memory.

4. Reuse the explicit formula from method 1 but cache all factorials. This keeps memory low (storing $n$ big integers instead of the $n \cdot k$ needed by method 3) yet still runs slower than method 3, though faster than methods 1 and 2.

To choose the best implementation, we measured in Table 3 and the figures following it, which method generates the largest partitions on a personal computer. For each method, we unrank partitions in $\mathcal{L}_{\lfloor \sqrt{n+1} \rfloor}^n$ for increasing $n$ until either RAM exceeds 16 GB or user time per generation exceeds 250 ms. These thresholds are arbitrary but reasonable for a desktop setup. We did not enforce them for Stirling-related partitions because that algorithm is much slower; dropping the limits let us generate partitions large enough for our Stirling experiments. The following curves report the Lah results.
<figure><img src="image_6.png" /><figcaption>Figure 3: Average execution time for unranking Lah partitions using different methods to provide Lah numbers.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Table 3: Comparative memory usage for unranking Lah partitions (left: Comparison between all methods, right: Zoom on the behavior of the 3 methods with less memory consumption).</figcaption></figure>

Method 3 generates the largest Lah-related partitions within our memory and time constraints. While it performs well for large partitions, its memory footprint can be prohibitive for some applications. Unlike with Stirling-related partitions, parallel computing cannot reduce memory consumption here without sacrificing speed: generating the $k^{th}$ block of a Lah partition is much faster than computing the $k^{th}$ column of the Lah dynamic-programming matrix. To reduce cache size by a factor $c$, we store only those $\lfloor n/k \rfloor$ where $n \bmod c = 0$ and recompute the rest using the recurrence (Fact 14).
<figure><img src="image_8.png" /><figcaption>Figure 4: Average execution time for un-ranking Lah partitions using a reduced cache for Lah numbers.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Figure 5: Comparative memory usage for unranking Lah partitions using a reduced cache for Lah numbers.</figcaption></figure>

For unordered Lah partitions, Figure 3 shows that lexicographic and combinatorial unranking have similar performance. For ordered Lah partitions, however, the lexicographic algorithm is significantly faster. Transitioning from unordered to ordered Lah partitions removes a constraint tied to the canonical form in lexicographic order but introduces an additional term in combinatorial order, forcing an extra big-integer division in the combinatorial-order algorithm. The following curve illustrates this difference:

<figure><img src="image_10.png" /><figcaption>Figure 6: Average execution time for unranking ordered Lah partitions using the combinatorial and the lexicographic order.</figcaption></figure>

**Proposition 64.** The worst case time complexity of the algorithm UNRANKING for Lah-related partitions, of a set-partition of n in k blocks, has a bit-complexity bounded by

$$O((n-k) \cdot D(n \log(n)) + n \cdot M(n \log(n)))$$
where $D(n)$ is the bit complexity for the division of two numbers, each one containing $n$ bits and $M(n)$ is the bit complexity for the multiplication of two numbers, each one containing $n$ bits.

In our implementation in Go, the division of big integers is performed using a quadratic algorithm.

*Proof.* The algorithm calls NEXTBLOCKLAH (cf Algorithm 2) once per block ($k$ times total). This function contains a while loop that determines one block element per iteration. Each element requires a division of two large integers and a multiplication of integers with bit sizes $\log(n)$ and $n \log(n)$, except the smallest element, determined with only a multiplication. Thus, the bit-complexity is bounded by the stated upper bound $O((n-k) \cdot D(n \log(n)) + n \cdot M(n \log(n)))$. $\square$

### 3.3.3 Integer partitions

Unlike set partitions, integer partitions offer no significant implementation choices for their unranking algorithm, since only the recurrence relation in Fact 22 is known for counting integer partitions with exactly $k$ parts. However, Ruskey [21] proposes ideas for unranking algorithm that generates integer partitions with a fixed number of parts in reverse lexicographic order and reverse canonical form (summands in decreasing order). By reversing the summand order to increasing, we obtain a lexicographic unranking algorithm comparable to ours. For convenience, the algorithm derived from Ruskey's ideas is implemented in the accompanying code repository under the name `rev mirror rev can`. The following curves illustrate the results of these experiments$^6$.

<figure><img src="image_11.png" /><figcaption>Figure 7: Average time to generate one part of an integer partition using our lexicographic unranking algorithm.</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>Figure 8: Average execution time for unranking integer partitions using the ideas from [21] and our lexicographic unranking algorithm, for fixed $n$ and $k$ ranging from 1 to $n$.</figcaption></figure>

<footnote>$^6$In Figure 8 we note the existence of some peaks that are induced by cache management from Pypy.</footnote>
<figure><img src="image_13.png" /><figcaption>Figure 9: Average execution time for un-ranking $r$ integer partitions in $k$ parts for $k$ ranging from 1 to $n$ for $n$ ranging from 1 to 1000 with $r = c \frac{p(n,k)}{p(n)}$ with $c \in \mathbb{N}^*$.</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>Figure 10: Average execution time for un-ranking integer partitions using the ideas from [21] and our lexicographic unranking algorithm.</figcaption></figure>

These experiments show that the worst case occurs when $k$ is close to $n$, and that the average time to generate one part is proportional to the size of the last part. The Ferrers diagram serves as a classical representation of an integer partition, with its height corresponding to the size of the maximal part. Preliminary experiments involving binary search in the inner loop resulted in degraded performance, as consecutive parts of an integer partition typically differ by only small amounts. We will now formalize this observation and analyze the complexity of our lexicographic unranking algorithm for integer partitions.

**Theorem 65.** Let $1 \le k \le n$ be two positive integers. The worst case time complexity of the algorithm UNRANKINGINTPART, of a integer partition of $n$ in $k$ parts, has a bit-complexity bounded by

$$O(\sqrt{n}(k + h(p))),$$

where $h(p)$ is the height of the Ferrers diagram of the partition $p$ being generated.

The intuition behind the algorithm's operation is not immediate due to the technical calculations required for efficiency. However, the key concept involves determining each part sequentially, in increasing size (i.e., lexicographic order of the canonical representation). As the parts increase, the full partition is determined by calculating its upper envelope, corresponding the height of each part in the Ferrers diagram, and thus, once a part if computed, the calculation of the next one needs only to determine the difference from the previous one.

*Proof.* The algorithm UNRANKINGINTPART consists of two nested loops: an outer loop that iterates once for each partition part, and an inner loop that iterates once for each unit difference between consecutive parts. Both loops are necessary to eventually increase the part under consideration. The outer loop executes $k$ iterations, while the inner loop is constrained by the height of the Ferrers diagram, $h(p)$. Each iteration performs a linear operation on integers of size $O(\sqrt{n})$ (c.f. Proposition 23), resulting in the stated bit-complexity bound $O(\sqrt{n}(k + h(p)))$. $\square$
In practice, our algorithm seems to achieve linear complexity in $n$ for all values of $k$. There are several reasons for this behavior. First, the largest values for $p(n, k)$, when $k$ in ranging in 0 to $n$ contain $\sqrt{n}$ digits, which is relatively small compared to the size of the previous set partitions we considered. Second, as proved by Erdös in [7], the peak for integer partition numbers ($k$ varying) is very narrow, meaning that for most $k$ the values of $p(n, k)$ are relatively small in front of their maximum.

<figure><img src="image_15.png" /><figcaption>Figure 11: Average execution time for unranking integer partitions using our lexicographic unranking algorithm for different values of $k$.</figcaption></figure>

## 3.4 Free extension of our unranking algorithms

The method presented in this article can be adapted to other families of partitions without significant changes. The remaining problems are the problems related to set partitions in a non fixed number of blocks which are Problems 1.b, 5.a and 5.b of Table 1. The Problem 1.b is known under the name of Bell partitions. For this family, we get the following decomposition:

**Proposition 66.** Let $1 \le k \le n$ be two positive integers. Let $p'$ be a length $\ell - 1$ increasing sequence of integers starting with 1. Let $\alpha \in [n] \setminus p'$. Let $\mathcal{U}_k^n(p' \cdot \alpha)$ be the set of Bell partitions of $[n]$ in at most $k$ blocks whose prefix is $p' \cdot \alpha$. We have:

$$ \mathcal{U}_k^n(p' \cdot \alpha) = N^{-1}(\bar{p} :: \bar{\mathcal{U}}_{k-1}^{n-\ell}) \triangleright \mathcal{U}_k^n(p' \cdot \alpha \cdot [\alpha + 1, n]) $$

With the convention that $\mathcal{U}_k^0 = \emptyset$.

This decomposition leads straightforwardly to the following counting formula.

**Proposition 67.** Let $1 \le k \le n$ be two integers. Let $\ell$ and $d$ be two integers such that either $\ell = d = 1$ or $1 < \ell \le d$. Let $\mathcal{U}_k^n(p)$ be the number of Bell's set partitions in $\mathcal{U}_k^n$
whose prefix is p of length ℓ and whose greatest element in the prefix is α. We have:

$$U_k^n(p) = \sum_{u=0}^{\min(n-k-\ell+1, n-\alpha)} \sum_{i=1}^{k} \begin{Bmatrix} n-\ell-u \\ i-1 \end{Bmatrix} \begin{pmatrix} n-\alpha \\ u \end{pmatrix}.$$

By calling **Unranking(n,k,r,Bell,U)** (where **Bell(n,k)** returns $B(n,k)$ and the function **U(n,k,l,α,β)** returns the value of $U_k^n(p'.[[α,β]])$ for a prefix $p'$ of length 1) produces the lexicographic unranking of Bell partitions.

The Problem 5.b is the equivalent of Bell partitions for Lah partitions. The same reasoning leads to the following decomposition:

**Proposition 68.** Let $1 \le k \le n$ be two positive integers. Let $p$ be a length $ℓ$ sequence of integers. We denote by $\mathcal{L}_{\le k}^n(p)$ the set of Lah partitions of $[[n]]$ in at most $k$ blocks whose prefix is $p$. We have:

$$\left\{ \begin{array}{ll} \mathcal{L}_{\le k}^n(p) = \mathrel{\triangleright}^{n}_{i=1, i \notin p} \mathcal{L}_{\le k}^n(p.i) & \text{if } 1 \notin p; \\ \mathcal{L}_{\le k}^n(p) = N^{-1}(\bar{p} :: \overline{\mathcal{L}_{\le k-1}^{n-\ell}}) \mathrel{\triangleright} \mathcal{L}_{\le k}^n(p.([1,n] \setminus p)) & \text{if } 1 \in p. \end{array} \right.$$

Furthermore, for all $α, β \in [[n]] \setminus p$ satisfying $α < β$, if $1 \notin p$, we have

$$\mathcal{L}_{\le k}^n(p.([\alpha, \beta] \setminus p)) = \mathrel{\triangleright}_{\substack{i=\alpha \\ i \notin p}}^{\beta} \mathcal{L}_{\le k}^n(p.i).$$

By replacing $\lfloor n \rfloor$ by $\sum_{i=1}^k \lfloor n \rfloor$ in the counting formulas of Section 2 for Lah partitions, we obtain the lexicographic counting formulas for this family. The same modifications in the unranking algorithm for Lah partitions lead to the lexicographic unranking algorithm for Lah partitions in at most $k$ blocks. For the Problem 5.a, the reasoning is similar and the implementation can be found in the accompanying code repository.
# Acknowledgements

Both authors received support from ANR-FWF project PANDAG ANR-23-CE48-0014-01 and from ANR project COMETA-GAE ANR-25-CE48-0602.

# References

[1] N. Ali, A. Shamoon, N. Yadav, and T. Sharma. Peptide Combination Generator: a Tool for Generating Peptide Combinations. *ACS Omega*, 5(11):5781–5783, 2020.

[2] O. Bodini, A. Genitrini, C. Mailler, and M. Naima. Strict monotonic trees arising from evolutionary processes: Combinatorial and probabilistic study. *Advances in Applied Math.*, 133:102284, 2022.

[3] K. P. Bogart. *Combinatorics Through Guided Discovery*. Open Textbook Library, 2004.

[4] A. Curiel. Unranking of partitions. https://github.com/AMAURYCU/Unranking_of_partitions, 2025. Accessed: 2025-11-12.

[5] A. Curiel and A. Genitrini. Lexicographic Unranking Algorithms for the Twelvefold Way. In *35th International Conference on Probabilistic, Combinatorial and Asymp-totic Methods for the Analysis of Algorithms (AofA 2024)*, volume 302 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 17:1–17:14, 2024.

[6] G. L. Devi, Ch. Suneetha, M. Suresh, and S. Sarvalakshmi. Comprehensive Review of Catalan Number-Based Cryptographic Systems in Modern Encryption Focusing on Security, Performance, and Implementation Challenges. *International Journal of Applied Mathematics*, 38:505–526, 09 2025.

[7] P. Erdös and J. Lehner. The distribution of the number of summands in the partitions of a positive integer. *Duke Mathematical Journal*, 8:335–345, 1941.

[8] P. Flajolet and R. Sedgewick. *Analytic Combinatorics*. Cambridge University Press, USA, 1 edition, 2009.

[9] A. Genitrini and M. Pépin. Lexicographic Unranking of Combinations Revisited. *Algorithms*, 14(3), 2021.

[10] R. L. Graham, D. E. Knuth, and O. Patashnik. *Concrete Mathematics: A Foundation for Computer Science*. Addison-Wesley, Reading, MA, second edition, 1989.

[11] D. E. Knuth. *The Art of Computer Programming, Volume 4A, Combinatorial Algorithms*. Addison-Wesley Professional, 2011.

[12] G. Louchard. Asymptotics of the Stirling numbers of the second kind revisited. *Applicable Analysis and Discrete Mathematics*, 7(2):193–210, 2013.

[13] T. Mansour. *Combinatorics of Set Partitions*. Discrete Mathematics and Its Applications. Taylor & Francis, 2012.
[14] C. Martínez and X. Molinero. An experimental study of unranking algorithms. In *International Workshop on Experimental and Efficient Algorithms*, pages 326–340. Springer, 2004.

[15] I. Mező. *Combinatorics and Number Theory of Counting Sequences*. CRC Press, 2020.

[16] A. F. Myers. *k-out-of-n*:G System Reliability With Imperfect Fault Coverage. *IEEE Transactions on Reliability*, 56(3):464–473, 2007.

[17] A. Nijenhuis and H. S. Wilf. *Combinatorial algorithms*. Computer science and applied mathematics. Academic Press, New York, NY, 1975. [Second edition (1978) available on the author's website].

[18] G. Nyul and G. Rácz. The r-Lah numbers. *Discrete Mathematics*, 338(10):1660–1666, 2015.

[19] B.C. Rennie and A.J. Dobson. On stirling numbers of the second kind. *Journal of Combinatorial Theory*, 7(2):116–121, 1969.

[20] J. Riordan. *An Introduction to Combinatorial Analysis*. Wiley publication in mathematical statistics. Wiley, 1958.

[21] F. Ruskey. Combinatorial Generation, 2003.

[22] E. Russo, M. Palesi, S. Monteleone, D. Patti, A. Mineo, G. Ascia, and V. Catania. Dnn model compression for iot domain-specific hardware accelerators. *IEEE Internet of Things Journal*, 9(9):6650–6662, 2022.

[23] Y. Shablya, D. Kruchinin, and V. Kruchinin. Method for Developing Combinatorial Generation Algorithms Based on AND/OR Trees and Its Application. *Mathematics*, 8(6):962, 2020.

[24] T. Yu, P. Mascagni, J. Verde, J. Marescaux, D. Mutter, and N. Padoy. Live laparoscopic video retrieval with compressed uncertainty. *Medical Image Analysis*, 88:102866, 2023.
This appendix gathers the auxiliary material referenced in Section 3.1 and Section 3. Each part starts with a short pointer to the relevant result in the main text so that readers can navigate back and forth easily.

Reading guide.

• Section A: worked example for the combinatorial order supporting Theorem 54.

• Section B: numerical unranking trace for Proposition 56.

A Appendix related to the combinatorial order for Stirling partitions

This section spells out the recursive decomposition that underpins Section 3.1: we fully order $P_3^5$ using the construction formalized in Theorem 54.

In the following, we exhibit the recursive structure of the decomposition of the Stirling 3-partitions of $\llbracket 5 \rrbracket$:

<table><tr><td>13/24/5</td><td>14/23/5</td><td>1/23/45</td><td>123/4/5</td><td>13/2/45</td></tr><tr><td>145/2/3</td><td>1/24/35</td><td>1/234/5</td><td>12/34/5</td><td>15/23/4</td></tr><tr><td>1/2/345</td><td>14/2/35</td><td>1/235/4</td><td>15/2/34</td><td>124/3/5</td></tr><tr><td>134/2/5</td><td>14/25/3</td><td>135/2/4</td><td>12/35/4</td><td>12/3/45</td></tr><tr><td>125/3/4</td><td>15/24/3</td><td>1/25/34</td><td>1/245/3</td><td>13/25/4</td></tr></table>

Using this decomposition, we establish an order on Stirling 3-partitions: those with 5 as a singleton block come first, followed by those with 5 in the first block, then the second block, and finally the third block.

<table><thead><tr><th>5 is the last block</th><th>5 in the first block</th><th>5 in the second block</th><th>5 in the third block</th></tr></thead><tbody><tr><td>13/24/5</td><td>145/2/3</td><td>1/235/4</td><td>1/23/45</td></tr><tr><td>14/23/5</td><td>15/23/4</td><td>14/25/3</td><td>13/2/45</td></tr><tr><td>123/4/5</td><td>15/2/34</td><td>12/35/4</td><td>1/24/35</td></tr><tr><td>1/234/5</td><td>135/2/4</td><td>1/25/34</td><td>1/2/345</td></tr><tr><td>12/34/5</td><td>125/3/4</td><td>1/245/3</td><td>12/3/45</td></tr><tr><td>124/3/5</td><td>15/24/3</td><td>13/25/4</td><td>14/2/35</td></tr><tr><td>134/2/5</td><td></td><td></td><td></td></tr></tbody></table>

The order is not yet a total order. Indeed, two partitions in the same column are at this step incomparable. We distinguish them by applying recursively the same reasoning after having avoided the element 5 in each partition, thus reasoning about $P_2^4$ for the first column and about $P_3^4$ for the other ones. In the next table if an element $\alpha$ appear on the left of an element $\beta$ in a column, then $\alpha$ is smaller than $\beta$. Furthermore, if two elements
are in the same column but in different cells, the upper one is smaller than the lower one.

<table><thead><tr><th>5 is the 3<sup>rd</sup> block</th><th>5 in the 1<sup>st</sup> block</th><th>5 in the 2<sup>nd</sup> block</th><th>5 in the 3<sup>rd</sup> block</th></tr></thead><tbody><tr><td>4 is the 2<sup>nd</sup> block</td><td>4 is the 3<sup>rd</sup> block</td><td>4 is the 3<sup>rd</sup> block</td><td>4 is the last block</td></tr><tr><td>123/4/5</td><td>15/23/4</td><td>1/235/4</td><td>1/23/45</td></tr><tr><td>4 is in the 1<sup>st</sup> block</td><td>135/2/4</td><td>12/35/4</td><td>13/2/45</td></tr><tr><td>14/23/5</td><td>125/3/4</td><td>13/25/4</td><td>12/3/45</td></tr><tr><td>124/3/5</td><td>4 is in the 1<sup>st</sup> block</td><td>4 is in the 1<sup>st</sup> block</td><td>4 is in the 1<sup>st</sup> block</td></tr><tr><td>134/2/5</td><td>15/2/34</td><td>14/25/3</td><td>14/2/35</td></tr><tr><td>4 is in the 2<sup>nd</sup> block</td><td>4 is in the 2<sup>nd</sup> block</td><td>4 is in the 2<sup>nd</sup> block</td><td>4 is in the 2<sup>nd</sup> block</td></tr><tr><td>12/34/5</td><td>15/24/3</td><td>1/245/3</td><td>1/24/35</td></tr><tr><td>13/24/5</td><td>4 is in the 3<sup>rd</sup> block</td><td>4 is in the 3<sup>rd</sup> block</td><td>4 is in the 3<sup>rd</sup> block</td></tr><tr><td>1/234/5</td><td>15/2/34</td><td>1/25/34</td><td>1/2/345</td></tr></tbody></table>

By recursively repeating this process until only one element remains in each cell, we obtain the following order which is the order described by the combinatorial interpretation of the Stirling numbers (see proof of Fact 6).

<table><tbody><tr><td>RANK</td><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td></tr><tr><td>Partition</td><td>123/4/5</td><td>124/3/5</td><td>134/2/5</td><td>14/23/5</td><td>12/34/5</td><td>13/24/5</td></tr><tr><td>RANK</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td><td>11</td></tr><tr><td>Partition</td><td>1/234/5</td><td>125/3/4</td><td>135/2/4</td><td>15/23/4</td><td>145/2/3</td><td>15/24/3</td></tr><tr><td>RANK</td><td>12</td><td>13</td><td>14</td><td>15</td><td>16</td><td>17</td></tr><tr><td>Partition</td><td>15/2/34</td><td>12/35/4</td><td>13/25/4</td><td>1/235/4</td><td>14/25/3</td><td>1/245/3</td></tr><tr><td>RANK</td><td>18</td><td>19</td><td>20</td><td>21</td><td>22</td><td>23</td></tr><tr><td>Partition</td><td>1/25/34</td><td>12/3/45</td><td>13/2/45</td><td>1/23/45</td><td>14/2/35</td><td>1/24/35</td></tr><tr><td>RANK</td><td>24</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>Partition</td><td>1/2/345</td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>

In this table, we see that the first ${}^4_2$ = 7 partitions have 5 in their last block, while the next ${}^4_3$ = 6 partitions place 5 in one of the first blocks. Partitions ranked from 19 to 23 have 5 in their second block, and the remaining ones place 5 in their third block alongside another element.

## B Appendix related to the ordered Stirling partitions

This worked example continues the construction presented in Section 3. It traces the dichotomic decomposition of Proposition 56 on a concrete rank.

As an illustration, consider unranking $p$, the 20000-th ordered Stirling partition of $\llbracket 8 \rrbracket$ into 4 blocks. First, determine the first element of the first block. By the first equality in Proposition 56, this element is less than 4 because $20000 < \sum_{i=1}^4 T_4^8([i]) = 29724$. Using the same equality with $n = 8$, $k = 4$, $\alpha = 1$, and $\beta = 2$, it must exceed 2 because $20000 > \sum_{i=1}^2 T_4^8([i]) = 18312$. The only remaining option is 3. We then check whether the first block is complete via the second equality of Proposition 56; computing $O_{4-1}^{8-1} =$
1806 shows the block is complete since $20000 < 1806 + 18312$. Next, we seek the 1688-th ordered partition of $\llbracket 7 \rrbracket$ into 3 blocks; applying the same process shows the second block is 7. We then seek the $(1688 - 1652) = 36$-th ordered partition of $\llbracket 6 \rrbracket$ into 2 blocks. We discard candidates whose first element exceeds 4 or 3 because $36 < T_2^6([3, 4]) < T_2^6([4, 7])$, and we conclude that the first element is 2 since $36 > T_2^6([1, 2])$. The second equality of Proposition 56 shows this first block is not complete. Continuing in this manner yields the final partition $p = \llbracket 3 \rrbracket, \llbracket 7 \rrbracket, \llbracket 2, 4, 5, 8 \rrbracket, \llbracket 1, 6 \rrbracket$.