# Word symmetric functions and the Redfield-Pólya theorem†

Jean-Paul Bultel and Ali Chouria and Jean-Gabriel Luque and Olivier Mallet‡

Laboratoire LITIS, EA 4108, Université de Rouen, Saint-Étienne-du-Rouvray, France

**Abstract.** We give noncommutative versions of the Redfield-Pólya theorem in WSym, the algebra of word symmetric functions, and in other related combinatorial Hopf algebras.

**Résumé.** Nous donnons des versions non-commutatives du théorème d'énumération de Redfield-Pólya dans WSym, l'algèbre des fonctions symétriques sur les mots, ainsi que dans d'autres algèbres de Hopf combinatoires.

**Keywords:** Symmetric functions, Redfield-Pólya theorem, Combinatorial Hopf algebras, Operads

## 1 Introduction

The Redfield-Pólya enumeration theorem (R-P theorem) is one of the most exciting results in combinatorics of the twentieth century. It was first published by John Howard Redfield (18) in 1927 and independently rediscovered by George Pólya ten years later (17). Their motivation was to generalize Burnside's lemma on the number of orbits of a group action on a set (see e.g (3)). Note that Burnside attributed this result to Frobenius (8) and it seems that the formula was prior known to Cauchy. Although Redfield found the theorem before Pólya, it is often attributed only to Pólya. This is certainly due to the fact that Pólya popularized the result by providing numerous applications to counting problems and in particular to the enumeration of chemical compounds. The theorem is a result of group theory but there are important implications in many disciplines (chemistry, theoretical physics, mathematics — in particular combinatorics and enumeration etc.) and its extensions lead to Andrés Joyal's combinatorial species theory (1).

Consider two sets $X$ and $Y$ ($X$ finite) and let $G$ be a finite group acting on $X$. For a map $f: X \to Y$, define the vector $v_f = (\#\{x: f(x) = y\})_{y \in Y} \in \mathbb{N}^Y$. The R-P theorem deals with the enumeration of the maps $f$ having a given $v_f = v$ ($v$ fixed) up to the action of the group $G$. The reader can refer to (11) for proof, details, examples and generalizations of the R-P theorem.

Algebraically, the theorem can be pleasantly stated in terms of symmetric functions (see e.g. (15, 12));

<footnote>†This paper is partially supported by the ANR project PhysComb, ANR-08-BLAN-0243-04, the CMEP-TASSILI project 09MDU765, the ANR project CARMA ANR-12-BS01-0017 and the PEPS project COGIT.</footnote>

<footnote>‡email: jean-paul.bultel@univ-rouen.fr, ali.chourial@univ-rouen.fr, jean-gabriel.luque@univ-rouen.fr, olivier.mallet@univ-rouen.fr</footnote>
the cycle index polynomial is defined in terms of power sum symmetric functions and, whence writing in the monomial basis, the coefficients count the number of orbits of a given type. From the seminal paper (9), many combinatorial Hopf algebras have been discovered and investigated. The goal is to mimic the combinatorics and representation theory related to symmetric functions in other contexts. This paper asks the question of the existence of combinatorial Hopf algebras in which the R-P theorem can naturally arise. In this sense, the article is the continuation of (6, 7) in which the authors investigated some Hopf algebras in the aim to study the enumeration of bipartite graphs up to the permutations of the vertices.

Each function $f: X \to Y$ can be encoded by a word of size $\#X$ on an alphabet $A_Y = \{a_y : y \in Y\}$. Hence, intuitively, we guess that the R-P theorem arises in a natural way in the algebra of words $C\langle A\rangle$. The Hopf algebra of word symmetric functions WSym has been studied in (19, 2, 10). In S Section 2, we recall the basic definitions and properties related to this algebra and propose a definition for the specialization of an alphabet using the concept of operad (13, 14). In Section 3, we construct and study other related combinatorial Hopf algebras. In Section 4, we investigate the analogues of the cycle index polynomials in these algebras and give two noncommutative versions of the R-P theorem. In particular, we give a word version and a noncommutative version. Finally, in Subsection 4.5, we propose a way to raise Harary-Palmer type enumerations (the functions are now enumerated up to an action of $G$ on $X$ and an action of another group $H$ on $Y$) in WSym. For this last equality, we need the notion of specialization defined in Section 2.

# 2 Word symmetric functions

## 2.1 Basic definitions and properties

Consider the family $\Phi := \{\Phi^\pi\}_\pi$ whose elements are indexed by set partitions of $\{1, \dots, n\}$ (we will denote $\pi \upharpoonright n$). The algebra WSym (19) is generated by $\Phi$ for the shifted concatenation product: $\Phi^\pi \Phi^{\pi'} = \Phi^{\pi \pi'[n]}$ where $\pi$ and $\pi'$ are set partitions of $\{1, \dots, n\}$ and $\{1, \dots, m\}$, respectively, and $\pi'[n]$ means that we add $n$ to each integer occurring in $\pi'$. Other bases are known, for example, the word monomial functions defined by

$$ \Phi^\pi = \sum_{\pi \le \pi'} M_{\pi'} $$

where $\pi \le \pi'$ indicates that $\pi$ is finer than $\pi'$, i.e., that each block of $\pi'$ is a union of blocks of $\pi$.

WSym is a Hopf algebra when endowed with the shifted concatenation product and the following coproduct, where $\text{std}(\pi)$ means that for all $i$, we replace the $i$th smallest integer in $\pi$ by $i$:

$$ \Delta M_{\pi} = \sum_{\substack{\pi' \cup \pi'' = \pi \\ \pi' \cap \pi'' = \emptyset}} M_{\text{std}(\pi')} \otimes M_{\text{std}(\pi'')} $$

Note that the notion of standardization makes sense for more general objects. If $S$ is a total ordered set, the standardized $\text{std}(\ell)$, for any list $\ell$ of $n$ elements of $S$, is classicaly the permutation $\sigma = [\sigma_1, \dots, \sigma_n]$ verifying $\sigma[i] > \sigma[j]$ if $\ell[i] > \ell[j]$ or if $\ell[i] = \ell[j]$ and $i > j$. Now if the description of an object $o$ contains a list $\ell$, the standardized $\text{std}(o)$ is obtained by replacing $\ell$ by $\text{std}(\ell)$ in $o$.

Let $A$ be an infinite alphabet. The algebra WSym is isomorphic to WSym($A$), the subalgebra of $C\langle A\rangle$ defined by Rosas and Sagan (19) and constituted by the polynomials which are invariant by permutation of the letters of the alphabet. The explicit isomorphism sends each $\Phi^\pi$ to the polynomial $\Phi^\pi(A) := \sum_w w$
where the sum is over the words $w = w_1 \cdots w_n$ ($w_1, \dots, w_n \in A$) such that if $i$ and $j$ are in the same block of $\pi$ then $w_i = w_j$. Under this isomorphism, each $M_\pi$ is sent to $M_\pi(A) = \sum_w w$ where the sum is over the words $w = w_1 \cdots w_n$ ($w_1, \dots, w_n \in A$) such that $w_i = w_j$ if and only if $i$ and $j$ are in the same block of $\pi$. In the sequel, when there is no ambiguity, we will identify the algebras WSym and WSym$(A)$. With the realization explained above, the coproduct of WSym consists of identifying the algebra WSym $\otimes$ WSym with WSym$(A+B)$, where $A$ and $B$ are two noncommutative alphabets such that $A$ commutes with $B$, by setting $f(A)g(B) \sim f \otimes g$ (see. It is a cocommutative coproduct for which the polynomials $\Phi^{\{1, \dots, n\}}$ are primitive. Endowed with this coproduct, WSym has a Hopf structure which has been studied by Hivert et al. (10) and Bergeron et al. (2).

## 2.2 What are virtual alphabets in WSym?

We consider the set $\mathfrak{C}$ of set compositions together with additional elements $\{o_m : m > 1\}$ (we will also set $o_0 = \emptyset$) and a unity $1$. This set is a naturally bigraded set: if $\mathfrak{C}_n^m$ denotes the set of compositions of $\{1, \dots, n\}$ into $m$ subsets, we have $\mathfrak{C} = \{1\} \cup \bigcup_{n,m \in \mathbb{N}} \mathfrak{C}_n^m \cup \{o_m : m > 1\}$. We will also use the notations $\mathfrak{C}_n$ (resp. $\mathfrak{C}^m$) to denote the set of compositions of $\{1, \dots, n\}$ (resp. the set compositions into $m$ subsets together with $o_m$) with the special case: $1 \in \mathfrak{C}^1$. The formal space $\mathbb{C}[\mathfrak{C}^m]$ is naturally endowed with a structure of right $\mathbb{C}[\mathfrak{S}_m]$-module; the permutations acting by permuting the blocks of each composition and letting $o_m$ invariant. For simplicity, we will denote also by $\mathfrak{C}$ the collection $(\mathbb{S}$-module, see e.g.(13))[${\mathbb{C}}[\mathfrak{C}^0], \mathbb{C}[\mathfrak{C}^1], \dots, \mathbb{C}[\mathfrak{C}^m]$].

For each $1 \le i \le k$, we define partial compositions $\circ_i : \mathfrak{C}^k \times \mathfrak{C}^{k'} \to \mathfrak{C}^{k+k'-1}$ by:

1. If $\Pi = [\pi_1, \dots, \pi_k]$ and $\Pi' = [\pi'_1, \dots, \pi'_{k'}]$ then

$$ \Pi \circ_i \Pi' = \begin{cases} [\pi_1, \dots, \pi_{i-1}, \pi'_1[\pi_i], \dots, \pi'_{k'}[\pi_i], \pi_{i+1}, \dots, \pi_k] & \text{if } \Pi' \in \mathfrak{C}_{\#\pi_i} \\ o_{k+k'-1} & \text{otherwise,} \end{cases} $$

