# Non-commutative Frobenius characteristic of generalized parking functions

Jean-Baptiste Priez, Aladin Virmaux

► To cite this version:

Jean-Baptiste Priez, Aladin Virmaux. Non-commutative Frobenius characteristic of generalized parking functions: Application to enumeration. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.733-744, 10.46298/dmtcs.2504. hal-01337778

HAL Id: hal-01337778

https://hal.science/hal-01337778

Submitted on 27 Jun 2016

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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Non-commutative Frobenius characteristic of
generalized parking functions
Application to enumeration

Jean-Baptiste Priez† and Aladin Virmaux‡

LRI, Université Paris-Sud, Orsay, France

**Abstract.** We give a recursive definition of generalized parking functions that allows them to be viewed as a species. From there we compute a non-commutative characteristic of the generalized parking function module and deduce some enumeration formulas of structures and isomorphism types. We give as well an interpretation in several bases of non commutative symmetric functions. Finally, we investigate an inclusion-exclusion formula given by Kung and Yan.

**Résumé.** Nous donnons une définition récursive des fonctions de parking généralisées nous permettant de munir ces dernières d'une structure d'espèce. Nous utilisons ce point de vu pour donner une caractéristique de Frobenius non-commutative du module des fonctions de parking généralisées que nous appliquons afin de donner de nombreuses formules d'énumération de structures et de type d'isomorphismes, ainsi qu'une interprétation dans plusieurs bases des fonctions symétriques non commutatives. Enfin, nous étudions une formule d'inclusion-exclusion provenant de Kung et Yan.

**Keywords:** parking function, species, non-commutative symmetric functions

Introduction

Parking functions were introduced in [KW66] to model hashing problems in computer science and appear
in many different contexts in combinatorics. Generalized parking functions were introduced by Stanley
and Pitman [SP02]. Shortly after, Kung and Yan showed that the Gončarov polynomials form a natural
basis to manipulate generalized parking functions and stated numerous enumeration formulas [KY03].

The (linear span of the) set $\mathcal{F}_n$ of parking functions of length $n$ is naturally a module over the symmetric
group $S_n$ acting on positions. In [NT08] Novelli and Thibon observed that $\mathcal{F}_n$ is also a module over the
0-Hecke algebra $H_n(0)$. This allows us to lift canonically the Frobenius characteristic of $\mathcal{F}_n$, which lives
in the algebra of symmetric functions, as a non commutative Frobenius characteristic in the algebra of non
commutative symmetric functions. They then apply this technology to the non commutative Lagrange
inversion. Implicit in the calculations of [NT08] is the use of a recursive definition of parking functions to
derive functional equations on the Frobenius characteristic.

<footnote>†jean-baptiste.priez@lri.fr</footnote>

<footnote>‡aladin.virmaux@lri.fr</footnote>
In this paper we apply the same representation-theoretic approach to generalized parking functions and derive enumeration formulas such as those of Kung and Yan. A key observation is that generalized parking functions naturally form a species and that this species can be defined recursively.

This paper is organized as follows, beginning with background on species in Section 1, we the define in Section 2 the species $\mathcal{F}(\chi)$ of generalized parking functions. Then we will show that generalized parking functions can be defined recursively, which naturally translates into a functional equation on $\mathcal{F}(\chi)$ (Theorem 2). We derive a closed-form expression for this species by expressing it in terms of the species E of sets.

In Section 3 we apply the previous results to the computation of the non-commutative Frobenius characteristic of the module of parking functions, expressed in the complete basis of non-commutative symmetric functions (Theorem 3.4). From there, we derive new enumeration formulas, then express $ch(\mathcal{F}(\chi))$ in the ribbon and $\Lambda$ basis; the latter admits a nice combinatorial interpretation (Proposition 3.5).

Finally in Section 4 we state and prove an inclusion exclusion formula on the faces of a polytope for generalized parking functions, giving a combinatorial interpretation of [KY03, Theorem 4.2].

# 1 Species

In this paper we use the theory of species [BLL98] to encode the notion of labeled and unlabeled parking functions simultaneously. We recall some definitions and some classical operations for species.

**Definition:** A species $P$ is an endofunctor of the category of sets with bijections into itself. In other terms, $P$ is a rule which produces

* a finite set $P[U]$, for any finite set $U$,

* a function $P[\sigma]$, for any bijection $\sigma: U \to V$.

This function $P[\sigma]$ satisfies the functoriality conditions:

$$P[\tau \circ \sigma] = P[\tau] \circ P[\sigma]; \qquad P[Id_U] = Id_{P[U]},$$

for any bijections $\sigma: U \to V$ and $\tau: V \to W$, and with the identity map $Id_U: U \to U$.

Elements of $P[U]$ are called the $P$-structures on $U$ and functions $P[\sigma]$ are called the transports of $P$-structures along $\sigma$. Two structures $f \in P[U]$ and $g \in P[V]$ have the same isomorphism type if there is a bijection $\sigma: U \to V$ such that $P[\sigma](f) = g$. We denote $P_n$ the species $P$ restricted to sets of cardinality $n$.

**Characteristic species** The species 1 is $1[U] = \{\emptyset\}$ if $U = \emptyset$ and $\emptyset$ in otherwise.

**Species of sets** The species of sets $E$ is defined by $E[U] = \{U\}$, for any finite set $U$ (endowed with the trivial action $U \mapsto \sigma(U)$ for any bijection $\sigma: U \to V$ and any finite set $U$).

