{'fraction_non_alphanumeric': 0.0486525075852222, 'fraction_numerical': 0.015099054078172408, 'mean_word_length': 4.04247660187185, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 22, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Duplicial algebras and Lagrange inversion

We provide operadic interpretations for two Hopf subalgebras of the algebra of parking functions. The Catalan subalgebra is identified with the free duplicial algebra on one generator, and the Schröder subalgebra is interpreted by means of a new operad, which we call triduplicial. The noncommutative Lagrange inversion formula is then interpreted in terms of duplicial structures. The generic solution of the noncommutative inversion problem appears as the formal sum of all parking functions. This suggests that combinatorial generating functions derived by functional inversion should be obtainable by evaluating a suitable character on this generic solution. This idea is illustrated by means of the Narayana polynomials, of which we obtain bivariate “super-analogues” by lifting to parking functions a classical character of the algebra of symmetric functions. Other characters, such as evaluation of symmetric functions on a binomial element, are also discussed.


Introduction
In its simplest version, the Lagrange inversion formula gives the coefficients of the unique formal power series (1) u(t) = n≥0 c n t n+1 satisfying the functional equation ϕ(x) = n≥0 a n x n (a 0 = 0) is a series with nonzero constant term. As is well-known, the result is (4) c n = 1 n + 1 [x n ](ϕ(x)) n+1 .
There exist several combinatorial variations of this result, providing descriptions of c n as a polynomial in the a n as well as q-analogues or noncommutative versions.
As any generic identity among formal power series, the formula of Lagrange is equivalent to an identity on symmetric functions [9]. One may identify the a n with a sequence of algebraically independent generators of the algebra Sym(X) of symmetric functions, for example set a n = h n (X) (the complete homogeneous functions as in [17, Ex. 24 p. 35, Ex. 25 p. 132]) so that (5) ϕ(u) = n≥0 h n (X)u n = n≥1 (1 − ux n ) −1 =: σ u (X) and the result (4) reads (in λ-ring notation) (6) c n = 1 n + 1 h n ((n + 1)X) .
What makes this expression interesting is that this symmetric function is the Frobenius characteristic of the permutation representation of the symmetric group S n on the set PF n of parking functions of length n [5]. It has moreover been shown in [22] that noncommutative versions of the Lagrange formula such as in [4] or [25] could be formulated in terms of noncommutative symmetric functions [3]. Again, the term g n of degree n in the series g satisfying (7) g = n≥0 S n g n (where the S n are the noncommutative complete symmetric functions) is the Frobenius characteristic of the natural representation of the 0-Hecke algebra H n (0) on parking functions. Now, there is a combinatorial Hopf algebra, PQSym, which is based on parking functions. Denoting its natural basis by F a as in [20], we shall see that the series g is the image of the sum of all parking functions (8) G = a∈PF F a by a homomorphism of Hopf algebras. This morphism can be defined at the level of several intermediate Hopf algebras, such as SQSym or CQSym (both defined in [21]), which have as graded dimensions the sequences of little Schröder numbers and Catalan numbers respectively. We shall see that CQSym can be naturally identified with the free duplicial algebra on one generator, and that as an element of CQSym, G satisfies a quadratic functional equation allowing to identify it with the formal sum of all binary trees. This forces a bijection between these trees and nondecreasing parking functions, which in turn implies the existence of an involution explaining the symmetry properties of G observed in [22] and established there by means of a different involution. The operadic interpretation of CQSym suggests the existence of a similar one for SQSym. We thus introduce a new operad, which we call triduplicial, for which SQSym is the free algebra on one generator.
Finally, we illustrate the idea that combinatorial series derived by means of Lagrange inversion should come from some character of the algebra of parking functions. First, we generalize Lassalle's expression [10] of the Narayana polynomials c n (t) to super-Narayana polynomials P n (t, q) counting signed parking functions according to certain statistics, and such that P n (t, 0) = (1 + t)c n (1 + t). This last polynomial is known to count Schröder paths according to the number of horizontal steps [26, A060693].
These paths can be naturally encoded by a subset of signed parking functions, such that minus signs correspond to horizontal steps. We conclude by investigating the character of symmetric functions defined by evaluation on a binomial element, and obtain a combinatorial interpretation of its lift to parking functions. This paper is a continuation of [21,22]. We have only recalled the most basic definitions so as to make it reasonably self-contained.

Operads and combinatorial Hopf algebras
Combinatorial Hopf algebras are certain graded bialgebras based on combinatorial objects. This is a heuristic concept, and there is no general agreement on what should be their general definition. For us, they arise as natural generalizations of the algebra of symmetric functions. Surprisingly, most of these algebras also arise in the theory of operads (sometimes with non-obviously equivalent definitions). We shall see that our analysis of the noncommutative Lagrange inversion problem will allow to identify the operads associated with two algebras (CQSym and SQSym) from [21], for which the operadic interpretation was not known.
2.1. Noncommutative symmetric functions. The Hopf algebra of noncommutative symmetric functions [3], denoted by Sym, or by Sym(A) if we consider the realization in terms of an auxiliary alphabet, is the free associative algebra over a sequence (S n ) n≥1 , graded by deg (S n ) = n. For A = {a n |n ≥ 1} a totally ordered set of noncommuting indeterminates, we define the generating series so that S n (A) is the sum of all nondecreasing words of length n (and S 0 = 1). Bases of Sym n are labelled by compositions I = (i 1 , . . . , i r ) of n. The natural basis is S I = S i 1 · · · S ir . The reverse refinement order I ≤ J on compositions of n means that the parts of I are sums of consecutive parts of J. The length r of I is denoted by ℓ(I). The conjugate composition is denoted by I ∼ . The ribbon basis is defined by For two compositions I = (i 1 , . . . , i r ) and J = (j 1 , . . . , j s ), define (11) I · J = (i 1 , . . . , i r , j 1 , . . . , j s ) and I ⊲ J = (i 1 , . . . , i r + j 1 , . . . , j s ) . Then, Thus, in the R-basis, the multiplication of Sym is the sum of the two operations · and ⊲. For this reason, one may consider Sym as a dialgebra [14]. Both operations are associative, and furthermore where * 1 and * 2 are · or ⊲. Such an algebra is called an As (2) -algebra [28]. It is easy to see that Sym is actually the free As (2) -algebra on one generator. This is the simplest example of a combinatorial Hopf algebra associated with an operad. A somewhat more interesting example arises if we consider a slightly more general version of the noncommutative Lagrange inversion problem.

2.2.
Nondecreasing parking functions. The versions of [4] and [25] of the noncommutative inversion formula can be interpreted as solving the equation where S 0 is now another indeterminate not commuting with the other ones [22]. A nondecreasing parking function is a nondecreasing word π = π 1 . . . π n over [n] such that π i ≤ i. A parking function is any rearrangement of such a word.
The solution of (14) can be expressed in the form [22] (15) where NDPF n denotes the set of nondecreasing parking functions of length n. The evaluation of a word is the sequence ev(w) = (|w| i ) recording the number of occurences of each letter i. For example, the nondecreasing parking functions giving f 3 being (in this order) 123, 122, 113, 112, 111.
As shown in [21], there is a combinatorial Hopf algebra based on nondecreasing parking functions. We shall see that it is directly related to Lagrange inversion, and uncover its operadic interpretation.
2.3. Duplicial algebras. A duplicial algebra [12] is a vector space endowed with two associative operations ≺ and ≻ such that It is known that the free duplicial algebra D on one generator has a basis labelled by binary trees. The operations ≺ and ≻ can be respectively identified with the products \ (under) and / (over) (see [12]). The dimensions of the homogeneous components are therefore the Catalan numbers 1, 2, 5, 14 . . . . Here is another realization of D.
The Hopf algebra PQSym, defined in [20], is the linear span of elements F a where a runs over all parking functions. The sums (19) P π := a;a ↑ =π F a where a ↑ means the non-decreasing reordering and π runs over the set NDPF of non-decreasing parking functions, span a cocommutative Hopf subalgebra CQSym of PQSym. The basis P π is multiplicative: if α is of length k. For example, P 12 P 113 = P 12335 . The S n = P 1 n generate a Hopf subalgebra isomorphic to Sym, which is also a quotient of CQSym (see below).
Introduce now a second product involving a different kind of shifted concatenation: For example, P 12 ≺ P 113 = P 12224 .
Proposition 2.1. Let us denote the usual product of CQSym by ≻.
Proof -It is clear that ≻ and ≺ are associative. Also, since, denoting by n the length of α and by m the maximum letter of β, The other cross-associativity relation is not satisfied, since already (1 • 1) • 1 = 113 = 112 = 1 • (1 • 1). Thus, (CQSym, ≺, ≻) is duplicial. It is free on the generator x = P 1 , since all non decreasing parking functions can be obtained by iterating • and • on 1. Indeed, π ∈ NDPF is either non-connected, that is, of the form π = π ′ • π ′′ with nontrivial factor, or connected, in which case is can be written π = 1π ′ = 1 • π ′ for some other π ′ . Since nondecreasing parking functions of length n are in bijection with binary trees on n nodes, we see that CQSym is indeed free.
2.4. The duplicial operad. The duplicial operad is described in detail in [12]. Here is a brief summary. First, there is a notion of duplicial coproduct, allowing to define primitive elements.
The usual coproduct of CQSym is defined in terms of the parkization operation introduced in [21]. Selecting terms in this coproduct, we obtain a duplicial coproduct: endows CQSym with the structure of a duplicial bialgebra.
Proof -An immediate verification.
The primitive elements are defined by the condition δx = 0. It is known that the binary operation (26) {x, y} = x ≺ y − x ≻ y is magmatic, and that is preserves the primitive subalgebra of a duplicial algebra. As a consequence, the Dup-primitive subalgebra of CQSym is generated by x = P 1 for the operation {−, −}. This implies that (As, Dup, Mag) is a good triple of operads in the sense of Loday [12]. That is, we have As • Mag = Dup.
As an associative algebra for the product ≻, CQSym is free over its primitive subspace (which has dimension c n−1 in degree n as expected).
The duplicial operad is Koszul, and its dual Dup ! is defined by the same relations, together with two extra ones The dimension in degree n is n, and the linear generators are the hook-shaped trees There are known morphisms of operads Dup → As (2) , Dup → Dias and 2as → Dup [12]. The morphism of operads Dup → As (2) corresponds to the Hopf algebra morphism φ : CQSym → Sym (defined in [21]) where the composition t(π) is the packed evaluation of π, i.e., the composition obtained by removing the zeros from ev(π).
For a totally ordered alphabet A, FQSym(A) is the algebra spanned by the noncommutative polynomials where σ is a permutation in the symmetric group S n and Std(w) denotes the standardization of the word w. The multiplication rule is where the convolution α * β of α ∈ S k and β ∈ S l is the sum in the group algebra of S k+l [18] (39) The dendriform structure of FQSym is given by There is a scalar product on FQSym given by is the dual basis of G σ (as a Hopf algebra, FQSym is self-dual).
Now, x = G 1 generates a free dendriform algebra in FQSym, PBT, the Loday-Ronco algebra of planar binary trees [15]. The natural basis P T of this algebra can be interpreted as follows.
In FQSym, one can build from the dendriform operations a bilinear map [6] (45) so that the terms B T (a) of the binary tree expansion of the unique solution of the functional equation are precisely the basis P T of the free dendriform algebra on one generator x = F 1 for the choice a = 1 (B T (a) is the result of evaluating the expression encoded by the complete binary tree T with a in the leaves and B in the internal nodes). As for the solution X, it is just the sum of all G σ , that is, the sum of all words. This interpretation leads to simple derivations of the q-hook length formulas for binary trees [6], as well as to the combinatorial interpretations of various special functions such as the tangent [7] or possibly the Jacobi elliptic functions.
2.6. Word quasi-symmetric functions and tridendrifom algebras. A dendriform trialgebra [16] (or tridendriform algebra) is an associative algebra whose multiplication ⊙ splits into three pieces where • is associative, and The packed word u = pack(w) associated with a word w ∈ A * is obtained by the following process.
We denote by PW the set of packed words. With such a word, we associate the polynomial These polynomials span a subalgebra of K A , called WQSym for Word Quasi-Symmetric functions see, e .g., [6]).
The product on WQSym is given by where the convolution u ′ * W u ′′ of two packed words is defined as It is a dendriform trialgebra. The partial products being given by It is known [16] that the free dendriform trialgebra on one generator, denoted here by TD, is a free associative algebra with Hilbert series that is, the generating function of the super-Catalan, or little Schröder numbers, counting plane trees.
There is a natural embedding FQSym ֒→ WQSym given by On the polynomial realizations, this is indeed an inclusion. Both FQSym and WQSym can be interpreted as operads. The space of n-ary operations of the Zinbiel operad can be naturally identified with FQSym n [1], and for WQSym, the relevant operad is described in [19].
2.7. The triduplicial operad. Thus, the free dendriform and free tridendriform algebras on one generator arise naturally as quotients of WQSym, as well as the free tricubical algebra. Applying the same strategy to PQSym, we obtain together with CQSym (Catalan numbers), the little Schröder numbers (SQSym) and segmented compositions (powers of 3) [21]. Having identified CQSym with the duplicial operad, we may suspect that SQSym should have an operadic interpretation which is to Dup what T riDend is to Dend. This is indeed the case. The new operad will be called triduplicial. It is a quotient of the triplicial operad defined in [11] (one more relation).

