Jean-Paul Bultel

Ali Chouria

Jean-Gabriel Luque

Olivier Mallet

Word symmetric functions and the Redfield-Pólya theorem *

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.

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 [START_REF] Redfield | The Theory of Group-Reduced Distributions[END_REF] in 1927 and independently rediscovered by George Pólya ten years later [START_REF] Pólya | Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen[END_REF]. 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 [START_REF] Frobenius | Ueber die Congruenz nach einem aus zwei endlichen Gruppen gebildeten Doppelmodul[END_REF] 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 [START_REF] Bergeron | Combinatorial Species and Treelike Structures[END_REF]. Consider two sets X and Y (X finite) and let G be a finite group acting on X. For a map f : X → Y , define the vector v f = (#{x : f (x) = y)}) y∈Y ∈ 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 [START_REF] Krishnamurthy | Combinatorics, Theory and Applications[END_REF] 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. [START_REF] Macdonald | Symmetric functions and Hall polynomials[END_REF][START_REF] Lascoux | Symmetric Functions and Combinatorial Operators on Polynomials[END_REF]); 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 [START_REF] Gelfand | Noncommutative symmetric functions[END_REF], 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 [START_REF] Duchamp | Free quasi-symmetric functions, product actions and quantum field theory of partitions[END_REF][START_REF] Duchamp | Hopf Algebra of Diagrams[END_REF] 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 → Y can be encoded by a word of size #X on an alphabet A Y = {a y : y ∈ Y }. Hence, intuitively, we guess that the R-P theorem arises in a natural way in the algebra of words C A . The Hopf algebra of word symmetric functions WSym has been studied in [START_REF] Rosas | Symmetric functions in noncommuting variables[END_REF][START_REF] Bergeron | Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables[END_REF][START_REF] Hivert | Commutative Combinatorial Hopf Algebras[END_REF]. 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 [START_REF] Loday | Algebraic Operads[END_REF][START_REF] Markl | Handbook of Algebra[END_REF]. 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

Basic definitions and properties

Consider the family Φ := {Φ π } π whose elements are indexed by set partitions of {1, . . . , n} (we will denote π n). The algebra WSym [START_REF] Rosas | Symmetric functions in noncommuting variables[END_REF] is generated by Φ for the shifted concatenation product: Φ π Φ π ′ = Φ ππ ′ [n] where π and π ′ are set partitions of {1, . . . , n} and {1, . . . , m}, respectively, and π ′ [n] means that we add n to each integer occurring in π ′ . Other bases are known, for example, the word monomial functions defined by

Φ π = π≤π ′ M π ′
where π ≤ π ′ indicates that π is finer than π ′ , i.e., that each block of π ′ is a union of blocks of π.

WSym is a Hopf algebra when endowed with the shifted concatenation product and the following coproduct, where std(π) means that for all i, we replace the ith smallest integer in π by i:

∆M π = π ′ ∪π ′′ =π π ′ ∩π ′′ =∅ M std(π ′ ) ⊗ M std(π ′′ ) .
Note that the notion of standardization makes sense for more general objects. If S is a total ordered set, the standardized std(ℓ), for any list ℓ of n elements of S, is classicaly the permutation

σ = [σ 1 , . . . , σ n ] verfying σ[i] > σ[j] if ℓ[i] > ℓ[j] or if ℓ[i] = ℓ[
j] and i > j. Now if the description of an object o contains a list ℓ , the standardized std(o) is obtained by replacing ℓ by std(ℓ) in o.

Let A be an infinite alphabet. The algebra WSym is isomorphic to WSym(A), the subalgebra of C A defined by Rosas and Sagan [START_REF] Rosas | Symmetric functions in noncommuting variables[END_REF] and constituted by the polynomials which are invariant by permutation of the letters of the alphabet. The explicit isomorphism sends each Φ π to the polynomial Φ π (A) := w w where the sum is over the words w = w 1 • • • w n (w 1 , . . . , w n ∈ A) such that if i and j are in the same block of π then w i = w j . Under this isomorphism, each M π is sent to M π (A) = w w where the sum is over the words w = w 1 • • • w n (w 1 , . . . , w n ∈ A) such that w i = w j if and only if i and j are in the same block of π. 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 ⊗ 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) ∼ f ⊗ g (see. It is a cocommutative coproduct for which the polynomials Φ {1,...,n} are primitive. Endowed with this coproduct, WSym has a Hopf structure which has been studied by Hivert et

What are virtual alphabets in WSym?

We consider the set C of set compositions together with additional elements {o m : m > 1} (we will also set o 0 = []) and a unity 1. This set is a naturally bigraded set: if C m n denotes the set of compositions of {1, . . . , n} into m subsets, we have C = {1} ∪ n,m∈N C m n ∪ {o m : m > 1}. We will also use the notations C n (resp. C m ) to denote the set of compositions of {1, . . . , n} (resp. the set compositions into m subsets together with o m ) with the special case: 1 ∈ C 1 . The formal space C[C m ] is naturally endowed with a structure of right C[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 C the collection (S-module, see e.g.( 12)

)[C[C 0 ], C[C 1 ], . . . , C[C m ]].
For each 1 ≤ i ≤ k, we define partial compositions 12)) endowed with the partial compositions • i is an operad in the sense of Martin Markl [START_REF] Markl | Handbook of Algebra[END_REF], which means the compositions satisfy:

• i : C k ×C k ′ → C k+k ′ -1 by: 1. If Π = [π 1 , . . . , π k ] and Π ′ = [π ′ 1 , . . . , π ′ k ′ ] then Π• i Π ′ = [π 1 , . . . , π i-1 , π ′ 1 [π i ], . . . , π ′ k ′ [π i ], π i+1 , . . . , π k ] if Π ′ ∈ C #π i o k+k ′ -1 otherwise, where π ′ j [π i ] = {i j 1 , . . . , i jp } if π ′ j = {j 1 , . . . , j p } and π i = {i 1 , . . . , i k } with i 1 < • • • < i k ; 2. Π • i o k ′ = o k • i Π ′ = o k+k ′ -1 for each Π ∈ C k and Π ′ ∈ C k ′ ; 3. 1 • 1 Π ′ = Π ′ and Π • i 1 = Π for each Π ∈ C k and Π ′ ∈ C k ′ . Proposition 2.1 The S-module C ( i.e. each graded component C n is a S n - module (
1. (Associativity) For each 1 ≤ j ≤ k, Π ∈ C k , Π ′ ∈ C k ′ and Π ′′ ∈ C k ′′ : (Π• j Π ′ )• i Π ′′ =    (Π • i Π ′′ ) • j+k ′′ -1 Π ′ , for 1 ≤ i < j, Π • J (Π ′ • i-j+1 Π ′′ ), for j ≤ i < k ′ + j, (Π • i-k ′ +1 Π ′′ ) • j Π ′ , for j + k ′ ≤ i < k + k ′ -1, 2. (Equivariance) For each 1 ≤ i ≤ m, τ ∈ S m and σ ∈ S n , let τ • i σ ∈
S m+n-1 be given by inserting the permutation σ at the ith place in τ .

If Π ∈ C k and Π ′ ∈ C k ′ then (Πτ ) • i (Π ′ σ) = (Π • τ (i) Π ′ )(τ • i σ). 3. (Unitality) 1 • 1 Π ′ = Π ′ and Π • i 1 = Π for each Π ∈ C k and Π ′ ∈ C k ′ .
Let V = n V n be a graded space over C. We will say that V is a (symmetric) C-module, if there is an action of C on V which satisfies:

1. Each Π ∈ C m acts as a linear application V m → V .

(Compatibility with the graduation)

[π 1 , . . . , π m ](V j 1 , . . . , V jm ) = 0 if #π i = j i for some 1 ≤ i ≤ m and o m (V j 1 , . . . , V jm ) = 0. Otherwise, [π 1 , . . . , π m ] ∈ C n sends V #π 1 × • • • × V #πm to V n . Note also the special case 1(v) = v for each v ∈ V .
3. (Compatibility with the compositions)