Many operations on species allows a direct translation in terms of generating series: addition, multiplication, substitution, etc. These operations constitute combinatorial analogs of the usual operations on series. Here we will only use addition and multiplication. In the sequel, let $P$ and $Q$ be two species.

**Addition** The sum of $P$ and $Q$, noted $P + Q$, is defined by:

$$(P + Q)[U] = P[U] \sqcup Q[U]; \qquad (P + Q)[\sigma](f) = \begin{cases} P[\sigma](f) & \text{if } f \in P[U], \\ Q[\sigma](f) & \text{if } f \in Q[U], \end{cases}$$

for any finite set $U$, any bijection $\sigma: U \to V$ and any $f \in (P + Q)[U]$.
**Product** Similarly the product of species of P and Q, noted P · Q defines ordered pairs of structures $f = (g, h)$:

$$ (P \cdot Q)[U] = \sum_{S \sqcup T = U} P[S] \times Q[T] \qquad (P \cdot Q)[\sigma](f) = (P[\sigma_g](g), Q[\sigma_h](h)), $$

with $\sigma_g$ (respectively $\sigma_h$) the restriction of $\sigma$ to the underlying set of the P-structure $g$ (resp. Q-structure $h$). We denote $P^n$ the product of P with itself $n$ times: $P^n = P \cdots P^{n-1}$ (with $P^1 = P$ and $P^0 = 1$).

## 2 Parking functions

A parking function on finite set $U$ (of cardinality $u$) is a function $f: U \to \mathbb{N}_+$ such that $\#f^{-1}([k]) \ge k$, for any $k \in [u]$. The generalization introduced in [SP02] modifies the condition. Let $\chi: \mathbb{N}_+ \to \mathbb{N}$ be a non-decreasing sequence; the function $f: U \to \mathbb{N}$ is a $\chi$-parking function if $\#f^{-1}([\chi(k)]) \ge k$, for any $k \in [u]$.

**Remark 2.1:** The usual parking functions are $\chi$-parking functions with $\chi: i \mapsto i$, the identity map.

For the following, it will be more convenient to use another equivalent definition. A (generalized) parking function $f: U \to \mathbb{N}_+$ may be described as an ordered sequence of sets $(Q_i)_{i \in \mathbb{N}_+}$ where $Q_i = f^{-1}(i)$. From this definition we remark that the isomorphism types (unlabeled structures) of generalized parking functions are (generalized) Dyck paths, namely a staircase walk under a discrete curve $\chi$. Formally this defines a species:

**Definition 2.2:** The species of $\chi$-parking functions is:

* for any finite set $U$, the set of all sequences $(Q_i)_{i \in \mathbb{N}_+}$ of disjoint subsets of $U$ such that

$$ \sum_{i=1}^{\chi(k)} \#Q_i \ge k \qquad \text{for any } 1 \le k \le u, \qquad (1) $$

* for any bijection $\sigma: U \to V$, the relabeling action is $(Q_i)_{i \mapsto (\sigma(Q_i))}$ (for any $\chi$-parking function on $U$).

