# Impulse Propagation in Compositions and Words

Authors: Margaret Archibald; Aubrey Blecher; Charlotte Brennan; Arnold Knopfmacher; Toufik Mansour
Journal: International Journal of Mathematics and Mathematical Sciences
 (2021)

---

## Abstract

We consider compositions ofn represented as bargraphs and subject these to repeated impulses which start from the left at the top level and destroy horizontally connected parts. This is repeated while moving to the right first and then downwards to the next row and the statistic of interest is the number of impulses needed to annihilate the whole composition. We achieve this by conceptualizing a generating function that tracks compositions as well as the number of impulses used. This conceptualization is repeated for words (over a finite alphabet) represented by bargraphs.


---

## Body

## 1. Introduction

In several recent papers modelling physical or chemical situations, molecules and other structures are represented by combinatorial objects (e.g., compositions) and various physical entities (such as light or force) acting on the objects are modelled in the mathematical context of these combinatorial objects (see [1–4]). In this paper, we continue this project using bargraphs (see [5]) to model the physical objects subject to impulses which destroy them. An impulse starts from the left at the top level and destroys the blocks formed by the horizontally connected cells. The number of such impulses is the focus of attention. Each block on a given level requires a separate impulse to destroy it. Bargraphs are nonintersecting lattice paths in ℕ02 with three allowed types of steps; up 0,1, down 0,−1, and horizontal 1,0. They start at the origin with an up step and terminate immediately upon return to the x-axis. Bargraphs can represent compositions and words where the respective height of each horizontal step corresponds to the respective size of each part of the three structures. A composition is a bargraph of area n. It is well known that there are precisely 2n−1 compositions of size (or area) n see Figure 1.The impulses on the same horizontal level have the same color. There are two impulses on level 2.In what follows, we devote one section to each of the combinatorial structures (compositions and words). Each section develops the generating function for the number of impulses required to annihilate the respective structures, and we obtain the average number of such impulses required for each of the structures in relation to its defining parameter (size of the composition and length of words). InSection 4, we also study the number of impulses at level j in these bargraphs.


## 2. Compositions

