Séminaire Lotharingien de Combinatoire 75 (2017), Article B75h

WORD BELL POLYNOMIALS

AMMAR ABOUD^{†}, JEAN-PAUL BULTEL^{¶}, ALI CHOURIA^{‡}, JEAN-GABRIEL LUQUE^{‡}, AND OLIVIER MALLET^{‡}

Abstract. Multivariate partial Bell polynomials have been defined by E.T. Bell in 1934. These polynomials have numerous applications in Combinatorics, Analysis, Algebra, Probabilities, etc. Many of the formulas on Bell polynomials involve combinatorial objects (set partitions, set partitions into lists, permutations, etc.). So it seems natural to investigate analogous formulas in some combinatorial Hopf algebras with bases indexed by these objects. In this paper we investigate the connections between Bell polynomials and several combinatorial Hopf algebras: the Hopf algebra of symmetric functions, the Faà di Bruno algebra, the Hopf algebra of word symmetric functions, etc. We show that Bell polynomials can be defined in all these algebras, and we give analogs of classical results. To this aim, we construct and study a family of combinatorial Hopf algebras whose bases are indexed by colored set partitions.

1. Introduction

Multivariate partial Bell polynomials (Bell polynomials for short) have been defined by E.T. Bell in [1] in 1934. But their name is due to Riordan [29], who studied the Faà di Bruno formula [11, 12] allowing one to write the nth derivative of a composition f ∘ g in terms of the derivatives of f and g [28]. The applications of Bell polynomials in Combinatorics, Analysis, Algebra, Probability Theory, etc. are so numerous that it would take too long to exhaustively list them here. Let us give only a few seminal examples.

• The main applications to Probability Theory are based on the fact that the nth moment of a probability distribution is a complete Bell polynomial of the cumulants.

• Partial Bell polynomials are linked to Lagrange inversion. This follows from the Faà di Bruno formula.

• Many combinatorial formulas for Bell polynomials involve classical combinatorial

numbers like Stirling numbers, Lah numbers, etc. The Faà di Bruno formula and many combinatorial identities can be found in [7]. The

Ph.D. thesis of Mihoubi [24] contains a rather complete survey of the applications of these polynomials together with numerous formulas.

Some of the simplest formulas are related to the enumeration of combinatorial objects (set partitions, set partitions into lists, permutations, etc.). So it seems natural to investigate analogous formulas in some combinatorial Hopf algebras with bases indexed by these objects. We recall that combinatorial Hopf algebras are graded bialgebras with bases indexed by combinatorial objects such that the product and the coproduct have some compatibilities.

2010 Mathematics Subject Classification. 57T05, 11B73, 11B75.

Key words and phrases. Bell polynomials, Munthe-Kaas polynomials, set partitions, colored set partitions, Hopf algebras, symmetric functions, word symmetric functions, Faà di Bruno algebra, Lagrange inversion.

This paper is organized as follows. In Section 2, we investigate the combinatorial properties of colored set partitions. Section 3 is devoted to the study of the Hopf algebras of colored set partitions. After having introduced this family of algebras, we give some special cases which can be found in the literature. The main application explains the connections with Sym, the algebra of symmetric functions. This explains that we can recover some identities for Bell polynomials when the variables are specialized to combinatorial numbers from analogous identities in some combinatorial Hopf algebras. We show that the algebra WSym of word symmetric functions has an important role for this construction. In Section 4, we give a few analogs of complete and partial Bell polynomials in WSym, ΠQSym = WSym^{∗}, and ℂ⟨𝔸⟩ where 𝔸 = {a_{1}, …, a_{n}, … } is an infinite alphabet and investigate their main properties. Finally, in Section 5 we investigate the connection with other noncommutative analogs of Bell polynomials defined by Munthe-Kaas [33].

2. Definition, background and basic properties of colored set partitions

2.1. Colored set partitions. Let a = (a_{m})_{m≥1} be a sequence of nonnegative integers. A colored set partition associated with the sequence a is a set of pairs

Π = {[π_{1}, i_{1}], [π_{2}, i_{2}], …, [π_{k}, i_{k}]}