Definition 2.3.
A triduplicial algebra is a vector space V endowed with three associative laws ≺, ≻, • such that Recall from [21] that a parking quasi-ribbon is a segmented nondecreasing parking function where the bars only occur at positions · · · a|b · · · , with a < b. These objects encode hypoplactic classes of parking functions. The first ones are The number of parking quasi-ribbons of length n is the little Schröder number s n . With a parking quasi-ribbon q, we associate the elements where P(a) denotes the hypoplactic class of a. For example, The P q form a basis of a Hopf subalgebra of PQSym, denoted by SQSym [21]. As an associative algebra, it is isomorphic to TD, the free tridendriform algebra on one generator, which is itself a Hopf subalgebra of WQSym constructed by a similar method. However, this is not an isomorphism of Hopf algebras. Indeed, TD is selfdual, but SQSym is not. This raised the question of an operadic interpretation of SQSym. The following result provides an answer.
Theorem 2.4. The free triduplicial algebra on one generator T has the little Schröder numbers as graded dimensions. Its natural basis can be realised by parking quasiribbons, if we define ≺ and ≻ by shifted concatenation as above, and • as ordinary shifted concatenation with insertion of a bar: Proof -It is immediate to check that this defines a triduplicial structure, and that the subspace of SQSym generated by P 1 for these three operations contains all the quasi-ribbons P q . So the free triduplicial algebra has at least the sequence s n as graded dimensions. Now, the triduplicial relations can be presented as rewriting rules for evaluation trees. We then have the seven relations, the first three consisting in the associativity of the three operations, the next four ones being the four duplicial relations presented in Definition 2.3.
Now consider all these relations as oriented rewriting between trees, each left tree being replaced by its right counterpart. Then the free triduplicial algebra on one generator is spanned (not necessarily freely) by the trees that cannot be rewritten. Analysing the seven relations above, one sees that the trees that cannot be rewritten are of the following form: either the tree consisting in a single node, or a tree with any operation at its root whose left subtree is a leaf, or one of the following two trees: where A and B are trees that cannot be rewritten. The generating series S(x) of these trees staisfies therefore the functional equation (72) S = 1 + 3xS + 2x 2 S 2 , whose solution is the generating series of the s n , so that that the free triduplicial algebra on one generator has at mist the s n as graded dimensions. Therefore, the parking quasi-ribbons provide a faithful realization of it.
Thus, T can be identified with SQSym.
For the sake of completeness, let us mention that as in the case of Dup, the dual operad T riDup ! is defined by the same relations, together with four extra ones The sequence of dimensions is therefore 2 n − 1, as for the dual of TriDend [28].
2.8. Duplicial operations on parking functions. The free dendriform and tridendriform algebras on one generator arise naturally as subalgebras of FQSym and WQSym, which are themselves dendriform and tridendriform in a natural way. Similarly, the duplicial structure of the Catalan algebra CQSym is actually inherited from a duplicial structure on PQSym. The ≻ operation is the usual product (given by the ordinary shifted shuffle). The ≺ operation is also a kind of shifted shuffle, with a normalization factor.