(Π• i Π ′ )(v 1 , . . . , v k+k ′ -1 ) = Π(v 1 , . . . , v i-1 , Π ′ (v i , . . . , v i+k ′ -1 ), v i+k ′ , . . . , v k+k ′ -1 ). 4. (Symmetry) Π(v 1 , . . . , v k ) = (Πσ)(v σ(1) , . . . , v σ(k) ). If V is generated (as a C-module) by {v n : n ≥ 1} with v n ∈ V n , then setting v {π 1 ,...,πm} = [π 1 , . . . , π m ](v #π 1 , . . . , v #πm ), we have V n = span{v π : π n}.
Note that the existence of v π follows from the point 4 of the definition of a C-module.

Example 2.2 If

A is a noncommutative alphabet, the algebra C A can be endowed with a structure of C-module by setting

[π 1 , . . . , π m ](w 1 , . . . , w m ) = [π 1 ,...,πm] (w 1 , . . . , w m ) if w i ∈ A #π i for each 1 ≤ i ≤ m 0 otherwise where w 1 , . . . , w m ∈ A * and [π 1 ,...,πm] (w 1 , . . . , w m ) = a 1 . . . a n is the only word of A #π 1 +•••+#πm such that for each 1 ≤ i ≤ m, if π i = {j 1 , . . . , j ℓ }, a j 1 . . . a j ℓ = w j . Note that C[A] has also a structure of C-module defined by [π 1 , . . . , π m ](x 1 , . . . , x m ) = x 1 . . . x m if x i is a monomial of degree #π i . Proposition 2.3 WSym is a C-module.

Proof:

We define the action of C on the power sums by

[π 1 , . . . , π m ](Φ n 1 , . . . , Φ nm ) = Φ {π 1 ,...,πm} if n i = #π i for each 1 ≤ i ≤ m 0 otherwise.
and extend it linearly to the spaces WSym n . Since this action is compatible with the realization:

[π 1 , . . . , π m ](Φ n 1 , . . . , Φ nm )(A) = [π 1 ,...,πm] (Φ n 1 (A), . . . , Φ nm (A)) (the definition of π is given in Example 2.
2) and WSym is obviously stable by the action of C,

WSym(A) is a sub-C-module of C A . Hence, WSym is a C-module. A morphism of C-module is a linear map ϕ from a C-module V 1 to another C- module V 2 satisfying ϕΠ(v 1 , . . . , v m ) = Π(ϕ(v 1 ), . . . , ϕ(v m )) for each Π ∈ C m .
In this context, a virtual alphabet (or a specialization) is defined by a morphism of C-module ϕ from WSym to a C-module V . The image of a word symmetric function f will be denoted by f [ϕ]. The C-module WSym is free in the following sense:

Proposition 2.4 Let V be generated by v 1 ∈ V 1 , v 2 ∈ V 2 , . . . , v n ∈ V n , .
. . as a C-module (or equivalently, V n = span{v π : π n}). There exists a morphism of C-module ϕ : WSym → V , which sends Φ n to v n .

Proof This follows from the fact that {Φ π : π n} is a basis of WSym n . Let ϕ : WSym n → V n be the linear map such that ϕ(Φ π ) = V π ; this is obviously a morphism of C-module.

For convenience, we will write WSym[ϕ] = ϕWSym. 3 The Hopf algebra of set partitions into lists

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], [START_REF] Duchamp | Noncommutative symmetric functions VI: free quasi-symmetric functions and related algebras[END_REF][START_REF] Duchamp | Free quasi-symmetric functions, product actions and quantum field theory of partitions[END_REF]} and {[3, 1, 2], [START_REF] Duchamp | Free quasi-symmetric functions, product actions and quantum field theory of partitions[END_REF][START_REF] Duchamp | Noncommutative symmetric functions VI: free quasi-symmetric functions and related algebras[END_REF]} 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 [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF]. If Π is a set partition into lists of {1, . . . , n}, we will write Π n. We will denote by cycle support(σ) the cycle support of a permutation σ, 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 (σ, π) where σ is a permutation of size n and π is a set partition which is less fine than or equal to the cycle support of σ. Indeed, from a set partition π and a permutation σ, we obtain a set partition into lists Π by ordering the elements of each block of π so that they appear in the same order as in σ.

Construction

Let Π n and Π ′ n ′ be two set partitions into lists. Then, we set