where $\pi'_j[\pi_i] = \{i_{j_1}, \dots, i_{j_p}\}$ if $\pi'_j = \{j_1, \dots, j_p\}$ and $\pi_i = \{i_1, \dots, i_k\}$ with $i_1 < \dots < i_k$;

2. $\Pi \circ_i o_{k'} = o_k \circ_i \Pi' = o_{k+k'-1}$ for each $\Pi \in \mathfrak{C}^k$ and $\Pi' \in \mathfrak{C}^{k'}$;

3. $1 \circ_1 \Pi' = \Pi'$ and $\Pi \circ_i 1 = \Pi$ for each $\Pi \in \mathfrak{C}^k$ and $\Pi' \in \mathfrak{C}^{k'}$.

**Proposition 2.1** *The $\mathbb{S}$-module $\mathfrak{C}$ (i.e. each graded component $\mathfrak{C}_n$ is a $\mathbb{S}_n$-module (13)) endowed with the partial compositions $\circ_i$ is an operad in the sense of Martin Markl (14), which means the compositions satisfy:*

1. (Associativity) For each $1 \le j \le k$, $\Pi \in \mathfrak{C}^k$, $\Pi' \in \mathfrak{C}^{k'}$ and $\Pi'' \in \mathfrak{C}^{k''}$:

$$ (\Pi \circ_j \Pi') \circ_i \Pi'' = \begin{cases} (\Pi \circ_i \Pi'') \circ_{j+k'-1} \Pi', & \text{for } 1 \le i < j, \\ \Pi \circ_j (\Pi' \circ_{i-j+1} \Pi''), & \text{for } j \le i < k' + j, \\ (\Pi \circ_{i-k'+1} \Pi'') \circ_j \Pi', & \text{for } j + k' \le i < k + k' - 1, \end{cases} $$

2. (Equivariance) For each $1 \le i \le m$, $\tau \in \mathfrak{S}_m$ and $\sigma \in S_n$, let $\tau \circ_i \sigma \in \mathfrak{S}_{m+n-1}$ be given by inserting the permutation $\sigma$ at the $i$th place in $\tau$. If $\Pi \in \mathfrak{C}^k$ and $\Pi' \in \mathfrak{C}^{k'}$ then $(\Pi\tau) \circ_i (\Pi'\sigma) = (\Pi \circ_{\tau(i)} \Pi')(\tau \circ_i \sigma)$.
3. (Unitality) $\mathbf{1} \circ_1 \Pi' = \Pi'$ and $\Pi \circ_i \mathbf{1} = \Pi$ for each $\Pi \in \mathfrak{C}^k$ and $\Pi' \in \mathfrak{C}^{k'}$.

Let $V = \bigoplus_n V_n$ be a graded space over $\mathbb{C}$. We will say that $V$ is a (symmetric) $\mathfrak{C}$-module, if there is an action of $\mathfrak{C}$ on $V$ which satisfies:

1. Each $\Pi \in \mathfrak{C}^m$ acts as a linear application $V^m \to V$.

2. (Compatibility with the graduation) $[\pi_1, \dots, \pi_m](V_{j_1}, \dots, V_{j_m}) = \mathbf{0}$ if $\#\pi_i \neq j_i$ for some $1 \le i \le m$ and $\mathfrak{o}_m(V_{j_1}, \dots, V_{j_m}) = \mathbf{0}$. Otherwise, $[\pi_1, \dots, \pi_m] \in \mathfrak{C}_n$ sends $V_{\#\pi_1} \times \dots \times V_{\#\pi_m}$ to $V_n$. Note also the special case $\mathbf{1}(v) = v$ for each $v \in V$.

3. (Compatibility with the compositions)

$$ (\Pi \circ_i \Pi')(v_1, \dots, v_{k+k'-1}) = \Pi(v_1, \dots, v_{i-1}, \Pi'(v_i, \dots, v_{i+k'-1}), v_{i+k'}, \dots, v_{k+k'-1}). $$