A bilinear duplicial equation.
Let G ∈ PQSym be the formal sum of all parking functions Actually, G belongs to CQSym, and and each term B T (1) of the tree expansion of the solution is a single P π , thus forcing a bijection beween binary trees and nondecreasing parking functions.
Proof -Proposition 2.1 shows that CQSym is the free duplicial algebra on one generator. So we have already seen that each nondecreasing parking function has a unique expression of the form P α ≻ P 1 ≺ P β , where α and β are (possibly empty) nondecreasing parking functions. The same is true of binary trees, if one interprets ≺ and ≻ as the over-under operations [15,12], whence the correspondence.
The bijection between binary trees and nondecreasing parking functions can be described as follows. Starting with a tree T , its vertices are recursively labeled by integers, and the tree is flattened so as to read a word. The label of the root is the number m of vertices of its left subtree, plus one. The labels of the right subtree are its original ones shifted by m − 1.
For example,

Some Tamari intervals. This correspondence has an interesting compatibility with the Tamari order:
Proposition 3.2. Nondecreasing parking functions with the same packed evaluation I form an interval, whose cardinality is the coefficient of S I in g.
Proof -It is enough to show that the nondecreasing parking functions with packed evaluation J ≤ I for the reverse refinement order form an interval. Now, 1 i 1 ≻ . . . ≻ 1 ir is maximal among those for the Tamari order (this is the maximal element of the product in PBT of the trees encoded by the 1 i k ), and 1 n = 1 i 1 ≺ . . . ≺ 1 ir is its minimal element. This corresponds to S I through the embedding of Sym given by S n → 1 n . Thus this is an interval, and the intervals composed of nondecreasing parking functions with the same packed evaluation I correspond to the expansion of the ribbons RĪ∼ (conjugate mirror of I) on the basis of trees.
In other words, our bijection between binary trees and nondecreasing parking functions has the property that the trees having the same canopy [27,15] correspond to nondecreasing parking functions with the same packed evaluation.