such that π = {π_{1}, …, π_{k}} is a partition of {1, …, n} for some n ∈ ℕ, and 1 ≤ i_{ℓ} ≤ a_{#π_{ℓ}} for 1 ≤ ℓ ≤ k, where #s denotes the cardinality of the set s. The integer n is the size of Π. We write |Π| = n, Π ⊨ n, and Π ⇛ π. We denote the set of colored partitions of size n associated with the sequence a by CP_{n}(a). Notice that these sets are finite. We also set CP(a) = ⋃_{n} CP_{n}(a). We endow CP with the additional statistic #Π, and set CP_{n,k}(a) = {Π ∈ CP_{n}(a) : #Π = k}.

Example 1. Consider the sequence whose first terms are a = (1, 2, 3, …). The colored partitions of size 3 associated with a are

CP_{3}(a) = {{[{1, 2, 3}, 1]}, {[{1, 2, 3}, 2]}, {[{1, 2, 3}, 3]}, {[{1, 2}, 1], [{3}, 1]}, {[{1, 2}, 2], [{3}, 1]}, {[{1, 3}, 1], [{2}, 1]}, {[{1, 3}, 2], [{2}, 1]},

{[{2, 3}, 1], [{1}, 1]}, {[{2, 3}, 2], [{1}, 1]}, {[{1}, 1], [{2}, 1], [{3}, 1]}}.

The colored partitions of size 3 and cardinality 2 are

CP_{3,2}(a) = {{[{1, 2}, 1], [{3}, 1]}, {[{1, 2}, 2], [{3}, 1]}, {[{1, 3}, 1], [{2}, 1]}, {[{1, 3}, 2], [{2}, 1]}, {[{2, 3}, 1], [{1}, 1]}, {[{2, 3}, 2], [{1}, 1]}}.

It is well-known (see, e.g., [24]) that the number of colored set partitions of size n for a given sequence a = (a_{n})_{n} is equal to the evaluation of the complete Bell polynomial A_{n}(a_{1}, …, a_{m}, …). It is also known that the number of colored set partitions of size n and cardinality k is given by the evaluation of the partial Bell polynomial B_{n,k}(a_{1}, a_{2}, …, a_{m}, …). That is,

#CP_{n}(a) = A_{n}(a_{1}, a_{2}, …) and #CP_{n,k}(a) = B_{n,k}(a_{1}, a_{2}, …).

Now, let Π = {[π_{1}, i_{1}], … [π_{k}, i_{k}]} be a set such that the π_{j}’s are finite sets of nonnegative integers with the property that no integer belongs to more than one π_{j}, and 1 ≤ i_{j} ≤ a_{#(π_{j})} for any j. Then the standardization std(Π) of Π is well-defined as the unique colored set partition obtained by replacing the ith smallest integer in the π_{j}’s by i.

Example 2. For instance, we have

std({[{1, 4, 7}, 1], [{3, 8}, 1], [{5}, 3]}) = {[{1, 3, 5}, 1], [{2, 6}, 1], [{4}, 3]} .

We define two binary operations, ⊎ : CP_{n,k}(a) ⊗ CP_{n′,k′}(a) ⟶ CP_{n+n′,k+k′}(a),

Π ⊎ Π′ = Π ∪ Π′[n],

where Π′[n] means that we add n to each integer occurring in the sets of Π′, and ⋓: CP_{n,k} ⊗ CP_{n′,k′} ⟶ P(CP_{n+n′,k+k′}),

Π ⋓ Π′ = {Π̂ ∪ Π̂′ ∈ CP_{n+n′,k+k′}(a) : std(Π̂) = Π and std(Π̂′) = Π′}.

Example 3. We have

{[{1, 3}, 5], [{2}, 3]} ⊎ {[{1}, 2], [{2, 3}, 4]} = {[{1, 3}, 5], [{2}, 3], [{4}, 2], [{5, 6}, 4]},

and

{[{1}, 5], [{2}, 3]} ⋓ {[{1, 2}, 2]} = {{[{1}, 5], [{2}, 3], [{3, 4}, 2]}, {[{1}, 5], [{3}, 3], [{2, 4}, 2]}, {[{1}, 5], [{4}, 3], [{2, 3}, 2]},

{[{2}, 5], [{3}, 3], [{1, 4}, 2]}, {[{2}, 5], [{4}, 3], [{1, 3}, 2]}, {[{3}, 5], [{4}, 3], [{1, 2}, 2]}}.

The operator ⋓ provides an algorithm which computes all colored partitions:

CP_{n,k}(a) = ⋃_{i_{1}+···+i_{k}=n} ⋃_{j_{1}=1}^{a_{i_{1}}} ⋯ ⋃_{j_{k}=1}^{a_{i_{k}}}{[{1, …, i_{1}}, j_{1}]} ⋓ ⋯ ⋓ {[{1, …, i_{k}}, j_{k}]}.  (2.1)

Nevertheless, some colored partitions are generated more than once using this process. For a triple (Π, Π′, Π′′), we denote by α_{Π′,Π′′}^{Π} the number of pairs of disjoint subsets (Π̂′, Π̂′′) of Π such that Π̂′ ∪ Π̂′′ = Π, std(Π̂′) = Π′, and std(Π̂′′) = Π′′.

Remark 4. Notice that, for a = 1 = (1, 1, …) (i.e., the ordinary set partitions), there is an alternative way to construct the set CP_{n}(1) efficiently. It suffices to use the induction

CP_{0}(1) = {∅},
CP_{n+1}(1) = {π ∪ {{n + 1}} : π ∈ CP_{n}(1)} ∪ {(π \ {e})  (2.2)
∪ {e ∪ {n + 1}} : π ∈ CP_{n}(1), e ∈ π}}.

By the application of this recurrence, the set partitions of CP_{n+1}(1) are each obtained exactly once from the set partitions of CP_{n}(1).

2.2. Generating functions. The generating functions of the colored set partitions CP(a) is obtained from the cycle generating function for the species of colored set partitions. The construction is rather classical, see, e.g., [3]. Recall first that a species of structures is a rule F which produces for each finite set U, a finite set F [U], and for each bijection ϕ : U ⟶ V, a function F [ϕ] : F [U] ⟶ F [V] satisfying the following properties:

• for all pairs of bijections ϕ : U ⟶ V and ψ : V ⟶ W, we have F [ψ ∘ ϕ] = F [ψ] ∘ F [ϕ];

• if Id_{U} denotes the identity map on U, then F [Id_{U}] = Id_{F [U]}.

An element s ∈ F [U] is called an F -structure on U. The cycle generating function of a species F is the formal power series in infinitely many independent variables p_{1}, p_{2}, … (called power sums) defined by the formula

Z_{F} (p_{1}, p_{2}, …) = ∑_{n=0}^{∞} \frac{1}{n!} ∑_{σ∈𝔖_{n}} |F ([n])^{σ}|p^{ct(σ)},  (2.3)

where F ([n])^{σ} denotes the set of F -structures on [n] := {1, …, n} which are fixed by the permutation σ, ct(σ) is the cycle type of σ, that is, the decreasing vector of the cardinalities of the cycles of σ, and p^{λ} = p_{λ_{1}} ⋯ p_{λ_{k}} if λ is the vector [λ_{1}, …, λ_{k}]. For instance, the trivial species TRIV has only one TRIV-structure for every n. Hence, its cycle generating function is nothing else but the Cauchy function

σ_{1} := exp \{∑_{n≥1} \frac{p_{n}}{n} \} = ∑_{n≥0} h_{n}.  (2.4)

Here, h_{n} denotes the complete function h_{n} = ∑_{λ⊢n} \frac{1}{z_{λ}} p^{λ}, where λ ⊢ n means that λ is a partition of n, and z_{λ} = ∏_{i} i^{m_{i}(λ)}m_{i}(λ)! if m_{i}(λ) is the multiplicity of the part i in λ.

We consider also the species NCS(a) of non-empty colored sets having a_{n} NCS(a)- structures on [n] which are invariant under permutations. Its cycle generating function is

Z_{NCS(a)} = ∑_{n≥1} a_{n}h_{n}.  (2.5)

As a species, CP(a) is the composition TRIV ∘ NCS(a). Hence, its cycle generating function is obtained by computing the plethysm

Z_{NCS(a)}(p_{1}, p_{2}, …) = σ_{1}[Z_{NCS(a)}] = exp \{∑_{n>0} \frac{1}{n} ∑_{k>0} a_{k}p_{n}[h_{k}]\} .  (2.6)

The exponential generating function of CP(a) is obtained by setting p_{1} = t and p_{i} = 0 for i > 1 in (2.6):

∑_{n≥0} A_{n}(a_{1}, a_{2}, …)\frac{t^{n}}{n!} = exp \{∑_{i>0} \frac{a_{i}}{i!} t^{i}\} .  (2.7)

We deduce easily that the A_{n}(a_{1}, a_{2}, …) are multivariate polynomials in the variables a_{i}’s. These polynomials are called complete Bell polynomials [1]. The double generating function of #(CP_{n,k}(a)) is easily deduced from (2.7) by

∑_{n≥0} ∑_{k≥0} B_{n,k}(a_{1}, a_{2}, …)\frac{x^{k}t^{n}}{n!} = exp \{x ∑_{i>0} \frac{a_{i}}{i!} t^{i}\} .  (2.8)

Hence,

∑_{n≥k} B_{n,k}(a_{1}, a_{2}, …)\frac{t^{n}}{n!} = \frac{1}{k!} (∑_{i>0} \frac{a_{i}}{i!} t^{i})^{n} .  (2.9)

So, we have

A_{n}(a_{1}, a_{2}, …) = ∑_{k=1}^{n} B_{n,k}(a_{1}, a_{2}, …), for all n ⩾ 1 and A_{0}(a_{1}, a_{2}, …) = 1. (2.10)

The multivariate polynomials B_{n,k}(a_{1}, a_{2}, …) are called partial Bell polynomials [1]. Let S_{n,k} denote the Stirling number of the second kind, which counts the number of ways to partition a set of n objects into k nonempty subsets. We have

B_{n,k}(1, 1, …) = S_{n,k}.  (2.11)

Note also that A_{n}(x, x, …) = ∑_{k=0}^{n} S_{n,k}x^{k} is the classical univariate Bell polynomial denoted by ϕ_{n}(x) in [1]. There are several other identities that involve combinatorial numbers, for instance, we have

B_{n,k}(1!, 2!, 3!, …) = \binom{n − 1}{k − 1}\frac{n!}{k!}, (Unsigned Lah numbers \underline{A105278} in [30]), (2.12)

B_{n,k}(1, 2, 3, …) = \binom{n}{k}k^{n−k}, (Idempotent numbers \underline{A059297} in [30]),  (2.13)
B_{n,k}(0!, 1!, 2!, …) = |s_{n,k}|, (Stirling numbers of the first kind \underline{A048994} in [30]). (2.14)

We can also find many other examples in [1, 7, 23, 34, 25].

Remark 5. Without loss of generality, when needed, we will suppose a_{1} = 1 in the remainder of this paper. Indeed, if a_{1} ≠ 0, then the generating function gives

B_{n,k}(a_{1}, a_{2}, …, a_{p}, …) = a_{1}^{k}B_{n,k} (1, \frac{a_{2}}{a_{1}} , ⋯, \frac{a_{p}}{a_{1}} )  (2.15)

and, when a_{1} = 0,

B_{n,k}(0, a_{2}, …, a_{p}, …) = \begin{cases}0, if n < k, \\ \frac{n!}{(n−k)!}B_{n,k}(a_{2}, …, a_{p}, …), & if n ≥ k. \end{cases}  (2.16)

Notice that the ordinary series of the isomorphism types of CP(a) is obtained by setting p_{i} = t^{i} in (2.6). Observing that under this specialization we have p_{k}[h_{n}] = t^{nk}, we obtain, unsurprisingly, the ordinary generating function of colored (integer) partitions

∏_{i>0} \frac{1}{(1 − t^{i})^{a_{i}}} .  (2.17)

2.3. Bell polynomials and symmetric functions. The algebra of symmetric functions [22, 20] is isomorphic to its polynomial realization Sym(𝕏) on an infinite set 𝕏 = {x_{1}, x_{2}, … } of commuting variables, where the algebra Sym(𝕏) is defined as the set of polynomials invariant under permutation of the variables. As an algebra, Sym(𝕏) is freely generated by the power sum symmetric functions p_{n}(𝕏), defined by p_{n}(𝕏) = ∑_{i⩾1} x_{i}^{n}, or the complete symmetric functions h_{n}, where h_{n} is the sum of all monomials of total degree n in the variables x_{1}, x_{2}, . . .. The generating function for the h_{n}, called Cauchy function, is

σ^{t}(𝕏) = ∑_{n⩾0} h^{n}(𝕏)t^{n} = ∏_{i⩾1}(1 − x^{i}t)^{−1}.  (2.18)

The relationship between the two families (p_{n})_{n∈ℕ} and (h_{n})_{n∈ℕ} is described in terms of generating functions by the Newton formula:

σ_{t}(𝕏) = exp \{∑_{n⩾1} p_{n}(𝕏)\frac{t^{n}}{n} \} .  (2.19)

Notice that Sym is the free commutative algebra generated by p_{1}, p_{2} …, i.e., Sym = ℂ[p_{1}, p_{2}, …] and Sym(𝕏) = ℂ[p_{1}(𝕏), p_{2}(𝕏), …] when 𝕏 is an infinite alphabet without relations among the variables. As a consequence of the Newton Formula (2.19), it is also the free commutative algebra generated by h_{1}, h_{2}, . . .. The freeness of the algebra provides a mechanism of specialization. For any sequence of commuting scalars u = (u_{n})_{n∈ℕ}, there is an algebra homomorphism ϕ_{u} sending p_{n} to u_{n}, for n ∈ ℕ (respectively sending h_{n} to a certain v_{n} which can be deduced from u). These homomorphisms are manipulated as if there exists an underlying alphabet (so called virtual alphabet) 𝕏_{u} such that p_{n}(𝕏_{u}) = u_{n} (respectively h_{n}(𝕏_{u}) = v_{n}). The interest of such a vision is that one defines operations on sequences and symmetric functions by manipulating alphabets.

The bases of Sym are indexed by the partitions λ ⊢ n of all the integers n. A partition λ of n is a finite nondecreasing sequence of positive integers (λ_{1} ≥ λ_{2} ≥ ⋯) such that ∑_{i} λ_{i} = n.

By specializing either the power sums p_{i} or the complete functions h_{i} to the numbers \frac{a_{i}}{i!} , the partial and complete Bell polynomials are identified with well-known bases.

The algebra Sym is usually endowed with three coproducts:

• the coproduct Δ such that the power sums are Lie-like (Δ(p_{n}) = p_{n} ⊗ 1 + 1 ⊗ p_{n});

• the coproduct Δ′ such that the power sums are group-like (Δ′(p_{n}) = p_{n} ⊗ p_{n});

• the coproduct of Faà di Bruno (see, e.g., [9, 18]). Most of the formulas on Bell polynomials can be stated and proved using specializations

and these three coproducts. Since this is not really the purpose of our article, we have deferred a list of examples which are alternative proofs, in terms of symmetric functions, of existing formulas to Appendix A. One of the aims of our paper is to lift some of these identities to other combinatorial Hopf algebras.

3. Hopf algebras of colored set partitions

3.1. The Hopf algebras CWSym(a) and CΠQSym(a). Let CWSym(a) (CWSym for short when there is no ambiguity) be the algebra defined by its basis (Φ_{Π})_{Π∈CP(a)} indexed by colored set partitions associated with the sequence a = (a_{m})_{m≥1} and the product

Φ_{Π}Φ_{Π′} = Φ_{Π⊎Π′}.  (3.1)

Example 6. For instance,

Φ_{{[{1,3,5},3],[{2,4},1]}}Φ_{{[{1,2,5},4],[{3},1],[{4},2]}} = Φ_{{[{1,3,5},3],[{2,4},1],[{6,7,10},4],[{8},1],[{9},2]}}.

Let CWSym_{n} be the subspace generated by the elements Φ_{Π} with Π ⊨ n. For any n, we consider an infinite alphabet 𝔸_{n} of noncommuting variables, and we suppose 𝔸_{n} ∩𝔸_{m} = ∅ when n ≠ m.

For any colored set partition Π = {[π_{1}, i_{1}], [π_{2}, i_{2}], …, [π_{k}, i_{k}]}, we construct a polynomial Φ_{Π}(𝔸_{1}, 𝔸_{2}, …) ∈ ℂ ⟨⋃_{n} 𝔸_{n}⟩,

Φ_{Π}(𝔸_{1}, 𝔸_{2}, …) := ∑_{w=a_{1}...a_{n}} w,  (3.2)

where the sum is over the words w = a_{1} … a_{n} satisfying • For 1 ≤ ℓ ≤ k, a_{j} ∈ 𝔸_{i_{ℓ}} if and only if j ∈ π_{ℓ}.

• If j_{1}, j_{2} ∈ π_{ℓ}, then a_{j_{1}} = a_{j_{2}}.

Example 7. We have

Φ_{\{[\{1,3\},3],[\{2\},1],[\{4\},3]\}}(𝔸_{1}, 𝔸_{2}, …) = ∑_{\begin{matrix}a_{1},a_{2}∈𝔸_{3} \\ b∈𝔸_{1} \end{matrix}} a_{1}ba_{1}a_{2}.

Proposition 8. The family

Φ(a) := (Φ_{Π}(𝔸_{1}, 𝔸_{2}, …))_{Π∈CP(a)}

spans a subalgebra of ℂ ⟨⋃_{n} 𝔸_{n}⟩ which is isomorphic to CWSym(a).

Proof. First, observe that span(Φ(a)) is stable under concatenation. Indeed,

Φ_{Π}(𝔸_{1}, 𝔸_{2}, …)Φ_{Π′}(𝔸_{1}, 𝔸_{2}, …) = Φ_{Π⊎Π′}(𝔸_{1}, 𝔸_{2}, …).

Furthermore, this shows that span(Φ(a)) is homomorphic to CWSym(a) and that an explicit (surjective) homomorphism is given by Φ_{Π} ⟶ Φ_{Π}(𝔸_{1}, 𝔸_{2}, …). Observing that the family Φ(a) is linearly independent, the fact that the algebra CWSym(a) is graded in finite dimension implies the result. □

We turn CWSym into a Hopf algebra by defining the coproduct

Δ(Φ_{Π}) = ∑_{\begin{matrix}Π̂_{1}∪Π̂_{2}=Π \\ Π̂_{1}∩Π̂_{2}=∅ \end{matrix}} Φ_{std(Π̂_{1})} ⊗ Φ_{std(Π̂_{2})} = ∑_{Π_{1},Π_{2}} α_{Π_{1},Π_{2}}^{Π}Φ_{Π_{1}} ⊗ Φ_{Π_{2}}.  (3.3)

Indeed, CWSym splits as a direct sum of finite dimension spaces as

CWSym = ⨁_{n} CWSym_{n}.

This defines a natural graduation on CWSym. Hence, since it is a connected algebra, it suffices to verify that it is a bialgebra. More precisely:

Δ(Φ_{Π}Φ_{Π′}) = Δ(Φ_{Π⊎Π′})

= ∑_{Π̂_{1}∪Π̂_{2}=Π,Π̂′_{1}∪Π̂′_{2}=Π′[n] Π̂_{1}∩Π̂_{2}=∅,Π̂′_{1}∩Π̂′_{2}=∅} Φ_{std(Π̂_{1})⊎std(Π̂′_{1})} ⊗ Φ_{std(Π̂_{2})⊎std(Π̂′_{2})}

= Δ(Φ_{Π})Δ(Φ_{Π′}).

Notice that Δ is cocommutative.

Example 9. For instance,

Δ (Φ_{{[{1,3},5],[{2},3]}}) = Φ_{{[{1,3},5],[{2},3]}} ⊗ 1 + Φ_{{[{1,2},5]}} ⊗ Φ_{{[{1},3]}} + Φ_{{[{1},3]}} ⊗ Φ_{{[{1,2},5]}} + 1 ⊗ Φ_{{[{1,3},5],[{2},3]}}.

The graded dual CΠQSym(a) (which will be called CΠQSym for short when there is no ambiguity) of CWSym is the Hopf algebra generated as a space by the dual basis (Ψ_{Π})_{Π∈CP(a)} of (Φ_{Π})_{Π∈CP(a)}. Its product and its coproduct are given by

Ψ_{Π′}Ψ_{Π′′} = ∑_{Π∈Π′⋓Π′′} α_{Π′,Π′′}^{Π}Ψ_{Π} and Δ(Ψ_{Π}) = ∑_{Π′⊎Π′′=Π} Ψ_{Π′} ⊗ Ψ_{Π′′}.

Example 10. For instance, we have

Ψ_{{[{1,2},3]}}Ψ_{{[{1},4],[{2},1]}} = Ψ_{{[{1,2},3],[{3},4],[{4},1]}} + Ψ_{{[{1,3},3],[{2},4],[{4},1]}}
+ Ψ_{{[{1,4},3],[{2},4],[{3},1]}} + Ψ_{{[{2,3},3],[{1},4],[{4},1]}}
+ Ψ_{{[{2,4},3],[{1},4],[{3},1]}} + Ψ_{{[{3,4},3],[{1},4],[{2},1]}}

and

Δ(Ψ_{{[{1,3},3],[{2},4],[{4},1]}}) = 1 ⊗ Ψ_{{[{1,3},3],[{2},4],[{4},1]}} + Ψ_{{[{1,3},3],[{2},4]}} ⊗ Ψ_{{[{1},1]}} + Ψ_{{[{1,3},3],[{2},4],[{4},1]}} ⊗ 1.

3.2. Special cases. In this section, we investigate a few interesting special cases of the construction that we presented in the previous section.

3.2.1. Word symmetric functions. The most prominent example follows from the specialization a_{n} = 1 for all n. In this case, the Hopf algebra CWSym is isomorphic to WSym, the Hopf algebra of word symmetric functions. Let us briefly recall its construction. The algebra of word symmetric functions is a way to construct a noncommutative analog of the algebra Sym. Its bases are indexed by set partitions. After the seminal paper [32], this algebra was investigated in [2, 16] as well as an abstract algebra as in its realization with noncommutative variables. Its name comes from its realization as a subalgebra of ℂ⟨𝔸⟩ where 𝔸 = {a_{1}, …, a_{n}, … } is an infinite alphabet.

Consider the family of functions Φ := {Φ_{π}}_{π} whose elements are indexed by set partitions of {1, …, n}. The algebra WSym is formally generated by Φ using the shifted concatenation product: Φ_{π}Φ_{π′} = Φ_{ππ′[n]}, where π and π′ are set partitions of {1, …, n} and {1, …, m}, respectively, and π′[n] is the partition arising from π′ by adding n to each integer occurring in π′. The polynomial realization WSym(𝔸) ⊂ ℂ⟨𝔸⟩ is defined by Φ_{π}(𝔸) = ∑_{w}w, where the sum is over the words w = a_{1} ⋯ a_{n}, and where i, j ∈ π_{ℓ} implies a_{i} = a_{j}, if π = {π_{1}, …, π_{k}} is a set partition of {1, …, n}.

Example 11. For instance, we have Φ_{{{1,4},{2,5,6},{3,7}}}(𝔸) = ∑_{a,b,c∈𝔸} abcabbc.

Although the construction of WSym(𝔸), the polynomial realization of WSym, seems to be close to Sym(𝕏), the structures of the two algebras are quite different since the Hopf algebra WSym is not self-dual. The graded dual ΠQSym := WSym^{∗} of WSym admits a realization in the same subspace (WSym(𝔸)) of ℂ⟨𝔸⟩, but for the shuffle product.

With no surprise, we notice the following fact:

Proposition 12.

• The algebras CWSym(1, 1, …), WSym, and WSym(𝔸) are isomorphic.

• The algebras CΠQSym(1, 1, …), ΠQSym, and (WSym(𝔸), ) are isomorphic.

In the rest of the paper, when there is no ambiguity, we will identify the algebras WSym and WSym(𝔸).

The word analog of the basis (c_{λ})_{λ} of Sym ^{1} is the dual basis (Ψ_{π})_{π} of (Φ_{π})_{π}.

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 π.

Example 13. For instance,

Φ_{{{1,4},{2,5,6},{3,7}}} = M_{{{1,4},{2,5,6},{3,7}}} + M_{{{1,2,4,5,6},{3,7}}} + M_{{{1,3,4,7},{2,5,6}}}
+ M_{{{1,4},{2,3,5,6,7}}} + M_{{{1,2,3,4,5,6,7}}}.

From the definition of the M_{π}, we deduce that the polynomial representation of the word monomial functions is given by M_{π}(𝔸) = ∑_{w}w where the sum is over the words w = a_{1} ⋯ a_{n} where i, j ∈ π_{ℓ} if and only if a_{i} = a_{j}, where π = {π_{1}, …, π_{k}} is a set partition of {1, …, n}.

Example 14. M_{{{1,4},{2,5,6},{3,7}}}(𝔸) = ∑_{a,b,c∈𝔸 a≠b,a≠c,b≠c}abcabbc.

The analog of complete symmetric functions is the basis (S_{π})_{π} of ΠQSym which is the dual of the basis (M_{π})_{π} of WSym.

The algebra ΠQSym is also realized in the space WSym(𝔸): it is the subalgebra of (ℂ⟨𝔸⟩, ) generated by Ψ_{π}(𝔸) = π! Φ_{π}(𝔸) where π! = #π_{1}! ⋯ #π_{k}! for π = {π_{1}, …, π_{k}}. Indeed, the linear map Ψ_{π} ⟶ Ψ_{π}(𝔸) is a bijection sending Ψ_{π_{1}}Ψ_{π_{2}} to

∑_{\begin{matrix}π=π′_{1}∪π′_{2}, π′_{1}∩π′_{2}=∅ \\ π_{1}=std(π′_{1}), π_{2}=std(π′_{2}) \end{matrix}} Ψ_{π}(𝔸) = π_{1}! π_{2}! ∑_{\begin{matrix}π=π′_{1}∪π′_{2}, π′_{1}∩π′_{2}=∅ \\ π_{1}=std(π′_{1}), π_{2}=std(π′_{2}) \end{matrix}} Φ_{π}(𝔸)

= π_{1}! π_{2}!Φ_{π_{1}}(𝔸) Φ_{π_{2}}(𝔸) = Ψ_{π_{1}}(𝔸) Ψ_{π_{2}}(𝔸).

With these notations the image of S_{π} is S_{π}(𝔸) = ∑_{π′≤π} Ψ_{π′}(𝔸). For our realization, the duality bracket ⟨ | ⟩ implements the scalar product ⟨ | ⟩ on the space WSym(𝔸) for which ⟨S_{π_{1}}(𝔸)|M_{π_{2}}(𝔸)⟩ = ⟨Φ_{π_{1}}(𝔸)|Ψ_{π_{2}}(𝔸)⟩ = δ_{π_{1},π_{2}}.

The subalgebra of (WSym(𝔸), ) generated by the complete functions S_{{{1,...,n}}}(𝔸) is isomorphic to Sym. Therefore, we define σ_{t}^{W} (𝔸) and ϕ_{t}^{W} (𝔸) by

σ_{t}^{W} (𝔸) = ∑_{n≥0} S_{{{1,...,n}}}(𝔸)t^{n}

and

ϕ_{t}^{W} (𝔸) = ∑_{n≥1} Ψ_{{{1,...,n}}}(𝔸)t^{n−1}.

These series are linked by the equality

σ_{t}^{W} (𝔸) = exp (ϕ_{t}^{W} (𝔸)) ,  (3.4)

where exp is the exponential in (WSym(𝔸), ). Furthermore, the coproduct of WSym consists in identifying the algebra WSym ⊗ WSym with WSym(𝔸 + 𝔹), where 𝔸 and 𝔹 are two alphabets such that the letters of 𝔸 commute with those of 𝔹. Hence, we have σ_{t}^{W} (𝔸 + 𝔹) = σ_{t}^{W} (𝔸) σ_{t}^{W} (𝔹). In particular, we define the multiplication of an alphabet 𝔸 by a constant k ∈ ℕ by

1 The basis (c_{λ})_{λ}, with c_{λ} = \frac{p_{λ}}{z_{λ}}, denotes, as usual, the dual basis of the power sum basis (p_{λ})_{λ}.

σ_{t}^{W} (k𝔸) = ∑_{n≥0} S_{{{1,...,n}}}(k𝔸)t^{n} = σ_{t}^{W} (𝔸)^{k}.

Unlike in Sym, the knowledge of the complete functions S_{{{1,...,n}}}(𝔸) does not allow us to recover all the polynomials using only the algebraic operations. In [5], we made an attempt to define virtual alphabets by reconstituting the whole algebra using the action of an operad. Although the general mechanism remains to be defined, the case where each complete function S_{{{1,...,n}}}(𝔸) is specialized to a sum of words of length n can be understood via this construction. More precisely, we consider the family of multilinear kary operators _{Π} indexed by set compositions (a set composition is a sequence [π_{1}, …, π_{k}] of subsets of {1, …, n} such that {π_{1}, …, π_{k}} is a set partition of {1, …, n}) acting on words by _{[π_{1},...,π_{k}]}(a_{1}^{1} ⋯ a_{n_{1}}^{1}, …, a_{1}^{k} ⋯ a_{n_{k}}^{k}) = b_{1} ⋯ b_{n} with b_{i_{ℓ}^{p}} = a_{ℓ}^{p} if π_{p} = {i_{1}^{p} < ⋯ < i_{n_{p}}^{p}} and _{[π_{1},...,π_{k}]}(a_{1}^{1} ⋯ a_{n_{1}}^{1}, …, a_{1}^{k} ⋯ a_{n_{k}}^{k}) = 0 if #π_{p} ≠ n_{p} for some 1 ≤ p ≤ k.

Let P = (P_{n})_{n≥1} be a family of homogeneous word polynomials such that deg(P_{n}) = n for all n. We set S_{{{1,...,n}}} [𝔸^{(P)}] = P_{n} and

S_{{π_{1},...,π_{k}}} [𝔸^{(P)}] = _{[π_{1},...,π_{k}]}(S_{{{1,...,#π_{1}}}} [𝔸^{(P)}] , …, S_{{{1,...,#π_{k}}}} [𝔸^{(P)}]).

The space WSym [𝔸^{(P)}] generated by the polynomials S_{{π_{1},...,π_{k}}} [𝔸^{(P)}] and endowed with the two products · and is homomorphic to the double algebra (WSym(𝔸), ·, ). Indeed, let π = {π_{1}, …, π_{k}} ⊩ n and π′ = {π′_{1}, …, π′_{k′}} ⊩ n′ be two set partitions. Then we have

S_{π} [𝔸^{(P)}] · S_{π′} [𝔸^{(P)}] = _{[{1,...,n},{n+1,...,n+n′}]} (S_{π} [𝔸^{(P)}] , S_{π′} [𝔸^{(P)}])
= _{[π_{1},...,π_{k},π′_{1}[n],...,π′_{k′}[n]]} (S_{{1,...,#π_{1}}} [𝔸^{(P)}] , …, S_{{1,...,#π_{k}}} [𝔸^{(P)}] ,
S_{{1,...,#π′_{1}}} [𝔸^{(P)}] , …, S_{{1,...,#π′_{k′}}} [𝔸^{(P)}])
= S_{π⊎π′} [𝔸^{(P)}]

and

S_{π} [𝔸^{(P)}] S_{π′} [𝔸^{(P)}] = ∑_{I∪J={1,...,n+n′}, I∩J=∅} _{[I,J]} (S_{π} [𝔸^{(P)}] , S_{π′} [𝔸^{(P)}])
= ∑ _{[π′′_{1},...,π′′_{k+k′}]} (S_{{1,...,#π_{1}}} [𝔸^{(P)}] , …, S_{{1,...,#π_{k}}} [𝔸^{(P)}] ,
S_{{1,...,#π′_{1}}} [𝔸^{(P)}] , …, S_{{1,...,#π′_{k′}}} (𝔸^{(P)}]) ,

where the second sum is over the partitions {π′′_{1}, …, π′′_{k+k′}} ∈ π ⋓ π′ satisfying std({π′′_{1}, …, π′′_{k}}) = π, std({π′′_{k+1}, …, π′′_{k+k′}}) = π′, #π′′_{i} = π_{i}, for k + 1 ≤ i ≤ k + k′. Hence,

S_{π} [𝔸^{(P)}] S_{π′} [𝔸^{(P)}] = ∑_{π′′∈π⋓π′} S_{π′′} [𝔸^{(P)}] .

In other words, we consider the elements of WSym [𝔸^{(P)}] as word polynomials in the virtual alphabet 𝔸^{(P)} specializing the elements of WSym(𝔸).

3.2.2. Biword symmetric functions. The bi-indexed word algebra BWSym was defined in [5]. We recall its definition here: the bases of BWSym are indexed by set partitions into lists, which can be constructed from a set partition by ordering each block. We denote the set of the set partitions of {1, …, n} into lists by PL_{n}.

Example 15. The sets {[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 \underline{A000262} [30]. The first values are

1, 1, 3, 13, 73, 501, 4051, …

If Π̂ is a set partition into lists of {1, …, n}, we write Π ⊪ n. Set

Π̂ ⊎ Π̂′ = Π̂ ∪ {[l_{1} + n, …, l_{k} + n] : [l_{1}, …, l_{k}] ∈ Π̂′} ⊪ n + n′.

Let Π̂′ ⊂ Π̂ ⊪ n. Since the integers appearing in Π̂′ are all distinct, the standardization std(Π̂′) of Π̂′ is the unique set partition into lists obtained by replacing the ith smallest integer in Π̂ by i. For example, std({[5, 2], [3, 10], [6, 8]}) = {[3, 1], [2, 6], [4, 5]}.

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

ΦΠ̂ΦΠ̂′ = Φ_{Π̂⊎Π̂′}  (3.5)

and its coproduct

Δ(ΦΠ̂) = ∑ Φ_{std(Π̂′)} ⊗ Φ_{std(Π̂′′)},  (3.6)

where the sum is over the pairs (Π̂′, Π̂′′) such that Π̂′ ∪ Π̂′′ = Π̂ and Π̂′ ∩ Π̂′′ = ∅.

The product of the graded dual BΠQSym of BWSym is completely described in the dual basis (ΨΠ̂)Π̂ of (ΦΠ̂)Π̂ by

ΨΠ̂_{1}ΨΠ̂_{2} = ∑ ΨΠ̂,  (3.7)

where the sum is over the Π̂’s such that there exist Π̂′_{1} and Π̂′_{2} satisfying Π̂ = Π̂′_{1} ∪ Π̂′_{2}, Π̂′_{1} ∩ Π̂′_{2} = ∅, std(Π̂′_{1}) = Π̂_{1}, and std(Π̂′_{2}) = Π̂_{2}.

Now consider a sequence of bijections ι_{n} from {1, …, n!} to the symmetric group 𝔖_{n}, for all positive integers n. The linear map κ : CP(1!, 2!, 3!, …) ⟶ PL := ⋃ PL_{n} sending

{[{i_{1}^{1}, …, i_{n_{1}}^{1}}, m_{1}], …, [{i_{1}^{k}, …, i_{n_{k}}^{k}}, m_{k}]} ∈ CP_{n}(1!, 2!, 3!, …),

with i_{1}^{j} ≤ ⋯ ≤ i_{n_{j}}^{j}, to

{[i_{(ι_{n_{1}}(m_{1}))_{1}}^{1}, …, i_{(ι_{n_{1}}(m_{1}))_{n_{1}}}^{1}], …, [i_{(ι_{n_{k}} (m_{k}))_{1}}^{k}, …, i_{(ι_{n_{k}} (m_{k}))_{n_{k}}}^{k}]}

is a bijection. Hence, a simple check shows that the linear map sending Ψ^{Π} to Ψ^{κ(Π)} is an isomorphism. Thus, we have the following facts.

Proposition 16.

• The Hopf algebras CWSym(1!, 2!, 3!, …) and BWSym are isomorphic.

• The Hopf algebras CΠQSym(1!, 2!, 3!, …) and BΠQSym are isomorphic.

3.2.3. Word symmetric functions of level 2. We consider the algebra WSym_{(2)} which is spanned by the Φ_{Π}’s where Π is a set partition of level 2, that is, a partition of a partition π of {1, …, n} for some n. More explicitly, a partition of partition of size n is a set {{π_{1,1}, …, π_{1,m_{1}}}, …, {π_{k,1}, …, π_{k,m_{k}}}} such that the π_{i,j}’s are pairwise disjoint and π_{1,1} ∪ ⋯ ∪ π_{1,m_{1}} ∪ ⋯ ∪ π_{k,1} ∪ ⋯ ∪ π_{k,m_{k}} = {1, …, n}.

Example 17. The 12 partitions of partition of size 3 are

{{{1}}, {{2}}, {{3}}} ,
{{{1}, {2}}, {{3}}}, {{{1, 2}}, {{3}}}, {{{1, 2}, {3}}},
{{{1}, {3}}, {{2}}}, {{{1, 3}}, {{2}}}, {{{1, 3}, {2}}},
{{{2}, {3}}, {{1}}}, {{{2, 3}}, {{1}}}, {{{2, 3}, {1}}},
{{{1}, {2}, {3}}}, {{{1, 2, 3}}}.

To obtain this set, it suffices to list the set partitions of size 3 and replace each block by the partitions of the block in all the possible ways. For instance, the set partition {{1, 3}, {2}} yields the 2 partitions of partition {{{1, 3}}, {{2}}} and {{{1}, {3}}, {{2}}}.

Notice that partitions of partition are in bijection with pairs of partitions (Π_{1}, Π_{2}) such that Π_{2} is coarser than Π_{1}, for instance,

{{{1, 3, 4}, {5}}, {{2, 6}, {7}}, {{8}}} ∼ ({{1, 3, 4}, {2, 6}, {5}, {7}, {8}}, {{1, 3, 4, 5}, {2, 7, 6}, {8}})

The product of this algebra is given by Φ_{Π}Φ_{Π′} = Φ_{Π∪Π′[n]}, where Π′[n] = {e[n] : e ∈ Π′}. The dimensions of the homogeneous components of this algebra are given by the exponential generating function

∑_{i} b_{i}^{(2)} \frac{t^{i}}{i!} = exp(exp(exp(t) − 1) − 1).

The first values are

1, 3, 12, 60, 358, 2471, 19302, 167894, 1606137, …

see sequence \underline{A000258} of [30].

The coproduct is defined by

Δ(Φ_{Π}) = ∑_{\begin{matrix}Π′∪Π′′=Π \\ Π′∩Π′′=∅ \end{matrix}} Φ_{std(Π′)} ⊗ Φ_{std(Π′′)},

where, if Π is a partition of a partition of {i_{1}, …, i_{k}}, std(Π) denotes the standardization of Π, that is, the partition of partition of {1, …, k} obtained by replacing each occurrence of i_{j} by j in Π. The coproduct being co-commutative, the dual algebra ΠQSym_{(2)} := WSym_{(2)}^{∗} is commutative. The algebra ΠQSym_{(2)} is spanned by a basis (Ψ_{Π})_{Π} satisfying Ψ_{Π}Ψ_{Π′} = ∑_{Π′′} C_{Π,Π′}^{Π′′}Ψ_{Π′′}, where C_{Π,Π′}^{Π′′} is the number of ways to write Π′′ = A ∪ B with A ∩ B = ∅, std(A) = Π, and std(B) = Π′.

Let b_{n} be the nth Bell number A_{n}(1, 1, …). Considering a bijection from {1, …, b_{n}} to the set of the set partitions of {1, …, n} for all n, we obtain, in the same way as in the previous subsection, the following result.

Proposition 18.

• The Hopf algebras CWSym(b_{1}, b_{2}, b_{3}, …) and WSym_{(2)} are isomorphic.

• The Hopf algebras CΠQSym(b_{1}, b_{2}, b_{3}, …) and ΠQSym_{(2)} are isomorphic.

3.2.4. Cycle word symmetric functions. We consider the Grossman–Larson Hopf algebra of heap-ordered trees 𝔖Sym [15]. The combinatorics of this algebra has been extensively investigated in [16]. This Hopf algebra is spanned by the Φ_{σ} where σ is a permutation. We identify each permutation with the set of its cycles (for example, the permutation 321 is {(13), (2)}). The product in this algebra is given by Φ_{σ}Φ_{τ} = Φ_{σ∪τ[n]}, where n is the size of the permutation σ and τ[n] = {(i_{1} + n, i_{2} + n, …, i_{k} + n) | (i_{1}, …, i_{k}) ∈ τ}. The coproduct is given by

Δ(Φ_{σ}) = ∑ Φ_{std(σ|_{I})} ⊗ Φ_{std(σ|_{J})},  (3.8)

where the sum is over the partitions of {1, …, n} into 2 sets I and J such that the action of σ leaves the sets I and J globally invariant, σ|_{I} denotes the restriction of the permutation σ to the set I and std(σ|_{I}) is the permutation obtained from σ|_{I} by replacing the ith smallest label by i in σ|_{I}.

Example 19. We have

Δ(Φ_{3241}) = Φ_{3241} ⊗ 1 + Φ_{1} ⊗ Φ_{231} + Φ_{231} ⊗ Φ_{1} + 1 ⊗ Φ_{3241}.

The basis (Φ_{σ}) and its dual basis (Ψ_{σ}) are denoted by (S^{σ}) and (M_{σ}), respectively, in [16]. The Hopf algebra 𝔖Sym is not commutative but it is cocommutative, so it is not self-dual and not isomorphic to the Hopf algebra of free quasi-symmetric functions.

Let ι_{n} be a bijection from the set of the permutations of 𝔖_{n} that are cycles to {1, …, (n − 1)!}. We define the bijection κ : 𝔖_{n} ↔ CP(0!, 1!, 2!, …) by

κ(σ) = {[support(c_{1}), ι_{#support(c_{1})}(std(c_{1}))], …, [support(c_{k}), ι_{#support(c_{k})}(std(c_{k}))]} ,

if σ = c_{1} ⋯ c_{k} is the decomposition of σ into disjoint cycles and support(c) denotes the support of the cycle c, i.e., the set of the elements which are permuted by the cycle.

Example 20. For instance, set

ι_{1}(1) = 1, ι_{3}(231) = 2, and ι_{3}(312) = 1.

Then we have

κ(32415867) = {[{2}, 1], [{1, 3, 4}, 2], [{5}, 1], [{6, 7, 8}, 1]}.

The linear map K : 𝔖Sym ⟶ CWSym(0!, 1!, 2!, …) sending Φ_{σ} to Φ_{κ(σ)} is an algebra isomorphism. Indeed, it is straightforward to see that it is a bijection, furthermore κ(σ ∪ τ[n]) = κ(σ) ⊎ κ(τ). Moreover, if σ ∈ 𝔖_{n} is a permutation and {I, J} is a partition of {1, …, n} into two subsets such that the action of σ leaves I and J globally invariant, we check that κ(σ) = Π_{1} ∪ Π_{2} with Π_{1} ∩ Π_{2} = ∅, std(Π_{1}) = κ(std(σ|_{I})), and std(Π_{2}) = κ(std(σ|_{J})). Conversely, if κ(σ) = Π_{1} ∪ Π_{2} with Π_{1} ∩ Π_{2} = ∅, then there exists a partition {I, J} of {1, …, n} into two subsets such that the action of σ leaves I and J globally invariant, std(Π_{1}) = κ(std(σ|_{I})), and std(Π_{2}) = κ(std(σ|_{J})).

In other words,

Δ(Φ_{κ(σ)}) = ∑ Φ_{κ(std(σ|_{I}))} ⊗ Φ_{κ(std(σ|_{J})},  (3.9)

where the sum is over the partitions of {1, …, n} into 2 sets I and J such that the action of σ leaves the sets I and J globally invariant. Hence K is a coalgebra homomorphism and, as with the previous examples, we have the following isomorphism property.

Proposition 21.

• The Hopf algebras CWSym(0!, 1!, 2!, …) and 𝔖Sym are isomorphic.

• The Hopf algebras CΠQSym(0!, 1!, 2!, …) and 𝔖Sym^{∗} are isomorphic.

3.2.5. Miscellaneous subalgebras of the Hopf algebra of endofunctions. We denote by End the combinatorial class of endofunctions (an endofunction of size n ∈ ℕ is a function from {1, …, n} to itself). Given a function f from a finite subset A of ℕ to itself, we denote by std(f) the endofunction ϕ ∘ f ∘ ϕ^{−1}, where ϕ is the unique increasing bijection from A to {1, 2, …, #(A)}. Given a function g from a finite subset B of ℕ (disjoint from A) to itself, we denote by f ∪ g the function from A ∪ B to itself whose f and g are the restrictions to A and B, respectively. Finally, given two endofunctions f and g, of size n and m, respectively, we denote the endofunction f ∪ g̃ by f • g, where g̃ is the unique function from {n + 1, n + 2, …, n + m} to itself such that std(g̃) = g.

Now, let EQSym be the Hopf algebra of endofunctions [16]. This Hopf algebra is defined by its basis (Ψ_{f}) indexed by endofunctions, the product

Ψ_{f}Ψ_{g} = ∑_{std(f̃)=f,std(g̃)=g,f̃∪g̃∈End} Ψ_{f̃∪g̃}  (3.10)

and the coproduct

Δ(Ψ_{h}) = ∑_{f•g=h} Ψ_{f} ⊗ Ψ_{g}.  (3.11)

This algebra is commutative but not cocommutative. We denote its graded dual by ESym := EQSym^{∗} and the basis of ESym dual to (Ψ_{f}) by (Φ_{f}). In [16], the bases (Φ_{σ}) and (Ψ_{σ}) are denoted by (S^{σ}) and (M_{σ}), respectively. The product and the coproduct in ESym are given by

Φ_{f}Φ_{g} = Φ_{f•g}  (3.12)

and

Δ(Φ_{h}) = ∑_{f∪g=h} Φ_{std(f)} ⊗ Φ_{std(g)},  (3.13)

respectively.

Remark 22. The Ψ_{f}’s, where f is a bijective endofunction, span a Hopf subalgebra of EQSym obviously isomorphic to 𝔖QSym := 𝔖Sym^{∗}, that is, isomorphic to CΠQSym(0!, 1!, 2!, …) from Section 3.2.4.

As suggested by [16], we investigate a few other Hopf subalgebras of EQSym.

• The Hopf algebra of idempotent endofunctions is isomorphic to the Hopf algebra CΠQSym(1, 2, 3, …) . The explicit isomorphism sends Ψ_{f} to Ψ_{ϕ(f)}, where, for any idempotent endofunction f of size n,

ϕ(f) = {[f^{−1}(i), #({j ∈ f^{−1}(i) | j ≤ i})]|1 ≤ i ≤ n, f^{−1}(i) ≠ ∅}.  (3.14)

• The Hopf algebra of involutive endofunctions is isomorphic to

CΠQSym(1, 1, 0, …, 0, …) ↪ ΠQSym.

Namely, it is a Hopf subalgebra of 𝔖QSym, and the natural isomorphism from 𝔖QSym to CΠQSym(0!, 1!, 2!, …) sends it to the subalgebra CΠQSym(1, 1, 0, …, 0, …).

• In the same way, the endofunctions such that f^{3} = Id generate a Hopf subalgebra of 𝔖QSym ↪ EQSym isomorphic to the Hopf algebra CΠQSym(1, 0, 2, 0, …, 0, …).

• More generally, the endofunctions such that f^{p} = Id generate a Hopf subalgebra of 𝔖QSym ↪ EQSym isomorphic to CΠQSym(τ(p)), where τ(p)_{i} = (i−1)! if i | p and τ(p)_{i} = 0 otherwise.

3.3. Specializations. The aim of this section is to show how the specialization c_{n} ⟶ \frac{a_{n}}{n!} factorizes through ΠQSym and CΠQSym.

Firstly, we notice that the algebra Sym is isomorphic to the subalgebra of ΠQSym generated by the family (Ψ_{{{1,...,n}}})_{n∈ℕ}; the explicit isomorphism α sends c_{n} to Ψ_{{{1,...,n}}}. The image of h_{n} is S_{\{\{1,...,n\}\}}, and the image of c_{λ} = \frac{1}{λ^{!}} c_{λ_{1}} ⋯ c_{λ_{k}} is ∑_{π⊩λ} Ψ_{π}, where π ⊩ λ means that π = {π_{1}, …, π_{k}} is a set partition such that #π_{1} = λ_{1}, …, #π_{k} = λ_{k}, and λ^{!} = \frac{λ_{1}···λ_{k}}{z_{λ}} = ∏_{i} 𝔪_{i}(λ)!, where 𝔪_{i}(λ) denotes the multiplicity of i in λ. Indeed, c_{λ} is mapped to \frac{1}{λ^{!}} Ψ_{\{\{1,...,λ_{1}\}\}} ⋯ Ψ_{\{\{1,...,λ_{k}\}\}} and Ψ_{\{\{1,...,λ_{1}\}\}} ⋯ Ψ_{\{\{1,...,λ_{k}\}\}} = λ^{!} ∑_{π⊩λ} Ψ_{π}.

Now, the linear map β_{a} : ΠQSym ⟶ CΠQSym(a) sending Ψ_{π} to the element ∑_{Π⇛π} Ψ_{Π}

for all π is an algebra homomorphism and the subalgebra { \atop ΠQSym} := β_{a}(ΠQSym) is isomorphic to ΠQSym if and only if a ∈ (ℕ \ {0})^{ℕ}.

Let γ_{a} : CΠQSym(a) ⟶ ℂ be the linear map sending Ψ_{Π} to \frac{1}{|Π|!}. We have

γ_{a}(Ψ_{Π_{1}}Ψ_{Π_{2}}) = ∑_{Π=Π′_{1}∪Π′_{2},Π′_{1}∩Π′_{2}=∅ std(Π′_{1})=Π_{1}, std(Π′_{2})=Π_{2}} γ_{a}(Ψ_{Π}).  (3.15)

We remark that, for each Π occurring on the right-hand side of (3.15), we have γ_{a}(Π) =

\frac{1}{(|Π_{1}|+|Π_{2}|)!}. The number of terms in the sum being ( \begin{matrix}|Π_{1}| + |Π_{2}| \\ |Π_{1}| \end{matrix} ), one obtains

γ_{a}(Ψ_{Π_{1}}Ψ_{Π_{2}}) = \frac{1}{(|Π_{1}| + |Π_{2}|)!}\binom{|Π_{1}| + |Π_{2}|}{|Π_{1}|} = \frac{1}{|Π_{1}|! |Π_{2}|!} = γ_{a}(Ψ_{Π_{1}})γ_{a}(Ψ_{Π_{2}}). (3.16)

In other words, γ_{a} is an algebra homomorphism. Furthermore, the restriction γ̂_{a} of γ_{a} to { \atop ΠQSym} is an algebra homomorphism that sends β_{a}(Ψ_{\{\{1,...,n\}\}}) to \frac{a_{n}}{n!} . It follows that, if f ∈ Sym, then we have

f(𝕏^{(a)}) = γ̂_{a}(β_{a}(α(f))).  (3.17)

The following theorem summarizes this section.

Theorem 23. The diagram

[figure: CΠQSym(a); γ_{a}; { \atop ΠQSym}; β_{a}; γ̂_{a}; ΠQSym; α; ℂ = Sym[𝕏^{(a)}]; Sym]

is commutative.

4. Word Bell polynomials

4.1. Bell polynomials in ΠQSym. Since Sym is isomorphic to the subalgebra of ΠQSym generated by the elements Ψ_{{{1,...,n}}}, we can compute

A_{n}(Ψ_{{{1}}}, Ψ_{{{1,2}}}, …, Ψ_{{{1,...,m}}}, …).

From (3.4), we have

A_{n}(1! Ψ_{{{1}}}, 2! Ψ_{{{1,2}}}, …, m! Ψ_{{{1,...,m}}}, …) = n! S_{{{1,...,n}}} = n! ∑_{π⊩n} Ψ_{π}.  (4.1)

Notice that, from the previous section, the image of the Bell polynomial

A_{n}(Ψ_{{{1}}}, Ψ_{{{1,2}}}, …, Ψ_{{{1,...,m}}}, …)

under the homomorphism γ sending Ψ_{\{\{1,...,n\}\}} to \frac{1}{n!} is

γ(A_{n}(1! Ψ_{{{1}}}, 2! Ψ_{{{1,2}}}, …, m! Ψ_{{{1,...,m}}}, …)) = b_{n} = A_{n}(1, 1, …).

In the same way, we have

B_{n,k}(1! Ψ_{\{\{1\}\}}, 2! Ψ_{\{\{1,2\}\}}, …, m! Ψ_{\{\{1,...,m\}\}}, …) = n! ∑_{\begin{matrix}π⊩n \\ #π=k \end{matrix}} Ψ_{π}.  (4.2)

If (F_{n})_{n} is a homogeneous family of elements of ΠQSym, such that |F_{n}| = n, we define

A_{n}(F_{1}, F_{2}, …) = \frac{1}{n!}A_{n}(1! F_{1}, 2! F_{2}, …, m! F_{m}, …)  (4.3)

and

B_{n,k}(F_{1}, F_{2}, …) = \frac{1}{n!}B_{n,k}(1! F_{1}, 2! F_{2}, …, m! F_{m}, …).  (4.4)

By considering the map β_{a} ∘ α as a specialization of Sym, we see that the following identities hold in CΠQSym(a):

A_{n} ( ∑_{1≤i≤a_{1}} Ψ_{{[{1},i]}}, ∑_{1≤i≤a_{2}} Ψ_{{[{1,2},i]}}, …, ∑_{1≤i≤a_{m}} Ψ_{{[{1,...,m},i]}}, …) = ∑_{Π⊨n} Ψ_{Π}

and

B_{n,k} ( ∑_{1≤i≤a_{1}} Ψ_{\{[\{1\},i]\}}, ∑_{1≤i≤a_{2}} Ψ_{\{[\{1,2\},i]\}}, …, ∑_{1≤i≤a_{m}} Ψ_{\{[\{1,...,m\},i]\}}, …) = ∑_{\begin{matrix}Π⊨n \\ #Π=k \end{matrix}} Ψ_{Π}.

Example 24. In BΠQSym ∼ CΠQSym(1!, 2!, …), we have

B_{n,k} (Ψ_{\{[1]\}}, Ψ_{\{[1,2]\}} + Ψ_{\{[2,1]\}}, …, ∑_{σ∈𝔖_{m}} Ψ_{\{[σ]\}}, …) = ∑_{\begin{matrix}Π̂⊨n \\ #Π̂=k \end{matrix}} ΨΠ̂,

where the sum on the right is over the set partitions of {1, …, n} into k lists. By considering the homomorphism sending Ψ_{\{[σ_{1},...,σ_{n}]\}} to \frac{1}{n!}, we see that Theorem 23 allows us to recover B_{n,k}(1!, 2!, 3!, …) = L_{n,k}, the number of set partitions of {1, …, n} into k lists.

Example 25. In ΠQSym_{(2)} ∼ CΠQSym(b_{1}, b_{2}, …), we have

B_{n,k} (Ψ_{{{{1}}}}, Ψ_{{{{1,2}}}} + Ψ_{{{{1},{2}}}}, …, ∑_{π⊩m} Ψ_{{π}}, …) = ∑_{Π partition of π⊩n #Π=k} Ψ_{Π},

where the sum on the right is over the set partitions of {1, …, n} of level 2 into k blocks. By considering the homomorphism sending Ψ_{\{π\}} to \frac{1}{n!} for π ⊩ n, we see that Theorem 23 allows us to recover B_{n,k}(b_{1}, b_{2}, b_{3}, …) = S_{n,k}^{(2)}, the number of set partitions into k sets of a partition of {1, …, n}.

Example 26. In 𝔖Sym^{∗} ∼ CΠQSym(0!, 1!, 2! …), we have

B_{n,k} (Ψ_{[1]}, Ψ_{[2,1]}, Ψ_{[2,3,1]} + Ψ_{[3,1,2]}, …, ∑_{σ∈𝔖_{n} ; σ is a cycle} Ψ_{{π}}, …) = ∑_{σ∈𝔖_{n} σ has k cycles} Ψ_{σ},

where the sum on the right is over the permutations of size n having k cycles. By considering the homomorphism sending Ψ_{σ} to \frac{1}{n!} for σ ∈ 𝔖_{n}, we see that Theorem 23 allows us to recover B_{n,k}(0!, 1!, 2!, …) = s_{n,k}, the number of permutations of 𝔖_{n} having exactly k cycles.

Example 27. In the Hopf algebra of idempotent endofunctions, we have

B_{n,k} (Ψ_{f_{1,1}}, Ψ_{f_{2,1}} + Ψ_{f_{2,2}}, Ψ_{f_{3,1}} + Ψ_{f_{3,2}} + Ψ_{f_{3,3}}, …, ∑_{i=1}^{n} Ψ_{f_{n,i}}, …)

= ∑_{|f|=n,#(f({1,...,n}))=k} Ψ_{f},

where for i ≥ j ≥ 1, f_{i,j} is the constant endofunction of size i and of image {j}. Here, the sum on the right is over idempotent endofunctions f of size n such that the cardinality of the image of f is k. By considering the homomorphism sending Ψ_{f} to \frac{1}{n!} for |f| = n, we see that Theorem 23 allows us to recover that B_{n,k}(1, 2, 3, …) is the number of these idempotent endofunctions. This number equals the idempotent number \binom{n}{k}k^{n−k} [17, 31].

4.2. Bell polynomials in WSym. Bell polynomials can alternatively be defined recursively by using the derivative that sends letter a_{i} to a_{i+1} for all i. This definition is particularly interesting since noncommutative analogs (Munthe-Kaas polynomials) are defined in the same way (see [10] and Section 5). In this section we describe a word analog of this formula.

18 A. ABOUD, J.-P. BULTEL, A. CHOURIA, J.-G. LUQUE, AND O. MALLET

We define the operator ∂ acting linearly on the right of WSym by

1∂ = 0 and Φ_{{π_{1},...,π_{k}}}∂ = ∑_{i=1}^{k} Φ_{({π_{1},...,π_{k}}\π_{i})∪{π_{i}∪{n+1}}}.

In fact, the operator ∂ acts on Φ_{π} almost as the multiplication of M_{{{1}}} on M_{π}. More precisely, we have the following relation. Proposition 28. We have:

∂ = ϕ^{−1} ∘ μ ∘ ϕ − μ,

where ϕ is the linear operator satisfying M_{π}ϕ = Φ_{π}, and μ is the multiplication by Φ_{{{1}}}. Example 29. For instance, we have

Φ_{{{1,3},{2,4}}}∂ = Φ_{{{1,3},{2,4}}}(ϕ^{−1}μϕ − μ)
= M_{{{1,3},{2,4}}}μϕ − Φ_{{{1,3},{2,4},{5}}}

= (M_{{{1,3,5},{2,4}}} + M_{{{1,3},{2,4,5}}} + M_{{{1,3},{2,4},{5}}})ϕ − Φ_{{{1,3},{2,4},{5}}}

= Φ_{{{1,3,5},{2,4}}} + Φ_{{{1,3},{2,4,5}}} + Φ_{{{1,3},{2,4},{5}}} − Φ_{{{1,3},{2,4},{5}}}
= Φ_{{{1,3,5},{2,4}}} + Φ_{{{1,3},{2,4,5}}}.

Following Remark 4, we define the elements 𝔄_{n} of WSym recursively as

𝔄_{0} = 1, 𝔄_{n+1} = 𝔄_{n}(Φ_{{{1}}} + ∂).  (4.5)

So we have

𝔄_{n} = 1(Φ_{{{1}}} + ∂)^{n}.  (4.6)

Easily, one shows that 𝔄_{n} provides an analog of complete Bell polynomials in WSym. Proposition 30.

𝔄_{n} = ∑_{π⊩n} Φ_{π}.

Noticing that the multiplication by Φ_{{{1}}} adds one block to each partition, we give the following analog for partial Bell polynomials. Proposition 31. If we set

𝔅_{n,k} = [t^{k}]1(tΦ_{{{1}}} + ∂)^{n},  (4.7)

then we have 𝔅_{n,k} = ∑_{\begin{matrix}π⊩n \\ #π=k \end{matrix}} Φ_{π}.

Example 32. We have

1(tΦ_{{{1}}} + ∂)^{4} = t^{4}Φ_{{{1},{2},{3},{4}}} + t^{3}(Φ_{{{1,2},{3},{4}}} + Φ_{{{1,3},{2},{4}}}

+ Φ_{{{1},{2,3},{4}}} + Φ_{{{1,4},{2},{3}}} + Φ_{{{1},{2,4},{3}}} + Φ_{{{1},{2},{3,4}}})

+ t^{2}(Φ_{{{1,3,4},{2}}} + Φ_{{{1,2,3},{4}}} + Φ_{{{1,2,4},{3}}} + Φ_{{{1,2},{3,4}}} + Φ_{{{1,3},{2,4}}}

+ Φ_{{{1,4},{2,3}}} + Φ_{{{1},{2,3,4}}}) + tΦ_{{{1},{3},{4},{2}}}.

Hence,

𝔅_{4,2} = Φ_{{{1,3,4},{2}}} + Φ_{{{1,2,3},{4}}} + Φ_{{{1,2,4},{3}}} + Φ_{{{1,2},{3,4}}} + Φ_{{{1,3},{2,4}}} + Φ_{{{1,4},{2,3}}} + Φ_{{{1},{2,3,4}}}.

4.3. Bell polynomials in ℂ⟨𝔸⟩. Both WSym and ΠQSym admit word polynomial realizations in a subspace WSym(𝔸) of the free associative algebra ℂ⟨𝔸⟩ over an infinite alphabet 𝔸. When endowed with the concatenation product, WSym(𝔸) is isomorphic to WSym, and, when endowed with the shuffle product, it is isomorphic to ΠQSym. Alternatively to the definitions of partial Bell polynomials in ΠQSym (4.4) and in WSym, we set, for a sequence of polynomials (F_{i})_{i∈ℕ} in ℂ⟨𝔸⟩,

∑_{n≥0} B_{n,k}(F_{1}, …, F_{m}, …)t^{n} = \frac{1}{k!} (∑_{i} F_{i}t^{i}) ^{k}  (4.8)

and

A_{n}(F_{1}, …, F_{m}, …) = ∑_{k≥1} B_{n,k}(F_{1}, …, F_{m}, …).  (4.9)

This definition generalizes (4.4) and (4.7) in the following sense.

Proposition 33. We have

B_{n,k}(Ψ_{{{1}}}(𝔸), …, Ψ_{{{1,...,m}}}(𝔸), …) = B_{n,k}(Ψ_{{{1}}}(𝔸), …, Ψ_{{{1,...,m}}}(𝔸), …)

and

B_{n,k}(Φ_{{{1}}}(𝔸), …, Φ_{{{1,...,m}}}(𝔸), …) = 𝔅_{n,k}(𝔸).

Proof. The two identities follow from

Ψ_{π_{1}}(𝔸) Ψ_{π_{2}}(𝔸) = ∑_{\begin{matrix}π=π′_{1}∪π′_{2}, π′_{1}∩π′_{2}=∅ \\ std(π′_{1})=π_{1}, std(π′_{2})=π_{2} \end{matrix}} Ψ_{π}(𝔸).  □

Equality (4.8) allows us to show more general properties. For instance, let 𝔸′ and 𝔸′′ be two disjoint subalphabets of 𝔸, and set

S_{n}^{𝔸′}(𝔸′′) = S_{{{1}}}(𝔸′) S_{{{1,...,n−1}}}(𝔸′′).

Observing that

∑_{n} B_{n,k}(S_{1}^{𝔸′}(𝔸′′), …, S_{m}^{𝔸′}(𝔸′′), …)t^{n}

= t^{k}S_{{{1},...,{k}}}(𝔸′) (∑_{n≥0} S_{{{1,...,n}}}(𝔸′′)t^{n}) ^{k} = t^{k}S_{{{1},...,{k}}}(𝔸′) σ_{t}^{W} (k𝔸′′),

we obtain a word analog of the formula allowing one to write a Bell polynomial as a symmetric function (see Eq. (A.8) in Appendix A).

Proposition 34. We have

B_{n,k}(S_{1}^{𝔸′}(𝔸′′), …, S_{m}^{𝔸′}(𝔸′′), …) = S_{{{1},...,{k}}}(𝔸′) S_{{{1,...,n−k}}}(k𝔸′′).

For simplicity, let us write B_{n,k}^{𝔸′}(𝔸′′) := B_{n,k}(S_{1}^{𝔸′}(𝔸′′), …, S_{m}^{𝔸′}(𝔸′′), …).

Let k = k_{1} + k_{2}. From

S_{\{\{1\},...,\{k_{1}\}\}}(𝔸′) S_{\{\{1\},...,\{k_{2}\}\}}(𝔸′) = \binom{k}{k_{1}}S_{\{\{1\},...,\{k\}\}}(𝔸′)

and

S_{{{1,...,n−k}}}(k𝔸′′) = ∑_{i+j=n−k} S_{{{1,...,i}}}(k_{1}𝔸′′) S_{{{1,...,i}}}(k_{2}𝔸′′),

we deduce an analog of the binomiality of the partial Bell polynomials (see Eq. (A.9) in Appendix A).

Corollary 35. Let k = k_{1} + k_{2} be three nonnegative integers. Then we have

\binom{k}{k_{1}}B_{n,k}^{𝔸′}(𝔸′′) = ∑_{i=0}^{n} B_{i,k_{1}}^{𝔸′}(𝔸′′) B_{n−i,k_{2}}^{𝔸′}(𝔸′′).  (4.10)

Example 36. Consider a family of functions (f_{k})_{k} such that f_{k} : ℕ ⟶ ℂ⟨𝔸⟩ and

f_{0} = 1 and f_{n}(α + β) = ∑_{n=i+j} f_{i}(α) f_{j}(β).  (4.11)

From (4.8), we obtain

B_{n,k}(f_{0}(a), …, f_{m−1}(a), …)t^{n} = \frac{1}{k!} ∑_{i_{1}+···+i_{k}=n−k} f_{i_{1}}(a) ⋯ f_{i_{k}}(a).

Hence, iterating (4.11), we deduce

B_{n,k}(f_{0}(a), …, f_{m−1}(a), …) = \frac{1}{k!}f_{n−k}(ka).

Set f_{n}(k) = k! B_{n,k}^{𝔸′}(𝔸′′) and f_{0}(k) = 1. By (4.10), the family (f_{n})_{n∈ℕ} satisfies (4.11). Hence we obtain an analog of the composition formula (see Eq. (A.13) in Appendix A):

k_{1}! B_{n,k_{1}}(1, …, k_{2}! B_{m−1,k_{2}}^{𝔸′}(𝔸′′), …) = (k_{1}k_{2})! B_{n−k_{1},k_{1}k_{2}}^{𝔸′}(𝔸′′).

Suppose now that 𝔸′′ = 𝔸′′_{1} + 𝔸′′_{2}. By

S_{{{1,...,n}}}(𝔸′′) = ∑_{i=0}^{n} S_{{{1,...,i}}}(𝔸′′_{1}) S_{{{1,...,n−i}}}(𝔸′′_{2}),

Proposition 34 allows us to write a word analog of the convolution formula for Bell polynomials (see formula (A.10) in Appendix A).

Corollary 37. We have

S_{{{1},...,{k}}}(𝔸′) B_{n,k}^{𝔸′}(𝔸′′) = ∑_{i=0}^{n} B_{i,k}^{𝔸′}(𝔸′′_{1}) B_{n−i,k}^{𝔸′}(𝔸′′_{2}).  (4.12)

Let k_{1} and k_{2} be two positive integers. We have

∑_{n} B_{n,k_{1}}(B_{k_{2},k_{2}}^{𝔸′}(𝔸′′), …, B_{k_{2}+m−1,k_{2}}^{𝔸′}(𝔸′′), …)t^{n} = \frac{1}{k_{1}!} (∑_{m≥1} B_{k_{2}+m−1,k_{2}}^{𝔸′}(𝔸′′)t^{m}) ^{k_{1}}
= t^{k_{1}}S_{{{1},...,{k_{2}k_{1}}}}(𝔸′) σ_{t}^{W} (k_{1}k_{2}𝔸′′).

This implies the following identity.

Proposition 38. We have

B_{n,k_{1}}(B_{k_{2},k_{2}}^{𝔸′}(𝔸′′), …, B_{k_{2}+m−1,k_{2}}^{𝔸′}(𝔸′′), …) = B_{n−k_{1}+k_{1}k_{2},k_{1}k_{2}}^{𝔸′}(𝔸′′).  (4.13)

4.4. Specialization again. In [5], we have shown that one can construct a double algebra which is homomorphic to (WSym(𝔸), ., ). This is a general construction which is an attempt to properly define the concept of a virtual alphabet for WSym. In our context, the construction is simpler and can be described as follows.

Let F = (F_{π}(𝔸))_{π} be a basis of WSym(𝔸). We say that F is shuffle-compatible if

F_{{π_{1},...,π_{k}}}(𝔸) = _{[π_{1},...,π_{k}]} (F_{{{1,...,#π_{1}}}}(𝔸), …, F_{{{1,...,#π_{k}}}}(𝔸)) .

Then we have

F_{π_{1}}(𝔸) F_{π_{2}}(𝔸) = ∑_{\begin{matrix}π=π′_{1}∪π′_{2},π′_{1}∩π′_{2}=∅ \\ std(π′_{1})=π_{1},std(π′_{2})=π_{2} \end{matrix}} F_{π} and F_{π_{1}}(𝔸).F_{π_{2}}(𝔸) = F_{π_{1}⊎π_{2}}(𝔸).

Example 39. The bases (S_{π}(𝔸))_{π}, (Φ_{π}(𝔸))_{π}, and (Ψ_{π}(𝔸))_{π} are shuffle-compatible but not the basis (M_{π}(𝔸))_{π}.

Straightforwardly, we have the following fact.

Claim 40. Let (F_{π}(𝔸))_{π} be a shuffle-compatible basis of WSym(𝔸). Let 𝔹 be another alphabet and let P = (P_{k})_{k>0} be a family of noncommutative polynomials of ℂ⟨𝔹⟩ such that deg P_{k} = k. Then the space spanned by the polynomials

F_{{π_{1},...,π_{k}}}[𝔸_{F}^{(P)}] := _{[π_{1},...,π_{k}]} (P_{#π_{1}}, …, P_{#π_{k}})

is stable under concatenation and shuffle product in ℂ⟨𝔹⟩. So it is a double algebra which is homomorphic to (WSym(𝔸), ., ). We denote this double algebra by WSym[𝔸_{F}^{(P)}] and the image of an element f ∈ WSym(𝔸) under the homomorphism WSym(𝔸) ⟶ WSym[𝔸_{F}^{(P)}] sending F_{{π_{1},...,π_{k}}} to F_{{π_{1},...,π_{k}}}[𝔸_{F}^{(P)}] by f[𝔸_{F}^{(P)}].

With these notations, we have

B_{n,k}(P_{1}, …, P_{m}, …) = 𝔅_{n,k}[𝔸_{Φ}^{(P)}].

Example 41. We define a specialization by setting

Φ_{\{\{1,...,n\}\}}[𝔖] = ∑_{\begin{matrix}σ∈𝔖_{n} \\ σ_{1}=1 \end{matrix}} b_{σ[1]} … b_{σ[n]},

where the letters b_{i} belong to an alphabet 𝔹. Let σ ∈ 𝔖_{n} be a permutation and σ = c_{1}∘⋯∘ c_{k} its decomposition into disjoint cycles. Each cycle c^{(i)} is denoted by a sequence of integers (n_{1}^{(i)}, …, n_{ℓ_{i}}^{(i)}) such that n_{1}^{(i)} = min{n_{1}^{(i)}, …, n_{ℓ_{i}}^{(i)}). Let c̃^{(i)} ∈ 𝔖_{ℓ_{i}} be the permutation which is the standardization of the sequence n_{1}^{(i)} … n_{ℓ_{i}}^{(i)}. The cycle support of σ is the partition

support(σ) = {{n_{1}^{(1)}, …, n_{ℓ^{(i)}}^{(1)}}, …, {n_{1}^{(k)}, …, n_{ℓ^{(k)}}^{(k)}}}.

We define w[c^{(i)}] = b_{c̃^{(i)}[1]} ⋯ b_{c̃^{(i)}[ℓ^{(i)}]} and w[σ] = _{[π_{1},...,π_{k}]}(w[c^{(1)}], …, w[c^{(k)}]), where π_{i} =

{n_{1}^{(i)}, …, n_{ℓ^{(i)}}^{(i)}} for 1 ≤ i ≤ k.

For instance, if σ = 312654 = (132)(46)(5), we have w[(132)] = b_{1}b_{3}b_{2}, w[(46)] = b_{1}b_{2}, w[(5)] = b_{1}, and w[σ] = b_{1}b_{3}b_{2}b_{1}b_{1}b_{2}.

So, we have

B_{n,k}(Φ_{\{\{1\}\}}[𝔖], …, Φ_{\{\{1,...,m\}\}}[𝔖], …) = 𝔅_{n,k}[𝔖] = ∑_{\begin{matrix}π⊩n \\ #π=k \end{matrix}} Φ_{π}[𝔖] = ∑_{\begin{matrix}σ∈𝔖_{n} \\ #support(σ)=k \end{matrix}} w[σ].

For instance,

B_{4,2}(b_{1}, b_{1}b_{2}, b_{1}b_{2}b_{3} + b_{1}b_{3}b_{2}, b_{1}b_{2}b_{3}b_{4} + b_{1}b_{3}b_{2}b_{4} + b_{1}b_{2}b_{4}b_{3} + b_{1}b_{3}b_{4}b_{2}
+ b_{1}b_{4}b_{2}b_{3} + b_{1}b_{4}b_{3}b_{2}, …)
= Φ_{{{1},{2,3,4}}}[𝔖] + Φ_{{{2},{1,3,4}}}[𝔖] + Φ_{{{3},{1,2,4}}}[𝔖] + Φ_{{{4},{1,2,3}}}[𝔖]
+ Φ_{{{1,2},{3,4}}}[𝔖] + Φ_{{{1,3},{2,4}}}[𝔖] + Φ_{{{1,4},{2,3}}}[𝔖]
= 2b_{1}b_{1}b_{2}b_{3} + 2b_{1}b_{1}b_{3}b_{2} + b_{1}b_{2}b_{1}b_{3} + b_{1}b_{3}b_{2}b_{1} + b_{1}b_{2}b_{3}b_{1} + b_{1}b_{3}b_{2}b_{1}
+ b_{1}b_{2}b_{1}b_{2} + 2b_{1}b_{1}b_{2}b_{2}.

Notice that the sum of the coefficients of the words occurring in the expansion of 𝔅_{n,k}[𝔖] is equal to the Stirling number s_{n,k}. Hence, this specialization gives another word analog of formula (2.14).

5. Munthe-Kaas polynomials

5.1. Munthe-Kaas polynomials from WSym. In order to generalize the Runge– Kutta method to integration on manifolds, Munthe-Kaas [33] introduced a noncommutative version of Bell polynomials. We recall here the construction in a slightly different variant adapted to our notation, the operators acting on the right of the algebra. Consider an alphabet 𝔻 = {d_{1}, d_{2}, … }. The algebra ℂ⟨𝔻⟩ is equipped with the derivative defined by d_{i}∂ = d_{i+1}. The noncommutative Munthe-Kaas Bell polynomials are defined by setting t = 1 in MB_{n}(t) = 1.(td_{1} + ∂)^{n}. The partial noncommutative Bell polynomial MB_{n,k} is the coefficient of t^{k} in MB_{n}(t).

Example 42. We have • MB_{1}(t) = d_{1}t,

• MB_{2}(t) = d_{1}^{2}t^{2} + d_{2}t,

• MB_{3}(t) = d_{1}^{3}t^{3} + (2d_{2}d_{1} + d_{1}d_{2})t^{2} + d_{3}t,

• MB_{4}(t) = d_{1}^{4}t^{4} + (3d_{2}d_{1}^{2} + 2d_{1}d_{2}d_{1} + d_{1}^{2}d_{2})t^{3} + (3d_{3}d_{1} + 3d_{2}^{2} + d_{1}d_{3})t^{2} + d_{4}t.

We consider the map χ which sends a set partition π = {π_{1}, …, π_{k}}, where min(π_{i}) < min(π_{i+1}) for 0 < i < k, to the integer composition [#(π_{1}), …, #(π_{k})]. The linear map Ξ sending Φ_{π} to d_{χ(π)[1]} ⋯ d_{χ(π)[k]} is an algebra homomorphism. Hence, we deduce the following proposition.

Proposition 43. We have

Ξ (𝔅_{n,k}) = MB_{n,k}.  (5.1)

Example 44. We have

Ξ (𝔅_{3,2}) = Ξ (Φ_{{{1},{2,3}}} + Φ_{{{1,3},{2}}} + Φ_{{{1,2},{3}}}) = d_{1}d_{2} + 2d_{2}d_{1} = MB_{3,2}.

We recover a result due to Ebrahimi-Fard et al. [10].

Theorem 45. If j_{1}+⋯+j_{k} = n, the coefficient of d_{j_{1}} ⋯ d_{j_{k}} in MB_{n,k} is equal to the number of partitions of {1, 2, …, n} into blocks π_{1}, …, π_{k} such that #(π_{ℓ}) = j_{ℓ} for 1 ≤ ℓ ≤ k and min(π_{1}) < ⋯ < min(π_{k}).

5.2. Dendriform structure and quasideterminant formula. The algebra ΠQSym is equipped with a Zinbiel structure. The notion of Zinbiel algebra is due to Loday [21]. This is an algebra equipped with two nonassociative products ≺ and ≻ satisfying

• (u ≺ v) ≺ w = u ≺ (v ≺ w) + u ≺ (v ≻ w),
• (u ≻ v) ≺ w = u ≻ (v ≺ w),
• u ≻ (v ≻ w) = (u ≺ v) ≻ w + (u ≻ v) ≻ w,
• u ≺ v = v ≻ u.

The Zinbiel structure on ΠQSym is defined for any π ⊩ n and π′ ⊩ m by Φ_{π} ≺ Φ_{π′} =

∑^{′} Φ_{π[I]∪π′[J]} (respectively Φ_{π} ≻ Φ_{π′} = ∑^{′′} Φ_{π[I]∪π′[J]}), where ∑^{′} (respectively ∑^{′′}) means that the sum is over the partitions I ∪J = {1, …, n+m} ( I ∩J = ∅) such that #(I) = n, #(J) = m, and 1 ∈ I (respectively 1 ∈ J), and π[I] is obtained from π by replacing ℓ by i_{ℓ} for all ℓ if I = {i_{1}, …, i_{n}} and i_{1} < ⋯ < i_{n}. Refer to [26, 27, 13] for other combinatorial Hopf algebras with a dendriform structure.

We notice that

∑_{n} B_{n,k}(Φ_{{{1}}}, Φ_{{{1,2}}}, …)t^{n} = (∑_{i} Φ_{{{1,...,i}}}t^{i})≺^{→} k ,  (5.2)

where u≺^{→} k = u≺^{→} k − 1 ≺ u and u≺^{→} 0 = 1.

Definition 46. Let A_{n} = (a_{ij})_{1≤i≤j≤n} be an upper triangular matrix whose entries are in a Zinbiel algebra. We define the polynomial

P(A_{n}; t) = t ∑_{k=1}^{n} P(A_{k−1}) ≺ a_{k,n} and P(A_{0}) = 1.  (5.3)

Example 47. We have

P(A_{4}, t) = tP(A_{3}) ≺ a_{44} + tP(A_{2}) ≺ a_{34} + tP(A_{1}) ≺ a_{24} + tP(A_{0}) ≺ a_{14}
= t^{4}((a_{11} ≺ a_{22}) ≺ a_{33}) ≺ a_{44} + t^{3}(a_{11} ≺ a_{23}) ≺ a_{44}

+ t^{3}(a_{12} ≺ a_{33}) ≺ a_{44} + t^{3}(a_{11} ≺ a_{22}) ≺ a_{34} + t^{2}a_{12} ≺ a_{34} + at_{11}^{2} ≺ a_{24} + ta_{14}.

24 A. ABOUD, J.-P. BULTEL, A. CHOURIA, J.-G. LUQUE, AND O. MALLET

By induction, we find

P(A_{n}; t) = ta_{1n} + ∑_{\begin{matrix}1≤j_{1}<j_{2} \\ <···<j_{k} \end{matrix}} t^{k}(⋯ (a_{1j_{1}} ≺ (a_{j_{1}+1,j_{2}}) ≺ (a_{j_{2}+1,j_{3}}) ≺ ⋯ ≺ a_{j_{k−1}+1,j_{k}}) ≺ a_{j_{k}+1,n}).

(5.4)

Setting M_{n} := (Φ_{{{1,...,j−i+1}}})_{1≤i≤j≤n}, we get the following proposition. Proposition 48. We have

B_{n,k}(Φ_{{{1}}}, Φ_{{{1,2}}}, …) = [t^{k}]P(M_{n}; t).  (5.5)

Example 49. We have

P(A_{3}; t) = t^{3}(a_{11} ≺ a_{22}) ≺ a_{33} + t^{2}(a_{11} ≺ a_{23} + a_{12} ≺ a_{33}) + ta_{13}.

Hence

P(M_{3}; t) = t^{3}(Φ_{{{1}}} ≺ Φ_{{{1}}}) ≺ Φ_{{{1}}} + t^{2}(Φ_{{{1}}} ≺ Φ_{{{1,2}}} + Φ_{{{1,2}}} ≺ Φ_{{{1}}})
+ tΦ_{{{1,2,3}}}
= t^{3}Φ_{{{1},{2},{3}}} + t^{2}(Φ_{{{1},{2,3}}} + Φ_{{{1,2},{3}}} + Φ_{{{1,3},{2}}}) + tΦ_{{{1,2,3}}}
= t^{3}B_{3,3} + t^{2}B_{3,2} + tB_{3,1}.

Formula (5.4) is reminiscent of a well-known result on quasideterminants. Proposition 50 (Gelfand et al. [14]). We have

| \begin{matrix}a_{11} & a_{12} & a_{13} & ⋯ & a_{1n} \\ −1 & a_{22} & a_{23} & ⋯ & a_{2n} \\ 0 & −1 & a_{33} & ⋯ & a_{3n} \\ & ⋯ \\ 0 & ⋯ & 0 & −1 & a_{nn} \end{matrix} | = a_{1n} + ∑_{1≤j_{1}<j_{2}<···<j_{k}<n} a_{1j_{1}}a_{j_{1}+1,j_{2}} ⋯ a_{j_{k}+1,n}.  (5.6)

Furthermore, formula (5.5) is an analog of the following result of Ebrahimi-Fard et al. Theorem 51 (Ebrahimi-Fard et al. [10]). We have

MB_{n}(1) = | \begin{matrix}\binom{n−1}{0}d_{1} & \binom{n−1}{1}d_{2} & \binom{n−1}{2}d_{3} & ⋯ & \binom{n − 1}{n − 1}d_{n} \\ −1 & \binom{n−2}{0}d_{1} & \binom{n−2}{1}d_{2} & ⋯ & \binom{n−2}{n−2}d_{n−1} \\ 0 & −1 & \binom{n−3}{0}d_{1} & ⋯ & \binom{n−3}{n−3}d_{n−3} \\ & ⋯ \\ 0 & ⋯ & 0 & −1 & \binom{0}{0}d_{1} \end{matrix} | .

The connection between all these results remains to be investigated.

Acknowledgements. This paper is partially supported by the PHC MAGHREB project IThèM (14MDU929M) and the ANR project CARMA.

References

[1] E. T. Bell. Exponential polynomials. Ann. Math. (2), 35: 258–277, 1934.

[2] N. Bergeron, C. Reutenauer, M. Rosas, and M. Zabrocki. Invariants and coinvariants of the symmetric groups in noncommuting variables. Canad. J. Math., 60(2): 266–296, 2008.

[3] F. Bergeron, G. Labelle, and P. Leroux. Combinatorial Species and Tree-Like Structures. Cambridge University Press, Cambridge, 1998.

[4] S. Bouroubi and M. Abbas. New identities for Bell’s polynomials. New approaches. Rostock Math. Kolloq., 61: 49–55, 2006.

[5] J.-P. Bultel, A. Chouria, J.-G. Luque, and O. Mallet. Word symmetric functions and the Redfield– Pólya theorem. FPSAC’2013, DMTCS Proceedings, (01): 563–574, 2013.

[6] R. M. Corless, G. H. Gonnet, D. E. Hare, D. J. Jeffrey, and D. E. Knuth. On the Lambert W function. Adv. Comput. Math., 5: 329–359, 1996.

[7] L. Comtet. Advanced Combinatorics: The art of finite and infinite expansions. D. Reidel Publishing Co., Dordrecht, 1974.

[8] D. Cvijović. New identities for the partial Bell polynomials. Appl. Math. Lett., 24(9): 1544–1547, 2011.

[9] P. Doubilet. A Hopf algebra arising from the lattice of partitions of a set. J. Algebra, 28(1): 127–132, 1974.

[10] K. Ebrahimi-Fard, A. Lundervold, and D. Manchon. Noncommutative Bell polynomials, quasideterminants and incidence Hopf algebras. Int. J. Algebra Comput., 24(05): 671–705, 2014.

[11] F. Faà di Bruno. Sullo sviluppo delle funzioni. Ann. Sci. Mat. Fis., 6: 479–480, 1855.

[12] F. Faà di Bruno. Note sur une nouvelle formule de calcul différentiel. Quarterly J. Pure Appl. Math., 1: 359–360, 1857.

[13] L. Foissy. Bidendriform bialgebras, trees, and free quasi-symmetric functions. J. Pure Appl. Algebra 209 (2): 439–459, 2007.

[14] I. Gelfand, S. Gelfand, V. Retakh, and R. Wilson. Quasideterminants. Adv. Math., 193(1): 56–141, 2005.

[15] R. Grossman and R. G. Larson. Hopf-algebraic structure of families of trees. J. Algebra, 126(1):1 84–210, 1989.

[16] F. Hivert, J.-C. Novelli, and J.-Y. Thibon. Commutative combinatorial Hopf algebras. J. Algebraic Combin., 28(1): 65–95, 2008.

[17] B. Harris and L. Schoenfeld. The number of idempotent elements in symmetric semigroups. J. Combin. Theory, 3(2): 122–135, 1967.

[18] S. A. Joni and G.-C. Rota. Coalgebras and bialgebras in combinatorics. Stud. Appl. Math., 61(2): 93–139, 1979.

[19] S. Khelifa and Y. Cherruault. New results for the Adomian method. Kybernetes, 29(3): 332–355, 2000.

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

[21] J.-L. Loday, Cup-product for Leibniz cohomology and dual Leibniz algebras. Math. Scand., 77: 189– 196, 1995.

[22] I. G. Macdonald. Symmetric functions and Hall polynomials. 2nd ed. Oxford University Press, 1998.

[23] M. Mihoubi. Bell polynomials and binomial type sequences. Discrete Math., 308(12): 2450–2459, 2008.

[24] M. Mihoubi. Polynômes multivariés de Bell et polynômes de type binomial. Thèse de Doctorat, L’Université des Sciences et de la Technologie Houari Boumedienne, 2008.

[25] M. Mihoubi. Partial Bell polynomials and inverse relations. J. Integer Seq., 13(4), 2010.

[26] J.-C. Novelli and J.-Y. Thibon. Construction de trigèbres dendriformes. C. R. Acad. Sci, Paris, Sér. I, 342: 365–369, 2006.

[27] J.-C. Novelli, and J.-Y. Thibon. Hopf algebras and dendriform structures arising from parking functions. Fund. Math., 193: 189–241, 2007.

[28] J. Riordan. Derivatives of composite functions. Bull. Amer. Math. Soc., 52: 664–667, 1946.

[29] J. Riordan. An Introduction to Combinatorial Analysis. John Wiley & Sons, New York, 1958; Princeton University Press, Princeton, N.J., 1980.

[30] N. J. A. Sloane. The on-line encyclopedia of integer sequences.

[31] M. Tainiter. Generating functions on idempotent semigroups with application to combinatorial analysis. J. Combin. Theory, 5(3): 273–288, 1968.

[32] M. C. Wolf. Symmetric functions of non-commutative elements. Duke Math. J., 2(4): 626–637, 1936.

[33] H. Z. Munthe-Kaas, Lie–Butcher theory for Runge–Kutta methods. BIT, 35(4): 572–587, 1995.

[34] W. Wang and T. Wang. General identities on Bell polynomials. Computers Math. Appl., 58(1): 104–118, 2009.

Appendix A. Bell polynomials and coproducts in Sym

In fact, most of the identities on Bell polynomials can be obtained by manipulating generating functions and they are closely related to some other identities occurring in the literature. Typically, the relation between the complete Bell polynomials A_{n}(a_{1}, a_{2}, …) and the variables a_{1}, a_{2}, … is very closely related to the Newton Formula which links the generating function of complete symmetric functions h_{n} (Cauchy series) to that of the power sums p_{n}. The symmetric functions form a commutative algebra Sym freely generated by the complete functions h_{n} or the power sum functions p_{n}. Hence, specializing the variable a_{n} to some numbers is equivalent to specializing the power sum functions p_{n}. More soundly, the algebra Sym can be endowed with coproducts conferring to it the structure of a Hopf algebra. For instance, the coproduct for which the power sums are primitive turns Sym into a self-dual Hopf algebra. The coproduct can be translated in terms of generating functions by a product of two Cauchy series. This kind of manipulations appears also in the context of Bell polynomials, for instance when computing the complete Bell polynomials of the sum of two sequences of variables a_{1} + b_{1}, a_{2} + b_{2}, . . .. Another coproduct turns Sym into a non-cocommutative Hopf algebra called the Faà di Bruno algebra which is related to Lagrange inversion. Finally, the coproduct such that the power sums are group-like can be related also to a few other formulas on Bell polynomials. The aim of this section is to investigate these connections and in particular to restate some known results in terms of symmetric functions and virtual alphabets. We also give a few new results that are difficult to prove without the help of symmetric functions.

A.1. Bell polynomials as symmetric functions. First, let us recall some operations on alphabets. Given two alphabets 𝕏 and 𝕐, we define (see, e.g., [20]) the alphabet 𝕏+𝕐 by:

p_{n}(𝕏 + 𝕐) = p_{n}(𝕏) + p_{n}(𝕐)  (A.1)

and the alphabet α𝕏 (respectively 𝕏𝕐), for α ∈ ℂ by:

p_{n}(α𝕏) = αp_{n}(𝕏) (respectively p_{n}(𝕏𝕐) = p_{n}(𝕏)p_{n}(𝕐)).  (A.2)

In terms of Cauchy functions, these transforms imply

σ_{t}(𝕏 + 𝕐) = σ_{t}(𝕏)σ_{t}(𝕐)  (A.3)

and

σ_{t}(𝕏𝕐) = ∑_{λ} \frac{1}{z_{λ}} p^{λ}(𝕏)p^{λ}(𝕐)t^{|λ|}.  (A.4)

WORD BELL POLYNOMIALS 27

In fact σ_{t}(𝕏𝕐) encodes the kernel of the scalar product defined by ⟨p^{λ}, c_{μ}⟩ = δ_{λ,μ} with c_{λ} = \frac{p^{λ}}{z_{λ}}. Notice that c_{n} = \frac{p_{n}}{n} and

Sym = ℂ[c_{1}, c_{2}, …].  (A.5)

From (2.7) and (2.19), we obtain the following identity. Proposition 52. We have h_{n} = \frac{1}{n!}A_{n}(1! c_{1}, 2! c_{2}, …).

Conversely, Equality (A.5) implies that the homomorphism ϕ_{a} sending c_{i} to \frac{a_{i}}{i!} for all i is well defined for any sequence of numbers a = (a_{i})_{i∈ℕ\\{0\}}, and ϕ_{a}(h_{n}) = \frac{1}{n!}A_{n}(a_{1}, a_{2}, …).

Let us also define h_{n}^{(k)}(𝕏) = [α^{k}]h_{n}(α𝕏). From (2.19) and (A.2), we have

h_{n}^{(k)} = ∑_{λ=[λ_{1},...,λ_{k}]⊢n} c_{λ} = [t^{n}]\frac{1}{k!} (∑_{i≥1} c_{i}t^{i})^{k} ,

and thus everything works as if we use a special (virtual) alphabet 𝕏^{(a)} satisfying c_{n}(𝕏^{(a)}) = n! a_{n}. More precisely, the following identity holds true. Proposition 53. We have

ϕ_{a}(h_{n}^{(k)}) = h_{n}^{(k)}(𝕏^{(a)}) = \frac{1}{n!}B_{n,k}(a_{1}, …, a_{k}, …).  (A.6)

Example 54. Let 1 be the virtual alphabet defined by c_{n}(1) = \frac{1}{n} for all n ∈ ℕ. In this case, the Newton Formula yields h_{n}(1) = 1. Hence A_{n}(0!, 1!, 2!, …, (m − 1)!, …) = n! and

B_{n,k}(0!, 1!, 2!, …, (m − 1)!, …) = n! [α^{k}][t^{n}] (\frac{1}{1 − t})^{α} = s_{n,k},

the Stirling number of the first kind. Example 55. A more complicated example is treated in [4, 19], where a_{i} = i^{i−1}. In this case, the specialization gives

σ_{t}(α𝕏^{(a)}) = exp{−αW (−t)},

where W (t) = ∑_{n=1}^{∞}(−n)^{n−1} \frac{t^{n}}{n!} is the Lambert W function satisfying W (t) exp\{W (t)\} = t (see, e.g., [6]). Hence,

σ_{t}(α𝕏^{(a)}) = (\frac{W (−t)}{−t})^{α} .

However, the expansion of the series (\frac{W (t)}{t})^{α} is known to be

(\frac{W (t)}{t})^{α} = 1 + ∑_{n=1}^{∞} \frac{1}{n!}α(α + n)^{n−1}(−t)^{n}.  (A.7)

Hence, we obtain B_{n,k}(1, 2, 3^{2}, …, m^{m−1}, …) = \binom{n−1}{k−1}n^{n−k}. Note that the expansion of W (t) and (A.7) are usually obtained by the use of Lagrange inversion.

Example 56. With these notations, we have B_{n,k}(a_{1} + b_{1}, …) = \frac{1}{n!}h_{n}^{(k)}(𝕏^{(a)} + 𝕏^{(b)}), and classical properties of Bell polynomials can be deduced from symmetric functions through this formalism. For instance, the equalities c_{n}(𝕏^{(a)} + 𝕏^{(b)}) = c_{n}(𝕏^{(a)}) + c_{n}(𝕏^{(b)}) and h_{n}(𝕏^{(a)} + 𝕏^{(b)}) = ∑_{i+j=n} h_{i}(𝕏^{(a)})h_{j}(𝕏^{(b)}) give

A_{n}(a_{1} + b_{1}, …) = ∑_{i+j=n} \binom{n}{i}A_{i}(a_{1}, a_{2}, …)A_{j}(b_{1}, b_{2}, …)

and

B_{n,k}(a_{1} + b_{1}, …) = ∑_{r+s=k} ∑_{i+j=n} \binom{n}{i}B_{i,r}(a_{1}, a_{2}, …)B_{j,s}(b_{1}, b_{2}, …).

Example 57. Another example is given by

A_{n}(1a_{1}b_{1}, 2a_{2}b_{2}, …, ma_{m}b_{m}, …) = n! ∑_{λ⊢n} det (\frac{A_{λ_{i}−i+j}(a_{1}, a_{2}, …)}{(λ_{i} − i + j)!})

× det (\frac{A_{λ_{i}−i+j}(b_{1}, b_{2}, …)}{(λ_{i} − i + j)!}) ,

where we used the convention A_{−n} = 0 for n > 0. This formula is a consequence of the Jacobi–Trudi formula and is derived from the Cauchy kernel (A.4), observing that c_{n}(𝕏^{(a)}𝕏^{(b)}) = nc_{n}(𝕏^{(a)})c_{n}(𝕏^{(b)}) and

h_{n}(𝕏^{(a)}𝕏^{(b)}) = ∑_{λ⊢n} s_{λ}(𝕏^{(a)})s_{λ}(𝕏^{(b)}) = ∑_{λ⊢n} det (h_{λ_{i}−i+j}^{(a)}(𝕏^{a})) det (h_{λ_{i}−i+j}^{(b)}(𝕏^{b})) ,

where s_{λ} = det (h_{λ_{i}−i+j}^{(a)}) is a Schur function (see, e.g., [22]).

A.2. Other interpretations. First we focus on Identity (2.9), and we interpret it as the Cauchy function σ_{t}(k𝕏̂^{(a)}), where 𝕏̂^{(a)} is the virtual alphabet such that h_{i−1}(𝕏̂^{(a)}) = \frac{a_{i}}{i!} . This means that we consider the homomorphism ϕ̂_{a} : Sym ⟶ ℂ sending h_{i} to \frac{a_{i+1}}{(i+1)!}. We suppose that a_{1} = 1, otherwise we use (2.15) and (2.16). With these notations, the following relation holds true.

Proposition 58. We have

B_{n,k}(a_{1}, a_{2}, …) = \frac{n!}{k!}h_{n−k}(k𝕏̂^{(a)}).  (A.8)

Example 59. If a_{i} = i, we have h_{i}(𝕏̂^{(a)}) = \frac{1}{i!}, and so σ_{t}(k𝕏̂^{(a)}) = exp(kt). Hence, we recover the classical result

B_{n,k}(1, 2, …, m, …) = \binom{n}{k}k^{n−k}.

From h_{n}(𝕏 + 𝕐) = ∑_{i+j=n} h_{i}(𝕏)h_{j}(𝕐), we deduce two classical identities, namely

\binom{k_{1} + k_{2}}{k_{1}}B_{n,k_{1}+k_{2}}(a_{1}, a_{2}, …) = ∑_{i=0}^{n} \binom{n}{i}B_{i,k_{1}}(a_{1}, a_{2}, …)B_{n−i,k_{2}}(a_{1}, a_{2}, …) (A.9)

and

\binom{n}{k}B_{n−k,k} (a_{1}b_{1}, …, \frac{1}{m + 1} ∑_{i=1}^{m} \binom{m + 1}{i}a_{i}b_{m+1−i}, …)

= ∑_{i=k}^{n−k} \binom{n}{i}B_{i,k}(a_{1}, a_{2}, …)B_{i,k}(b_{1}, b_{2}, …). (A.10)

Indeed, formula (A.9) is obtained by setting 𝕏 = k_{1}𝕏̂^{(a)} and 𝕐 = k_{2}𝕏̂^{(a)}. Formula (A.10) is called the convolution formula for Bell polynomials (see, e.g., [24]), and is obtained by setting 𝕏 = 𝕏̂^{(a)} and 𝕐 = 𝕏̂^{(b)} in the left-hand side and 𝕏 = k𝕏̂^{(a)} and 𝕐 = k𝕏̂^{(b)} in the right-hand side.

Example 60. The partial Bell polynomials are known to be involved in interesting identities for binomial functions. Let us first recall that a binomial sequence is a family of functions (f_{n})_{n∈ℕ} satisfying f_{0}(x) = 1 and

f_{n}(a + b) = ∑_{k=0}^{n} \binom{n}{k}f_{k}(a)f_{n−k}(b),  (A.11)

for all a, b ∈ ℂ and n ∈ ℕ. Setting h_{n}(𝔸) := \frac{f_{n}(a)}{n!} and h_{n}(𝔹) := \frac{f_{n}(b)}{n!}, with these notations we have f_{n}(ka) = n! h_{n}(k𝔸). Hence,

B_{n,k}(1, …, if_{i−1}(a), …) = \frac{n!}{k!}h_{n−k}(k𝔸) = \binom{n}{k}f_{n−k}(ka).  (A.12)

Notice that from (A.9), we see that

f_{n}(k) = \begin{cases}\binom{n}{k}^{−1}B_{n,k}(a_{1}, a_{2}, …), & if n > 0, \\ 1, & if n = 0, \end{cases}

is binomial, and we obtain

\binom{n}{k_{1}k_{2}}^{−1}B_{n,k_{1}}(1, …, i\binom{i − 1}{k}^{−1}B_{i−1,k_{2}}(a_{1}, a_{2}, …), …)

= \binom{n − k_{1}}{k_{1}k_{2}}^{−1}B_{n−k_{1},k_{1}k_{2}}(a_{1}, a_{2}, …). (A.13)

Several related identities are compiled in [24].

Example 61. Extracting the coefficient of t^{n−k−1} on the left-hand side and the right-hand side of the equality \frac{d}{dt}σ_{t}((k + 1)𝕏) = (k + 1) (\frac{d}{dt}σ_{t}(𝕏)) σ_{t}(k𝕏), we obtain

(n − k)h_{n−k}((k + 1)𝕏) = (k + 1) ∑_{i=1}^{n−k} ih_{i}(𝕏)h_{n−i−k}(𝕏),

and we recover the identity (see, e.g., [8])

B_{n,k}(a_{1}, a_{2}, …) = \frac{1}{n − k} ∑_{i=1}^{n−k} \binom{n}{i} [(k + 1) − \frac{n + 1}{i + 1}] (i + 1)a_{i}B_{n−i,k}(a_{1}, a_{2}, …). (A.14)

Example 62. Let (a_{n})_{n>0} and (b_{n})_{n>0} be two sequences of numbers such that a_{1} = b_{1} = 1 and

d_{n} = n! ∑_{λ⊢n−1} det (\frac{a_{λ_{i}−i+j+1}}{(λ_{i} + j + 1)!}) det (\frac{b_{λ_{i}−i+j+1}}{(λ_{i} + j + 1)!})

with the convention a_{−n} = b_{−n} = 0 if n ≥ 0. The Cauchy kernel and the orthogonality of Schur functions give

B_{n,k}(d_{1}, d_{2}, …) = \frac{n!}{k!} ∑_{λ⊢n−k}(k_{1}! k_{2}!)^{ℓ(λ)} det (\frac{B_{λ_{i}−i+j+k_{1},k_{1}}(a_{1}, a_{2}, …)}{(λ_{i} − i + j + k_{1})!})

× det (\frac{B_{λ_{i}−i+j+k_{1},k_{1}}(b_{1}, b_{2}, …)}{(λ_{i} − i + j + k_{1})!}) ,

for k_{1}k_{2} = k. Indeed, it suffices to use the fact that

h_{n}(k𝕏^{(a)}𝕏^{(b)}) = ∑_{λ⊢n} s_{λ}(k_{1}𝕏^{(a)})s_{λ}(k_{2}𝕏^{(b)}).

The sum 𝕏 + 𝕐 and the product 𝕏𝕐 of alphabets are two examples of coproducts endowing Sym with the structure of a Hopf algebra. The sum of alphabets encodes the coproduct Δ for which the power sums are of Lie type (i.e., Δ(p_{n}) = p_{n} ⊗ 1 + 1 ⊗ p_{n} ∼ p_{n}(𝕏 + 𝕐) = p_{n}(𝕏) + p_{n}(𝕐) by identifying f ⊗ g with f(𝕏)g(𝕐)), whilst the product of alphabets encodes the coproduct Δ′ for which the power sums are group-like (i.e., Δ′(p_{n}) = p_{n} ⊗ p_{n} ∼ p_{n}(𝕏𝕐) = p_{n}(𝕏)p_{n}(𝕐)).

The algebra of symmetric functions can be endowed with another coproduct that confers the structure of a Hopf algebra: this is the Faà di Bruno algebra [9, 18]. This algebra is rather important since it is related to the Lagrange–Bürmann formula. The Bell polynomials also appear in this context. As a consequence, one can define a new operation on alphabets corresponding to the composition of Cauchy generating functions. Let 𝕏 and 𝕐 be two alphabets and set f(t) = tσ_{t}(𝕏) and g(t) = tσ_{t}(𝕐). The composition 𝕏 ∘ 𝕐 is defined by σ_{t}(𝕏 ∘ 𝕐) = \frac{1}{t}(f ∘ g)(t). The relationship with Bell polynomials can be established by observing that we have

\frac{1}{t}f ∘ g = ∑_{n≥0} (∑_{k=1}^{n+1} \frac{k!}{(n + 1)!}h_{k−1}(𝕏)B_{n+1,k}(1, 2h_{1}(𝕐), 3! h_{2}(𝕐), …)) t^{n}.

Equivalently,

h_{n}(𝕏 ∘ 𝕐) = ∑_{k=0}^{n} \frac{(k + 1)!}{(n + 1)!}h_{k}(𝕏)B_{n+1;k+1}(1, 2! h_{1}(𝕐), 3! h_{2}(𝕐), …).

The antipode of the Faà di Bruno algebra is also described in terms of alphabets as the operation which associates to an alphabet 𝕏 the alphabet 𝕏^{⟨−1⟩} satisfying σ_{t}(𝕏∘𝕏^{⟨−1⟩}) = 1. More explicitly, we have

h_{n}(𝕏^{⟨−1⟩}) = \frac{n!}{(2n + 1)! (n + 1)}B_{2n+1,n}(1, −2! e_{1}(𝕏), 3! e_{2}(𝕏), …),  (A.15)

where the e_{n}(𝕏)’s are the elementary symmetric functions defined by ∑_{n} e_{n}(𝕏)t^{n} = \frac{1}{σ_{−t}(𝕏)}.

Example 63. Let ω(t) = tσ_{t}(𝕏). The Lagrange inversion consists in finding an alphabet 𝕏′ such that ϕ(t) = σ_{t}(𝕏′). According to (A.15), it suffices to set 𝕏′ = −𝕏^{⟨−1⟩}. Let F (t) = σ_{t}(𝕐). When stated in terms of alphabets, the Lagrange–Bürmann formula reads

F (ω(t)) = 1 + ∑_{n≥1} \frac{d^{n−1}}{du^{n−1}} [σ′_{u}(𝕐)σ_{u}(−n𝕏^{⟨−1⟩})]|_{u=0} \frac{t^{n}}{n!}.

In other words, we have h_{n−k}(−n𝕏^{⟨−1⟩}) = \frac{(k−1)!}{(n−1)!}B_{n,k}(1, 2! h_{1}(𝕏), 3! h_{3}(𝕏), …). So we recover a result due to Sadek Bouroubi and Moncef Abbas [4]:

B_{n,k}(1, h_{1}(2𝕏), …, (m − 1)! h_{m−1}(m𝕏), …) = \frac{(n − 1)!}{(k − 1)!}h_{n−k}(n𝕏).

† USTHB, Faculty of Mathematics, Po. Box 32 El Alia 16111 Algiers, Algeria.

  E-mail address: aboudam@gmail.com

¶ Laboratoire LITIS - EA 4108, Université de Rouen, Avenue de l’Université - BP 8 76801 Saint-Étienne-du-Rouvray Cedex.

  E-mail address: jeanpaulbultel@gmail.com

‡ Laboratoire LITIS - EA 4108, Université de Rouen, Avenue de l’Université - BP 8 76801 Saint-Étienne-du-Rouvray Cedex.

  E-mail address: (ali.chouria1, jean-gabriel.luque, olivier.mallet)@univ-rouen.fr