THE EXPECTED VARIATION OF RANDOM BOUNDED INTEGER SEQUENCES OF FINITE LENGTH

(1)

THE EXPECTED VARIATION OF RANDOM BOUNDED INTEGER SEQUENCES OF FINITE LENGTH

RUDOLFO ANGELES, DON RAWLINGS, LAWRENCE SZE, AND MARK TIEFENBRUCK

Received 24 November 2004 and in revised form 15 June 2005

From the enumerative generating function of an abstract adjacency statistic, we deduce the mean and variance of the variation on random permutations, rearrangements, compositions, and bounded integer sequences of finite length.

1. Introduction

When the finite sequence of integersw=1, 3, 2, 2, 4, 3 is sketched as below,

w=

4

3 3

2 2

1

(1.1)

its most compelling aspect is its verticalvariation, that is, the sum of the vertical distances between its adjacent terms. Denoted by varw, the vertical variation of the sequence in (1.1) is varw=2 + 1 + 0 + 2 + 1=6. Our purpose here is to compute the mean and variance of var on four classical sets of combinatorial sequences.

To formalize matters and place our problem in the context of other work, let [m]ⁿ denote the set of sequencesw=x1x2···x_nof lengthnwith eachx_i∈ {1, 2,...,m}. For a real-valued function f on [m]², the f-adjacency numberofw=x1x2···xn∈[m]ⁿ is defined to be

adfw=

n−1 k=1

fxkxk+1

. (1.2)

International Journal of Mathematics and Mathematical Sciences 2005:14 (2005) 2277–2285 DOI:10.1155/IJMMS.2005.2277

(2)

Table 1.1

Sequences Expected value of var Variance of var

Sn n²−1

3

(n−2)(n+ 1)(4n−7) 90

[m]ⁿ (n−1)(m²−1)

3m

(m²−1)(6m²n+ 6n−7m²−2) 90m²

Rn(i) 2

n

1≤x<y≤m

(y−x)ixiy See (3.10)

Cn(m) 2(n−1) (m−1)ⁿ⁻¹

m/2

x=1

(m−2x)ⁿ⁻¹ See (3.18)

Some specializations of thef-adjacency number have been considered elsewhere. For instance, iff(xy) is 1 whenx < yand 0 otherwise, then adfwis known as therise numberof w[1,3,4]. For the selection f(xy)= |y−x|, adfw=varw. In a sorting problem of com- puter science, Levcopoulos and Petersson [5] introduced the related notion of oscillation (varw−n+ 1) as a measure of the presortedness of a sequence ofndistinct numbers.

In [6], compositions were enumerated by theirascent variation, the f-adjacency statistic induced by f(xy)=y−x ifx < yand 0 otherwise. For the case f(xy)=h(|y−x|) wherehis a linear, convex, or concave increasing real-valued function, Chao and Liang [2] described the arrangements ofndistinct integers for which adf achieves its extreme values.

Besides considering the distribution of var on the set [m]ⁿ, we also consider it on the set of rearrangementsR_n(i1,i2,...,i_m) consisting of sequences of lengthn=i1+i2+

···+i_mwhich containlexactlyi_l times, on the set of permutationsS_n=R_n(1, 1,..., 1) of{1, 2,...,n}, and on the set of compositions ofmintonpartsCn(m)= {x1x2···xn∈ [m]ⁿ:x1+x2+···+xn=m}. For m,n≥2,Table 1.1 displays the mean and variance of var on these four sets. Thekth falling factorial ofn isn^k=n(n−1)···(n−k+ 1), i=(i1,i2,...,i_m), and, forra real number,r denotes the greatest integer less than or equal tor. The results inTable 1.1are new. David and Barton [3, Chapter 10] present the distributions of several statistics (some f-adjacency numbers, some not) primarily on permutations. We also note that Tiefenbruck [7] derived a generating function for compositions with bounded parts by a close relative of var. We leave open questions con- cerning the asymptotic behavior of var.

2. Enumerative factorial moments for f-adjacencies

Before working specifically with var, we discuss the enumerative generating function for adf on sequences as developed by F´edou and Rawlings [4]. Let [m]^∗denote the set of sequences of 1, 2,...,mof finite length (including the empty sequence of length 0). For w=x1x2···xn∈[m]^∗, we defineZ^w=zx1zx2···zxn. The enumerative generating function for adf over [m]^∗is then defined to beG(p)=