3.3.
An involution on CQSym. The natural involution (mirror symmetry) on binary trees induces an involution ι on nondecreasing parking functions, which is similar to (but different from) the involution ν of [22]. Defining a basis Q π by Now, there is a Hopf algebra morphism φ : CQSym → Sym mapping P π to S t(π) , where the composition t(π) is the packed evaluation of π. This maps sends G to the noncommutative Lagrange series g [22], The involution ι is mapped to S I → S I ∼ . This provides a simple proof of the symmetry of g observed in [22,Sec. 7].

4.1.
The formula of Lassalle for the Narayana polynomials. It has been observed by M. Lassalle [10] that the Narayana polynomials c n (q) could be expressed in the form (85) qc n (q) = 1 n + 1 h n ((n + 1)q) in λ-ring notation, with the assumption that x = 1 − q is of rank 1. Otherwise said, the image of the symmetric function g n (X) by the character of Sym sending the power sum p n to 1 − x n . This character is also well-defined on Sym [8], and we shall see that it can be lifted to PQSym, as well as the two-parameter extension This result can then be given a combinatorial interpretation by following a chain of morphisms whose composition builds up a character of PQSym.

4.2.
From parking functions to permutations. The polynomial realization of the dual PQSym * given in [20] implies the existence of an embedding of Hopf algebras which is actually an inclusion of the polynomial realizations: Thus, the dual map is a surjective morphism of Hopf algebras.

