ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 9 (2015) 287-300
Levels in bargraphs
Aubrey Blecher, Charlotte Brennan *, Arnold Knopfmacher t
University of the Witwatersrand, The John Knopfmacher Centre for Applicable Analysis and Number Theory, Johannesburg, South Africa
Received 20 January 2014, accepted 8 February 2015, published online 8 July 2015
Abstract
Bargraphs are lattice paths in N0, which start at the origin and terminate immediately upon return to the x-axis. The allowed steps are the up step (0,1), the down step (0, -1) and the horizontal step (1,0). The first step is an up step and the horizontal steps must all lie above the x-axis. An up step cannot follow a down step and vice versa. In this paper we consider levels, which are maximal sequences of two or more adjacent horizontal steps. We find the generating functions that count the total number of levels, the leftmost x-coordinate and the height of the first level and obtain the generating function for the mean of these parameters. Finally, we obtain the asymptotics of these means as the length of the path tends to infinity.
Keywords: Bargraphs, levels, generating functions, asymptotics. Math. Subj. Class.: 05A15, 05A16
1 Introduction
Bargraphs are lattice paths in N0, starting at the origin and ending upon first return to the x-axis. The allowed steps are the up step, u = (0,1), the down step, d = (0, -1) and the horizontal step, h = (1,0). The first step has to be an up step and the horizontal steps must all lie above the x-axis. An up step cannot follow a down step and vice versa. It is clear that the number of down steps must equal the number of up steps. Related lattice paths such as Dyck paths and Motzkin paths have been studied extensively (see [4, 9]) whereas until now bargraphs which are fundamental combinatorial structures, have not attracted the same amount of interest.
* Corresponding author. This material is based upon work supported by the National Research Foundation under grant number 86329
^This material is based upon work supported by the National Research Foundation under grant number 81021 E-mail addresses: Aubrey.Blecher@wits.ac.za (Aubrey Blecher), Charlotte.Brennan@wits.ac.za (Charlotte Brennan), Arnold.Knopfmacher@wits.ac.za (Arnold Knopfmacher)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
288
Ars Math. Contemp. 9 (2015) 165-186
Bousquet-Melou and Rechnitzer in [2] and Geraschenko in [8] have studied bargraphs which were named skylines in the latter, and wall polyominoes as per the study of Feretic, in [6]. Bargraphs models arise frequently in statistical physics, see for example [3, 5, 10, 12, 15, 17]. In addition, bargraphs are commonly used in probability theory to represent frequency diagrams and are also related to compositions of integers [11].
In this paper, we consider levels, which are maximal sequences of two or more adjacent horizontal steps. We find different generating functions in each of the following sections where x counts the horizontal steps, y counts the up vertical steps and w counts one of the following parameters: the total number of levels and the horizontal position or the height of the first level. To facilitate these computations, we also find the generating function for paths with no levels.
The study of levels in bargraphs is related to the modelling of tethered polymers under pulling forces, see [13, 14]. These pulling forces have vertical and horizontal components and tend to be resisted by what is known as the stiffness of the polymers. The polymers undergo phase changes, called the stretched (adsorption) phase, where the polymer is stretched vertically. The free (desorbed) phase occurs only when the vertical force is zero. In the bargraph models of polymers positive or negative energy is added to points in levels on the bargraph (called stiffness sites), they tend to keep the polymer horizontal or cause it to bend.
As an example of a bargraph we have
Figure 1: A bargraph with 12 up steps, 13 horizontal steps and 4 levels
Often in the lattice walk and polygon literature, "bargraphs" refer to polygon structures (which would be obtained from the objects considered here by joining the first and last vertices with horizontal steps). The objects discussed here are sometimes called "partially directed walks above a wall" depending on the context (in polymer modelling work for example).
The main tool for elucidating the statistics of interest in this study is a decomposition of bargraphs which is based on the first return to level one. This was described initially by Prellberg and Brak in [16] and more recently in [2], where it is called the wasp-waist decomposition. The present authors have also discussed it in [1].
It follows from the wasp-waist decomposition that the generating function B(x,y) which counts all bargraphs is
6.
1 2 3 4 5 6 7 8 9 I0I1I2I3I41
B := B(x,y)
1 — x — y — xy — \J (1 — x — y — xy)2 — 4x2y
(1.1)
2x
A. Blecher et al.: Levels in bargraphs
289
□ -□ + CÛ
Û
Figure 2: Wasp-waist decomposition of bargraphs
Here x counts the number of horizontal steps and y counts the number of up steps (see Theorem 1 in [1]) or [2, 7]).
The series expansion, B(x, y) begins
x(y + y2 + y 3 + y4) + x2(y + 3y2 + 5y3 + 7y4) + x3(y + 6y2 + 16y3 + 31y4) + x4(y + 10y2 + 40y3 + 105y4 + 219y4).
The bold coefficient of x4y2 is illustrated below with the full set of 10 bargraphs with 4 horizontal steps and 2 vertical up steps.
+
+
+
1
2
3
4
5
In [1, 2] the authors found an asymptotic expression for B(z, z), where z marks the semiperimeter of the bargraphs. This is known as the generating function for the isotropic case. The dominant singularity p is the positive root of
D := 1 - 4z + 2z2 + z4 = 0,	(1.2)
given by
1 /	4 x 22/3
3 V - (13 + 3V33)1/3
We have B(z, z)--(1 - p)1/2 as z ^ p. Hence
1 /	4 X 22/3	/	,_ \ 1/3\
P =1 (-1 - (13 + 3V2/3)i/3 + (2<13 + 3^330 ) =°295598-. (13)
VT-7-
3
[zn]B(z,z) ^	p-n.	(1.4)
n pn3
290
Ars Math. Contemp. 9 (2015) 165-186
The following definitions will be used:
A level in a bargraph is a maximal sequence of two or more adjacent horizontal steps denoted by hr where r > 2. It is preceded and followed by either an up step or a down step. The length of the level is the number r of horizontal steps in the sequence. The height of a level is the y-coordinate of the horizontal steps in the sequence.
Thus, the graph in Figure 1 has four levels, three of length 2 and one of length 3. In all the generating functions of the following sections, the horizontal steps are counted by x, the vertical up steps are counted by y and the parameter that is under investigation by w. In each section, we use G(x, y, w) or F(x, y, w) for the generating function where the definition of G or F applies only to the section under consideration.
2 Total number of levels
2.1 Generating function for the number of levels
A level is a sequence of two or more adjacent horizontal steps as defined in the previous section. Let F(x,y,w) be the generating function where w marks the total number of levels. Using the wasp-waist decomposition in Figure 2, we have
F := F(x,y,w)= ^ + ^ + ^ + xyF + FF	(2.1)
1 2 3 4 5
The numbers below the terms refer to the cases in the wasp-waist decomposition. This will be done throughout the paper. The generating function F2 := F2 (x, y, w) is the analogous function restricted to case 2. We use the following symbolic decomposition for F2



FR
m
□d
FR
Figure 4: Decomposition for F2
where FR is the generating function for bargraphs in which the first column is of height 2 or more. The function FR is easily obtained by considering all bargraphs except those starting with a column of height one. Thus
FR = F - xy - F2.
(2.2)
From Figure 4, we get
2R
F2 = x(F — xy — xF ) + wx y + wx F
(2.3)
+
+
A. Blecher et al.: Levels in bargraphs
291
So, combining equations (2.1), (2.2) and (2.3), we find
1 / 2 2
F -^-^ 1 - x - y - xy + 2x y - 2wx y-
2(x - x2 + wx2) y
J4(-x + x 2 - wx2)(xy - x 2y + wx2y) + (1 - x - y - xy + 2x 2 y - 2wx2y)2 ^ .
(2.4)
In order to find the generating function for the total number of levels in bargraphs, we differentiate F with respect to w and then put w = 1 to obtain
dF	(! - x)(! - y) (l - x - y - xy - ^(1 - x - y - xy)2 - 4x2y)
FLevels •
dw
2^/(1 - x - y - xy)2 - 4x2y
w=i	- x - y
where z marks the semiperimeter. The series expansion begins
x2(y + y2 + y3 + y4) + x3(y + 5y2 + 9y3 + 13y4) + x4(y + 12y2 + 38y3 + 79y4).
There are in total 12 levels in our example in Figure 3. This is shown in bold in the series expansion.
2.2 Asymptotics in the isotropic case
We consider bargraphs with respect to the semiperimeter by substituting z for x and y in F to obtain
(1 - z)2(1 - 2z - z2 - Vl - 4z + 2z2 + z4)
,. - Ao.
FLevels (z? z)
V1 - 4z + 2z2 + z4	'
In order to compute the asymptotics for the coefficients, we use singularity analysis as described in [7]. Let p be as in (1.2) and (1.3). We find that as z —y p
1 - 4p + 4p2 - p4
F Levels
4jp(1 - P -	'
By singularity analysis we have
[znl F 1 - 4p +4p2 - p4 p_n [z \F Levels ~ - ¡—f.	P .
Vn n\Jp (1 - p - p3)
Then after dividing by the asymptotic expression for the total number of bargraphs found in (1.4), we get the following result:
Theorem 2.1. The average number of levels in bargraphs of semiperimeter n is asymptotic to
1 - 4p + 4p2 - p4 2(1 - P - P3) as n —>• oo where C = 0.117516 • • • .
■ n = Cn,
292
Ars Math. Contemp. 9 (2015) 165-186
3 Bargraphs with no levels
3.1 Generating function for the number of graphs with no level
Because we require it later, we begin by enumerating a special class of bargraphs, namely one in which an adjacent sequence of horizontal steps does not occur (i.e. the only sequences of horizontals are single). This is denoted by F0 := F(x, y, 0) where F is the generating function (2.4) from the previous section.
We use the wasp-waist decomposition in Figure 2 to obtain
Fo=^+Fo3+y^o+yFox+F0F0-3 ■	(3.1)
1 2 3 4 5 Case 2 is explained below in Figure 5.
□
□ - □
Figure 5: Explanation for case 2, decomposition of F0,2
Thus
which leads to
Fo,2 = x(Fo - xy - Fq^) ,
F
0,2
x(Fq - xy)
1 + x
(3.2)
The exclusions in case 2 are because we are not allowing adjacent horizontal steps. Hence, from (3.1) and (3.2), we have:
x(Fo - xy) fox(fo - xy) fq = xy +--—--+ yFo + yFox + ■
1 + x
1 + x
1
Solving this for F0, we obtain
Fq
1 - y - 2xy - V1 - y V1 - y - 4xy - 4x2y
2x
The series expansion for F0 begins
(3.3)
x(y + y2 + y3 + y4) + x2(2y2 + 4y3 + 6y4) + x3(y2 + 7y3 + 18y4) + x4 (6y3 + 32y4 + 92y5).
Our example in Figure 3, shows that indeed there are no bargraphs having 4 horizontal and 2 up steps and no levels, which is confirmed by the lack of x4y2 term.
A. Blecher et al.: Levels in bargraphs
293
3.2 Asymptotics in the isotropic case
As before we substitute z for x and y in F0 and obtain
N 1 - z - 2z2 - VT—Z V1 - z - 4z2 - 4z3
Fo(z,z) =-2z-•
Let t be the dominant root of 1 - z - 4z2 - 4z3 = 0, its value is
t = ;T (-4 + (224 - 24V87)1/3 + 2(28 + 3V87)1/3) = 0.34781 • • • . Using singularity analysis we have as z ^ t
„ , , V1-T/t(1 + 8t + 12t2)z fo(z,z)---2t-•
Extracting coefficients will yield the asymptotic number of bargraphs with no levels.
Vr-t^JT (1 + 8t + 12t 2) _„
[zn]Fo(z, z) ~
4%/ n n3
as n ^ to.
For n = 100, there are 3.20775 x 1042 bargraphs whereas the asymptotics give 3.24376 x 1042.
4 Horizontal position of the first level 4.1 Generating function for the mean
Now we derive a generating function Gx for bargraphs in which the leftmost x-coordinate of the first level is counted by w. In the case where the bargraph has no level, we define the horizontal position to be 0. In Figure 6, the start of the first level is the point with coordinates (2, 5) and therefore the x-coordinate of the start of the first level here is 2.
294
Ars Math. Contemp. 9 (2015) 165-186
By the wasp-waist decomposition we have
cx=++yG+yGGxx+
1 2 3 4 5
(4.1)
To calculate the generating function for case 2, we use Figure 7 below. The part labelled L in Figure 7 indicates a bargraph with at least one level.
L
□
0
L
m
nD
Figure 7: Decomposition for FL ,2
+
+
Note that FL,2 is the generating function for case 2, (paths which have at least 1 level).
The generating function for the graph labelled "a" in Figure 7 is therefore Gx - F0, since F0 is the generating function for graphs with no levels from Section 3. Thus, using Figure 7, we have:
Fl,2 := FL,2(x,y,w) = wx(Gx - Fo -	+ x2y + x2B
where B is the generating function for all bargraphs from equation (1.1). Hence,
wxGx - wxFo + x2 y + x2B
fL, 2 =-7—,-,	(4.2)
1 + wx
and from (3.2)
I . l-y-2xy+Vl-W 1-y-4xy-4x2y x -xy +--2x-
Fo.2 = —— (Fo - xy) =
1 + x	1 + x
A. Blecher et al.: Levels in bargraphs
295
So, for case 2
F2 = Fl,2 + Fo,2 . Thus finally, the decomposition for case 5 requires Figure 8 below:
D
I a 1_£_1
Figure 8: Case 5
For case 5, we have the concatenation of two bargraphs labelled a and £. There are three cases depending on whether the graphs a and £ have levels or not.
i.	Graph a has levels with generating function y(Gx —F0), in which case the generating
function for £ is —.
1 y
ii.	Neither graph has levels, thus the generating function is F0F0,2 where F0,2 is as in (3.2) or
iii.	Graph a has no levels but graph £ has, so the generating function is F0(xw, y)F2 where F0(w) := F0(xw, y) indicates that x has been replaced by xw in F0(x, y).
Thus
Gx = + ^fW yC* + yGxx + ((Gx — Fo )xB + FoFo,2 + Fo(xw, y)F2) 1 2 3 4	5
where in all but one case, the parameters have been omitted. We solve for Gx, leading to
Gx (x,y,w)

Bx2F0
+1 + BxFo - ~b~+t - F0F0 2 - x2yF+(1w) + wx(f°1)2 + ^x+1 - Fo 2 - WX+-
wx + 1	0 wx+1	0 °>2	wx+1 1 wx+1 1 wx + 1	°>2 wx + 1
xy
where
Fo(w) =
Bx + wxF0(w) + wx + + 1
Bx + wx + 1 + wx + 1 + xy + y 1
1 — y — 2wxy — /1 — y\J 1 — y — 4wxy — 4w2x2y 2wx
(4.3)
Remark: We note that from (3.3) F0(w)|w=1 = F0.
296
Ars Math. Contemp. 9 (2015) 165-186
Now, in order to find the mean horizontal position, we calculate:
dGx
w=1
dw
(Bx(x + 1) + F0x + (x + 1)2y - 1)2
Ff
x {Fo((x + 1)Fg + Fo + 1)(Fo,2 + xy + y - 1) + Foa((x + 1)F^ + Fq + 1) +B2x2(x(-Fq + Fq + 1) - Fq) + Bx(2x2y(-Fq + Fq + 1) - (y - 1)F^ +x(F02 - 3yFg + Fq + Foy + Fq + y)) + xy(x2y(-F^ + Fq + 1) - yF^ + 2F^ +x(F02 - 2yFg + 2F^ + Foy + Fq + y) + Fq + 1)}
where
dFo (w)
o
dw
y (-2xVy-T + J(2x + 1)2y - 1 -	- J(2x + 1)2y - 1 + V^-^
2^(2x + 1)2y - 1	'
(4.4)
The series expansion of ^Sr I =1 begins
x
dw lw=1
3 (2y2 + 4y3 + 6y4) + x4 (5y2 + 25y3 + 60y4) . In our example in Figure 3, the sum of the horizontal positions of the first levels is 5.
4.2 Asymptotics in the isotropic case
Using singularity analysis and computer algebra we find that
dw
where p is as in (1.3) and
1 - P
-2 ci(p)Jp (1 - p - p3)(^1 - p)
\ 1/2
c1(p)
((-1 + P)P2 + V-Ï+PJY^) JY(p)
X (J-1+ p(1 - P - 12p2 - 4p3 + 13p4 + 27p5 + 18p6 + 18p7 + 4p8) +(-1 + p + 4p2 + 8p3 - 5p4 + p5 - 6p6 - 2p7) JY^)
as z ^ p and Y(p) = -1 + p + 4p2 + 4p3 The coefficient is

cl(pWp (1 - p - p3) p-n
w=i	Vnn3
dw
After dividing by the asymptotic number of bargraphs we get
x
A. Blecher et al.: Levels in bargraphs
297
Theorem 4.1. The average horizontal position of the first level in bargraphs is asymptotic to the constant
2pei(p) = 2.38298, as n ^ to. For n = 200, the exact average is 2.35787 • • •.
5 Height of the first level 5.1 Generating function for the mean
Let Gy (x, y, w) be the generating function for the y-coordinate of the first level for bar-graphs where w marks this coordinate. If there are no levels then there is no w, so we have a contribution to w0. As in the previous section, the first level in Figure 9 begins at the point (2, 5), with y-coordinate 5.
Height of first level
76 5 4 3' 2 1+
uH
ru
1 2 3 4 5 6 7 8 9 10 11 12 13 14 Figure 9: Height of the first level
Using the wasp-waist decomposition, this yields:
Gy = ^ + ^ + xFs +	(5.1)
1 2 3 4 5 Considering case 2 separately, we have for F2:
dD ■□(□-□-£])• m-tiO
Figure 10: Decomposition for F2
298
Ars Math. Contemp. 9 (2015) 165-186
Thus
F2 = x(Gy — xy — F2) + x2yw +
So
^ x(Gy — xy + xyw + xwB)	^ ^
1 + x
and
F3 = yw(Gy — Fq) + yFo	(5.3)
where the first and second terms distinguish between the cases where there are levels (which are therefore multiplied by w) and no levels.
Also separately, for the last case F5 we can use Figure 8. If a has levels, then the generating functions for a and ft are w(Gy — F0) and xB(x, y) respectively. On the other hand, if a has no levels, the generating functions are yF0 and F2. Thus
F5 = w(Gy — Fo)xB(x, y) + yFoF2.	(5.4)
Substituting (5.2), (5.3), and (5.4) in (5.1) and solving for Gy, we obtain
T
' = Bwx + Fx + w(x +1)y + ^ — 1	(5.5)
where
BFowx2	Bwx2 Fowx2y
T =--—--+ BFowx--—---—--+ Fo w(x + 1)y
x +1	x +1 x + 1
Fox2y	wx2y x2y
+ —n~— Fo(x + 1)y--tt + _tt — xy.
x + 1	x +1 x +1
The generating function for the sum of the heights of the first levels is obtained from the derivative of Gy with respect to w and then setting w = 1. Using the following substitutions
i X(x, y) = —1 + (1 + 2x)2y,
\ Y(x, y) = ( — 1 + y)( —1 + x2( —1 + y) + y + 2x(1 + y)),	( . )
we have
dGy dw
(-1 + x + y - xy + JY(x,y))
(x2(1 - y) + xjY(x, y) - JX(x,y)Vy-T + jY(x,y)) x (4x2(y - 1)y + x (-2jx(x,y)jy - 1y + JX(x,y)Jy - 1 + 4y2 - 3y - l)
+y (-JX (x,y)jy-1 + y - 1)) .	(5.7)
The series expansion of ^wr L=1 begins
x2 (y + 2y2 + 3y3 + 4y4) +x3 (y + 8y2 + 21y3 + 40y4) +
x4 (y + 15y2 + 71y3 + 198y4) .
A. Blecher et al.: Levels in bargraphs
299
Figure 3 illustrates that the sum of the heights of the first levels is 15 as shown in bold above.
5.2 Asymptotics in the isotropic case
Substituting z for both x and y in the above equation (5.7) and using X(z, z) := X(z) =
-1 + z + 4z2 + 4z3 and Y(z, z) := Y(z) = 1 - 4z + 2z2 + z4, we obtain
dGy dw
(-1 + 2z - z2 + /YJz))
((1 - z)z2 - yz-I/X(Z) + /Y(Z) + z/Y(i))
x |^4z3(z - 1) + z (-1 + z - Vz - 1 /X(z)J
+z (-1 - 3z + 4z2 + Vz - 1 /X(z) - 2zVz - 1 /X(z))]
--2 c2(p)/p(1 - p - p3) - p) /
by using computer algebra as z ^ p, where
(-2 + 2p + p2 - p3 + VXIP)) (l + P - 2p3 + pV-T+P^XIP})
C2(p) = 2p
(p2(-1+ p) + 7=1+7 ^X^)3
Hence
C2(pVp(1 - p - p3)p-n as n ^to
[z ] dw
where
W=1	vnre
Vn n3
Thus after dividing by the asymptotic number of bargraphs we obtain
Theorem 5.1. The average height of the first level in bargraphs is asymptotic to the constant
2 pc2(p) « 6.15883 ••• , as n ^ to.
For n = 300, the exact average is 6.00066 • • •.
References
[1]	A. Blecher, C. Brennan and A. Knopfmacher, Combinatorial parameters in bargraphs (2015), submitted.
[2]	M. Bousquet-Melou and A. Rechnitzer, The site perimeter of bargraphs, Adv. Appl. Math. 31 (2003), 86-112.
[3]	M. Bousquet-Melou and R. Brak, Exactly solved models of polyominoes and polygons, Chapter 3 of Polygons, Polyominoes and Polycubes, Lecture notes in physics, volume 775, Springer, Berlin, Heidelberg, 2009, 43-78.
[4]	E. Deutsch, Dyck path enumeration, Discrete Math. 204 1-3 (1999), 167-202.
[5]	P. Duchon, q-grammars and wall polyominoes, Ann. Comb. 3 (1999), 311-321.
w = 1
300
Ars Math. Contemp. 9 (2015) 165-186
[6]	S. Feretic, A perimeter enumeration of column-convex polyominoes, Discrete Math. Theor. Comput. Sci. 9 (2007), 57-84.
[7]	P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009.
[8]	A. Geraschenko, An investigation of skyline polynomials. http://people.brandeis. edu/~gessel/4 7a/geraschenko.pdf
[9]	K. Humphreys, A history and a survey of lattice path enumeration, J. Statist. Plann. Inference 140:8 (2010), 2237-2254.
[10]	E. J. Janse van Rensburg and P. Rechnitzer, Exchange symmetries in Motzkin path and bargraph models of copolymer adsorption. Electron. J. Comb. 9 (2002), R20.
[11]	D. Merlini, F. Uncini and M. C. Verri, A unified approach to the study of general and palindromic compositions, Integers 4 (2004), #A23.
[12]	J. Osborn and T. Prellberg, Forcing adsorption of a tethered polymer by pulling, J. Stat. Mech-TheoryE. (2010), P09018.
[13]	A. Owczarek, Exact solution for semi-flexible partially directed walks at an adsorbing wall, J. Stat. Mech.: Theor. and Exp. (2009), P11002.
[14]	A. Owczarek, Effect of stiffness on the pulling of an adsorbing polymer from a wall: an exact solution of apartially directed walk model, J. Phys. A: Math. Theor. 43 (2010), 225002 (16pp).
[15]	A. Owczarek and T. Prellberg, Exact Solution of the Discrete (1+1)-dimensional SOS Model with Field and Surface Interactions, J. Stat. Phys. 70:5/6 (1993), 1175-1194.
[16]	T. Prellberg and R. Brak, Critical exponents from nonlinear functional equations for partially directed cluster models. J. Stat. Phys. 78 (1995), 701-730.
[17]	C. Richard, I. Jensen and A. J. Guttmann, Scaling Function for Self-Avoiding Polygons, Proceedings TH2002 Supplement, Birkhauser Verlag, Basel, 2003, 267-277.