w∈[m]^∗p^adf^wZ^w.

By manipulatingG(p), we will obtain all of the information inTable 1.1(and more).

As a brief outline of our approach, note that the coeﬃcient ofp^kz1ⁱ¹z2ⁱ²···zⁱm^m inG(p) is

(3)

just the number of rearrangementswinR_n(i) with adfw=k. Thus, by dividing the coeﬃ- cient ofzⁱ1¹zⁱ2²···zmⁱ^minG(1) by the cardinality ofR_n(i), we will obtain the mean of adf. So, in general, we compute thedthenumerative factorial momentG⁽^d⁾(1)=

w∈[m]^∗(adfw)^d Z^w.

From the work of F´edou and Rawlings [4], it follows that

G(p)= 1

D(p), (2.1)

where

D(p)=1−

n≥1

x1···xn∈[m]ⁿ

Z^x¹^···^xⁿ

n−1 k=1

p^f⁽^x^k^x^k+1⁾−1. (2.2)

Examples are presented in [4,6] for whichDhas a closed form. We do not know a closed form forDwhen adf=var (that is, when f(x,y)= |y−x|). Nevertheless, (2.1) is still useful in computing the mean and variance of var.

Although the formula for taking thed-fold derivative with respect to pof a function of the form in (2.1) is known, we provide a short derivation. To avoid the quotient and chain rules, rewrite (2.1) asGD=1. Diﬀerentiating the latterdtimes,d≥1, and dividing byd! gives

d j=0

G⁽^d⁻^j⁾ (d−j)!

D⁽^j⁾

j! ⁼0. (2.3)

To solve forG⁽^d⁾, consider the system G⁽^d⁾

d!

D⁽⁰⁾

0! + G⁽^d⁻¹⁾ (d−1)!

D⁽¹⁾

1! + G⁽^d⁻²⁾ (d−2)!

D⁽²⁾

2! +···+G⁽⁰⁾ 0!

D⁽^d⁾ d! ⁼0, G⁽^d⁻¹⁾

(d−1)!

D⁽⁰⁾

0! + G⁽^d⁻²⁾ (d−2)!

D⁽¹⁾

1! +···+G⁽⁰⁾ 0!

D⁽^d⁻¹⁾ (d−1)!⁼0,

... G⁽¹⁾

1!

D⁽⁰⁾ 0! +G⁽⁰⁾

0!

D⁽¹⁾ 1! ⁼0, G⁽⁰⁾

0!

D⁽⁰⁾ 0! ⁼1,

(2.4)

where the topdequations arise from repeated application of (2.3). Cramer’s rule applied

(4)

to the above system yields

G^(d) d! ⁼

(−1)^d D^d⁺¹

D⁽¹⁾ 1!

D⁽²⁾ 2!

D⁽³⁾

3! ^···

D⁽^d⁾ d!

D⁽⁰⁾ 0!

D⁽¹⁾ 1!

D⁽²⁾ 2!

D⁽^d⁻¹⁾ (d−1)!

0 D⁽⁰⁾ 0!

D⁽¹⁾ 1!

D⁽^d⁻²⁾ (d−2)!

... ...

0 ··· 0 D⁽⁰⁾

0!

D⁽¹⁾ 1!

(2.5)

which, when expanded, implies that G⁽^d⁾=^d

ν=1

(−1)^ν D^ν⁺¹

j¹+···+jν=d jk≥1

d j1···jν

D⁽^j¹⁾···D⁽^j^ν⁾. (2.6)

To determine the enumerative factorial momentG⁽^d⁾(1), we see from (2.2) that D⁽^j⁾(1)= −

j+1

r=2

D⁽r^j⁾, (2.7)

where

D⁽r^j)=

x1···xr∈[m]^r

Z^x¹^···^x^r

l1+_···+lr−1=j lk≥1

j l1···l_r−1

_r₋₁

k=1

fxkxk+1

_l_k

. (2.8)

For instance,

D2=

xy∈[m]²

f(xy)zxzy, D2 =

xy∈[m]²

f(xy)²zxzy, D3=2

vxy∈[m]³

f(vx)f(xy)z_vz_xz_y. (2.9)

Further settingj=(j1,...,jν),s(j)=j1+···+jν, d