Π ⊎ Π ′ = Π ∪ {[l 1 + n, . . . , l k + n] : [l 1 , . . . , l k ] ∈ Π ′ } n + n ′ . Let Π ′ ⊂ Π n,
since the integers appearing in Π ′ are all distinct, the standardized std(Π ′ ) of Π ′ is well defined as the unique set partition into lists obtained by replacing the ith smallest integer in Π by i. For example, std({ [START_REF] Duchamp | Free quasi-symmetric functions, product actions and quantum field theory of partitions[END_REF][START_REF] Bergeron | Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables[END_REF], [START_REF] Burnside | Theory of groups of finite order[END_REF][START_REF] Krishnamurthy | Combinatorics, Theory and Applications[END_REF], [START_REF] Duchamp | Hopf Algebra of Diagrams[END_REF][START_REF] Gelfand | Noncommutative symmetric functions[END_REF] [START_REF] Bergeron | Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables[END_REF][START_REF] Duchamp | Hopf Algebra of Diagrams[END_REF], [START_REF] Duchamp | Noncommutative symmetric functions VI: free quasi-symmetric functions and related algebras[END_REF][START_REF] Duchamp | Free quasi-symmetric functions, product actions and quantum field theory of partitions[END_REF]}.

}) = {[3, 1],

Definition 3.3

The Hopf algebra BWSym is formally defined by its basis (Φ Π ) where the Π are set partitions into lists, its product

Φ Π Φ Π ′ = Φ Π⊎Π ′ and its coproduct ∆(Φ Π ) = Φ std(Π ′ ) ⊗ Φ std(Π ′′ )
, where the sum is over the

(Π ′ , Π ′′ ) such that Π ′ ∪ Π ′′ = Π and Π ′ ∩ Π ′′ = ∅.
Following Section 3.1 and for convenience, we will use alternatively Φ Π and Φ ( σ π ) to denote the same object. We define

M Π = M ( σ π ) by setting Φ ( σ π ) = π≤π ′ M ( σ π )
′ . The formula being diagonal, it defines M Π for any Π and proves that the family (M Π ) Π is a basis of BWSym. Consider for instance

{[3, 1], [2]} ∼ 321 {{1, 3}, {2}} , we have Φ {[3,1],[2]} = M {[3,1],[2]} + M {[3,2,1]} .
For any set partition into lists Π, let s(Π) be the corresponding classical set partition. Then, the linear application φ defined by φ(Φ Π ) = Φ s(Π) 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 σ ) whose product is E σ E τ = E σ/τ , where σ/τ is the word obtained by concatening σ and the word obtained from τ by adding the size of σ to all the letters (for example 321/132 = 321564). The subspace V of WSym ⊗ FQSym linearly spanned by the Φ π ⊗ E σ such that the cycle supports of σ is finer than π is a subalgebra, and the linear application sending Φ π,σ to Φ π ⊗E σ is an isomorphism of algebras. Moreover, when the set of cycle supports of σ is finer than π, M π ⊗ E σ also belongs to V and is the image of M ( σ π ) . The linear application from BWSym to FQSym which sends M {[σ]} to E σ and M Π to 0 if card(Π) > 1, is also a morphism of algebras.

Realization

Let A (j) = {a (j) i | i > 0} be an infinite set of bi-indexed noncommutative variables, with the order relation defined by a

(j) i < a (j) i ′ if i < i ′ . Let A = j A (j) . Consider the set partition into lists Π = {L 1 , L 2 , . . .} = {[l 1 1 , l 1 2 , . . . , l 1 n 1 ], [l 2 1 , l 2 2 , . . . , l 2 n 2 ], . . .} n.
Then, one obtains a polynomial realization BWSym(A) by identifying Φ Π with Φ Π (A), the sum of all the monomials a 1 . . . a n (where the a i are in A) such that k = k ′ implies a l k t , a l k ′ s ∈ A (j) for some j, and for each k, std(a i 1 . . .

a in k ) = std(l k 1 . . . l k n k ) with {l k 1 , . . . , l k n k } = {i 1 < • • • < i n k } (
The "B" of BWSym is for "bi-indexed letters"). The coproduct ∆ can be interpreted by identifying ∆(Φ Π ) with Φ Π (A+ B) as in the case of WSym. Here, if a ∈ A and b ∈ B then a and b are not comparable.

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

Now, let M ′

Π (A) be the sum of all the monomials a 1 . . . a n , a i ∈ A, such that a l k t and a l k ′ s belong in the same A (j) if and only if k = k ′ , and for each k,