4. (Symmetry) $\Pi(v_1, \dots, v_k) = (\Pi\sigma)(v_{\sigma(1)}, \dots, v_{\sigma(k)})$.

If $V$ is generated (as a $\mathfrak{C}$-module) by $\{v_n : n \ge 1\}$ with $v_n \in V_n$, then setting $v^{\{\pi_1, \dots, \pi_m\}} = [\pi_1, \dots, \pi_m](v_{\#\pi_1}, \dots, v_{\#\pi_m})$, we have $V_n = \operatorname{span}\{v^\pi : \pi \vdash n\}$. Note that the existence of $v^\pi$ follows from the point 4 of the definition of a $\mathfrak{C}$-module.

**Example 2.2** If $A$ is a noncommutative alphabet, the algebra $\mathbb{C}\langle A\rangle$ can be endowed with a structure of $\mathfrak{C}$-module by setting

$$ [\pi_1, \dots, \pi_m](w_1, \dots, w_m) = \begin{cases} \bigwedge^{[\pi_1, \dots, \pi_m]} (w_1, \dots, w_m) & \text{if } w_i \in A^{\#\pi_i} \text{ for each } 1 \le i \le m \\ 0 & \text{otherwise} \end{cases} $$

where $w_1, \dots, w_m \in A^*$ and $\bigwedge^{[\pi_1, \dots, \pi_m]}(w_1, \dots, w_m) = a_1 \dots a_n$ is the only word of $A^{\#\pi_1 + \dots + \#\pi_m}$ such that for each $1 \le i \le m$, if $\pi_i = \{j_1, \dots, j_\ell\}$, $a_{j_1} \dots a_{j_\ell} = w_j$.

Note that $\mathbb{C}[A]$ has also a structure of $\mathfrak{C}$-module defined by $[\pi_1, \dots, \pi_m](x_1, \dots, x_m) = x_1 \dots x_m$ if $x_i$ is a monomial of degree $\#\pi_i$.

**Proposition 2.3** $\mathrm{WSym}$ is a $\mathfrak{C}$-module.

**Proof:** We define the action of $\mathfrak{C}$ on the power sums by

$$ [\pi_1, \dots, \pi_m](\Phi^{n_1}, \dots, \Phi^{n_m}) = \begin{cases} \Phi^{\{\pi_1, \dots, \pi_m\}} & \text{if } n_i = \#\pi_i \text{ for each } 1 \le i \le m \\ 0 & \text{otherwise.} \end{cases} $$

and extend it linearly to the spaces $\mathrm{WSym}_n$. Since this action is compatible with the realization:

$$ [\pi_1, \dots, \pi_m](\Phi^{n_1}, \dots, \Phi^{n_m})(A) = \bigwedge^{[\pi_1, \dots, \pi_m]} (\Phi^{n_1}(A), \dots, \Phi^{n_m}(A)) $$

(the definition of $\bigwedge_\pi$ is given in Example 2.2) and $\mathrm{WSym}$ is obviously stable by the action of $\mathfrak{C}$, $\mathrm{WSym}(A)$ is a sub-$\mathfrak{C}$-module of $\mathbb{C}\langle A\rangle$. Hence, $\mathrm{WSym}$ is a $\mathfrak{C}$-module. ■

A morphism of $\mathfrak{C}$-module is a linear map $\varphi$ from a $\mathfrak{C}$-module $V_1$ to another $\mathfrak{C}$-module $V_2$ satisfying $\varphi\Pi(v_1, \dots, v_m) = \Pi(\varphi(v_1), \dots, \varphi(v_m))$ for each $\Pi \in \mathfrak{C}^m$. In this context, a virtual alphabet (or a specialization) is defined by a morphism of $\mathfrak{C}$-module $\varphi$ from $\mathrm{WSym}$ to a $\mathfrak{C}$-module $V$. The image of a word symmetric function $f$ will be denoted by $f[\varphi]$. The $\mathfrak{C}$-module $\mathrm{WSym}$ is free in the following sense:
**Proposition 2.4** Let $V$ be generated by $v_1 \in V_1, v_2 \in V_2, \dots, v_n \in V_n, \dots$ as a $\mathfrak{C}$-module (or equivalently, $V_n = \text{span}\{v^\pi : \pi \vdash n\}$). There exists a morphism of $\mathfrak{C}$-module $\varphi : \text{WSym} \to V$, which sends $\Phi^n$ to $v_n$.

**Proof:** This follows from the fact that $\{\Phi^\pi : \pi \vdash n\}$ is a basis of $\text{WSym}_n$. Let $\varphi : \text{WSym}_n \to V_n$ be the linear map such that $\varphi(\Phi^\pi) = V^\pi$; this is obviously a morphism of $\mathfrak{C}$-module. $\blacksquare$

For convenience, we will write $\text{WSym}[\varphi] = \varphi\text{WSym}$.

**Example 2.5** 1. Let $A$ be an infinite alphabet. The restriction to $\text{WSym}(A)$ of the morphism of algebra $\varphi : \mathbb{C}\langle A \rangle \to \mathbb{C}[A]$ defined by $\varphi(a) = a$ is a morphism of $\mathfrak{C}$-module sending $\text{WSym}(A)$ to $\text{Sym}(A)$ (the algebra of symmetric functions on the alphabet $A$). This morphism can be defined without the help of alphabets, considering that $\text{Sym}$ is generated by the power sums $p_1, \dots, p_n, \dots$ with the action $[\pi_1, \dots, \pi_m](p_{\#\pi_1}, \dots, p_{\#\pi_m}) = p_{\#\pi_1} \dots p_{\#\pi_m}$.

2. Let $A$ be any alphabet (finite or not). If $V$ is a sub-$\mathfrak{C}$-module of $\mathbb{C}\langle A \rangle$ generated by the homogeneous polynomials $P_n \in \mathbb{C}[A^n]$ as a $\mathfrak{C}$-module, the linear map sending, for each $\pi = \{\pi_1, \dots, \pi_m\}$, $\Phi^\pi$ to $\bigwedge_{\Pi} [P_{\#\pi_1}, \dots, P_{\#\pi_m}]$, where $\Pi = [\pi_1, \dots, \pi_m]$, is a morphism of $\mathfrak{C}$-module.

# 3 The Hopf algebra of set partitions into lists

## 3.1 Set partitions into lists

A set partition into lists is an object which can be constructed from a set partition by ordering each block. For example, $\{[1, 2, 3], [4, 5]\}$ and $\{[3, 1, 2], [5, 4]\}$ are two distinct set partitions into lists of the set $\{1, 2, 3, 4, 5\}$. The number of set partitions into lists of an $n$-element set (or set partitions into lists of size $n$) is given by Sloane's sequence A000262 (20). If $\Pi$ is a set partition into lists of $\{1, \dots, n\}$, we will write $\Pi \Vdash n$. We will denote by cycle_support($\sigma$) the cycle support of a permutation $\sigma$, i.e., the set partition associated to its cycle decomposition. For instance, cycle_support(325614) = $\{\{135\}, \{2\}, \{4, 6\}\}$. A set partition into lists can be encoded by a set partition and a permutation in view of the following easy result:

**Proposition 3.1** For all $n$, the set partitions into lists of size $n$ are in bijection with the pairs $(\sigma, \pi)$ where $\sigma$ is a permutation of size $n$ and $\pi$ is a set partition which is less fine than or equal to the cycle support of $\sigma$.

Indeed, from a set partition $\pi$ and a permutation $\sigma$, we obtain a set partition into lists $\Pi$ by ordering the elements of each block of $\pi$ so that they appear in the same order as in $\sigma$.

**Example 3.2** Starting the set partition $\pi = \{\{1, 4, 5\}, \{6\}, \{3, 7\}, \{2\}\}$ and the permutation $\sigma = 4271563$, we obtain the set partition into lists $\Pi = \{[4, 1, 5], [7, 3], [6], [2]\}$.

## 3.2 Construction

Let $\Pi \Vdash n$ and $\Pi' \Vdash n'$ be two set partitions into lists. Then, we set $\Pi \uplus \Pi' = \Pi \cup \{[l_1 + n, \dots, l_k + n] : [l_1, \dots, l_k] \in \Pi'\} \Vdash n + n'$. Let $\Pi' \subset \Pi \Vdash n$, since the integers appearing in $\Pi'$ are all distinct, the standardized std($\Pi'$) of $\Pi'$ is well defined as the unique set partition into lists obtained by replacing the $i$th smallest integer in $\Pi$ by $i$. For example, std($\{[5, 2], [3, 10], [6, 8]\}$) = $\{[3, 1], [2, 6], [4, 5]\}$.
**Definition 3.3** The Hopf algebra BWSym is formally defined by its basis $(\Phi^{\Pi})$ where the $\Pi$ are set partitions into lists, its product $\Phi^{\Pi} \Phi^{\Pi'} = \Phi^{\Pi \oplus \Pi'}$ and its coproduct $\Delta(\Phi^{\Pi}) = \sum \Phi^{\text{std}(\Pi')} \otimes \Phi^{\text{std}(\Pi'')}$, where the sum is over the $(\Pi', \Pi'')$ such that $\Pi' \cup \Pi'' = \Pi$ and $\Pi' \cap \Pi'' = \emptyset$.

Following Section 3.1 and for convenience, we will use alternatively $\Phi^{\Pi}$ and $\Phi^{(\sigma)}$ to denote the same object.

We define $M_{\Pi} = M_{(\sigma)}$ by setting $\Phi^{(\sigma)} = \sum_{\pi \le \pi'} M_{(\sigma)}$. The formula being diagonal, it defines $M_{\Pi}$ for any $\Pi$ and proves that the family $(M_{\Pi})_{\Pi}$ is a basis of BWSym. Consider for instance $\{[3, 1], [2]\} \sim \binom{321}{\{\{1, 3\}, \{2\}\}}$, we have $\Phi^{\{[3,1], [2]\}} = M_{\{[3,1], [2]\}} + M_{\{[3,2,1]\}}$.

For any set partition into lists $\Pi$, let $s(\Pi)$ be the corresponding classical set partition. Then, the linear application $\phi$ defined by $\phi(\Phi^{\Pi}) = \Phi^{s(\Pi)}$ is obviously a morphism of Hopf algebras. As an associative algebra, BWSym has also algebraical links with the algebra FQSym (4). Recall that this algebra is defined by its basis $(E^{\sigma})$ whose product is $E^{\sigma} E^{\tau} = E^{\sigma/\tau}$, where $\sigma/\tau$ is the word obtained by concatening $\sigma$ and the word obtained from $\tau$ by adding the size of $\sigma$ to all the letters (for example 321/132 = 321465).

The subspace $V$ of WSym $\otimes$ FQSym linearly spanned by the $\Phi^{\pi} \otimes E^{\sigma}$ such that the cycle supports of $\sigma$ is finer than $\pi$ is a subalgebra, and the linear application sending $\Phi^{\pi, \sigma}$ to $\Phi_{\pi} \otimes E^{\sigma}$ is an isomorphism of algebras. Moreover, when the set of cycle supports of $\sigma$ is finer than $\pi$, $M_{\pi} \otimes E^{\sigma}$ also belongs to $V$ and is the image of $M_{(\sigma)}$.

The linear application from BWSym to FQSym which sends $M_{\{[\sigma]\}}$ to $E^{\sigma}$ and $M_{\Pi}$ to 0 if $\text{card}(\Pi) > 1$, is also a morphism of algebras.

### 3.3 Realization

Let $A^{(j)} = \{a_i^{(j)} | i > 0\}$ be an infinite set of bi-indexed noncommutative variables, with the order relation defined by $a_i^{(j)} < a_{i'}^{(j)}$ if $i < i'$. Let $A = \bigcup_j A^{(j)}$. Consider the set partition into lists $\Pi = \{L^1, L^2, \dots\} = \{[l_1^1, l_2^1, \dots, l_{n_1}^1], [l_1^2, l_2^2, \dots, l_{n_2}^2], \dots\} \nVdash n$. Then, one obtains a polynomial realization BWSym($A$) by identifying $\Phi^{\Pi}$ with $\Phi^{\Pi}(A)$, the sum of all the monomials $a_1 \dots a_n$ (where the $a_i$ are in $A$) such that $k = k'$ implies $a_{l_k}$, $a_{l_k'} \in A^{(j)}$ for some $j$, and for each $k$, $\text{std}(a_{i_1} \dots a_{i_{n_k}}) = \text{std}(l_1^k \dots l_{n_k}^k)$ with $\{l_1^k, \dots, l_{n_k}^k\} = \{i_1 < \dots < i_{n_k}\}$. (The “B” of BWSym is for “bi-indexed letters”). The coproduct $\Delta$ can be interpreted by identifying $\Delta(\Phi^{\Pi})$ with $\Phi^{\Pi}(A+B)$ as in the case of WSym. Here, if $a \in A$ and $b \in B$ then $a$ and $b$ are not comparable.

**Proposition 3.4** The Hopf algebras BWSym and BWSym($A$) are isomorphic.

Now, let $M'_{\Pi}(A)$ be the sum of all the monomials $a_1 \dots a_n$, $a_i \in A$, such that $a_{l_k}$ and $a_{l_k'}$ belong in the same $A^{(j)}$ if and only if $k = k'$, and for each $k$, $\text{std}(a_{i_1} \dots a_{i_{n_k}}) = \text{std}(l_1^k \dots l_{n_k}^k)$ with $\{l_1^k, \dots, l_{n_k}^k\} = \{i_1 < \dots < i_{n_k}\}$. For example, the monomial $a_1^{(1)} a_1^{(1)} a_2^{(1)}$ appears in the expansion of $\Phi_{\{[1,3],[2]\}}$, but not in the one of $M'_{\Pi}$ form a new basis $(M'_{\Pi})$ of BWSym. Note that this basis is not the same as $(M_{\Pi})$. For example, one has

$$ \Phi^{\{[1],[2]\}} = M_{\{[1],[2]\}} + M_{\{[1,2]\}} = M'_{\{[1],[2]\}} + M'_{\{[1,2]\}} + M'_{\{[2,1]\}} $$

Consider the basis $F_{\sigma}$ of FQSym defined in (4). The linear application, from BWSym to FQSym, which sends $M'_{\{[\sigma]\}}$ to $F_{(\sigma^{-1})}$, and $M'_{\Pi}$ to 0 if $\text{card}(\Pi) > 1$, is a morphism of algebras.
## 3.4 Related Hopf algebras

By analogy with the construction of BWSym, we define a “B” version for each of the algebras Sym, QSym and WQSym. In this section, we sketch briefly how to construct them; the complete study is deferred to a forthcoming paper.

As usual when $L = [\ell_1, \dots, \ell_k]$ and $M = [m_1, \dots, m_2]$ are two lists, the shuffle product is defined recursively by $[ ] \sqcup L = L \sqcup [ ] = \{L\}$ and $L \sqcup M = [\ell_1].([\ell_2, \dots, \ell_k] \sqcup M) \cup [m_1].(L \sqcup [m_2, \dots, m_k])$. The algebra of biword quasi-symmetric functions (BWQSym) has its bases indexed by set compositions into lists. The algebra is defined as the vector space spanned by the formal symbols $\Phi_{\Pi}$, where $\Pi$ is a composition into lists of the set $\{1, \dots, n\}$ for a given $n$, together with the product $\Phi_{\Pi}\Phi_{\Pi'} = \sum_{\Pi'' \in \Pi \sqcup \Pi'[n]} \Phi_{\Pi''}$, where $\Pi'[n]$ means that we add $n$ to each of the integers in the lists of $\Pi'$ and $\Pi$ is a composition into lists of $\{1, \dots, n\}$. Endowed with the coproduct defined by $\Delta(\Phi_{\Pi}) = \sum_{\Pi'.\Pi''=\Pi} \Phi_{\mathrm{std}(\Pi')} \otimes \Phi_{\mathrm{std}(\Pi'')}$, BWQSym has a structure of Hopf algebra. Note that BWQSym $= \bigoplus_n$ BWQSym$_n$ is naturally graded; the dimension of the graded component BWQSym$_n$ is $2^{n-1}n!$ (see sequence A002866 in (20)).

The algebra BSym $= \bigoplus_n$ BSym$_n$ is a graded cocommutative Hopf algebra whose bases are indexed by multisets of permutations. Formally, we set BSym$_n = \mathrm{span}\{\phi^{\{\sigma_1, \dots, \sigma_k\}} : \sigma_i \in \mathfrak{S}_{n_i}, n_1 + \dots + n_k = n\}$, $\phi^{S_1}, \phi^{S_2} = \phi^{S_1 \cup S_2}$ and for any permutation $\sigma$, $\phi^{\{\sigma\}}$ is primitive. The dimensions of the graded components are given by the sequence A077365 of (20).

Finally, BQSym $= \bigoplus_n$ BQSym$_n$ is generated by $\phi_{[\sigma_1, \dots, \sigma_k]}$, its product is $\phi_L \phi_{L'} = \sum_{L'' \in L \sqcup L'} \phi_{L''}$ and its coproduct is $\Delta(\phi_L) = \sum_{L=L', L''} \phi_{L'} \otimes \phi_{L''}$. The dimension of the graded component BQSym$_n$ is given by Sloane's sequence A051296 (20).

# 4 On the R-P theorem

## 4.1 R-P theorem and symmetric functions

Consider two sets X and Y such that X is finite ($\#X = n$), together with a group $G \subset \mathfrak{S}_n$ acting on X by permuting its elements. We consider the set $Y^X$ of the maps $X \to Y$. The type of a map $f$ is the vector of the multiplicities of its images; more precisely, $\mathrm{type}(f) \in \mathbb{N}^Y$ with $\mathrm{type}(f)_y = \#\{x \in X : f(x) = y\}$. For instance, consider $X = \{a, b, c, d, e\}$, $Y = \{0, 1, 2\}$, $f(a) = f(c) = f(d) = 1$, $f(b) = 2$, $f(c) = 0$: we have $\mathrm{type}(f) = [1^0, 3^1, 1^2]$. The action of G on X induces an action of G on $Y^X$. Obviously, the type of a function is invariant for the action of G. Then all the elements of an orbit of G in $Y^X$ have the same type, so that the type of an orbit will be the type of its elements. The question is: how to count the number $n_I$ of orbits for the given type $I$? Note that, if $\lambda_I$ denotes the (integer) partition obtained by removing all the zeros in $I$ and reordering its elements in the decreasing order, $\lambda_I = \lambda_{I'}$ implies $n_I = n_{I'}$; it suffices to understand how to compute $n_\lambda$ when $\lambda$ is a partition. The Redfield-Pólya theorem deals with this problem and its main tool is the cycle index:

$$Z_G := \frac{1}{\#G} \sum_{\sigma \in G} p^{\mathrm{cycle\_type}(\sigma)},$$

where cycle_type($\sigma$) is the (integer) partition associated to the cycle of $\sigma$ (for instance $\sigma = 325614 = (135)(46)$, cycle_type($\sigma$) = $[3, 2, 1]$). When $\lambda = [\lambda_1, \dots, \lambda_k]$ is a partition, $p^\lambda$ denotes the (commutative) symmetric function $p^\lambda = p_{\lambda_1} \dots p_{\lambda_k}$ and $p_n$ is the classical power sum symmetric function.
The Redfield-Pólya theorem states:

**Theorem 4.1** The expansion of $Z_G$ on the basis $(m_\lambda)$ of monomial symmetric functions is given by

$$Z_G = \sum_{\lambda} n_{\lambda} m_{\lambda}.$$

**Example 4.2** Suppose that we want to enumerate the non-isomorphic non-oriented graphs on three vertices. The symmetric group $\mathfrak{S}_3$ acting on the vertices induces an action of the group

$$G := \{123456, 165432, 345612, 321654, 561234, 543216\} \subset \mathfrak{S}_6$$

on the edges. The construction is not unique. We obtain the group $G$ by labelling the 6 edges from 1 to 6. Hence, to each permutation of the vertices corresponds a permutation of the edges. Here, the 1 labels the loop from the vertex 1 to itself, 2 labels the edge which links the vertices 1 and 2, 3 is the loop from the vertex 2 to itself, 4 labels the edge from the vertex 2 to the vertex 3, 5 is the loop from the vertex 3 to itself, finally, 6 links the vertices 1 and 3. The cycle index of $G$ is

$$Z_G = \frac{1}{6}(p_1^6 + 3p_2^2p_1^2 + 2p_3^2) = m_6 + 2m_{51} + 4m_{42} + 6m_{411} + 6m_{33} + \dots$$

The coefficient 4 of $m_{42}$ means that there exists 4 non-isomorphic graphs with 4 edges coloured in blue and 2 edges coloured in red.

## 4.2 Word R-P theorem

If $\sigma$ is a permutation, we define $\Phi^{\sigma} := \Phi^{cycle support}(\sigma)$. Now for our purpose, a map $f \in Y^X$ will be encoded by a word $w$: we consider an alphabet $A = \{a_y : y \in Y\}$, the elements of $X$ are relabelled by 1, 2, ..., $\#X = n$ and $w$ is defined as the word $b_1...b_n \in A^n$ such that $b_i = a_{f(i)}$. With these notations, the action of $G$ on $Y^X$ is encoded by the action of the permutations of $G$ on the positions of the letters in the words of $A^n$.

It follows that for any permutation $\sigma \in G$, one has

$$\Phi^{\sigma} = \sum_{w\sigma=w} w. \qquad (1)$$

The cycle support polynomial is defined by $Z_G := \sum_{\sigma \in G} \Phi^{\sigma}$. From (1) we deduce

$$Z_G = \sum_w \#\mathrm{Stab}_G(w)w$$

where $\mathrm{Stab}_G(w) = \{\sigma \in G : w\sigma = w\}$ is the subgroup of $G$ which stabilizes $w$. In terms of monomial functions, this yields:

**Theorem 4.3**

$$Z_G = \sum_{\pi} \#\mathrm{Stab}_G(w_{\pi})M_{\pi}$$

where $w_{\pi}$ is any word $a_1...a_n$ such that $a_i = a_j$ if and only if $i, j \in \pi_k$ for some $1 \le k \le n$.
**Example 4.4** Consider the same example as in Example 4.2. Each graph is now encoded by a word $a_1a_2a_3a_4a_5a_6$: the letter $a_1$ corresponds to the colour of the vertex 1, the letter 2 to the colour of the vertex 2 and so on.
The cycle support polynomial is

$$Z_G := \Phi\{\{1\},\{2\},\{3\},\{4\},\{5\},\{6\}\} + \Phi\{\{2,6\},\{3,5\},\{1\},\{4\}\} \\ + \Phi\{\{1,3\},\{4,6\},\{2\},\{5\}\} + \Phi\{\{1,5\},\{2,4\},\{3\},\{6\}\} + 2\Phi\{\{1,3,5\},\{2,4,6\}\}$$

The coefficient of $M_{\{2,6\},\{3,5\},\{1\},\{4\}}$ in $Z_G$ is 2 because it appears only in $\Phi\{\{1\},\{2\},\{3\},\{4\},\{5\},\{6\}$ and $\Phi\{\{2,6\},\{3,5\},\{1\},\{4\}\}$. The monomials of $M_{\{2,6\},\{3,5\},\{1\},\{4\}}$ are of the form $abcdbcb$, where $a, b, c$ and $d$ are four distinct letters. The stabilizer of $abcdbcb$ in $G$ is the two-element subgroup $\{123456, 165432\}$.

Note that the cycle support polynomial has already appeared in the literature on the work of Sagan and Gebhard (5) on a slightly different setting which is a special case of our purpose.

## 4.3 From word R-P theorem to R-P theorem

The aim of this section is to link the numbers $n_I$ of Section 4.1 and the numbers $\#\text{Stab}_G(w)$ appearing in Section 4.2.

If $w$ is a word we will denote by $\text{orb}_G(w)$ its orbit under the action of $G$. The Orbit-stabilizer theorem (see e.g. (3)) together with Lagrange's theorem gives:

$$\#G = \#\text{orb}_G(w)\#\text{Stab}_G(w) \qquad (2)$$

Denote by $\Lambda(\pi)$ the unique integer partition defined by $(\#\pi_1, \dots, \#\pi_k)$ if $\pi = \{\#\pi_1, \dots, \pi_k\}$ with $\#\pi_1 \ge \#\pi_2 \ge \dots \ge \#\pi_k$. If $\lambda = (m^{k_m}, \dots, 2^{k_2}, 1^{k_1})$ we set $\lambda! = k_m! \dots k_2! k_1!$. The shape of a word $w$ is the unique set partition $\pi(w)$ such that $w$ is a monomial of $M_{\pi(w)}$. Note that all the orbits of words with a fixed shape $\pi$ have the same cardinality. Let $\pi = \{\pi_1, \dots, \pi_k\}$ and $A_k = \{a_1, \dots, a_k\}$ be an alphabet of size $k$. we will denote by $S_{\pi, A_k}$ the set of words $w$ with size $k$ such that the number of letter $a_i$ in $w$ is $\#\pi_i$. All the words of $S_{\pi, A_k}$ have the same coefficients in $Z_G$ and this set splits into $\frac{\Lambda(\pi)!}{\#\text{orb}(w_\pi)}$ orbits of size $\#\text{orb}(w_\pi)$

$$n_{\lambda} = \sum_{\Lambda(\pi)=\lambda} \frac{\lambda!}{\#\text{orb}_G(w_{\pi})} = \sum_{\Lambda(\pi)=\lambda} \frac{\lambda! \#\text{Stab}_G(w_{\pi})}{\#G} \qquad (3)$$

If we consider the morphism of algebra $\theta: \text{WSym} \to \text{Sym}$ which sends $\Phi_n$ to $p_n$, we have $\theta(M_\pi) = \Lambda(\pi)!m_\lambda$. Hence, we have

$$\frac{1}{\#G}\theta(Z_G) = \sum_{\lambda} \left( \sum_{\Lambda(\pi)=\lambda} \frac{\lambda!}{\#\text{orb}_G(w_{\pi})} \right) m_{\lambda} = \sum_{\lambda} n_{\lambda}m_{\lambda}$$

as expected by the Redfield-Pólya theorem (Theorem 4.1).

## 4.4 R-P theorem without multiplicities

Examining with more details Example 4.4, the coefficient 2 of $M_{\{2,6\},\{3,5\},\{1\},\{4\}}$ in $Z_G$ follows from the group $\{123456, 165432\}$ of order two which stabilizes $abcdbcb$. In terms of set partitions into lists, this can be interpreted by $M_{\{2,6\},\{3,5\},\{1\},\{4\}} + M_{\{6,2\},\{5,3\},\{1\},\{4\}} \to 2M_{\{2,6\},\{3,5\},\{1\},\{4\}}$. We deduce the following version (without multiplicities) of Theorem 4.3 in BWSym.
**Theorem 4.5** Let G be a permutation group. We have

$$
\mathbb{Z}_G := \sum_{\sigma \in G} \Phi^{(\text{cycle support}(\sigma))} = \sum_{\pi} \sum_{\sigma \in \text{Stab}_\pi(G)} M_{(\sigma)}.
$$

Consider again Example 4.4.

$$
\begin{align*}
\mathbb{Z}_G ={}& \Phi^{\binom{123456}{4}\binom{3}{2}\binom{4}{5}\binom{6}{6}} + \Phi^{\binom{165432}{26}\binom{35}{4}\binom{4}{6}} + \Phi^{\binom{345612}{135}\binom{246}{46}} \\
& + \Phi^{\binom{321654}{26}\binom{46}{5}} + \Phi^{\binom{561234}{135}\binom{246}{46}} + \Phi^{\binom{543216}{15}\binom{234}{6}}.
\end{align*}
$$

When expanded in the monomial M basis, there are exactly 2 terms of the form $M_{(\{2,6\},\{3,5\},\{1\},\{4\})}$ (for $\sigma = 123456$ and $\sigma = 165432$). Note that we can use another realization which is compatible with the space but not with the Hopf algebra structure. It consists to set $\tilde{\Phi}^{(\sigma)} := \sum_w (w^\sigma)$, where the sum is over the words $w = w_1 \dots w_n$ ($w_i \in A$) such that if $i$ and $j$ are in the same block of $\pi$ then $w_i = w_j$. If we consider the linear application $\tilde{\psi}$ sending $\Phi^{(\sigma)}$ to $\tilde{\Phi}^{(\sigma)}$, $\tilde{\psi}$ sends $M_{(\sigma)}$ to $\tilde{M}_{(\sigma)} := \sum_w (w^\sigma)$, where the sum is over the words $w = w_1 \dots w_n$ ($w_i \in A$) such that $i$ and $j$ are in the same block of $\pi$ if and only if $w_i = w_j$. Let $w$ be a word, the set of permutations $\sigma$ such that $(w^\sigma)$ appears in the expansion of $\tilde{\psi}(\mathbb{Z}_G)$ is the stabilizer of $w$ in $G$. The linear application sending each biword $(w^\sigma)$ to $w$ sends $\tilde{\Phi}^{(\sigma)}$ to $\Phi^\pi$ and $\sum_{\sigma \in \text{Stab}_G(w)} (w^\sigma)$ to $\#\text{Stab}_G(w)w$. Note that $\#\text{Stab}_G(w)$ is also the coefficient of the corresponding monomial $M_{\pi(w)}$ in the cycle support polynomial $Z_G$. For instance, we recover the coefficient 2 in Example 4.4 from the biwords $(123456)_{abcdcb}$ and $(165432)_{abcdcb}$ in $\tilde{\psi}(\mathbb{Z}_G)$.

4.5 WSym and Harary-Palmer type enumerations

Let $A := \{a_1, \dots, a_m\}$ be a set of formal letters and $I = [i_1, \dots, i_k]$ a sequence of elements of $\{1, \dots, m\}$. We define the virtual alphabet $A_I$ by

$$
\Phi^n(A_I) := (a_{i_1} \dots a_{i_k})^{\frac{n}{k}} + (a_{i_2} \dots a_{i_k} a_{i_1})^{\frac{n}{k}} + \dots + (a_{i_k} a_1 \dots a_{i_{k-1}})^{\frac{n}{k}},
$$

if $k$ divides $n$ and $0$ otherwise. If $\sigma \in \mathfrak{S}_m$ we define the alphabet $A_\sigma$ as the formal sum of the alphabets
$A_c$ associated to its cycles:

$$
\Phi^{\{1\dots n\}}[A_{\sigma}] := \sum_{c \text{ cycle in } \sigma} \Phi^{n}[A_{c}].
$$

From Example 2.5.2, the set $\{\Phi^{\{1,\dots,n\}}[A_\sigma] : n \in \mathbb{N}\}$ generates the sub-$\mathfrak{C}$-module $\text{WSym}[A_\sigma]$ of $\mathfrak{C}\langle A \rangle$
(the composition $\Pi$ acting by $\sqcup_\Pi$).

Let $H \subset \mathfrak{S}_m$ and $G \subset \mathfrak{S}_n$ be two permutation groups. We define $Z(H; G) := \sum_{\tau \in H} \Phi^G[A_\tau]$.

**Proposition 4.6** We have:

$$
Z(H; G) = \sum_{w \in A^n} \#\mathrm{Stab}_{H,G}(w)w
$$

where $\mathrm{Stab}_{H,G}(w)$ denotes the stabilizer of $w$ under the action of $H \times G$ ($H$ acting on the left on the names of the variables $a_i$ and $G$ acting on the right on the positions of the letters in the word); equivalently, $\mathrm{Stab}_{H,G}(a_{i_1} \dots a_{i_k}) = \{(\tau, \sigma) \in H \times G : a_{\tau(i_\sigma(j))}$ for each $1 \le j \le n\}.$
Hence, from Burnside's classes formula, sending each variable to 1 in $Z(H; G)$, we obtain the number of orbits of $H \times G$.

**Example 4.7** Consider the set of the non-oriented graphs without loop whose edges are labelled by three colours. Suppose that we consider the action of the group $H = \{123, 231, 312\} \subset \mathfrak{S}_n$ on the colours. We want to count the number of graphs up to permutation of the vertices ($G = \mathfrak{S}_3$) and the action of $H$ on the edges. There are three edges, and each graph will be encoded by a word $a_{i_1}a_{i_2}a_{i_3}$ where $i_j$ denotes the colour of the edge $j$. We first compute the specialization $\Phi^{\{1...n\}}[A_\sigma]$ for $1 \le n \le 3$ and $\sigma \in H$. We find $\Phi^{\{1\}}[A_{123}] = a_1+a_2+a_3$, $\Phi^{\{1\}}[A_{231}] = \Phi^{\{1\}}[A_{312}] = 0$, $\Phi^{\{1,2\}}[A_{123}] = a_1^2+a_2^2+a_3^2$, $\Phi^{\{1,2\}}[A_{231}] = \Phi^{\{1,2\}}[A_{312}] = 0$, $\Phi^{\{1,2,3\}}[A_{123}] = a_1^3+a_2^3+a_3^3$, $\Phi^{\{1,2,3\}}[A_{213}] = a_2a_3a_1+a_3a_1a_2+a_1a_2a_3$, and $\Phi^{\{1,2,3\}}[A_{312}] = a_1a_3a_2+a_3a_2a_1+a_2a_1a_3$. Now, we deduce the values of the other $\Phi^\pi[A_\sigma]$ with $\pi \nmid 3$ and $\sigma \in H$ by the action of $\bowtie_\Pi$. For instance:

$$ \Phi^{\{1,2\},\{3\}}[A_{123}] = \bowtie_{\{1,2\},\{3\}} (\Phi^{\{1,2\}}[A_{123}], \Phi^{\{1\}}[A_1]) \\ = a_1^3 + a_1^2 a_2 + a_1^2 a_3 + a_2^2 a_1 + a_2^3 + a_2^2 a_3 + a_3^2 a_1 + a_3^2 a_2 + a_3^3. $$

We find also

$$ \Phi^{\{1,3\},\{2\}}[A_{123}] = a_1^3 + a_1 a_2 a_1 + a_1 a_3 a_1 + a_2 a_1 a_2 + a_2^3 + a_2 a_3 a_2 + a_3 a_1 a_3 + a_3 a_2 a_3 + a_3^3, $$

$$ \Phi^{\{1\},\{2,3\}}[A_{123}] = a_1^3 + a_2 a_1^2 + a_3 a_1^2 + a_1 a_2^2 + a_2^3 + a_3 a_2^2 + a_1 a_3^2 + a_2 a_3^3 + a_3^3, $$

$$ \Phi^{\{1\},\{2\},\{3\}}[A_{123}] = (a_1 + a_2 + a_3)^3. $$

The other $\Phi^\pi[A_\sigma]$ are zero. Hence,

$$ \begin{aligned} Z[H; \mathfrak{S}_3] &= \Phi^{123}[A_{123}] + \Phi^{132}[A_{123}] + \Phi^{213}[A_{123}] + \Phi^{321}[A_{123}] + \\ & \qquad \Phi^{231}[A_{231}] + \Phi^{231}[A_{312}] + \Phi^{312}[A_{231}] + \Phi^{312}[A_{312}] \\ &= 6(a_1^3 + a_2^3 + a_3^3) + 2 \sum_{i \neq j} a_i^2 a_j + 2 \sum_{i \neq j} a_j a_i a_j + 2 \sum_{i \neq j} a_j a_i a_i^2 \\ & \qquad + 3(a_1 a_2 a_3 + a_2 a_3 a_1 + a_3 a_1 a_2) + 3(a_1 a_3 a_2 + a_3 a_2 a_1 + a_2 a_1 a_3). \end{aligned} $$

The coefficient 3 of $a_1a_2a_3$ means that the word is invariant under the action of three pairs of permutations (here (123, 123), (231, 312), (312, 231)). Setting $a_1 = a_2 = a_3 = 1$, we obtain $Z[H, \mathfrak{S}_3] = 18 \times 4: 18$ is the order of the group $H \times \mathfrak{S}_3$ and 4 is the number of orbits:

$\{a_1^3, a_2^3, a_3^3\}, \{a_1^2 a_2, a_1 a_2 a_1, a_2 a_1^2, a_2^2 a_3, a_2 a_3 a_2, a_3 a_2^2, a_3^2 a_1, a_3 a_1 a_3, a_1 a_3^2\}, \{a_2^2 a_1, a_2 a_1 a_2, a_1 a_2^2, a_1^2 a_3, a_1 a_3 a_1, a_3 a_1^2, a_3^2 a_2, a_3 a_2 a_3, a_1 a_3^2\}, \text{ and } \{a_1 a_2 a_3, a_1 a_3 a_2, a_2 a_1 a_3, a_2 a_3 a_1, a_3 a_1 a_2, a_3 a_2 a_1\}$.

## References

[1] F. Bergeron, G. Labelle, P. Leroux, *Combinatorial Species and Tree-like Structures*, Encyclopedia of Mathematics and Its Applications No. 67, Cambridge University Press (1997).

[2] N. Bergeron, C. Reutenauer, M. Rosas, M. Zabrocki, *Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables*, Canad. J. Math. 60, no. 2, 266-296(2008).

[3] W. Burnside, *Theory of groups of finite order*, Cambridge University Press (1897).

[4] G.H.E. Duchamp, F. Hivert, J.-Y. Thibon, *Noncommutative symmetric functions VI: free quasi-symmetric functions and related algebras*, International Journal of Algebra and Computation 12, 671-717 (2002).
[5] David D. Gebhard, Bruce E. Sagan, *A Chromatic Symmetric Function in Noncommuting Variables*, Journal of Algebraic Combinatorics **13**, 227-255 (2001).

[6] G. H. E. Duchamp, J.-G. Luque, K. A. Penson and C. Tollu, *Free quasi-symmetric functions, product actions and quantum field theory of partitions*, Sém. Latter Comb. **12** B54Am (2007).

[7] G.H.E. Duchamp, J.-G. Luque, J.-C. Novelli, C. Tollu, F. Toumazet, *Hopf Algebra of Diagrams*, International Journal of Algebra and Computation **21**, No. 3 1-2 (2011).

[8] F.G. Frobenius, "Ueber die Congruenz nach einem aus zwei endlichen Gruppen gebildeten Doppe-

[9] I.M. Gelfand, D. Krob, A. Lascoux, B. Leclerc, V.S. Retakh, J.-Y. Thibon, *Noncommutative sym- metric functions*, Advances in Mathematics **112**, 218-348 (1995).

[10] F. Hivert, J.-C. Novelli, J.-Y. Thibon, *Commutative Combinatorial Hopf Algebras*, J. Algebraic Combin. **28** (2008), no. 1, 65-95.

[11] V. Krishnamurthy, *Combinatorics, Theory and Applications*, Affiliated East-West Press, 1985, 483p.

[12] A. Lascoux, *Symmetric Functions and Combinatorial Operators on Polynomials*, CBMS Regional Conference Series in Mathematics, American Mathematical Society (2003).

[13] J.-L. Loday, B. Valette, *Algebraic Operads*, Grundlehren der mathematischen Wissenschaften **364**, Springer 2012.

[14] M. Markl, *Operads and PROPs*, Handbook of Algebra, Volume **5**, Pages 87-140 (2008).

[15] I.G. Macdonald, *Symmetric functions and Hall polynomials*, 2nd ed, Oxford University Press, 1995.

[16] J.-C. Novelli, F. Patras, J.-Y. Thibon, *Natural Endomorphisms of Quasi-Shuffle Hopf Algebras*, arXiv:1101.0725v1.

[17] G. Pólya, *Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen*, Acta Mathematica **68** (1): 145-254 (1937).

[18] J.H. Redfield, *The Theory of Group-Reduced Distributions*, American Journal of Mathematics **49** (3): 433-455 (1927).

[19] M. Rosas, B. Sagan, *Symmetric functions in noncommuting variables*, Trans. Amer. Math. Soc. **358**(1): 215-232 (2006).

[20] N. J. A. Sloane. The On-Line Encyclopedia of Integer Sequences. http://oeis.org/.