In this paper, we study the distribution on \([k]^n\) for the parameter recording the number of indices \(i \in [n-1]\) within a word \(w=w_1\cdots w_n\) such that \(|w_{i+1}-w_i|\ \leq 1\) and compute the corresponding (bivariate) generating function. A circular version of the problem wherein one considers whether or not \(|w_n-w_1|\ \leq 1\) as well is also treated. As special cases of our results, one obtains formulas involving staircase and Hertzsprung words in both the linear and circular cases. We make use of properties of special matrices in deriving our results, which may be expressed in terms of Chebyshev polynomials. A generating function formula is also found for the comparable statistic on finite set partitions with a fixed number of blocks represented sequentially.
Let \([k]=\{1,\ldots,k\}\) for a positive integer \(k\), with \([0]=\varnothing\). Members of \([k]^n\) are sequences of length \(n\) with letters in \([k]\), and are referred to as \(k\)-ary words. A variety of statistics based on the relative sizes of adjacent letters have been previously considered on \([k]^n\). For example, in [2], the authors enumerate \(k\)-ary words according to the number of occurrences of various infinite families of subword patterns and, as a consequence, obtain results for all subwords of length three. The problem of studying the distribution for the number of indices \(i \in [n-1]\) such that \(w_{i+1}-w_i=d\) for a fixed positive integer \(d\) within \(w=w_1\cdots w_n \in [k]^n\) was studied in [5, 10], where formulas for the generating function of the distribution were found. Further, in [5], analogous formulas involving the absolute difference \(|w_{i+1}-w_i|\) are found and the statistic on \([k]^n\) tracking the number of indices \(i\) such that \(w_{i+s}-w_i=d\) for a fixed \(d\) and \(s\) is considered. The distribution of the latter parameter has also been studied on permutations [19], represented in the one-line notation.
In this paper, we consider the distribution of the following two further statistics on \([k]^n\). For a word \(w=w_1\cdots w_n\in[k]^n\), we let \[\begin{aligned} {s}(w)&= \#\{\,i \in [n-1]\;:\;|w_{i+1}-w_i|\ \leq 1\},\\ {cs}(w)&= \#\{\,i\in[n]\;:\;|w_{i+1}-w_i|\ \leq 1\}, \end{aligned}\] where \(w_{n+1}=w_1\). For example, if \(w=423353 \in [5]^6\), then we have \({s}(w)=2\), accounting for the 2,3 and 3,3 strings, and \({cs}(w)=3\), which also accounts for \(w_6=3,w_1=4\). Let \(F_k(x,t)\) and \(G_k(x,t)\) denote the generating functions for the distributions of the \({s}\) and \({cs}\) statistics on \([k]^n\) for a fixed \(k\geq1\). That is, \[F_k(x,t)=1+\sum_{n \geq 1}\left(\sum_{w \in [k]^n}t^{{s}(w)}\right)x^n,\] and \[G_k(x,t)=1+\sum_{n \geq 1}\left(\sum_{w \in [k]^n}t^{{cs}(w)}\right)x^n.\]
Here, we find explicit formulas for \(F_k(x,t)\) and \(G_k(x,t)\) in terms of Chebyshev polynomials. Kitaev and Remmel [7] studied \(F_k(x,t)\) though they did not determine an explicit formula, instead finding an expression for \(F_k(x,t)\) as a sum over the entries of the inverse of a certain matrix (with \(G_k(x,t)\) apparently not being considered at all). In the proofs of our expressions for \(F_k(x,t)\) and \(G_k(x,t)\), we draw extensively upon linear algebra, in particular utilizing the Sherman–Morrison inverse formula as well as the inverse of a special matrix. In order to obtain our formula for \(G_k(x,t)\), we evaluate several sums of products involving Chebyshev polynomials of the second kind, see Table 1 below.
Recall that a staircase word \(w=w_1\cdots w_n\) is one in which \(|w_{i+1}-w_i|\ \leq 1\) for all \(1\leq i\leq n-1\). If, in addition, \(|w_n-w_1|\ \leq 1\), then \(w\) is said to be a cyclic staircase word. Note that \(w\) is a staircase or cyclic staircase word if and only if \({s}(w)=n-1\) or \({cs}(w)=n\), respectively. The study of (cyclic) staircase words seems to have begun with the work of Knopfmacher et al. [9]. A number of generalizations and refinements have been subsequently considered; see, e.g., [4, 7, 18, 13, 17]. Our formulas for \(F_k(x,t)\) and \(G_k(x,t)\) will be seen to generalize those obtained by Knopfmacher et al. [9], who calculated the (univariate) generating functions for the number of staircase and cyclic staircase words.
By a partition of a set, we mean a collection of non-empty, pairwise disjoint subsets, called blocks, whose union is the set. Let \(\mathcal{P}_{n,k}\) denote the set of partitions of \([n]\) having \(k\) blocks. We also consider here the \({s}\)-parameter distribution on \(\mathcal{P}_{n,k}\), where partitions are represented sequentially using their canonical sequential forms. This extends related results found in [12, 14] concerning the distribution on \(\mathcal{P}_{n,k}\) for the parameters tracking the number of indices \(i\in [n-1]\) such that \((w_i,w_{i+1})=(a,a+1)\) for some \(1 \leq a \leq k-1\) and/or the number of \(j \in [n]\) such that \((w_j,w_{j+1})=(k,1)\) (where \(w_{n+1}=w_1\)). See also Mansour’s text [11, Chapter 4] for further examples of statistics concerning the relative sizes of adjacent letters within members of \(\mathcal{P}_{n,k}\), represented sequentially.
The organization of this paper is as follows. In the next section, we review some basic properties of the Chebyshev polynomials of both kinds and establish closed form expressions involving sums of certain products, which we will need in establishing our main results. In the third section, we establish explicit formulas for \(F_k(x,t)\) and \(G_k(x,t)\) for each fixed \(k \geq 1\), where we make use of the transfer-matrix method (e.g., [20, Section 4.7]). Several particular cases are noted, which yield formulas for the generating functions that enumerate both linear and cyclic staircase words as well as linear and cyclic Hertzsprung words (i.e., those for which the value of \({s}\) or \({cs}\) is zero). In the final section, we compute the generating function for the \({s}\)-parameter distribution on \(\mathcal{P}_{n,k}\). By differentiation with respect to \(t\), we obtain an explicit formula for the sum of the \({s}\)-values of all the members of \(\mathcal{P}_{n,k}\), which may also be afforded a combinatorial explanation.
Let \(T_n(x)\) denote the \(n\)-th Chebyshev polynomial of the first kind defined recursively by \(T_n(x)=2xT_{n-1}(x)-T_{n-2}(x)\) for \(n \geq 2\), with initial conditions \(T_0(x)=1\) and \(T_1(x)=x\). Let \(U_n(x)\) denote the \(n\)-th Chebyshev polynomial of the second kind satisfying the same recurrence, but with initial conditions \(U_0(x)=1\) and \(U_1(x)=2x\). Both kinds of Chebyshev polynomials arise in a variety of pure and applied settings; see, e.g., [16] and references contained therein. The Chebyshev polynomials form the basis for the cosine and sine multi-angle formulas from trigonometry via the relations \(T_n(\cos\theta)=\cos(n\theta)\) and \(U_n(\cos\theta)=\frac{\sin((n+1)\theta)}{\sin\theta}\) for all \(n \geq0\). A basic formula relating the two kinds of Chebyshev polynomials is given by \(T_{n}(x)=(U_{n}(x)-U_{n-2}(x))/2\) (see [16, Exercise 1.2.1.5 (a)]).
In order to establish our main results below, we make use of the explicit formulas of several summations involving \(U_n(x)\), which are given in Table 1 below.
Lemma 2.1. We have
\[\begin{aligned} q_1(m,x) & =\frac{U_{m+1}(x)-U_{m}(x)-1}{2(x-1)}-1,\nonumber\\ q_2(m,x) & =\frac{U_{2m}(x)-2m-1}{4(x^{2}-1)}+U_{m}^{2}(x)-1,\nonumber\\ q_3(m,x) & =\frac{U_{m}(x)-(m+1)T_{m+2}(x)}{2(1-x^{2})}-U_{m}(x),\nonumber\\ q_4(m,x) & =\frac{U_{2m+1}(x)-2(m+1)x}{4(x^{2}-1)},\nonumber \end{aligned}\] \[\begin{aligned} q_5(m,x)&=\frac{U_{2m+3}(x)-U_{2m+1}(x)-4x(x+1)(U_{m+1}(x)-U_{m}(x))+2x(2x+1)}{8(x^2-1)(x-1)(2x+1)},\nonumber\\ q_6(m,x)&=\frac{U_{2m+3}(x)-U_{2m-1}(x)+U_{m-1}(x)-U_{m+3}(x)-2T_{2m}(x)-4T_{m+2}(x)+2U_{2}(x)}{8(x^2-1)(x-1)(2x+1)},\nonumber\\ q_7(m,x)&=\frac{2(m+2)x(2+T_{2m+4}(x))-(2+T_{2}(x))U_{2m+3}(x)}{16x(x^{2}-1)^{2}}-U_{m}^{2}(x),\nonumber\\ q_8(m,x)&=\frac{2x^2(m+1-U_{2m+2}(x))+(m+2)T_{2m+2}(x)}{8(x^{2}-1)^{2}}+\frac{T_{2}(x)U_{2m+3}(x)}{16x(x^{2}-1)^{2}}.\nonumber \end{aligned}\]
| \(q_1(m,x)\) | \(\displaystyle \sum_{i=1}^{m} U_{i}(x)\) |
|---|---|
| \(q_2(m,x)\) | \(\displaystyle \sum_{i=1}^{m} U_{i}^{2}(x)\) |
| \(q_3(m,x)\) | \(\displaystyle \sum_{i=1}^{m} U_{i}(x)\,U_{m-i}(x)\) |
| \(q_4(m,x)\) | \(\displaystyle \sum_{i=1}^{m} U_{i}(x)\,U_{i-1}(x)\) |
| \(q_5(m,x)\) | \(\displaystyle \sum_{i=1}^{m} U_{i}(x)\,U_{i-1}(x)\,U_{m-i}(x)\) |
| \(q_6(m,x)\) | \(\displaystyle \sum_{i=1}^{m} U_{i}(x)\,U_{m-i}^{2}(x)\) |
| \(q_7(m,x)\) | \(\displaystyle \sum_{i=1}^{m} U_{i}^{2}(x)\,U_{m-i}^{2}(x)\) |
| \(q_8(m,x)\) | \(\displaystyle \sum_{i=1}^{m} U_{i}(x)\,U_{i-1}(x)\,U_{m-i}(x)\,U_{m-i-1}(x)\) |
Proof. The formulas for \(q_1(m,x)\) and \(q_3(m,x)\) are already known and occur, for example, in [9] and [3], respectively. The others may be shown by a variety of algebraic methods, such as through use of the Binet formula or the generating function for Chebyshev polynomials. We provide here only a proof of \(q_2(m,x)\), where a quick trigonometric argument may be given as follows. By [6, Eq. 1.351.1], we have \[\sum_{i=1}^m\sin^{2}(ix) =\frac{2m+1}{4}-\frac{\sin((2m+1)x)}{4\sin x}.\] Dividing both sides by \(\sin^2(x)\), and using the fact \(U_i(\cos\theta)=\sin((i+1)\theta)/\sin\theta\), we have \[\sum_{i=1}^mU_{i-1}^2(\cos x)=\frac{2m+1-U_{2m}(\cos x)}{4\sin^{2}x}.\] Substituting \(x\mapsto\arccos x\), we obtain \[\sum_{i=1}^mU_{i-1}^2(x)=\frac{U_{2m}(x)-2m-1}{4(x^2-1)},\] from which the asserted formula follows immediately. ◻
Finally, let us introduce some notation. If \(\mathbf{v}\) is a vector, we denote by \(\mathbf{v}^T\) the transpose of \(\mathbf{v}\). We denote the all \(1\)’s vector of length \(k\) by \(\mathbf{1}=(1,\ldots,1)^T\) and the \(i\)-th component of a column or row vector \(\mathbf{v}\) by \((\mathbf{v})_i\). If \(p\) is a condition, then the indicator function \(\boldsymbol{1}_p\) is equal to \(1\) if \(p\) is true and \(0\) otherwise. If \(M\) is a matrix, we write \((M)_{i,j}\) for the \((i,j)\)-th entry of \(M\).
In the following theorem, we calculate \(F_k(x,t)\). A formula was already found in [7, Theorem 4], but only implicitly as a sum over the entries of the inverse of a certain matrix. We obtain here an elegant explicit formula for \(F_k(x,t)\) in terms of the Chebyshev polynomials.
Theorem 3.1. Let \(\phi = (1-x(t-1))/(2x(t-1))\). Then \[\label{t1e1} F_k(x,t) = \frac{1}{1-x\gamma_k(x,t)}, \qquad k \geq 1, \tag{1}\] where \[\gamma_k(x,t) = \frac{k}{1-3x(t-1)}-\frac{2x(t-1)}{(1-3x(t-1))^{2}}\frac{U_{k}(\phi)-U_{k-1}(\phi)-1}{U_{k}(\phi)}.\]
Proof. The result is seen to hold in the case \(k=1\) since \(F_k(x,t)=\frac{1-x(t-1)}{1-xt}\), so we may assume \(k \geq 2\). Let \(B(t)\) be the square matrix of size \(k\) defined by \[(B(t))_{i,j}=\begin{cases} t, & {if } |i-j|\ \leq 1,\\ 1, & {if } |i-j|\ > 1. \end{cases}\] A word \(w=w_{1}\cdots w_{n}\in[k]^{n}\) has weight \[t^{{s}(w)}=\prod_{i=1}^{n-1}(B(t))_{w_i,w_{i+1}}.\] Thus, the coefficient of \(x^n\) is given by \[\sum_{w_1\cdots w_n\in[k]^n}\prod_{i=1}^{n-1}(B(t))_{w_i,w_{i+1}}=\mathbf 1^T(B(t))^{n-1}\mathbf 1.\] It follows that \[\begin{aligned} F_k(x,t)&=1+\sum_{n\geq1}x^{n}\mathbf{1}^{T}(B(t))^{n-1}\mathbf{1}\nonumber\\ &=1+x\mathbf{1}^{T}\left(\sum_{n\geq0}(xB(t))^{n}\right)\mathbf{1}\nonumber\\ &=1+x\mathbf 1^T(I-xB(t))^{-1}\mathbf 1.\nonumber \end{aligned}\] Note that \(I-xB(t)=C(x(t-1))+(-x)\mathbf{1}\mathbf{1}^T\), where \(C(x)\) is the square matrix of size \(k\) given by \[(C(x))_{i,j}=\begin{cases} 1-x, & \text{if }|i-j|\ =0,\\ -x, & \text{if }|i-j|\ =1,\\ 0, & \text{if }|i-j|\ \geq 2. \end{cases}\]
The matrix \(C(x)\) was analyzed by Knopfmacher et al. [9], who, using results from [21], showed that its inverse is given explicitly by \[\left(C(x)^{-1}\right)_{i,j}=\frac{1}{xU_{k}\left(\frac{1-x}{2x}\right)}\begin{cases} U_{i-1}\left(\frac{1-x}{2x}\right)U_{k-j}\left(\frac{1-x}{2x}\right), & {if } i\leq j,\\ U_{j-1}\left(\frac{1-x}{2x}\right)U_{k-i}\left(\frac{1-x}{2x}\right), & {otherwise}. \end{cases}\] By the Sherman–Morrison formula (e.g., [1]), we have \[\label{e3} (I-xB(t))^{-1} = C(x(t-1))^{-1} + \frac{xC(x(t-1))^{-1}\mathbf{1}\mathbf{1}^TC(x(t-1))^{-1}}{1-x\mathbf{1}^TC(x(t-1))^{-1}\mathbf{1}}. \tag{2}\] We claim \[\label{e4} \mathbf{1}^{T}C(x(t-1))^{-1}\mathbf{1}=\gamma_k(x,t). \tag{3}\] Indeed, \[\begin{aligned} &\mathbf{1}^{T}C(x(t-1))^{-1}\mathbf{1}\nonumber\\ &=\sum_{i=1}^{k}\sum_{j=1}^{k}(C(x(t-1))^{-1})_{i,j}\nonumber\\ &=\frac{1}{x(t-1)U_{k}(\phi)}\left(\sum_{i=1}^{k}U_{i-1}(\phi)\sum_{j=i}^{k}U_{k-j}(\phi)+\sum_{i=2}^{k}U_{k-i}(\phi)\sum_{j=1}^{i-1}U_{j-1}(\phi)\right)\nonumber\\ &=\frac{1}{x(t-1)U_{k}(\phi)}\left(\sum_{i=1}^{k}U_{i-1}(\phi)(q_{1}(k-i,\phi)+1)+\sum_{i=2}^{k}U_{k-i}(\phi)(q_{1}(i-2,\phi)+1)\right)\nonumber\\ &=\frac{1}{2x(t-1)(\phi-1)U_{k}(\phi)}\Bigg(\sum_{i=1}^{k}\left(U_{i-1}(\phi)U_{k-i+1}(\phi)-U_{i-1}(\phi)U_{k-i}(\phi)-U_{i-1}(\phi)\right)\nonumber\\&\hspace{128pt}+\sum_{i=2}^{k}\left(U_{k-i}(\phi)U_{i-1}(\phi)-U_{k-i}(\phi)U_{i-2}(\phi)-U_{k-i}(\phi)\right)\Bigg)\nonumber\\ &=\frac{q_3(k,\phi)-q_3(k-2,\phi)-q_{1}(k-1,\phi)-q_{1}(k-2,\phi)-U_{k-1}(\phi)-U_{k-2}(\phi)-2}{2x(t-1)(\phi-1)U_{k}(\phi)}\nonumber\\ &=\frac{1}{4x(t-1)(\phi-1)^{2}(\phi+1)U_{k}(\phi)}\Bigg((k+1)\phi U_{k+1}(\phi)-(2\phi^{2}+\phi+1+k)U_{k}(\phi)\nonumber\\&\qquad+(2-2\phi^{2}-(k-1)\phi)U_{k-1}(\phi)+(\phi+1+k)U_{k-2}(\phi)+2\phi+2\Bigg).\nonumber \end{aligned}\] Replacing \(U_{k-2}(\phi)\) with \(2\phi U_{k-1}(\phi)-U_{k}(\phi)\) and \(U_{k+1}(\phi)\) with \(2\phi U_{k}(\phi)-U_{k-1}(\phi)\), the asserted claim follows after some algebra.
Set \[\alpha_{i}(x)=\frac{U_{k-i}(x)(U_i(x)-1)-U_{i-1}(x)\left(U_{k-i-1}(x)+1\right)}{U_k(x)}.\] We claim \[\label{e5}\left(C(x(t-1))^{-1}\boldsymbol{1}\boldsymbol{1}^TC(x(t-1))^{-1}\right)_{i,j}=\frac{\alpha_i(\phi)\alpha_j(\phi)}{(1-3x(t-1))^{2}}. \tag{4}\]Indeed, \[\begin{aligned} (C(x(t-1))^{-1}\boldsymbol{1})_{i}&=\sum_{s=1}^{k}\left(C(x(t-1))^{-1}\right)_{i,s}\nonumber\\ &=\frac{1}{x(t-1)U_{k}(\phi)}\left(U_{k-i}(\phi)\sum_{s=1}^{i-1}U_{s-1}(\phi)+U_{i-1}(\phi)\sum_{s=i}^{k}U_{k-s}(\phi)\right)\nonumber\\ &=\frac{U_{k-i}(\phi)(q_{1}(i-2,\phi)+1)+U_{i-1}(\phi)(q_{1}(k-i,\phi)+1)}{x(t-1)U_{k}(\phi)}\nonumber\\ &=\frac{U_{i-1}(\phi)(U_{k-i+1}(\phi)-1)-U_{k-i}(\phi)(U_{i-2}(\phi)+1)}{2(\phi-1)x(t-1)U_{k}(\phi)}.\nonumber \end{aligned}\] Upon replacing \(U_{k-i+1}(\phi)\) by \(2\phi U_{k-i}(\phi)-U_{k-i-1}(\phi)\) and \(U_{i-2}(\phi)\) by \(2\phi U_{i-1}(\phi)-U_{i}(\phi)\), we get \[\label{k0} (C(x(t-1))^{-1}\boldsymbol{1})_{i}=\frac{\alpha_i(\phi)}{1-3x(t-1)}. \tag{5}\] Similarly, \[\left(\boldsymbol{1}^TC(x(t-1))^{-1}\right)_j=\frac{\alpha_j(\phi)}{1-3x(t-1)}.\] Since \[\left(C(x(t-1))^{-1}\boldsymbol{1}\boldsymbol{1}^TC(x(t-1))^{-1}\right)_{i,j}=(C(x(t-1))^{-1}\boldsymbol{1})_{i}\left(\boldsymbol{1}^TC(x(t-1))^{-1}\right)_j,\] the assertion follows.
Finally, we claim \[\sum_{i=1}^k \alpha_i(x)=k-\frac{U_{k}(x)-U_{k-1}(x)-1}{(x-1)U_{k}(x)}.\] Indeed, \[\begin{aligned} \sum_{i=1}^{k}\alpha_{i}(x) &=\frac{1}{U_{k}(x)}\sum_{i=1}^{k}(U_{k-i}(x)(U_{i}(x)-1)-U_{i-1}(x)(U_{k-i-1}(x)+1))\nonumber\\ &=\frac{q_{3}(k,x)-q_3(k-2,x)-2q_{1}(k-1,x)-U_{k-2}(x)-2}{U_{k}(x)}\nonumber\\ &=\frac{(k+1)T_{k+2}(x)-(k-1)T_{k}(x)-(2x^2+2x+1)U_k(x)+2(x+1)U_{k-1}(x)}{2(x^2-1)U_k(x)}\nonumber\\ &\quad+\frac{U_{k-2}(x)+2x+2}{2(x^2-1)U_k(x)}\nonumber\\ &=\frac{(kT_{2}(x)-2x-2)U_{k}(x)+2(1-(k-1)x)U_{k-1}(x)+kU_{k-2}(x)+2x+2}{2(x^{2}-1)U_{k}(x)},\nonumber \end{aligned}\] where we have used Lemma 2.1 and then the fact \(T_m(x)=(U_m(x)-U_{m-2}(x))/2\) to simplify the resulting expression. Replacing \(U_{k-2}(x)\) with \(2xU_{k-1}(x)-U_k(x)\) and \(T_2(x)\) with \(2x^2-1\) in the last equality, the assertion follows.
Putting everything together, we have \[\begin{aligned} F_k(x,t)&=1+x\mathbf{1}^T(I-xB(t))^{-1}\mathbf{1}\nonumber\\ &=1+x\mathbf{1}^TC(x(t-1))^{-1}\mathbf{1} + \frac{x^2\sum_{i,j=1}^k(C(x(t-1))^{-1}\boldsymbol{1}\boldsymbol{1}^TC(x(t-1))^{-1})_{i,j}}{1-x\mathbf{1}^TC(x(t-1))^{-1}\mathbf{1}} \nonumber\\ &=1+x\mathbf{1}^TC(x(t-1))^{-1}\mathbf{1} + \frac{x^2}{(1-3x(t-1))^{2}}\frac{\sum_{i,j=1}^k\alpha_i(\phi)\alpha_j(\phi)}{1-x\mathbf{1}^TC(x(t-1))^{-1}\mathbf{1}} \nonumber\\ &=1+x\gamma_k(x,t)+\frac{x^{2}(\gamma_k(x,t))^{2}}{1-x\gamma_k(x,t)}\nonumber\\ &=\frac{1}{1-x\gamma_k(x,t)}.\nonumber \end{aligned}\] ◻
Note \(U_m(z)\) is a polynomial in \(z\) of degree \(m\) for all \(m\geq0\), which implies \[\lim_{t\rightarrow 1}\left(\frac{U_k(\phi)-U_{k-1}(\phi)-1}{U_k(\phi)}\right)=1,\] and hence \(F_k(x,1)=\lim_{t\rightarrow1}F_k(x,t)=\frac{1}{1-kx}\), as expected, by (1). Differentiation of \(F_k(x,t)\) with respect to \(t\) then yields the following result.
Corollary 3.2. The sum of the \({s}\)-values of all the members of \([k]^n\) for \(n,k \geq1\) is given by \((n-1)(3k-2)k^{n-2}\).
Proof. Since \(F_k(x,1)=\frac{1}{1-kx}\), we have \[\frac{\partial}{\partial t}F_k(x,t)\big|_{t=1} =\frac{x\frac{\partial}{\partial t}\gamma_k(x,t)\big|_{t=1}}{(1-kx)^2},\] with \[\frac{\partial}{\partial t}\gamma_k(x,t)\big|_{t=1} =\lim_{t\rightarrow1}\frac{\partial}{\partial t}\gamma_k(x,t)=3kx-2x\lim_{t\rightarrow 1}\left(\frac{U_k(\phi)-U_{k-1}(\phi)-1}{U_k(\phi)}\right)=(3k-2)x.\]Hence, \[[x^n]\frac{\partial}{\partial t}F_k(x,t)\big|_{t=1} =[x^n]\left(\frac{(3k-2)x^2}{(1-kx)^2}\right)=(n-1)(3k-2)k^{n-2},\] which yields the stated formula.
This result may also be realized combinatorially as follows. Let \(\mathcal{A}\) denote the set of marked members \(w=w_1\cdots w_n \in [k]^n\) wherein some index \(i \in [n-1]\) such that \(|w_{i+1}-w_i|\ \leq 1\) is distinguished from the others. Then the sum of the \({s}\)-values of all the members of \([k]^n\) is given by \(|\mathcal{A}|\). To find \(|\mathcal{A}|\), note first that there are \(n-1\) choices for the marked index, say \(j \in [n-1]\), and \(k^{n-2}\) choices for the letters \(w_i\) such that \(i \in [n]-\{j,j+1\}\). There are then \(k\) choices for \(a=w_j\), and for each \(a\), three choices for \(w_{j+1}\), namely, \(a\) or \(a \pm1\), provided \(a \in [2,k-1]\). If \(a=1\) or \(k\), then there are only two choices for \(w_{j+1}\) in both cases, since \(w_{j+1}=0\) or \(w_{j+1}=k+1\) is not allowed. Thus, there are \(3k-2\) possibilities for \(w_j,w_{j+1}\), independent of the other letters and the choice of \(j\), whence \(|\mathcal{A}|\ =(n-1)(3k-2)k^{n-2}\), as desired. ◻
As a special case of Theorem 3.1, we obtain [9, Theorem 2.2].
Corollary 3.3. Let \(A_k(x)\) be the generating function for the number of staircase words over \([k]\). Then \[A_k(x) = 1+\frac{x(k-(3k+2)x)}{(1-3x)^{2}}+\frac{2x^{2}}{(1-3x)^{2}}\frac{U_{k-1}\left(\frac{1-x}{2x}\right)+1}{U_k\left(\frac{1-x}{2x}\right)}.\]
Proof. Let \(a_{n,m}\) denote the number of words \(w\in[k]^n\) such that \({s}(w)=m\). Thus, \[A_k(x)= 1+\sum_{n\geq 1}a_{n,n-1}x^n.\] By the definitions, we have \[F_k(x,t)-1=\sum_{n\geq 1}\sum_{m=0}^{n-1}a_{n,m}x^nt^m,\] and hence \[\frac{F_k\left(tx,\frac{1}{t}\right)-1}{t}=\sum_{n\geq1}\sum_{m=0}^{n-1}a_{n,m}x^nt^{n-1-m}.\] Therefore, \[\begin{aligned} A_k(x)&=1+\frac{F_k\left(tx,\frac{1}{t}\right)-1}{t}\Bigg|_{t=0}\nonumber\\&=1+\frac{x(k-(3k+2)x)}{(1-3x)^{2}}+\frac{2x^{2}}{(1-3x)^{2}}\frac{U_{k-1}\left(\frac{1-x}{2x}\right)+1}{U_{k}\left(\frac{1-x}{2x}\right)}.\nonumber \end{aligned}\] ◻
Recall that Hertzsprung’s problem asks for the number of ways to arrange \(n\) non-attacking kings on an \(n\times n\) board such that each row and each column contains exactly one king (see A002464 in [18]). This problem is clearly equivalent to the one of finding the number of permutations of \([n]\) such that consecutive entries differ by at least \(2\). We propose the name Hertzsprung for the analogous problem on words.
Definition 3.4. A word \(w\) over \([k]\) is said to be Hertzsprung if \({s}(w)=0\). We say that \(w\) is cyclic Hertzsprung if \({cs}(w)=0\).
Corollary 3.5. The generating function for the number of Hertzsprung words over \([k]\) is given by \[\left(1-\frac{kx}{1+3x}-\frac{2x^{2}}{(1+3x)^{2}}\frac{U_{k}\left(-\frac{1+x}{2x}\right)-U_{k-1}\left(-\frac{1+x}{2x}\right)-1}{U_{k}\left(-\frac{1+x}{2x}\right)}\right)^{-1}.\]
Proof. The assertion follows immediately from evaluating \(F_k(x,0)\). ◻
The first few cases of Corollary 3.5 are given in Table 2 below.
| \(k\) | Generating function |
|---|---|
| \(2\) | \(1+2x\) |
| \(3\) | \(\frac{1+2x-x^2}{1-x}\) |
| \(4\) | \(\frac{1+3x+x^2}{1-x-x^2}\) |
| \(5\) | \(\frac{1+3x-2x^3}{1-2x-2x^2+2x^3}\) |
It is possible to explain the generating functions given in Table 2 directly by considering the recurrences satisfied by the underlying sequences (in the \(k=4\) and \(k=5\) cases), an exercise we will leave for the reader to explore.
For the next result, we calculate \(G_k(x,t)\). To the best of our knowledge, the generating function \(G_k(x,t)\) has not been previously studied, except in the special case corresponding to cyclic staircase words by Knopfmacher et al. [9, Theorem 3.2].
Theorem 3.6. If \(k \geq 1\), then \[\begin{aligned} &G_k(x,t)=1+\frac{1+3x(t-1)}{(1-3x(t-1))(1+x(t-1))}\Bigg[\frac{1}{1-x\gamma_k(x,t)}+kx(t-1)-1\nonumber\\&-\frac{2x(t-1)(k+1)}{(1+3x(t-1))U_{k}\left(\frac{1-x(t-1)}{2x(t-1)}\right)}\left(\frac{1-x\frac{1+k-U_{k}\left(\frac{1-x(t-1)}{2x(t-1)}\right)}{1-3x(t-1)}}{1-x\gamma_k(x,t)}+U_{k-1}\left(\frac{1-x(t-1)}{2x(t-1)}\right)-1\right)\Bigg],\nonumber \end{aligned}\] where \(\gamma_k(x,t)\) is as before.
Proof. The formula is seen to reduce when \(k=1\) to \(G_1(x,t)=\frac{1}{1-xt}\), as required, so we may assume \(k \geq 2\). A word \(w=w_{1}\cdots w_{n}\in[k]^{n}\) contributes the weight \[t^{{cs}(w)}=(B(t))_{w_n,w_{1}}\prod_{i=1}^{n-1}(B(t))_{w_i,w_{i+1}},\] towards \(x^n\). Thus, the coefficient of \(x^n\) is given by \[\sum_{w_1\cdots w_n\in[k]^n}(B(t))_{w_n,w_{1}}\prod_{i=1}^{n-1}(B(t))_{w_i,w_{i+1}}=\operatorname{tr}((B(t))^n),\] where \(\operatorname{tr}\) denotes the trace, which implies \[\label{eq:G-def} G_{k}(x,t)= 1+\operatorname{tr}(xB(t)(I-xB(t))^{-1}). \tag{6}\]
Let us write \(B=B(t)\) and \(C=C(x(t-1))\). Note \(B=\mathbf1\mathbf1^T+(t-1) D\), where \(D\) is the square matrix of size \(k\) given by \[(D)_{i,j}=\begin{cases} 1, & \text{if }|i-j|\ \leq 1,\\ 0, & \text{otherwise}. \end{cases}\] By (2), the linearity of trace and the fact \({tr}(PQ)={tr}(QP)\) for all matrices \(P\) and \(Q\) such that both products are defined, we get \[\begin{aligned} {tr}(xB(I-xB)^{-1}) &=x{tr}(BC^{-1})+\frac{x^2{tr}(BC^{-1}\mathbf{1}\mathbf{1}^TC^{-1})}{1-x\mathbf{1}^TC^{-1}\mathbf{1}}\nonumber\\ &=x\mathbf1^TC^{-1}\mathbf1+x(t-1){tr}(DC^{-1})+\frac{x^2\mathbf{1}^TC^{-1}BC^{-1}\mathbf{1}}{1-x\mathbf{1}^TC^{-1}\mathbf{1}}.\nonumber \end{aligned}\] By (3), \(\mathbf1^TC^{-1}\mathbf1=\gamma_k(x,t)\). Further, we have \[\begin{aligned} {tr}(DC^{-1})&=\frac{1}{x(t-1)U_k}\left(\sum_{i=1}^{k}(C^{-1})_{i,i}+2\sum_{i=1}^{k-1}(C^{-1})_{i,i+1}\right)\nonumber\\ &=\frac{2q_{3}(k-2,\phi)+q_{3}(k-1,\phi)+2U_{k-2}+U_{k-1}}{x(t-1)U_k}\nonumber\\ &=\frac{(1+3x(t-1))kU_{k}-2(k+1)U_{k-1}}{(1+x(t-1))(1-3x(t-1))U_{k}},\nonumber \end{aligned}\] where \(U_k=U_k(\phi)\) throughout this proof.
Now consider \(\mathbf{1}^TC^{-1}BC^{-1}\mathbf{1}\). We have \[\begin{aligned} \mathbf{1}^TC^{-1}BC^{-1}\mathbf{1}&=\mathbf{1}^TC^{-1}(\mathbf1\mathbf1^T+(t-1) D)C^{-1}\mathbf{1}\nonumber\\&=(\gamma_{k}(x,t))^{2}+(t-1)\left(\sum_{i=1}^{k}(C^{-1}\mathbf{1})_{i}^{2}+2\sum_{i=1}^{k-1}(C^{-1}\mathbf{1})_{i}(C^{-1}\mathbf{1})_{i+1}\right).\nonumber \end{aligned}\] By (5), \[\begin{aligned} (C^{-1}\mathbf1)_i&=\frac{\alpha_i(\phi)}{1-3x(t-1)}=\frac{U_{k-i}(U_i-1)-U_{i-1}(U_{k-i-1}+1)}{(1-3x(t-1))U_k}.\nonumber \end{aligned}\] Thus, \[\begin{aligned} \sum_{i=1}^k(C^{-1}\mathbf{1})_{i}^{2} &=\frac{1}{(1-3x(t-1))^2U_k^2}\sum_{i=1}^k\big(U_i^2U_{k-i}^2-2U_iU_{k-i}^2+U_{k-i}^2-2U_iU_{i-1}U_{k-i}U_{k-i-1}\\ &\quad-2U_{i}U_{i-1}U_{k-i}+2U_{i-1}U_{k-i}U_{k-i-1}+2U_{i-1}U_{k-i}+U_{i-1}^2U_{k-i-1}^2+2U_{i-1}^2U_{k-i-1}\\ &\quad+U_{i-1}^2\big) \end{aligned}\] and \[\begin{aligned} &\sum_{i=1}^{k-1}(C^{-1}\mathbf{1})_{i}(C^{-1}\mathbf{1})_{i+1}\\ &=\frac{1}{(1-3x(t-1))^2U_k^2}\sum_{i=1}^{k-1}\big(U_iU_{i+1}U_{k-i}U_{k-i-1}-U_iU_{k-i}U_{k-i-1}-U_i^2U_{k-i}U_{k-i-2}\\ &\quad-U_i^2U_{k-i}-U_{i+1}U_{k-i}U_{k-i-1}+U_{k-i}U_{k-i-1}+U_iU_{k-i}U_{k-i-2}+U_iU_{k-i}-U_{i-1}U_{i+1}U_{k-i-1}^2\\ &\quad+U_{i-1}U_{k-i-1}^2+U_iU_{i-1}U_{k-i-1}U_{k-i-2}+U_iU_{i-1}U_{k-i-1}-U_{i-1}U_{i+1}U_{k-i-1}+U_{i-1}U_{k-i-1}\\ &\quad+U_iU_{i-1}U_{k-i-2}+U_iU_{i-1}\big). \end{aligned}\]
Note that the upper index of summation in the last sum may run up to \(i=k\) without changing the value of the sum, as \(U_{-1}=0\) and \(U_{-2}=-1\). Thus, combining the various terms from the last two sums, and making use of the recurrence for \(U_n\) several times, we get \[\begin{aligned} &\sum_{i=1}^{k}(C^{-1}\mathbf{1})_{i}^{2}+2\sum_{i=1}^{k-1}(C^{-1}\mathbf{1})_{i}(C^{-1}\mathbf{1})_{i+1}\\ &=\frac{1}{(1-3x(t-1))^2U_k^2}\bigg(\sum_{i=1}^k\big(2U_{i-1}^2+2U_{i-1}U_{k-i}+4U_iU_{i-1}+2U_{i-1}U_{k-i-1}+2U_iU_{k-i}\\ &\quad-4U_{i}U_{i-1}U_{k-i}+4U_iU_{i-1}U_{k-i-1}-2U_iU_{i-1}U_{k-i+1}+2U_iU_{k-i}U_{k-i-2}+2U_iU_{i-1}U_{k-i-2}\\ &\quad-2U_{i-1}U_{i+1}U_{k-i-1}-4U_i^2U_{k-i}+4U_{i-1}U_{k-i-1}^2+U_i^2U_{k-i}^2+U_{i-1}^2U_{k-i-1}^2\\ &\quad-2U_iU_{i-1}U_{k-i}U_{k-i-1}+2U_{i}U_{i-1}U_{k-i}U_{k-i+1}+2U_iU_{i-1}U_{k-i-1}U_{k-i-2}-2U_i^2U_{k-i}U_{k-i-2}\\ &\quad-2U_{i-1}U_{i+1}U_{k-i-1}^2\big)-2U_k+2U_k^2\bigg)\\ &=\frac{1}{(1-3x(t-1))^2U_k^2}\bigg(\sum_{i=1}^k\big(2U_{i-1}^2+2U_{i-1}U_{k-i-1}+2U_{i-1}U_{k-i}+2U_iU_{k-i}+4U_iU_{i-1}\\ &\quad+2U_iU_{i-1}U_{k-i-1}+4U_{i-1}U_{k-i}U_{k-i-1}-4U_iU_{i-1}U_{k-i}-2U_iU_{k-i}U_{k-i-1}+4U_{i-1}^2U_{k-i-1}\\ &\quad+2U_{i-1}U_{k-i-1}^2-4U_iU_{k-i}^2-2U_i^2U_{k-i}+3U_{i-1}^2U_{k-i-1}^2+3U_i^2U_{k-i}^2-6U_iU_{i-1}U_{k-i}U_{k-i-1}\big)\\ &\quad-2U_kU_{k-1}\bigg)\\ &=\frac{1}{(1-3x(t-1))^2U_k^2}\big(2q_{2}(k-1,\phi) +2q_{3}(k-2,\phi) +2q_{3}(k-1,\phi) +2q_{3}(k,\phi)\\ &\quad+4q_{4}(k,\phi)+6\,q_{5}(k-1,\phi) -6q_{5}(k,\phi) +6q_{6}(k-2,\phi) -6q_{6}(k,\phi) +3q_{7}(k-2,\phi)\\ &\quad+3q_{7}(k,\phi)-6q_{8}(k,\phi) +2 +2U_{k-2} +2U_{k-1} +2U_{k} +9U_{k-2}^{2} -2U_{k}^{2}\big)\\ &=\frac{1}{(1-3x(t-1))^2U_k^2}\bigg(-2U_{k}U_{k-1}-\frac{U_{k}U_{k-1}}{x(t-1)+1}-\frac{3U_{k}U_{k-1}}{3x(t-1)-1}\\ &\quad-\left(\frac{k+1}{3x(t-1)-1}+\frac{k+1}{x(t-1)+1}\right)(U_{k}-U_{k-1}-1)\\ &\quad-\left(\frac{3}{3x(t-1)-1}-\frac{11}{x(t-1)+1}+2\right)U_{k}\\ &\quad+\left(3k+2+\frac{3}{3x(t-1)-1}-\frac{1}{x(t-1)+1}\right)U_{k}^{2}\bigg), \end{aligned}\] where the last equality follows after the application of Lemma 2.1 and several algebraic steps.
Putting everything together in (6), we conclude \[\begin{aligned} G_k(x,t)&=1+\frac{x\gamma_{k}(x,t)}{1-x\gamma_{k}(x,t)}+\frac{x(t-1)}{(1-3x(t-1))U_{k}}\bigg(3kU_{k}-2\frac{kU_{k}+(k+1)U_{k-1}}{x(t-1)+1}\\ &\quad+\frac{x}{(1-3x(t-1))(1-x\gamma_{k}(x,t))}\bigg(\frac{10-2U_{k-1}}{x(t-1)+1}+3kU_{k}\\ &\quad+\bigg(2U_{k}+\frac{3U_{k}-k-1}{3x(t-1)-1}-\frac{U_{k}+k+1}{x(t-1)+1}\bigg)\frac{U_{k}-U_{k-1}-1}{U_{k}}\bigg)\bigg), \end{aligned}\] from which the asserted formula for \(G_k(x,t)\) follows after some algebra. ◻
We note the following special cases of Theorem 3.6. First, one can show \(G_k(x,1)=\lim_{t\rightarrow1}G_k(x,t)=\frac{1}{1-kx}\), as expected, proceeding as before. Differentiation with respect to \(t\) or direct reasoning then leads to the following result.
Corollary 3.7. If \(n \geq 2\) and \(k\geq 1\), then the sum of the \({cs}\)-values of all the members of \([k]^n\) is given by \(n(3k-2)k^{n-2}\).
Computing \(\lim_{t\rightarrow0}G_k\left(tx,\frac{1}{t}\right)\) in Theorem 3.6 recovers [9, Theorem 3.2].
Corollary 3.8. The generating function for the number of cyclic staircase words over \([k]\) is given by \[1+\frac{kx(1+3x)}{(1+x)(1-3x)}-\frac{2(k+1)x}{(1+x)(1-3x)}\frac{U_{k-1}\left(\frac{1-x}{2x}\right)}{U_k\left(\frac{1-x}{2x}\right)}.\]
Computing \(G_k(x,0)\) yields the following formula for cyclic Hertzsprung words.
Corollary 3.9. The generating function for the number of cyclic Hertzsprung words over \([k]\) is given by \[\begin{aligned} &1+\frac{1-3x}{(1-x)(1+3x)}\Bigg[\frac{x\gamma_k(x,0)}{1-x\gamma_k(x,0)}-kx\nonumber\\&+\frac{2x(k+1)}{(1-3x)U_{k}\left(-\frac{1+x}{2x}\right)}\left(\frac{1-x\frac{1+k-U_{k}\left(-\frac{1+x}{2x}\right)}{1+3x}}{1-x\gamma_k(x,0)}+U_{k-1}\left(-\frac{1+x}{2x}\right)-1\right)\Bigg].\nonumber \end{aligned}\]
The first few cases of Corollary 3.9 are given in Table 3 below.
| \(k\) | Generating function |
|---|---|
| \(2\) | \(1\) |
| \(3\) | \(\frac{1+x^{2}}{1-x^{2}}\) |
| \(4\) | \(\frac{1+3x^2-3x^4}{1-3x^2+x^4}\) |
| \(5\) | \(\frac{1+6x^2+4x^3-12x^4}{1-6x^2-2x^3+4x^4}\) |
Let \(\mathcal{P}_{n,k}\) denote the set of partitions of \([n]\) with \(k\) blocks. Let \(\Pi=B_1/B_2/\cdots/B_k \in \mathcal{P}_{n,k}\), where the blocks \(B_i\) are arranged from left to right in ascending order of their smallest elements. Recall that \(\Pi\) may be represented sequentially as \(\pi=\pi_1\cdots\pi_n\) wherein \(i \in B_{\pi_i}\) for all \(i\in[n]\); see, e.g., [15, 22]. The sequence \(\pi\) satisfies what is known as the restricted growth condition, meaning \(\pi_{i+1}\leq \max(\pi_1\cdots\pi_i)+1\) for \(1 \leq i \leq n-1\). Recall that the cardinality of \(\mathcal{P}_{n,k}\) is given by the Stirling number of the second kind, which we will denote by \(S(n,k)\).
Define \({s}(\Pi)\) for a partition \(\Pi\) to be the \({s}\)-value of its corresponding restricted growth sequence. In this section, we determine an explicit formula for the generating function of the distribution of the \({s}\)-statistic on \(\mathcal{P}_{n,k}\) for all \(n \geq k\), where \(k \geq 2\) is fixed. That is, we find \[P_k(x,t)=\sum_{n\geq k}\left(\sum_{\pi \in \mathcal{P}_{n,k}}t^{{s}(\pi)}\right)x^n, \qquad k \geq 2.\]
In order to do so, first note that \(\pi=\pi_1\cdots\pi_n \in \mathcal{P}_{n,k}\) implies it may be represented as \(\pi=\pi^{(1)}\cdots \pi^{(k)}\), where \(\pi^{(i)}\) for each \(i\) is a nonempty \(i\)-ary word starting with \(i\). We thus need to ascertain the contribution towards \(P_k(x,t)\) coming from each section \(\pi^{(i)}\). Given \(i \geq 2\), let \(\ell_i(x,t)\) denote the generating function enumerating all \(i\)-ary words \(w\) (including the empty word) according to the value of \({s}(iw(i+1))\). Given \(1 \leq i \leq k\), let \(F_k^{(i)}(x,t)\) denote the restriction of \(F_k(x,t)\) to \(k\)-ary words whose first letter is \(i\). Considering the contribution \(\frac{tx}{1-tx}\) coming from the initial section \(\pi^{(1)}\), we have \[\label{pare1} P_k(x,t)=\frac{tx^{k-1}F_k^{(k)}(x,t)}{1-tx}\prod_{i=2}^{k-1}\ell_i(x,t), \qquad k \geq 2. \tag{7}\]
Using (7), one may obtain the following explicit formula for \(P_k(x,t)\).
Theorem 4.1. If \(k \geq 2\), then \[\label{parth1e1} P_k(x,t)=\frac{tx^k\lambda_kF_k(x,t)}{1-tx}\prod_{i=2}^{k-1}\left(\lambda_i(1+x(t-1)\lambda_i)F_i(x,t)+(t-1)\frac{(2\phi+1)U_{i-1}(\phi)}{U_i(\phi)}\right), \tag{8}\] where \(F_k(x,t)\) and \(\phi\) are as in Theorem 3.1 and \(\lambda_i=\frac{U_i(\phi)-U_{i-1}(\phi)-1}{(1-3x(t-1))U_i(\phi)}\) for \(2 \leq i \leq k\).
Proof. We first determine a formula for \(F_k^{(k)}(x,t)\). Upon considering the first letter within a word enumerated by \(F_{k}^{(i)}(x,t)\), we obtain the system \[F_k^{(i)}(x,t)=x+x\sum_{j=1}^kt^{\boldsymbol{1}_{|i-j| \leq1}}F_k^{(j)}(x,t), \qquad 1 \leq i \leq k,\] which may be rewritten in matrix form as \(\mathbf{F}=x((I-xB(t))^{-1}\mathbf{1}\), where \[\mathbf{F}=(F_k^{(1)}(x,t),\ldots,F_k^{(k)}(x,t))^T.\]
We then seek a formula for \((\mathbf{F})_k\), and, by (2), thus need expressions for \((C^{-1}\boldsymbol{1})_k\) and \((C^{-1}\mathbf{11}^TC^{-1}\boldsymbol{1})_k\), where \(C=C(x(t-1))\). By (5) with \(i=k\), we have \[(C^{-1}\boldsymbol{1})_k=\frac{\alpha_k(\phi)}{1-3x(t-1)}=\lambda_k,\] where \(\alpha_i\) for \(1 \leq i \leq k\) is as in the proof of Theorem 3.1. Further, by (4), we have \[(C^{-1}\boldsymbol{1}\boldsymbol{1}^TC^{-1}\boldsymbol{1})_k=\sum_{j=1}^k(C^{-1}\boldsymbol{1}\boldsymbol{1}^TC^{-1})_{k,j}=\frac{(C^{-1}\boldsymbol{1})_k}{1-3x(t-1)}\sum_{j=1}^k\alpha_j(\phi)=\lambda_k\gamma_k(x,t),\] by the fact \(\sum_{j=1}^k\alpha_j(\phi)=(1-3x(t-1))\gamma_k(x,t)\). Thus, by (2) and (3), we get \[\begin{aligned} F_k^{(k)}(x,t)&=(\mathbf{F})_k=x(C^{-1}\boldsymbol{1})_k+\frac{x^2(C^{-1}\boldsymbol{1}\boldsymbol{1}^TC^{-1}\boldsymbol{1})_k}{1-x\gamma_k(x,t)}=x\lambda_k\left(1+\frac{x\gamma_k(x,t)}{1-x\gamma_k(x,t)}\right)\\ &=x\lambda_kF_k(x,t), \end{aligned}\] where we have made use of (1) in the last equality.
This accounts for the factor of \(x\lambda_kF_k(x,t)\) in (8), so to complete the proof, it suffices to show \[\label{parthe2} \ell_i(x,t)=\lambda_i(1+x(t-1)\lambda_i)F_i(x,t)+(t-1)\frac{(2\phi+1)U_{i-1}(\phi)}{U_i(\phi)}, \qquad 2 \leq i \leq k-1. \tag{9}\] To do so, we consider some further generating functions as follows. Given \(k\geq2\), let \(H_k(x,t)=\frac{F_k^{(k)}(x,t)}{x}\), which is seen to enumerate \(k\)-ary words \(w\) of length \(n\) for all \(n \geq0\) according to the value of \({s}(kw)\). Let \(H_k^{(i)}(x,t)\) for \(1 \leq i \leq k\) denote the restriction of \(H_k\) to those \(w\) ending in the letter \(i\). We will denote \(H_k^{(i)}(x,t)\) for \(1 \leq i \leq k\) and \(H_k(x,t)\) by \(h_i\) and \(H\), respectively. Note \(H=1+\sum_{i=1}^kh_i\), by the definitions. The \(h_i\) are seen to satisfy the following system of equations: \[\begin{aligned} h_1&=xH+xt(t-1)(h_1+h_2),\\ h_i&=xH+x(t-1)(h_{i-1}+h_i+h_{i+1}), \qquad 2 \leq i \leq k-2,\\ h_{k-1}&=xH+x(t-1)(h_{k-2}+h_{k-1}+h_k+1),\\ h_k&=xH+x(t-1)(h_{k-1}+h_k+1). \end{aligned}\]
The preceding system may be rewritten as \(C\mathbf{h}=xH\boldsymbol{1}+\mathbf{v}\), where \(\mathbf{h}=(h_1,\ldots,h_k)^T\) and \(\mathbf{v}=(0,\ldots,0,x(t-1),x(t-1))^T\). By the definitions, we have \[\label{parthe3} \ell_k(x,t)=H_k(x,t)+(t-1)(1+H_k^{(k)}(x,t)), \qquad k \geq2, \tag{10}\] with \(H_k(x,t)\) already found above to be \(\lambda_kF_k(x,t)\). Now \[h_k=(\mathbf{h})_k=xH(C^{-1}\boldsymbol{1})_k+x(t-1)((C^{-1})_{k,k-1}+(C^{-1})_{k,k}),\] with \((C^{-1}\boldsymbol{1})_k=\lambda_k\). By the formula for \((C^{-1})_{i,j}\) from [9], we have \[(C^{-1})_{k,k-1}+(C^{-1})_{k,k}=\frac{1}{x(t-1)U_k(\phi)}(U_{k-1}(\phi)+U_{k-2}(\phi)).\] Thus, we get \[h_k=x\lambda_k^2F_k(x,t)+\frac{U_{k-1}(\phi)+U_{k-2}(\phi)}{U_k(\phi)},\] whence (9) follows from (10), which completes the proof of (8). ◻
Note that \(P_k(x,t)\) is seen to reduce to \(\frac{x^k}{\prod_{i=1}^k(1-ix)}\) when \(t=1\), as expected. Using Theorem 4.1, one can establish the following explicit formula for the total \({s}\)-statistic value taken over all the members of \(\mathcal{P}_{n,k}\).
Corollary 4.2. If \(n \geq k \geq 2\), then the sum of the \({s}\)-values of all the members of \(\mathcal{P}_{n,k}\) is given by \[(k-1)S(n,k)+\left(3k-2-\binom{k}{2}\right)S(n-1,k)+\sum_{i=1}^k\sum_{j=0}^{n-k-2}(3i-2)i^jS(n-j-2,k).\]
Proof. We first seek \(\frac{\partial}{\partial t}\ell_i(x,t)\big|_{t=1}\) for \(2 \leq i \leq k-1\). To do so, first observe \[\lambda_i(x,1)=\lim_{t\rightarrow1}\lambda_i(x,t)=1,\] upon multiplying the numerator and denominator in \(\frac{U_{i}(\phi)-U_{i-1}(\phi)-1}{U_i(\phi)}\) by \((2x(t-1))^i\) to clear all fractions prior to evaluation at \(t=1\). Further, upon writing \[\lambda_i(x,t)=\frac{1}{1-3x(t-1)}\left(1-\frac{U_{i-1}(\phi)+1}{U_i(\phi)}\right),\] we have \[\frac{\partial}{\partial t}\lambda_i(x,t)\big|_{t=1}=3x-\lim_{t\rightarrow1}\frac{\partial}{\partial t}\left(\frac{U_{i-1}(\phi)+1}{U_i(\phi)}\right)=3x-\frac{2x\cdot d_{i-1}}{d_i}=3x-x=2x,\] where \(d_i\) denotes the coefficient of the term in \(U_i(z)\) of greatest degree, and hence \(d_i=2^i\). Also, recall \(F_i(x,t)=\frac{1}{1-ix}\) and \(\frac{\partial}{\partial t}F_i(x,t)\big|_{t=1} =\frac{(3i-2)x^2}{(1-ix)^2}\), from the proof of Corollary 3.2. Thus, by (9), we have \[\frac{\partial}{\partial t}\ell_i(x,t)\big|_{t=1} =1+\frac{3x}{1-ix}+\frac{(3i-2)x^2}{(1-ix)^2}.\] Similarly, since \(F_k^{(k)}(x,t)=x\lambda_kF_k(x,t)\), we get \[\frac{\partial}{\partial t}F_k^{(k)}(x,t)\big|_{t=1} =\frac{2x^2}{1-kx}+\frac{(3k-2)x^3}{(1-kx)^2}.\]
Combining the formulas found above, and making use of (7), yields \[\begin{aligned} &\frac{\partial}{\partial t}P_k(x,t)\big|_{t=1} =P_k(x,1)\left(1+\frac{x}{1-x}+\frac{\frac{\partial}{\partial t}F_k^{(k)}(x,t)\big|_{t=1}}{F_k^{(k)}(x,1)}+\sum_{i=2}^{k-1}\frac{\frac{\partial}{\partial t}\ell_i(x,t)\big|_{t=1}}{\ell_i(x,1)}\right)\\ &=P_k(x,1)\left(1+\frac{x}{1-x}+2x+\frac{(3k-2)x^2}{1-kx}+\sum_{i=2}^{k-1}\left(1-(i-3)x+\frac{(3i-2)x^2}{1-ix}\right)\right)\\ &=P_k(x,1)\left(k-1+\left(3k-2-\binom{k}{2}\right)x+\sum_{i=1}^k\frac{(3i-2)x^2}{1-ix}\right). \end{aligned}\] Recall the well-known formula [20, Eq. (1.94c)] \[\frac{x^k}{(1-x)(1-2x)\cdots(1-kx)}=\sum_{n\geq k}S(n,k)x^n.\] Extracting the coefficient of \(x^n\) in the last expression found for \(\frac{\partial}{\partial t}P_k(x,t)\big|_{t=1}\), upon observing the convolution, one then obtains the desired result. ◻
It is also possible to explain the prior result directly by combinatorial reasoning.
\(\mathbf{Combinatorial~proof~of~Corollary~ 4.2}\). By a good adjacency within an integral sequence \(w=w_1\cdots w_n\), we mean a pair of consecutive letters \(w_i,w_{i+1}\) for some \(i \in [n-1]\) such that \(|w_{i+1}-w_i|\ \leq1\). So we seek to enumerate all of the good adjacencies in members of \(\mathcal{P}_{n,k}\). An entry within a member of \(\mathcal{P}_{n,k}\), represented sequentially, will be described as initial if it corresponds to the leftmost occurrence of a letter of its kind. To establish the formula in Corollary 4.2, first note that \(k \geq 2\) implies that there are \(S(n,k)\) good adjacencies in which the second letter is an initial 2. Now consider inserting within a member \(\rho \in \mathcal{P}_{n-1,k}\) an extra 1 to directly follow the initial 1, or for each \(i \in [2,k]\), an \(i-1\) to directly precede the initial \(i\) or an \(i\) or \(i-1\) to follow it, with no \(i-1\) being added prior to \(i\) if \(i=2\) (this case having already been accounted for). There are then \(3k-3\) possibilities regarding the insertions of letters for each \(\rho\), and hence there are \((3k-3)S(n-1,k)\) good adjacencies in the members of \(\mathcal{P}_{n,k}\) where exactly one of the letters is initial, excluding the case (considered above) in which the second letter is an initial 2.
We now enumerate adjacencies of the form \(i,i+1\), where \(2 \leq i \leq k-1\) and both letters are initial. First note that there are \((k-2)S(n,k)\) initial letters \(i \in [2,k-1]\) within the members of \(\mathcal{P}_{n,k}\) in all. From these, we subtract those whose successor is less than or equal to the letter in question. Note that such letters may be obtained by starting with some \(\rho \in \mathcal{P}_{n-1,k}\) and inserting an element of \([i]\) to directly follow the initial \(i\) for some \(i \in [2,k-1]\). There are then \(2+3+\cdots+k-1=\binom{k}{2}-1\) possible letters to be inserted into each \(\rho\) for a total of \((\binom{k}{2}-1)S(n-1,k)\) initial letters \(i \in [2,k-1]\) whose successor is not initial. Hence, by subtraction, there are \((k-2)S(n,k)-(\binom{k}{2}-1)S(n-1,k)\) adjacencies of the form \(i,i+1\) wherein both letters are initial and \(i>1\).
Finally, we enumerate good adjacencies \(a,b\) in which neither \(a\) nor \(b\) is initial. If \(\pi \in \mathcal{P}_{n,k}\) contains such an adjacency, then \(\pi\) may be expressed as \[\pi=\pi^{(1)}\cdots\pi^{(i-1)}i\alpha ab\beta\pi^{(i+1)}\cdots\pi^{(k)},\] for some \(i \in [k]\), where \(\pi^{(r)}\) for each \(r \in [k]-\{i\}\) is \(r\)-ary and starts with \(r\) and \(\alpha,\beta\) are \(i\)-ary, with \(a,b \in [i]\) such that \(|a-b|\ \leq 1\). Note that there are \(3i-2\) possibilities for \((a,b)\), as there are three possible \(b\) for each \(a\) where we must exclude \((a,b)=(1,0)\) and \((i,i+1)\). If \(j=|\alpha|\), then we have \(\pi^{(1)}\cdots\pi^{(i-1)}i\beta\pi^{(i+1)}\cdots\pi^{(k)} \in \mathcal{P}_{n-j-2,k}\), with \(0 \leq j \leq n-k-2\). Considering all possible \(i\) and \(j\) then implies that there are \(\sum_{i=1}^k\sum_{j=0}^{n-k-2}(3i-2)i^jS(n-j-2,k)\) good adjacencies altogether in \(\mathcal{P}_{n,k}\) in which neither \(a\) nor \(b\) is initial. Combining this case with those prior yields the desired formula for the sum of the \({s}\)-values of all the members of \(\mathcal{P}_{n,k}\). ◻