std(a i 1 . . . a in k ) = std(l k 1 . . . l k n k ) with {l k 1 , . . . , l k n k } = {i 1 < • • • < i n k }. For example, the monomial a (1) 1 a (1) 1 a (1) 2 appears in the expansion of Φ {[1,3],[2]} , but not in the one of M ′ {[1,3],[2]} . The M ′ Π form a new basis (M ′ Π ) of BWSym.
Note that this basis is not the same as (M Π ). For example, one has

Φ {[1],[2]} = M {[1],[2]} + M {[1,2]} = M ′ {[1],[2]} + M ′ {[1,2]} + M ′ {[2,1]} .
Consider the basis F σ of FQSym defined in (4). The linear application, from BWSym to FQSym, which sends M ′ {[σ]} to F σ , and M ′ Π to 0 if card(Π) > 1, is a morphism of algebras.

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 = [ℓ 1 , . . . , ℓ k ] and M = [m 1 , . . . , m 2 ] are two lists, the shuffle product is defined recursively by [ ]

L = L [ ] = {L} and L M = [ℓ 1 ].([ℓ 2 , . . . , ℓ k ] M) ∪ [m 1 ].(L [m 2 , . . . , m k ]
). The algebra of biword quasisymmetric functions (BWQSym) has its bases indexed by set compositions into lists. The algebra is defined as the vector space spanned by the formal symbols Φ Π , where Π is a composition into lists of the set {1, . . . , n} for a given n, together with the product Φ Π Φ Π ′ = Π ′′ ∈Π Π ′ [n] Φ Π ′′ , where Π ′ [n] means that we add n to each of the integers in the lists of Π ′ and Π is a composition into lists of {1, . . . , n}. Endowed with the coproduct defined by∆(Φ Π ) = Π ′ .Π ′′ =Π Φ std(Π ′ ) ⊗ Φ std(Π ′′ ) , BWQSym has a structure of Hopf algebra. Note that BWQSym = n BWQSym n is naturally graded; the dimension of the graded component BWQSym n is 2 n-1 n! (see sequence A002866 in [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF]). The algebra BSym = n BSym n is a graded cocommutative Hopf algebra whose bases are indexed by sets of permutations. Formally, we set BSym n = span{φ {σ 1 ,...,σ k } :

σ i ∈ S n i , n 1 + • • • + n k = n}, φ S 1 .φ S 2 = φ S 1 ∪S 2
and for any permutation σ, φ {σ} is primitive. The dimensions of the graded components are given by the sequence A077365 of [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF].

Finally, BQSym = n BQSym n is generated by φ [σ 1 ,...,σ k ] , its product is φ L φ L ′ = L ′′ ∈L L ′ φ L ′′ and its coproduct is ∆(φ L ) = L=L ′ .L ′′ φ L ′ ⊗ φ L ′′ .
The dimension of the graded component BQSym n is given by Sloane's sequence A051296 [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF].

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 ⊂ S n acting on X by permuting its elements. We consider the set Y X of the maps X → Y . The type of a map f is the vector of the multiplicities of its images; more precisely, type(f ) ∈ N Y with type(f

) y = #{x ∈ 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 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 λ I denotes the (integer) partition obtained by removing all the zeros in I and reordering its elements in the decreasing order, λ I = λ I ′ implies n I = n I ′ ; it suffices to understand how to compute n λ when λ is a partition. The Redfield-Pólya theorem deals with this problem and its main tool is the cycle index:

Z G := 1 #G σ∈G p cycle type(σ) ,
where cycle type(σ) is the (integer) partition associated to the cycle of σ (for instance σ = 325614 = (135)(46), cycle type(σ) = [3, 2, 1]). When λ = [λ 1 , . . . , λ k ] is a partition, p λ denotes the (commutative) symmetric function p λ = p λ 1 . . . p λ 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 λ ) of monomial symmetric functions is given by

Z G = λ n λ m λ .
Example 4.2 Suppose that we want to enumerate the non-isomorphic nonoriented graphs on three vertices. The symmetric group S 3 acting on the vertices induces an action of the group