Compositions ofn (see [6]) are finite sequences of positive integers σii=1k such that(1)σ1+σ2+⋯+σk=n,where the σi are called parts and denote the height of the columns in the associated bargraph.The generating functionPx,y,u (see [7]) will count compositions where x marks the size of the composition n, y is the number of parts, and u is the number of impulses.We shall considerPx,y,u|a, the generating function for compositions where the first part is of size a. We decompose this situation into three cases: namely, where the composition has only one part (of size a), or for more than one part, we take compositions starting with a part of size b and prepend a part of size a to the left with a<b or else we prepend a part a≥b. We sum the three respective generating functions:(2)Px,y,u|a=xayua+∑a≤bxayPx,y,u|b+∑a>bxayua−bPx,y,u|b.For convenience, suppress the other variables and introduce variablev that tracks the size of the first letter. So, we define(3)Pv≔Px,y,u,v=1+∑a≥1Px,y,u|ava.Thus,(4)Pv=1+∑a≥1xayuava+∑a≥1∑a≤bxayPx,y,u|bva+∑a≥1∑a>bxayua−bPx,y,u|bva=1+xyuv1−xuv+y∑b≥1∑a=1bxavaPx,y,u|b+y∑b≥1∑a=b+1∞xaua−bvaPx,y,u|b=1+xyuv1−xuv+y∑b≥1xv1−xvb1−xv+y∑b≥1u−bPx,y,u|bxuvb+11−xuv=1+xyuv1−xuv+y∑b≥1xv−xvb+11−xv+y∑b≥1uPx,y,u|bxvb+11−xuv=1+xyuv1−xuv+xyv1−xvP1−1−Pxv−1+xyuv1−xuvPxv−1=1+xyuv1−xuv+xyv1−xvP1−xyuv1−xuv+Pxvxyuv1−xuv−xyv1−xv=1+xyv1−xvP1+Pxvxyvu−11−xuv1−xv.This is an expression that can be iterated. For simplicity, we defineAv:=xyvu−1/1−xuv1−xv. Thus,(5)Pv=1+xyv1−xvP1+Av1+x2yv1−x2vP1+Px2vAxv=1+Av+xyv1−xv+Avx2yv1−x2vP1+AvAxv1+x3yv1−x3vP1+Px3vx3yvu−11−x3uv1−x3v=1+Av+AvAxv+xyv1−xv+Avx2yv1−x2v+AvAxvx3yv1−x3vP1+AvAxvAx2vPx3v.Carrying on this process ad infinitum, we obtain(6)Pv=1+∑j≥0∏i=0jAxiv+P1∑j≥0yxj+1v1−xj+1v∏i=0j−1Axiv=1+∑j≥0∏i=0jxi+1yvu−11−xi+1uv1−xi+1v+P1∑j≥0yxj+1v1−xj+1v∏i=0j−1xi+1yvu−11−xi+1uv1−xi+1v=1+∑j≥0yvu−1j+1∏i=0jxi+11−xi+1uv1−xi+1v+P1∑j≥0yxj+1v1−xj+1vyvu−1j∏i=0j−1xi+11−xi+1uv1−xi+1v.Now, substitutingv=1 yields(7)P1=1+∑j≥0yu−1j+1∏i=0jxi+11−xi+1u1−xi+1+P1∑j≥0yxj+11−xj+1yu−1j∏i=0j−1xi+11−xi+1u1−xi+1.Thus, we can state the following result.Theorem 1.
We have(8)Px,y,u=1+∑j≥0yu−1j+1∏i=0jxi+1/1−xi+1u1−xi+11−∑j≥0yxj+1/1−xj+1yu−1j∏i=0j−1xi+1/1−xi+1u1−xi+1.
For example, in Theorem1 with u=1, we get back the well-known generating function for all compositions:(9)Px,y,1,1=11−yx/1−x=1−x1−x−xy,where the size of the composition is counted by x and the number of parts is counted by y.
Theorem1 shows that(10)dduPx,y,u|u=1=xy1−x21−yx/1−x21−yx/1−x2=xy1−x2−yx1−x21−x−yx2,which leads to(11)dduPx,1,u|u=1=x1−x−x21−x21−2x2=∑n≥03n+102n−9−−1n18xn.
Thus, we can state the following result.Corollary 1.
The total number of impulses over all compositions ofn is given by(12)3n+102n−9−−1n18.
Dividing by2n−1, we find that the average number of impulses to destroy a composition of size n is(13)n3+109+O2−nasn⟶∞.


## 3. Words

Words over the alphabetk are finite sequences a1a2…an, where each ai∈k (see [6]). For the purposes of this paper, we represent each such word as a bargraph (see the previous section) with maximum column height k.The generating functionWkx,u will count words over the alphabet k of length n (bargraphs with n columns and the height of each column is at most k), where x marks the size of the words n and u is the number of impulses. Let Wkx,u|a be the generating function for such words where the first part is of size a. By (2) and the fact that Wkx,u=1+∑a=1kWkx,u|a, we have(14)Wkx,u|a=xua+x∑b=akWkx,u|b+x∑b=1a−1ua−bWkx,u|b=xua−1+xWkx,u+x∑b=1a−1ua−b−1Wkx,u|b.By induction ona, we obtain(15)Wkx,u|a=∑π1π2⋯πm∈Caxmuπ1−1+Wkx,u∏j=2muπj−1,where Ca is the set of compositions of a. Actually, ∑π1…πm∈Ca means ∑m∑π1…πm∈Ca,m. Thus,(16)Wkx,u−1=∑a=1kWkx,u|a=∑a=1k∑π1π2⋯πm∈Caxmuπ1−1+Wkx,u∏j=2muπj−1,which implies the following theorem.Theorem 2.
We have(17)Wkx,u=1+∑a=1k∑π1π2⋯πm∈Caxm∏j=1muπj−11−∑a=1k∑π1π2⋯πm∈Caxm∏j=2muπj−1.
In particular,Wkx,1=1/1−∑a=1kx=1/1−kx, which is the well-known generating function for the number of words of length n over the alphabet k.
Differentiating the equation in Theorem2 yields(18)dduWkx,u|u=1=x1−kxk+12+x1−kx2k+13,which leads to the following corollary.Corollary 2.
The total number of impulses for all words of lengthn over alphabet k is given by(19)k+12+nk+13kn−1.
Hence, the average number of impulses for a word of lengthn is k2−1/6n+k+1/2.