This viewpoint on generalized parking functions in terms of sequences reveals a recursive definition. A simple way to put forward the recurrence is to view a generalized parking function $(Q_i)$ as a decorated path/staircase walk defined by: the first tread (horizontal step) goes to $(\#Q_1, 1)$ and is decorated by $Q_1$. The second tread decorated by $Q_2$ starts at $(\#Q_1, 1)$ and goes to $(\#(Q_1 \cup Q_2), 2)$. The third starts where the second ends, goes to $(\#(Q_1 \cup Q_2 \cup Q_3), 3)$ and is decorated by $Q_3$, etc. (see Example 1).

From this graphic representation it is easy to notice that a $\chi$-parking function $(Q_i)$ on $U$ is either a sequence of empty sets if $U = \emptyset$, or a sequence of sets $(Q_i)_{i \in [\chi(1)]}$ of union $S \subseteq U$, concatenated with another generalized parking function on $U \setminus S$ defined from another non-decreasing function $\psi_s$ (See Example 2). This new map is defined by a shift of $\chi$ characterized by the cardinality $s$ of $S$:

$$ \psi_s(m) = \chi(s+m) - \chi(1). $$

In the following, we will implicitly denote by $\psi_n$ the shift of $\chi$ by $n$.

### 2.1 Recursive definition

The recursive splitting described earlier involves a natural constructive definition of the $\chi$-parking functions species in terms of species operations based on the species of sets E.
**Example 1:** Let $\chi$ be the sequence $2, 2, 3, 5, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, \dots$ and it is pictured in red. Let $(Q_i) = (\{d, f, m\}, \{g\}, \{a, h\}, \emptyset, \{c, e, j, k, n, p\}, \emptyset, \emptyset, \emptyset, \{b, i, l, o, q, r, s, t\}, \emptyset)$ be a $\chi$-parking function on $\{a, b, c, \dots, t\}$. The parking function is represented by the decorated blue path.

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

**Theorem 2.3:** The species of $\chi$-parking functions is isomorphic to the species $\mathcal{F}(\chi)$ recursively defined as

$$ \mathcal{F}(\chi) = (\mathbb{E}^{\chi(1)})_0 + \sum_{n \ge 1} (\mathbb{E}^{\chi(1)})_n \cdot \mathcal{F}(\psi_n). \qquad (2) $$

**PROOF:** A generalized parking function $(Q_i)$ is an infinite sequence of disjoint subsets of a finite set $U$ and with $Q_i = \emptyset$ for $i > \chi(u)$, so $(Q_i)$ may be seen as a sequence of length $\chi(u+1)$. The relabeling action is trivially the same. By induction, any $\mathcal{F}(\chi)$-structures satisfies the generalized parking functions condition (1). Finally, any $\chi$-parking functions on $U$ can be divided into factors $D_p = (Q_i)_i$ with $\chi(p-1) < i \le \chi(p)$ for any $p \in [u]$. By induction again, each factor $D_p$ corresponds to a structure on the left term of the sum 2, $((\mathbb{E}^{\psi_{\alpha_p}(1)})_{\beta_p})$ with $\alpha_p = \beta_{p-1}$. ■

Thanks to species theory [BLL98], this constructive definition of the $\chi$-parking functions gives automatically a cycle index series: the series of (commutative) Frobenius characteristic of the natural symmetric group action on $\mathcal{F}_n(\chi)$. Furthermore, the terminal elements of our grammar $(\mathbb{E}^k)_n$ are well-known to be characterized by the *permutational 0-Hecke modules*.

## 2.2 Closed-form equivalent definition

In order to give a closed-form expression of the species $\mathcal{F}(\chi)$ one needs to understand the map $\psi_n$ according to $\chi$. Tracking the recursion of the definition is only about following the different choices of $n$ in (2). This recursive definition is mainly defined by the map $\psi_n$ of equation (2). When expanding $\mathcal{F}(\chi)$, we remark that the map evolves as follows:

$$ \psi_n : m \mapsto \chi(m+n) - \chi(1) $$

$$ \psi'_{n_1} : m \mapsto \chi(m+n+n_1) - \chi(1+n_1) $$

$$ \psi''_{n_2} : m \mapsto \chi(m+n+n_1+n_2) - \chi(1+n_1+n_2) $$

$\vdots$
**Example 2:** Let $(Q_i)$ be the $\chi$-parking function defined in Example 1; it is the concatenation of the sequence of the two first sets $(\{d, f, m\}, \{g\})$ and the $\psi$-parking function $(\{a, h\}, \emptyset, \{c, e, j, k, n, p\}, \emptyset, \emptyset, \emptyset, \{b, i, l, o, q, r, s, t\}, \emptyset)$ on $\{a, b, c, \dots, t\} \setminus \{d, f, g, m\}$ with $\psi$ the sequence 3, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 8, 8, \dots$. In other terms we have $\psi(m) = \chi(m+4) - \chi(1)$.

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

On the other hand each $\psi_n$ is always called with $m = 1$ by definition and each $n$ is always a positive integer. So the sequence $(n, n_1, n_2, \dots)$ is finite sequence of positive integer: a composition $\pi$.

**Definition 2.4:** Let $\pi = \pi_1 \cdots \pi_k$ be a composition of $n$. The map $\Upsilon$ is defined by:

$$ \Upsilon(\chi; \pi, i) = \begin{cases} \chi(1) & \text{if } i=1, \\ \chi(1+\pi(i-1)) - \chi(1+\pi(i-2)) & \text{otherwise.} \end{cases} \quad (3) $$

with $\pi(i) = \pi_1 + \cdots + \pi_i$ the partial sum of the first $i$ parts of $\pi$.

By expanding the recurrence (2) of theorem 2.3 we have:

**Proposition 2.5:**

$$ \mathcal{F}(\chi) = 1 + \sum_{n \ge 1} \mathcal{F}_n(\chi) \quad \text{with} \quad \mathcal{F}_n(\chi) = \sum_{\pi \vdash n} \prod_{i=1}^{\ell(\pi)} (\mathbb{E}^{\Upsilon(\chi; \pi, i)})_{\pi_i}. \quad (4) $$

**PROOF:** The exact formula obtained is

$$ \mathcal{F}(\chi) = (\mathbb{E}^{\chi(1)})_0 + \sum_{n \ge 1} \left( \sum_{\pi \vdash n} \prod_{i=1}^{\ell(\pi)} (\mathbb{E}^{\Upsilon(\chi; \pi, i)})_{\pi_i} \right) \cdot (\mathbb{E}^{\chi(n+1)-\chi(n)})_0. $$

It can be simplified by turning all pending empty sets at the end into the species 1 (remember that 1 is a neutral element for product of species).

# 3 Non-commutative Frobenius characteristic of $\mathcal{F}(\chi)$

In species theory, there are many combinatorial operations on structures, which are translated on operations in the cycles index series. In the case of generalized parking functions, the functional equation/grammar (2) is terminating on (and only on) finite sequences of sets. Those structures are well-known to have a more expressive non-commutative Frobenius characteristic.
We recall those characteristic in the first subsection, we then give the non-commutative characteristic of $\mathcal{F}(\chi)$ in bases: $(\mathbf{S}^\pi)$ the completes, $(\mathbf{R}_\pi)$ the ribbons Schur and $(\Lambda^\pi)$ the elementaries of the non-commutative symmetric functions. (Refer to [GKL$^+$95] for an overview on non-commutative symmetric functions.)

## 3.1 Species of sequence of k-sets

In this subsection we focus on the species $(\mathbb{E}^{\Upsilon}(\chi;\pi,i))_{\pi_i} \simeq (\mathbb{E}^k)_n$. In [KT97], the authors lift the right action of $\mathfrak{S}_n$ on $[k]^n$ by considering the natural right action of $H_n(0)$ on $\mathbb{C}[k]^n$. In the same way, we consider here the natural action of $H_n(0)$ on the linearized species $\mathbb{C}\mathbb{E}^k[n]$. Using species theory notations, we translate some classical results appearing in [KT97] (and [NT08]).

Let $Q = (Q_i)_{i \in [k]}$ be a structure in $\mathbb{E}^k[n]$ that is a sequence of $k$ disjoint subsets which covers the finite set $[n]$; more generally we could replace $[n]$ by any finite set $U$ endowed with a fixed total order so that the elementary transpositions are well defined. The Hecke algebra $H_n(0)$ acts on $\mathbb{C}\mathbb{E}^k[n]$ on the left by permuting the elements. By abuse of notations we note $Q^{-1}(i) = k$ if $i \in Q_k$. For $q = 0$, the action of $T_i$ is defined by:

$$ Q \cdot T_i = \begin{cases} \sigma_i(Q) & \text{if } Q^{-1}(i) < Q^{-1}(i+1) \\ 0 & \text{if } Q^{-1}(i) = Q^{-1}(i+1) \\ -Q & \text{otherwise,} \end{cases} \qquad (5) $$

where $\sigma_i$ is the corresponding elementary transposition ($\sigma_i$ is defined as the bijection with $i \mapsto i+1$, $i+1 \mapsto i$ and stays fixed otherwise); for example $(13|\cdot|2) \cdot T_1 = (23|\cdot|1)$.

The action of any element $T_i$ of $H_n(0)$ on $Q$ is either 0 or a rearrangement of $Q$. The orbits (isomorphism types) are indexed by decompositions $d = (d_1, \dots, d_k)$ of $n$ in $k$ parts with $d_i = \#Q_i$, that is generalized compositions including null parts. The rearrangements of $Q$ form a basis of an $H_n(0)$-projective module $M$ whose non-commutative characteristic is $\mathrm{ch}(M) = S^\pi$, where $\pi$ is the underlying composition of $d$ obtained by stripping away null parts.

The non-commutative characteristic of $\mathbb{C}\mathbb{E}^k[n]$ is therefore

$$ \mathrm{ch}(\mathbb{C}\mathbb{E}^k[n]) = \sum_{\pi \vdash n} \mathbf{M}_\pi(k)\mathbf{S}^\pi = \sum_{\pi \vdash n} \binom{k}{\ell(\pi)} \mathbf{S}^\pi = \mathbf{S}_n(k\mathbb{A}), \qquad (6) $$

where the binomial coefficients account for the number of ways to insert $k - \ell(\pi)$ empty sets in a sequence of $\ell(\pi)$ non-empty sets. The non-commutative complete function $\mathbf{S}^\pi$ is used here as a way to encode the relabeling action of a sequence of $\ell(\pi)$-sets with $\pi_1$ elements in the first set, $\pi_2$ elements in the second set etc. In the enumeration formula of structures (7), $\mathbf{S}^\pi(\mathbb{E})$ is specialized into the multinomial $\binom{n}{\pi_1, \dots, \pi_j}$ (the reader may consult the specialization $\mathbf{S}^\pi(\mathbb{E})$ in [HLNT11]). In terms of Hopf algebras operations $\mathbf{S}_n(k\mathbb{A})$ is equivalent to the Adams operations which iterate $k$ times the coproduct and then the product: $\mu^k \circ \Delta^k(\mathbf{S}_n)$ with $\Delta^k = (\Delta \otimes \mathrm{Id}^{k-1\otimes}) \circ \Delta^{k-1}$ and $\mu^k = \mu \circ (\mathrm{Id} \otimes \mu^{k-1})$.

**E**$^k$-structures enumeration From the characteristic of permutation representations, we recover easily the enumeration formula of $(\mathbb{E}^k)_n$-structures (or words on $[k]$ of length $n$):

$$ \mathfrak{e}_k(n) = \sum_{\substack{\pi \vdash n \\ \pi = \pi_1 \cdots \pi_j}} \binom{k}{j} \binom{n}{\pi_1, \dots, \pi_j} = k^n. \qquad (7) $$
**E**<sup>*k*</sup>-**isomorphism types enumeration** Similarly we recover the enumeration formula of (E<sup>*k*</sup>)<sub>*n*</sub>-isomorphism types (or non-decreasing words) by specializing S<sup>*π*</sup> ↦→ 1:

$$
\tilde{c}_k(n) = \sum_{\pi \vdash n} \binom{k}{\ell(\pi)} = \binom{n+k-1}{k-1}. \qquad (8)
$$

3.2 Complete basis formula

Using (6) and the recursive definition (2) we naturally obtain a recursive formula for the non-commutative
Frobenius characteristic series of the χ-parking functions:

$$
\begin{align*}
\mathrm{ch}(\mathcal{F}(\chi)) &= 1 + \sum_{n \ge 1} \mathrm{ch}(\mathbb{C}\mathrm{E}^{\chi(1)}[n])\mathrm{ch}(\mathcal{F}(\psi_n)) \\
&= 1 + \sum_{n \ge 1} \mathbf{S}_n(\chi(1)\mathbb{A})\mathrm{ch}(\mathcal{F}(\psi_n)).
\end{align*}
$$

By specializing $S^\pi$ to $\binom{n}{\pi_1, \dots, \pi_k}$ and to 1, we obtain (new) formulas to enumerate $\mathcal{F}(\chi)$-structures and types. Namely from (7), we obtain the following recursive enumeration formula for the number $f(\chi; n)$ of $\mathcal{F}(\chi)$-structures on a set of cardinality $n$:

$$
f(\chi; n) = \sum_{k=1}^{n} \binom{n}{k} \chi(1)^k f(\psi_k; n-k) \quad (9)
$$

with $f(\chi; 0) = 1$. Similarly, we derive from (8) the number of isomorphism types:

$$
\tilde{f}(\chi; n) = \sum_{k=1}^{n} \binom{n-\chi(1)-1}{\chi(1)-1} \tilde{f}(\psi_k; n-k), \quad (10)
$$

also with $\tilde{f}(\chi; 0) = 1$. From Proposition 2.5, we have a non-recursive version of $\mathrm{ch}(\mathcal{F}(\chi))$:

**Lemma 3.1:**

$$
\mathbf{ch}(\mathcal{F}_n(\chi)) = \sum_{\pi \vdash n} \overrightarrow{\prod_{i=1}^{\ell(\pi)}} \mathbf{S}^{\pi_i} (\Upsilon(\chi; \pi, i) \mathbb{A}) .
$$

In §3.1 we stated that $S_n(k\mathbb{A})$ is given by the non-commutative Cauchy identity (6). This characteristic, expressed as a sum of products of Adams operations according to $\chi$, lifts trivially [KY03, Corollary 5.6] in non-commutative symmetric functions:

**Proposition 3.2:** Let $\chi, \psi$ be two non-decreasing functions such that $\chi(m) = \alpha\psi(m)$, for any $m \in \mathbb{N}_+$.
$$ \mathrm{ch}(\mathcal{F}(\chi)) = \mathrm{ch}(\mathcal{F}(\psi))(\alpha\mathbb{A}). $$

By expanding the formula of Lemma 3.1 we now have a new sum over compositions, where terms are
products of binomials on parts of each composition (see Table 3). To get rid of any specialization alphabet,
we first need to refine $\Upsilon$ into $\Psi_\tau$; namely for $\pi$ a composition of $n$ and $\tau$ a composition of $\ell(\pi)$ we set

$$
\Psi_{\tau}(\chi; \pi, i) = \begin{cases} \chi(1) & \text{if } i=1, \\ \chi(1 + \pi(\tau(i))) - \chi(1 + \pi(\tau(i-1))) & \text{otherwise.} \end{cases}
$$

**Remark 3.3:** $\Psi_{(1,...,1)} = \Upsilon$.

The non-commutative characteristic $\mathrm{ch}(\mathcal{F}_n(\chi))$ of Lemma 3.1 can now be expanded into the following theorem:
<table><caption>Tab. 1: Some enumerations of $\mathcal{F}(\chi)$-structures for sets of cardinality $n = 0$ to 7.</caption><thead><tr><th>χ\n</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>OEIS</th></tr></thead><tbody><tr><th>m</th><td>1</td><td>1</td><td>3</td><td>16</td><td>125</td><td>1296</td><td>16807</td><td>262144</td><td>A000272</td></tr><tr><th>m + 1</th><td>1</td><td>2</td><td>8</td><td>50</td><td>432</td><td>4802</td><td>65536</td><td>1062882</td><td>A089104</td></tr><tr><th>2m</th><td>1</td><td>2</td><td>12</td><td>128</td><td>2000</td><td>41472</td><td>1075648</td><td>33554432</td><td>A097629</td></tr><tr><th>m² + m</th><td>1</td><td>2</td><td>20</td><td>512</td><td>25392</td><td>2093472</td><td>260555392</td><td>45819233280</td><td>A103353</td></tr></tbody></table>

<table><caption>Tab. 2: Some enumerations of $\mathcal{F}(\chi)$-types for $n = 0$ to 8.</caption><thead><tr><th>χ\n</th><th>0</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>OEIS</th></tr></thead><tbody><tr><th>m</th><td>1</td><td>1</td><td>2</td><td>5</td><td>14</td><td>42</td><td>132</td><td>429</td><td>1430</td><td>A000108</td></tr><tr><th>m + 2</th><td>1</td><td>3</td><td>9</td><td>28</td><td>90</td><td>297</td><td>1001</td><td>3432</td><td>11934</td><td>A000245</td></tr><tr><th>2m</th><td>1</td><td>2</td><td>7</td><td>30</td><td>143</td><td>728</td><td>3876</td><td>21318</td><td>120175</td><td>A006013</td></tr><tr><th>[m/3]</th><td>1</td><td>1</td><td>1</td><td>2</td><td>3</td><td>4</td><td>9</td><td>15</td><td>22</td><td>A124753</td></tr></tbody></table>

**Theorem 3.4:** The non-commutative characteristic of $\mathcal{F}_n(\chi)$ is given by:

$$ \mathrm{ch}(\mathcal{F}_n(\chi)) = \sum_{\pi \vdash n} \gamma_{\pi} \mathbf{S}^{\pi}, \quad \text{with} \quad \gamma_{\pi} = \sum_{\tau \vdash \ell(\pi)} \prod_{i=1}^{\ell(\tau)} \left( \frac{\Psi_{\tau}(\chi; \pi, i)}{\tau_i} \right). \qquad (11) $$

Using again Proposition 2.5, from (9) and (10), we get the following non recursive enumeration formula for $\chi$-structures and isomorphism types:

$$ f(\chi; n) = \sum_{\substack{\pi \vdash n \\ \pi = \pi_1 \cdots \pi_k}} \left( \prod_{i=1}^{n} \pi_i \right) \prod_{i=1}^{k} \Upsilon(\chi; \pi, i)^{\pi_i}, \quad \tilde{f}(\chi; n) = \sum_{\substack{\pi \vdash n \\ \pi = \pi_1 \cdots \pi_k}} \prod_{i=1}^{\ell(\pi)} \left( \frac{n - \Upsilon(\chi; \pi, i) - 1}{\Upsilon(\chi; \pi, i) - 1} \right). $$

**Example 3:** The first values of the non-commutative characteristic of $\mathcal{F}(m^2 - m + 1)$ are given by:

$$ \mathrm{ch}(\mathcal{F}_1(m^2 - m + 1)) = \mathbf{S}^1, \quad \mathrm{ch}(\mathcal{F}_2(m^2 - m + 1)) = 2\mathbf{S}^{11} + \mathbf{S}^2 $$

$$ \mathrm{ch}(\mathcal{F}_3(m^2 - m + 1)) = 9\mathbf{S}^{111} + 2\mathbf{S}^{12} + 6\mathbf{S}^{21} + \mathbf{S}^3 $$

$$ \mathrm{ch}(\mathcal{F}_4(m^2 - m + 1)) = 70\mathbf{S}^{1111} + 9\mathbf{S}^{112} + 21\mathbf{S}^{121} + 2\mathbf{S}^{13} + 51\mathbf{S}^{211} + 6\mathbf{S}^{22} + 12\mathbf{S}^{31} + \mathbf{S}^4 $$

We now investigate how the formula of Theorem 3.4 translates in other natural bases of non-commutative functions.

## 3.3 Ribbon Schur basis formula

Recall that the change of basis from the complete basis to the ribbon Schur functions basis ($\mathbf{R}_{\pi}$) is given by $\mathbf{S}^{\pi} = \sum_{\tau \le \pi} \mathbf{R}_{\tau}$, where $\le$ denotes the reverse refinement order.

**Example 4:** The compositions $\tau$ of 5 such that $\tau \le 212$ are 212, 32, 23 and 5.
$$
\begin{align*}
\mathbf{ch}(\mathcal{F}_0(\chi)) &= 1, & \mathbf{ch}(\mathcal{F}_1(\chi)) &= a_1 \mathbf{S}^1, & \mathbf{ch}(\mathcal{F}_2(\chi)) &= a_1 \mathbf{S}^2 + \left[ \begin{pmatrix} a_1 \\ 2 \end{pmatrix} + a_1 a_2 \right] \mathbf{S}^{11} \\
\mathbf{ch}(\mathcal{F}_3(\chi)) &= a_1 \mathbf{S}^3 + \left[ \begin{pmatrix} a_1 \\ 2 \end{pmatrix} + a_1(a_2 + a_3) \right] \mathbf{S}^{21} + \left[ \begin{pmatrix} a_1 \\ 2 \end{pmatrix} + a_1 a_2 \right] \mathbf{S}^{12} \\
&\quad + \left[ \begin{pmatrix} a_1 \\ 3 \end{pmatrix} + \begin{pmatrix} a_1 \\ 2 \end{pmatrix}(a_2 + a_3) + a_1 \begin{pmatrix} a_2 \\ 2 \end{pmatrix} + a_1 a_2 a_3 \right] \mathbf{S}^{111}
\end{align*}
$$

Tab. 3: The first values of the non-commutative characteristic with $\chi(m) = a_m + \chi(m-1)$ and $\chi(1) = a_1$ in the complete basis.

This change of basis gives the formula:

$$
\mathrm{ch}(\mathcal{F}_n(\chi)) = \sum_{\pi \vdash n} \left( \sum_{\pi \le \tau} \gamma_{\tau} \right) \mathbf{R}_{\pi}
$$

**Example 5:** The first values of the non-commutative characteristic of $\mathcal{F}(2m-1)$ are given by:

$$
\begin{align*}
\mathrm{ch}(\mathcal{F}_1(2m-1)) &= \mathbf{R}_1, & \mathrm{ch}(\mathcal{F}_2(2m-1)) &= 2\mathbf{R}_{11} + 3\mathbf{R}_2 \\
\mathrm{ch}(\mathcal{F}_3(2m-1)) &= 5\mathbf{R}_{111} + 7\mathbf{R}_{12} + 9\mathbf{R}_{21} + 12\mathbf{R}_3 \\
\mathrm{ch}(\mathcal{F}_4(2m-1)) &= 14\mathbf{R}_{1111} + 19\mathbf{R}_{112} + 23\mathbf{R}_{121} + 30\mathbf{R}_{13} + 28\mathbf{R}_{211} + 37\mathbf{R}_{22} + 43\mathbf{R}_{31} + 55\mathbf{R}_4
\end{align*}
$$

The coefficients of $\mathbf{R}_{1n}$ are (as excepted) Catalan numbers [A000108], and the coefficients of $\mathbf{R}_n$ are
(less excepted) the number of non-crossing trees with $n$ nodes [A001764].

3.4 Lambda basis formula

Recall that both bases ($\mathbf{S}^\pi$) and ($\Lambda^\pi$) are multiplicative and related by the formula $\mathbf{S}^\pi = \sum_{\tau \le \pi} (-1)^{\ell(\tau) - \ell(\pi)} \Lambda^\tau$.
Furthermore, the change of base from ribbon ($\mathbf{R}_\pi$) to lambda ($\Lambda^\pi$) is given by $\mathbf{R}_\pi = \sum_{\bar{\tau} \le \pi^-} (-1)^{\ell(\bar{\tau}) - \ell(\pi)} \Lambda^\tau$
(where $\bar{\tau}$ is the complement of $\tau$ and $\pi^-$ is the conjugate of $\pi$).

It follows that, in the Lambda basis, the characteristic of the module of parking functions is given by an
alternating sum:

$$
\mathrm{ch}(\mathcal{F}_n(\chi)) = \sum_{\pi \vdash n} \left( \sum_{\tau \vdash \ell(\pi)} (-1)^{n-\ell(\tau)} \prod_{i=1}^{\ell(\tau)} \left( \frac{\chi(1+\pi(\tau(i-1)))}{\tau_i} \right) \right) \Lambda^{\ell(\tau)}.
$$

**Example 6:**

$$
\begin{align*}
\mathrm{ch}(\mathcal{F}_1(m^2 - m + 1)) &= \Lambda^1, & \mathrm{ch}(\mathcal{F}_2(m^2 - m + 1)) &= 3\Lambda^{11} - \Lambda^2 \\
\mathrm{ch}(\mathcal{F}_3(m^2 - m + 1)) &= 18\Lambda^{111} - 3\Lambda^{12} - 7\Lambda^{21} + \Lambda^3 \\
\mathrm{ch}(\mathcal{F}_4(m^2 - m + 1)) &= 172\Lambda^{1111} - 18\Lambda^{112} - 36\Lambda^{121} + 3\Lambda^{13} - 70\Lambda^{211} + 7\Lambda^{22} + 13\Lambda^{31} - \Lambda^4
\end{align*}
$$

The coefficients once again admit a combinatorial interpretation.

**Proposition 3.5:** Let $\pi$ be a composition of $n$. The coefficient of $[\Lambda^\pi]$ is the number of non-decreasing
$\chi$-parking functions constant on each part of $\pi$, up to the sign.
**Example 7:** The coefficient $[\Lambda^\pi]\mathrm{ch}(\mathcal{F}_4(m^2 - m + 1))$ of the previous example is 7; this is the number of non-decreasing parking functions that are constant on each part of the composition 22: $(1234|\cdot|\cdot|\cdots)$, $(12|34|\cdot|\cdots)$, ..., $(12|\cdot|\cdot|\cdot|\cdot|34|\cdots)$.

# 4 An inclusion-exclusion formula

Originally we expected the formula

$$f(\chi; n) = \sum_{\substack{\pi=|n| \\ \pi=\pi_1 \cdots \pi_k}} (-1)^{n-k} \binom{n}{\pi_1, \dots, \pi_k} \prod_{i=1}^{k} \chi(1 + \pi(i-1))^{\pi_i} \quad [\text{KY03, Theorem 4.2}]$$

to be the specialization at $\Lambda^\pi \mapsto \binom{n}{\pi_1, \dots, \pi_k}$ of the non commutative characteristic of the module of generalized parking functions. This it turned out is not to be the case, therefore the aim of this section is to investigate this formula, in particular to try to find a representation theoretic interpretation of it.

First we need a few definitions; given an ordered alphabet $A$, recall that the *standardization* of a word $w \in A^*$ is the permutation obtained by scanning iteratively $w$ from left to right and relabeling $1, 2, \dots, n$ the occurrences of the smallest letters. For any non-decreasing sequence $\chi$ of integers, the $\chi$-standardization of a word $w$ is the word obtained by applying the same algorithm and then relabeling with $\chi(1), \chi(2), \dots, \chi(n)$. The word (in fact a generalized parking function) obtained is no longer a permutation. We denote by $\mathrm{Std}^\chi$ this operator.

**Example 8:** Let $\chi$ be the Catalan numbers $1, 1, 2, 5, 14, 42, \dots$ we have,

$$\mathrm{Std}^{\chi}(1, 4, 11, 1, 31, 1) = (1, 5, 14, 1, 42, 2).$$

**Definition 4.1:** A $\chi$-parking function $(Q_i)$ of size $n$ is primitive if the following is verified:

$$Q_i \neq \emptyset \iff i = \chi \left( 1 + \sum_{j < \chi(i)} \# Q_j \right).$$

We denote by $\mathcal{P}_{n-1}$ the set of primitive parking functions of size $n$.

In other words, in the sorted of $f$, all vertical paths join $\chi$.

An obvious bijection between primitive parking functions and ordered set partitions of $n$ is obtained by considering the sequence of non empty $Q_i$ in the same order. The *inversion set* of a primitive parking function $f$ is: $\mathrm{Inv}(f) = \{(i, j) : i < j \text{ and } f(i) \ge f(j)\}$.

**Example 9:** Let $\chi$ the sequence of prime numbers, the function $(13, 2, 3, 11, 3, 3)$ is primitive and its associated ordered set partition is $\{2\}|\{3, 5, 6\}|\{4\}|\{1\}$. The inversion set of $f$ is

$$\mathrm{Inv}(f) = \{(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (3, 5), (3, 6), (4, 5), (4, 6), (5, 6)\}.$$

The collection of ordered set partitions admits a nice representation as indexing the faces of a polytope (see [Zie95]). In this polytope the faces of dimension $i$ are the ordered set partitions with $n - i$ parts. In particular the ordered partition with only one part corresponds to the only face of dimension $n - 1$.

Through the aforementioned bijection we may alternatively label the faces of this polytope with the $\chi$ primitive parking functions; the dimension of the face indexed by $f$ is then $d(f) = n - \mathrm{Img}(f)$.

We name $\mathcal{P}_{n-1}$ the $n-1$ dimensional polytope of primitive parking function of size $n$. If $\chi$ is strictly increasing this is the *permutohedron*. Generalized parking functions (on $[n]$) can naturally be endowed with the product order inherited from $\mathbb{N}^n$: namely $f \le g$ if and only if $\forall i \le n, f(i) \le g(i)$. Seeing each
<figure><img src="image_4.png" /><figcaption>Tab. 4: The set {$p \in \mathcal{P}_{n-1} : p \ge f$} for $\chi = \text{id}$ and $f = (1123)$. Arrows represent a possible involution.</figcaption></figure>

face $e_f$ of $\mathcal{P}_{n-1}$ as the sum of parking functions lower than $f$, our main theorem states that, by doing an inclusion-exclusion process on the dimension of the faces, we obtain each generalized-parking function once and only once.

**Theorem 4.2:** In the vector space $\mathbb{C}\mathcal{F}_n(\chi)$ one has

$$ \sum_{f \in \mathcal{F}_n(\chi)} f = \sum_{f \in \mathcal{P}_{n-1}} (-1)^{d(f)} \sum_{p \le f} p. $$

More combinatorially, one can directly count $\chi$-parking functions from the previous theorem:

**Corollary 4.3 ([KY03, Theorem 4.2]):**

$$ f(\chi; n) = \sum_{\substack{Q \in \mathcal{F}_n(\chi) \\ Q \text{ primitive}}} (-1)^{d(Q)} \prod_{i=1}^{n} \chi(i)^{\#Q_{\chi(i)}}, $$

We prove it by using the signed involution principle. The aim is, for any $\chi$-parking function $f$ of size $n$, to give an involution $\mathcal{I}_f$ from {$p \in \mathcal{P}_{n-1} : p \ge f$} into itself such that:

$$ \mathcal{I}_f(p) = \begin{cases} p & \text{if } p = \text{Std}^\chi(f) \\ y & \text{with } d(y) = d(f) \pm 1 \quad \text{otherwise.} \end{cases} $$

Without loss of generality we can suppose that $f$ is non-decreasing so that $\text{Std}^\chi(f) = (\chi(1), \cdots, \chi(n))$. The involution is defined implicitly from the inversion set of $p$; it is $\text{Std}^\chi(f)$ if $\text{Inv}(p) = \emptyset$ and another primitive parking function of another dimension but with same inversion set otherwise. The key ingredient is given a primitive parking function $p$ with inversion set $\text{Inv}(p) = I$, to understand the set

$$ \text{Inv}_p = \{q \in \mathcal{P}_{n-1} : \text{Inv}(q) = \text{Inv}(p) \text{ and } q \ge p\}. $$

For a parking function $f \in \mathcal{P}_{n-1}$ the dimension is an invariant of the symmetric group action on the indices, as well as the cardinality of $\text{Inv}_p$. We can then state the following lemma:

**Lemma 4.4:** let $I$ be an inversion set and $h \ge f$ a primitive $\chi$-parking function with inversion $I$ of maximum dimension. The generating series $G_I(f)$ of the dimensions of the faces with inversion set $I$ is

$$ G_I(f) = \sum_{\substack{\text{Inv}(p)=I \\ p \ge f}} x^{d(p)} = (1+x)^{d(h)}. $$

The construction of $f_x$ is straightforward from Lemma 4.4, which completes the proof of Theorem 4.2. By adding the number of $\chi$-parking functions in each dimension we get the following formula:

**Proposition 4.5:**

$$ 0 = \sum_{k=0}^{n} (-1)^{n-k+1} \binom{n}{k} f(\chi; k) \chi(k+1)^{n-k}. $$
## Frobenius characteristic investigation

In the previous subsection the formula of Theorem 4.2 of [KY03] is expressed combinatorially as an alternating sum. This formula is the result of the exponential specialization of the following non-commutative characteristic:

$$ \mathcal{G}(\chi; n) = \sum_{\pi \mid n} (-1)^{n-\ell(\pi)} \prod_{i=1}^{\ell(\pi)} \chi(1 + \pi(i-1)) \Lambda^{\pi}. $$

Unfortunately this expression is not positive when expanded on the $\mathbb{R}$ basis. It's therefore not the characteristic of an indecomposable $H_n(0)$-module. Nevertheless it might still be interpretable as the characteristic of some exact sequence of $H_n(0)$-modules.

## Acknowledgments

We would like to thank Vincent Pilaud and Jean Christophe Novelli for their help and many discussions, especially about the last section. The first author would also like to thank François Bergeron for the truly rewarding summer internship in Montreal (supported by LIA LIRCO).

## References

[BLL98] Bergeron, Labelle, and Leroux. *Combinatorial species and tree-like structures*, volume 67 of *Encyclopedia of Mathematics and its Applications*. Cambridge University Press, Cambridge, 1998.

[GKL$^{+}$95] Gelfand, Krob, Lascoux, Leclerc, Retakh, and Thibon. Noncommutative symmetrical functions. *ADV APPL MATH*, 112(2):218–348, 1995.

[HLNT11] Hivert, Luque, Novelli, and Thibon. The $(1-E)$-transform in combinatorial hopf algebras. *J ALGEBR COMB*, 33(2):277–312, 2011.

[KT97] Krob and Thibon. Noncommutative symmetric functions iv: Quantum linear groups and hecke algebras at $q=0$. *J ALGEBR COMB*, 6(4):339–376, 1997.

[KW66] Konheim and Weiss. An occupancy discipline and applications. *SIAM J APPL MATH*, 14(6):1266–1274, 1966.

[KY03] Joseph P. S. Kung and Catherine Yan. Gončarov polynomials and parking functions. *J. Combin. Theory Ser. A*, 102(1):16–37, 2003.

[NT08] Novelli and Thibon. Noncommutative symmetric functions and lagrange inversion. *ADV APPL MATH*, 40(1):8–35, 2008.

[SP02] Stanley and Pitman. A polytope related to empirical distributions, plane trees, parking functions, and the associahedron. *DISCRETE COMPUT GEOM*, 27(4):603–602, 2002.

[Zie95] Ziegler. *Lectures on polytopes*, volume 152 of *Grad. Texts in Maths*. Springer-Verlag, NY, 1995.