4.3.
From permutations to compositions. The restriction of i * to SQSym takes its values in Sym, and precisely, where I is the shape of the quasi-ribbon q. Further restricting to CQSym ⊂ SQSym yields (92) i * (P π ) = S I where I = t(π) is the packed evaluation of π.

From compositions to scalars or polynomials.
At the level of Sym, we have many characters at our disposal. Since characters take their values in a commutative algebra (our ground field K), they come actually from characters of Sym. An important and classical example is evaluation on the virtual alphabet This character can be lifted in several ways to FQSym. One of them, denoted by [23] (see (96) below).

4.5.
Super-Narayana polynomials. Recall from [24] that a signed parking function is a pair (a, ε) where a is an ordinary parking function and ε a word of the same length over the alphabet {±1}. There are therefore 2 n (n + 1) n−1 signed parking functions of length n (cf. [26, A097629]). There is a Hopf algebra, denoted by PQSym (2) based on signed parking functions. The product in its F (a,ε) basis is given by the shifted shuffle of signed words.
Definition 4.1. A signed inversion of a signed parking function (a, ε) is a pair (i, j) with i < j such that either ε i a i > ε j a j (an ordinary inversion) or ε i a i = ε j a j and the common sign ε i is −1.
Similarly, a signed descent is an index i such that either ε i a i > ε i+1 a i+1 or ε i a i = ε i+1 a i+1 and the common sign ε i is −1.
The signed major index smaj(a, ε) is the sum of the signed descents.
where g n is interpreted as a commutative symmetric function). Then, a n (i, j) is equal to the number of signed parking functions (a, ε) of length n with i minus signs and j signed inversions, or with signed major index j. In particular, the coefficient of t k in P n (t, 0) is equal to the number of nondecreasing signed parking functions (a, ε) with k minus signs.
Proof -The signed inversions (resp. descents) of (a, ε) are the ordinary inversions (resp. descents) of (std(a), ε). Hence, sinv and smaj have the same distribution over signed parking functions of length n. Now, on the one hand, it has been shown in [23] that where m(ε) is the number of minus signs, and maj is computed w.r.t. the usual order of Z.
On the other hand, the map s : PQSym → PQSym (2) defined by is a morphism of algebras, and the map φ q,x : is a character of PQSym (2) (also if one replaces smaj by sinv).
Thanks to the characterization of signed inversions (or descents) as ordinary inversions (or descents) of the standardization, we see that Thus, where g can now be interpreted as an ordinary (commutative) symmetric function.
which coincides with that of [26, A060693] (up to the constant term, which is 1 for us).
Corollary 4.3. The coefficient of t k in P n (t) is the number of Schröder paths of semilength n with k horizontal steps. In particular, we recover the formula of Lassalle, since it is known that the generating polynomial for horizontal steps in Schröder paths is (t + 1)c n (t + 1). Hence (106) tc n (t) = P n (t − 1) .