## 4. Impulses at Levelj

DefineIjπ to be the number of impulses at level j in the bargraph π. For instance, I1π=1, I2π=2, I3π=1, I4π=1, and Ijπ=0 for all j≥5, where π is given in Figure 1. Define Hx,y;q1,q2,… to be the generating function for the number of compositions of n with exactly m parts and number of impulses at level j, that is,(20)Hx,y;q1,q2,…=∑n≥0∑m=0nxnym∑π∏j≥0qjIjπ,where ∑π is sum over all compositions of n with exactly m parts.Figure 1
Composition 122134 of 13 with 5 impulses.Let us write an equation forHx,y;q1,q2,…. Note that each composition π=π1π2⋯πm can be decomposed as follows: it is either empty; or π=1; or π1=1 and m≥2; or π1,…,πm≥2 and m≥1; or π1,…,πm−1≥2 with πm=1 and m≥2; or π1,…,πj−1≥2 with πj=1 and m>j>1. Thus, we have the following contributions 1, q1xy, xyHx,y;q1,q2,…−1, q1Hx,xy;q1,q2,…−1, q1xyHx,xy;q1,q2,…−1, and(21)xyHx,xy;q1,q2,…−1Hx,y;q1,q2,…−1,respectively. Hence,(22)Hx,y;q1,q2,…=1+q1xy+xyHx,y;q1,q2,…−1+q1Hx,xy;q2,q3,…−1+q1xyHx,xy;q2,q3,…−1+xyHx,xy;q2,q3,…−1Hx,y;q1,q2,…−1,which, by iterating, implies the following result.Theorem 3.
The generating functionHx,y;q1,q2,… satisfies(23)Hx,y;q1,q2,…=1−q1+q1Hx,xy;q2,q3,…1−xyHx,xy;q2,q3,….Moreover, it is given by(24)Note thatHx,y;1,1,…=1/1−xy/1−x satisfies Hx,y;1,1,…=Hx,xy;1,1,…/1−xyHx,xy;1,1,…. Define Hmx,y;q=Hx,y;q1,q2,… with qm=q and qj=1 for all j≠m. Then, Theorem 3 gives the following result.Theorem 4.
The generating functionHmx,y;q is given by(25)Hmx,y;q=Hm−1x,xy;q1−xyHm−1x,xy;q,where(26)H1x,y;q=1−q+qHx,xy;1,1,…1−xyHx,xy;1,1,…=1−q+q1−xy/1−x.
Defined/dqHmx,y;q|q=1 to be the generating function Hm′x,y. Then, Theorem 4 (and induction on m) shows that for all m≥1,(27)Hm′x,y=xmy/1−x1−xmy/1−x1−xy/1−x2.
Hence,Hm′x,1=xm1−x−xm/1−2x2, which leads to the following result.Corollary 3.
Letn≥m≥1. Then, the total number of impulses at level m over all bargraphs of n is given by(28)n−m+12n−m−n−m2n−m−1−n−2m+12n−2m.Whenm=1, this gives 2n−1 as expected since I1π=1 for every compositions of n.As another application, we consider the generating functionJmx,y=Hx,y;q1,q2,… with qj=0 for j ≥ m and qj=1 for all j<m. Note that Jmx,y is the generating function for the number of compositions of n with exactly m parts such that each part is at most m−1. Theorem 3 shows Amx,y=Am−1x,xy/1−xyAm−1x,xy with A1x,y=1. Hence, Amx,y=1/1−x+x2+⋯+xm−1y, for all m≥1, as it is well known (see [6]).



---

*Source: 8811261-2021-01-21.xml*