j

= d

j1···jν

, and D⁽µ^j⁾=

r¹+···+rν=µ rk≥2

D⁽r¹^j¹⁾···D⁽rν^j^ν⁾, (2.10)

it follows from (2.6) and (2.7) that G⁽^d⁾(1)=^d

ν=1

1 D^ν+1(1)

s(j)₌d jk≥1

d j

_d₊_ν

µ=2ν

D⁽µ^j⁾. (2.11)

(5)

AsD(1)=1−(z1+···+z_m), extracting the contributions made by allw∈[m]ⁿ from both sides of (2.11) gives thedth enumerative factorial moment of adf over [m]ⁿas

w∈[m]ⁿ

(adfw)^dZ^w= d ν=1

s(j)=d jk≥1

d j

_d₊_ν

µ=2ν

n+ν−µ ν

_m

i=1

zi

n−µ

D⁽µ^j⁾ (2.12)

valid ford≥1. Whend=1, 2, (2.9) and (2.12) imply that

w∈[m]ⁿ

adfw Z^w=(n−1) _m

i=1

z_i n−2

xy∈[m]²

f(xy)z_xz_y (2.13)

and that

w∈[m]ⁿ

(adfw)²Z^w=(n−1) _m

i=1

z_i _n−2

xy∈[m]²

f(xy)²z_xz_y

+ 2(n−2) _m

i=1

z_i n−3

vxy∈[m]³

f(vx)f(xy)z_vz_xz_y

+ (n−2)(n−3) _m

i=1

z_i

n−4

xy∈[m]²

f(xy)z_xz_y 2

.

(2.14)

3. Discussion ofTable 1.1

The entries inTable 1.1are consequences of (2.13) and (2.14) with f(xy)= |y−x|and with appropriate substitutions for Z. For the mean and variance of var on the set of bounded sequences [m]ⁿ, putzi=1 for 1≤i≤m. Noting that

xy∈[m]²

|y−x| =

1≤x<y≤m

2(y−x)=2 m+ 1

3

, (3.1)

it follows from (2.13) that the mean of var on [m]ⁿis 1

mⁿ

w∈[m]ⁿ

varw=2(n−1)mⁿ⁻² mⁿ

m+ 1 3

=(n−1)m²−1

3m . (3.2)

As

xy∈[m]²

|y−x|²=4 m+ 1

4

(3.3)

(6)

and as

vxy∈[m]ⁿ

|x−v||y−x| =

1≤v<x<y≤m

2(x−v)(y−x)

+

1≤x<y≤v≤m

4(v−x)(y−x)−

1≤x<y≤m

2(y−x)²

=7m²−8 10

m+ 1 3

,

(3.4)

(2.14) implies that 1 mⁿ

w∈[m]ⁿ

(varw)²=4(n−1) m²

m+ 1 4

+(n−2)7m²−8 5m³

m+ 1 3

+4(n−2)(n−3) m⁴

m+ 1 3

2

.

(3.5)

Then, subbing the last result into 1

mⁿ

w∈[m]ⁿ

(varw)²+(n−1)m²−1

3m ⁻

(n−1)m²−1 3m

2

(3.6) and simplifying gives the variance of var as recorded inTable 1.1.

ForRn(i), extracting the coeﬃcient ofzⁱ1¹zⁱ2²,···,zmⁱ^mfrom (2.13) leads to

w∈Rn(i)

varw=2(n−1)

1_≤x<y≤m

(y−x)

n−2

i1···i_x−1···i_y−1···i_m

. (3.7)

As the cardinality ofR_n(i) is

n i1i2···im

= n

i

, (3.8)

it follows that the mean of var onR_n(i) is n

i −1

w∈Rn(i)

varw=2 n

1_≤x<y≤m

(y−x)i_xi_y. (3.9)

Leti\r=(i1,...,i_r−1,...,i_n). For example, (3, 2, 1, 4)_\3\2\3=(3, 1,−1, 4). The variance on Rn(i) is then

n i

−1

w∈Rn(i)

varw²+2 n

1_≤x<y≤m

(y−x)i_xi_y− 2

n

1_≤x<y≤m

(y−x)i_xi_y 2

, (3.10)

(7)

where, upon extraction of the coeﬃcient ofzⁱ1¹zⁱ2²,...,zmⁱ^mfrom (2.14), we have