4.6.
A character of SQSym. The character yielding the Narayana polynomials has a simple description at the level of SQSym. Let b(q) be the number of bars of a parking quasi-ribbon q. Then, χ(P q ) = (1 + t)t b(q) is a character of SQSym. Let again G(z) = q z |q| P q = a z |a| F a be the sum of all parking functions (with a homogeneity variable z). Then, Thus, c n (1 + t) counts parking quasi-ribbons according to the number of bars. As we have already seen, the classical interpretation of c n (1 + t) is in terms of Schröder paths (the coefficient of t k is the number of paths of semilength n containing exactly k peaks but no peaks at level one [26, A126216]). Thus, parking quasi-ribbons with k bars are in bijection with these paths.
A simpler interpretation still in terms of Schröder paths is: the number of paths with k horizontal steps, and no peak after the last horizontal step.
Replacing the last horizontal step by a peak gives the missing paths, wich explains the factor (1 + t).

4.7.
Other characters. Any character of Sym (hence also of Sym) can be lifted to PQSym, thanks to the following property: Proof -Let a ∈ PF n andb b ∈ PF m , I = t(a) and J = t(b). Then, the product F a F b contains (n+m)! n!m! terms F c , which all have packed evaluation t(c) = I · J.
Of course, this is not a morphism of coalgebras, as this would imply by duality an embedding of QSym into a free associative algebra.
As an illustration of this principle, let us consider the classical character of Sym, given by evaluation on a binomial element. Recall that the symmetric functions of a binomial element α are given by (110) e n (α) = α n or, equivalently, h n (α) = α + n − 1 n , p n (α) = α . Thus, where χ is the character of Sym given by S n → 1 n! , and (112) is the cycle enumerator of the stabilizer of any word w of (packed) evaluation I. Dividing by χ(S I ), we have: is a character of PQSym.
From the previous considerations, we obtain a combinatorial interpretation of the coefficients of P n (α): Corollary 4.6. The coefficient of α k in P n (α) is equal to the number of pairs (a, σ) where a ∈ PF n and σ is a permutation in S n with k cycles, such that aσ = a.
We can observe a curious property of the reciprocal polynomials evaluated at q −1: if we set (120) Q n (q) = (q − 1) n−1 P n 1 q − 1 = n k=2 ((n + 1 − k)q + k) we obtain a q-analogue of (n + 1) n−1 whose coefficients form the triangle (121) 1 2 1 6 8 2 24 58 37 6 The first column is clearly n!. The second column is sequence A002538 in the OEIS [26], which counts the number of edges in the Hasse diagram of the Bruhat order on S n . Since the first column is the number of vertices, one may wonder whether the other numbers also have an interpretation in this context. This will be left as an open problem.