G := {123456, 165432, 345612, 321654, 561234, 543216} ⊂ 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 = 1 6 (p 6 1 + 3p 2 2 p 2 1 + 2p 2 3 ) = m 6 + 2m 51 + 4m 42 + 6m 411 + 6m 33 + . . .
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.

Word R-P theorem

If σ is a permutation, we define Φ σ := Φ cycle support(σ) . Now for our purpose, a map f ∈ Y X will be encoded by a word w : we consider an alphabet A = {a y : y ∈ Y }, the elements of X are relabelled by 1, 2, . . . , #X = n and w is defined as the word b 1 . . . b n ∈ 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 σ ∈ G, one has

Φ σ = wσ=w w. (1)
The cycle support polynomial is defined by Z

G := σ∈G Φ σ . From (1) we deduce Z G = w #Stab G (w)w
where Stab G (w) = {σ ∈ G : wσ = w} is the subgroup of G which stabilizes w. In terms of monomial functions, this yields :

Theorem 4.3 Z G = π #Stab G (w π )M π
where w π is any word a 1 . . . a n such that a i = a j if and only if i, j ∈ π k for some 1 ≤ k ≤ n.

Example 4.4 Consider the same example as in Example 4.2. Each graph is now encoded by a word a 1 a 2 a 3 a 4 a 5 a 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 := Φ {{1},{2},{3},{4},{5},{6}} + Φ {{2,6},{3,5},{1},{4}} +Φ {{1,3},{4,6},{2},{5}} + Φ {{1,5},{2,4},{3},{6}} + 2Φ {{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 Φ {{1},{2},{3},{4},{5},{6}} and Φ {{2,6},{3,5},{1},{4}} . The monomials of M {{2,6},{3,5},{1},{4}} are of the form abcdba, where a, b, c and d are four distinct letters. The stabilizer of abcdba in G is the two-element subgroup {123456, 165432}.

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 #Stab G (w) appearing in Section 4.2.

If w is a word we will denote by 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 = #orb G (w)#Stab G (w) (2)
Denote by Λ(π) the unique integer partition defined by (#π 1 , . . . ,

#π k ) if π = {#π 1 , . . . , π k } with #π 1 ≥ #π 2 ≥ • • • ≥ #π k . If λ = (m km , . . . , 2 k 2 , 1 k 1 ) we set λ ! = k m ! . . . k 2 !k 1 !.
The shape of a word w is the unique set partition π(w) such that w is a monomial of M π(w) . Note that all the orbits of words with a fixed shape π have the same cardinality. Furthermore, let π = {π 1 , . . . , π k } and A k be an alphabet of size k, the number of words of shape π on A k equals Λ(π) ! . Hence the set of all the words of shape π on the alphabet A k is partitioned into Λ(π) ! #orb(wπ ) orbits of size #orb(w π ). We deduce that:

n λ = Λ(π)=λ λ ! #orb G (w π ) = Λ(π)=λ λ ! #Stab G (w π ) #G . ( 3
)
If we consider the morphism of algebra θ : WSym → Sym which sends Φ n to p n , we have θ(M π ) = Λ(π) ! m λ . Hence, we have

1 #G θ(Z G ) = λ   Λ(π)=λ λ ! #orb G (w π )   m λ = λ n λ m λ
as expected by the Redfield-Pólya theorem (Theorem 4.1).

R-P theorem without multiplicities

In this section we give a BWSym version of the R-P theorem whose main property is to have no 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 abcdcb. In terms of set partitions into lists, this can be interpreted by M { [START_REF] Bergeron | Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables[END_REF][START_REF] Duchamp | Hopf Algebra of Diagrams[END_REF], [START_REF] Burnside | Theory of groups of finite order[END_REF][START_REF] Duchamp | Free quasi-symmetric functions, product actions and quantum field theory of partitions[END_REF], [START_REF] Bergeron | Combinatorial Species and Treelike Structures[END_REF], [START_REF] Duchamp | Noncommutative symmetric functions VI: free quasi-symmetric functions and related algebras[END_REF]} +M { [START_REF] Duchamp | Hopf Algebra of Diagrams[END_REF][START_REF] Bergeron | Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables[END_REF], [START_REF] Duchamp | Free quasi-symmetric functions, product actions and quantum field theory of partitions[END_REF][START_REF] Burnside | Theory of groups of finite order[END_REF], [START_REF] Bergeron | Combinatorial Species and Treelike Structures[END_REF], [START_REF] Duchamp | Noncommutative symmetric functions VI: free quasi-symmetric functions and related algebras[END_REF]} → 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

Z G := σ∈G Φ ( σ cycle support(σ) ) = π σ∈Stabπ (G) M ( σ π ) .
Consider again Example 4.4.

Z G = Φ ( 123456
{{1}{2}{3}{4}{5}{6}} ) + Φ ( 165432
{{1}{26}{35}{4}} ) + Φ ( 345612 {{135}{246}} ) + Φ ( 321654 {{13}{2}{46}{5}} ) + Φ ( 561234 {{135}{246}} ) + Φ ( 543216 {{15}{234}{6}} ) .
When expanded in the monomial M basis, there are exactly 2 terms of the form M ( σ {{2,6},{3,5},{1},{4}} ) (for σ = 123456 and σ = 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 Φ ( σ π ) := w σ w , where the sum is over the words w = w 1 . . . w n (w i ∈ A) such that if i and j are in the same block of π then w i = w j . If we consider the linear application ψ sending Φ ( σ π ) to Φ ( σ π ) , ψ sends M ( σ π ) to M ( σ π ) := w σ w , where the sum is over the words w = w 1 . . . w n (w i ∈ A) such that i and j are in the same block of π if and only if w i = w j . Let w be a word, the set of permutations σ such that σ w appears in the expansion of ψ(Z G ) is the stabilizer of w in G.

i k ) = {(τ, σ) ∈ H × G : a τ (i σ(j) ) for each 1 ≤ j ≤ n}.
Hence, from Burnside's classes formula, sending each variable to 1 in Z(H; G), we obtain the number of orbits of H × 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} ⊂ S n on the colours. We want to count the number of graphs up to permutation of the vertices (G = 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 Φ {1. 1 + a 3 2 + a 3 3 ) + 2 i =j a 2 i a j + 2 i =j a j a i a j + 2 i =j a j a 2 i +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 ).

The coefficient 3 of a 1 a 2 a 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 obtains Z[H, S 3 ] = 18 × 4: 18 is the order of the group H × S 3 and 4 is the number of orbits: {a 3 1 , a 3 2 , a 3 3 }, {a 2 1 a 2 , a 1 a 2 a 1 , a 2 a 2 1 , a 2 2 a 3 , a 2 a 3 a 2 , a 3 a 2 2 , a 2 3 a 1 , a 3 a 1 a 3 , a 1 a 2 3 }, {a 2 2 a 1 , a 2 a 1 a 2 , a 1 a 2 2 , a 2 1 a 3 , a 1 a 3 a 1 , a 3 a 2 1 , a 2 3 a 2 , a 3 a 2 a 3 , a 1 a 2 3 }, 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 }.

Example 2.5 1 .

 1 Let A be an infinite alphabet. The restriction to WSym(A) of the morphism of algebra ϕ : C A → C[A] defined by ϕ(a) = a is a morphism of C-module sending WSym(A) to Sym(A) (the algebra of symmetric functions on the alphabet A). This morphism can be defined without the help of alphabets, considering that Sym is generated by the power sums p 1 , . . . , p n , . . . with the action [π 1 , . . . , π m ](p #π 1 , . . . , p #πm ) = p #π 1 . . . p #πm .2. Let A be any alphabet (finite or not). If V is a sub-C-module ofC A generated by the homogeneous polynomials P n ∈ C[A n ] as a C-module, the linear map sending, for each π = {π 1 , . . . , π m }, Φ π to Π [P #π 1 , . . . , P #πm ], where Π = [π 1 , . . . , π m ], is a morphism of Cmodule.

Example 3 . 2

 32 Starting the set partition π = {{1, 4, 5}, {6}, {3, 7}, {2}} and the permutation σ = 4271563, we obtain the set partition into lists Π = {[4, 1, 5],[START_REF] Frobenius | Ueber die Congruenz nach einem aus zwei endlichen Gruppen gebildeten Doppelmodul[END_REF][START_REF] Burnside | Theory of groups of finite order[END_REF],[START_REF] Duchamp | Hopf Algebra of Diagrams[END_REF],[START_REF] Bergeron | Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables[END_REF]}.

4. 5 Proposition 4 . 6

 546 WSym and Harary-Palmer type enumerationsLet A := {a 1 , . . . , a m } be a set of formal letters and I = [i 1 , . . . , i k ] a sequence of elements of {1, . . . , m}. We define the virtual alphabet A I byΦ n (A I ) := (a i 1 . . . a i k ) n k + (a i 2 . . . a i k a i 1 ) n k + • • • + (a i k a 1 . . . a i k-1 ) n k ,if k divides n and 0 otherwise. If σ ∈ S m we define the alphabet A σ as the formal sum of the alphabets A c associated to its cycles:Φ {1...n} [A σ ] := c cycle in σ Φ n [A c ].From Example 2.5.2, the set {Φ {1,...,n} [A σ ] : n ∈ N} generates the sub-Cmodule WSym[A σ ] of C A (the composition Π acting by Π ). Let H ⊂ S m and G ⊂ S n be two permutation groups. We define Z(H;G) := τ ∈H Φ G [A τ ]. We have: Z(H; G) = w∈A n #Stab H,G (w)wwhere Stab H,G (w) denotes the stabilizer of w under the action of H × 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, Stab H,G (a i 1 . . . a

  The linear application sending each biword σ w to w sends Φ ( σ π ) to Φ π and Stab G (w)w. Note that #Stab G (w) is also the coefficient of the corresponding monomial M π(w) in the cycle support polynomial Z G . For instance, we recover the coefficient 2 in Example 4.4 from the biwords

	σ∈Stab G (w)	σ w to #

123456

abcdcb and 165432 abcdcb in ψ(Z G ).

  ..n} [A σ ] for 1 ≤ n ≤ 3 and σ ∈ H. We find Φ {1} [A 123 ] = a 1 + a 2 + a 3 , Φ {1} [A 231 ] = Φ {1} [A 312 ] = 0, Φ {1,2} [A 123 ] = a 2 1 + a 2 2 + a 2 3 , Φ {1,2} [A 231 ] = Φ {1,2} [A 312 ] = 0, Φ {1,2,3} [A 123 ] = a 3 1 + a 3 2 + a 3 3 , Φ {1,2,3} [A 213 ] = a 2 a 3 a 1 + a 3 a 1 a 2 + a 1 a 2 a 3 , and Φ {1,2,3} [A 312 ] = a 1 a 3 a 2 + a 3 a 2 a 1 + a 2 a 1 a 3 . Now, we deduce the values of the other Φ π [A σ ]with π 3 and σ ∈ H by the action of Π . For instance:Φ {{1,2},{3}} [A 123 ] = [{1,2},{3}] Φ {1,2} [A 123 ], Φ {1} [A 1 ] = a 3 1 + a 2 1 a 2 + a 2 1 a 3 + a 2 2 a 1 + a 3 2 + a 2 2 a 3 + a 2 3 a 1 + a 2 3 a 2 + a 3 3 . We find also Φ {{1,3},{2}} [A 123 ] = a 3 1 + a 1 a 2 a 1 + a 1 a 3 a 1 + a 2 a 1 a 2 + a 3 2 + a 2 a 3 a 2 + a 3 a 1 a 3 + a 3 a 2 a 3 + a 3 3 , Φ {{1},{2,3}} [A 123 ] = a 3 1 + a 2 a 2 1 + a 3 a 2 1 + a 1 a 2 2 + a 3 2 + a 3 a 2 2 + a 1 a 2 3 + a 2 a 2 3 + a 3 3 , Φ {{1},{2},{3}} [A 123 ] = (a 1 + a 2 + a 3 ) 3 . The other Φ π [A σ ] are zero. Hence, Z[H; S 3 ] = Φ 123 [A 123 ] + Φ 132 [A 123 ] + Φ 213 [A 123 ] + Φ321 [A 123 ]+ Φ 231 [A 231 ] + Φ 231 [A 312 ] + Φ 312 [A 231 ] + Φ 312 [A 312 ] = 6(a 3

* This paper is partially supported by the ANR project PhysComb, ANR-08-BLAN-0243-04, the CMEP-TASSILI project 09MDU765 and the ANR project CARMA ANR-12-BS01-0017.