w∈Rn(i)

(varw)²=(n−1)

1≤x,y≤m

|y−x|² n−2

i\x\y

+ 2(n−2)

1_≤v,x,y≤m

|x−v||y−x| n−3

i\v\x\y

+ (n−2)(n−3)

1_≤u,v,x,y≤m

|v−u||y−x|

n−4 i\u\v\x\y

.

(3.11)

The permutation entries inTable 1.1follow from (3.9) and (3.10). Selectingm=nand ik=1 for 1≤k≤nin (3.9) reveals the mean of var onSnas

1 n!

w∈Sn

varw=2 n

1_≤x<y≤n

(y−x)=2 n

n+ 1 3

=n²−1

3 . (3.12)

From (3.11), withm=nandi_k=1 for 1≤k≤n,

w∈Sn

(varw)²=(n−1)!

1_≤x,y≤n

|y−x|² + 2(n−2)!

1≤v,x,y≤n

|x−v||y−x| + (n−2)!

1_≤u,v,x,y≤m {u,v}∩{x,y}=∅

|v−u||y−x|

= 4 15

(n−2)!10n²+ 14n−27 n+ 1

4

.

(3.13)

So the variance of var onSnis 1

n!

w∈Sn

varw²+n²−1

3 ⁻

n²−1 3

2

=(n−2)(n+ 1)(4n−7)

90 . (3.14)

For w=x1···xn∈[m]ⁿ, let w =x1+···+xn. For the composition results in Table 1.1, setzk=q^kfor 1≤k≤m. Then (2.13) implies that

w∈[m]ⁿ

varw q^w=(n−1)qⁿ⁻² 1−q^m 1−q

n−2

1_≤x,y≤m

|y−x|q^x⁺^y (3.15)

(8)

and (2.14) leads to

w∈[m]ⁿ

(varw)²q^w=(n−1)qⁿ⁻² 1−q^m 1−q

n−2

1≤x,y≤m

|y−x|²q^x⁺^y + 2(n−2)qⁿ⁻³ 1−q^m

1−q

_n−3

1≤v,x,y≤m

|x−v||y−x|q^v+x+y + (n−2)(n−3)qⁿ⁻⁴ 1−q^m

1−q

_n−4

1≤u,v,x,y≤m

|v−u||y−x|q^u⁺^v⁺^x⁺^y. (3.16) Extracting the coeﬃcient ofq^mfrom (3.15) to obtain

w∈Cn(m)

varw=2(n−1)

1≤x<y≤m

(y−x)

m−1−x−y n−3

=2(n−1)

1_≤x≤m/2

m−2x n−1

(3.17)

and then dividing by the cardinality^m_n₋⁻1¹

ofC_n(m) gives the mean of var as stated in Table 1.1. The variance is

m−1 n−1

₋1

w∈Cn(m)

varw²+ 2(n−1) (m−1)ⁿ⁻¹

1_≤x≤m/2

(m−2x)ⁿ⁻¹

− 2(n−1) (m−1)ⁿ⁻¹

1_≤x≤m/2

(m−2x)ⁿ⁻¹ 2

,

(3.18)

where, pulling the coeﬃcient ofq^mfrom (3.16), we have

w∈Cn(m)

(varw)²=(n−1)

1≤x,y≤m

|y−x|²

m−1−x−y n−3

+ 2(n−2)

1≤v,x,y≤m

|x−v||y−x|

m−1−v−x−y n−4

+ (n−2)(n−3)

1≤u,v,x,y≤m

|v−u||y−x|

m−1−u−v−x−y n−5

. (3.19) The sums in (3.19) are marginally simplified. For instance,

1_≤x,y≤m

|y−x|²

m−1−x−y n−3

=4

1≤x≤m/2

m−2x n

. (3.20)

(9)

As a part of the second sum on the right-hand side of (3.19), we note that

1≤v<x<y≤m

(x−v)(y−x)

m−1−v−x−y n−4

=

2≤x≤(m+1)/2

m−3x+ 1 n

−

m−2x+ 1 n

+x

m−2x n−1

.

(3.21)

The four-fold sums arising in the last sum in (3.19) reduce to double sums.

Acknowledgment

This work is based on work supported by the National Science Foundation under Grant no. 0097392.

References

[1] L. Carlitz,Enumeration of compositions by rises, falls and levels, Math. Nachr.77(1977), 361–

371.

[2] C.-C. Chao and W.-Q. Liang,Arrangingndistinct numbers on a line or a circle to reach extreme total variations, European J. Combin.13(1992), no. 5, 325–334.

[3] F. N. David and D. E. Barton,Combinatorial Chance, Hafner, New York, 1962.

[4] J.-M. F´edou and D. P. Rawlings,Adjacencies in words, Adv. in Appl. Math.16(1995), no. 2, 206–218.

[5] C. Levcopoulos and O. Petersson,Heapsort—adapted for presorted files, Algorithms and Data Structures (Ottawa, ON, 1989), Lecture Notes in Comput. Sci., vol. 382, Springer, Berlin, 1989, pp. 499–509.

[6] D. P. Rawlings,Restricted words by adjacencies, Discrete Math.220(2000), no. 1-3, 183–200.

[7] M. Tiefenbruck,Enumerating compositions with bounded parts by variation, REU report, Cali- fornia Polytechnic State University, California, 2003.

Rudolfo Angeles: Department of Mathematics, College of Science and Mathematics, California, Polytechnic State University, San Luis Obispo, CA 93407, USA

Current address: Department of Statistics, Stanford University, Palo Alto, CA 94305-4065, USA E-mail address:[email protected]

Don Rawlings: Department of Mathematics, College of Science and Mathematics, California Polytechnic State University, San Luis Obispo, CA 93407, USA

E-mail address:[email protected]

Lawrence Sze: Department of Mathematics, College of Science and Mathematics, California, Poly- technic State University, San Luis Obispo, CA 93407, USA

E-mail address:[email protected]

Mark Tiefenbruck: Department of Mathematics, College of Science and Mathematics, California Polytechnic State University, San Luis Obispo, CA 93407, USA

Current address: 8989 Jasmine Lane Street, Cottage Grove, MN 55016-3436, USA E-mail address:[email protected]

(10)

Special Issue on

Modeling Experimental Nonlinear Dynamics and Chaotic Scenarios

Call for Papers

Thinking about nonlinearity in engineering areas, up to the 70s, was focused on intentionally built nonlinear parts in order to improve the operational characteristics of a device or system. Keying, saturation, hysteretic phenomena, and dead zones were added to existing devices increasing their behavior diversity and precision. In this context, an intrinsic nonlinearity was treated just as a linear approximation, around equilibrium points.

Inspired on the rediscovering of the richness of nonlinear and chaotic phenomena, engineers started using analytical tools from “Qualitative Theory of Diﬀerential Equations,”

allowing more precise analysis and synthesis, in order to produce new vital products and services. Bifurcation theory, dynamical systems and chaos started to be part of the mandatory set of tools for design engineers.

This proposed special edition of the Mathematical Prob- lems in Engineering aims to provide a picture of the impor- tance of the bifurcation theory, relating it with nonlinear and chaotic dynamics for natural and engineered systems.

Ideas of how this dynamics can be captured through precisely tailored real and numerical experiments and understanding by the combination of specific tools that associate dynamical system theory and geometric tools in a very clever, sophis- ticated, and at the same time simple and unique analytical environment are the subject of this issue, allowing new methods to design high-precision devices and equipment.

Authors should follow the Mathematical Problems in Engineering manuscript format described at http://www .hindawi.com/journals/mpe/. Prospective authors should submit an electronic copy of their complete manuscript through the journal Manuscript Tracking System athttp://

mts.hindawi.com/according to the following timetable:

Manuscript Due December 1, 2008 First Round of Reviews March 1, 2009 Publication Date June 1, 2009

Guest Editors

José Roberto Castilho Piqueira,Telecommunication and Control Engineering Department, Polytechnic School, The University of São Paulo, 05508-970 São Paulo, Brazil;

[email protected]

Elbert E. Neher Macau,Laboratório Associado de Matemática Aplicada e Computação (LAC), Instituto Nacional de Pesquisas Espaciais (INPE), São Josè dos Campos, 12227-010 São Paulo, Brazil ; [email protected] Celso Grebogi,Center for Applied Dynamics Research, King’s College, University of Aberdeen, Aberdeen AB24 3UE, UK; [email protected]

Hindawi Publishing Corporation http://www.hindawi.com