[go: up one dir, main page]
Scribd
Upload
109 views2 pages

Sequences With Adjacent Elements Unequal

Uploaded by

Đậu Đậu
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
109 views2 pages

Sequences With Adjacent Elements Unequal

Uploaded by

Đậu Đậu
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

256

Sequences with Adjacent ElementsUnequal


L. Q. EIFLER,K. B. REID, JR.1), and D. P. ROSELLE~) (Baton Rouge, Louisiana, U.S.A.)

1. Introduction

Several papers on a combinatorial problem posed by Smirnov have appeared


recently. This problem gives k classes of objects with s~ identical objects in the/-th
class and asks for the number, M(sl, ..., sk), of sequences of length s~ + ... +sk which
consist of these objects and in which no two objects from the same class are adjacent.
Asymptotic formulas are given in [5] and [6], applications are mentioned and a
table of values of M(sl, s2, sa) computed in [1], and the recurrence
k si

M(Sl ..... Sk) = Z Z (-- l ) J + l M ( S l , ' " ' s i - l ' si--J' si+! ..... st)' (1.1)
i=1 j=l
where M(s~ ..... s~_l, O, si+~, ..., sk)=M(st, ..., s,_~, s,+~, ..., Sk) is proved in [2] and
[3]. The latter also mentions the circular version of the problem.
Here we derive recurrences satisfied by and an explicit expression for M ( s t ..... Sk).
We also give a combinatorial argument in order to derive a simple explicit expression
for M(s, s, s). Finally, we give a solution for the circular version of the problem.

2. Three Classes of Elements

We begin by considering the case o f three classes of elements, say l's, 2's and 3's,
and an equal number of elements in each class. The sequences made up of these objects
can be divided into those which start and end with a 1 and those which start but do
not end with a 1. If there are A (s) of the first kind and B(s) of the second kind, then
it is immediate that
M(s, s, s) = 3A (s) + 3B(s). (2.1)
Hence it will suffice to determine A (s) and B(s). Notice that ifc~ denotes a sequence
counted by A (s), then c¢ consists of s - l non-void blocks of 2's and 3's with each
block preceded and followed by a 1. If t denotes the number of these blocks which
contain an odd number of elements, then it follows that t is even, say t = 2v. Thus there
are arrangements for the odd blocks. Fix such an arrangement and note that,

since the number of 2's and 3's being distributed are equal, exactly v of the odd blocks

1) Supported in part by National Science Foundation grant GP19691.


2) Supported in part by National Science Foundation grant GP19207.

Received September 24, 1970


Sequences with Adjacent Elements Unequal 257

begin with a 2 and exactly v begin with a 3. Choose the v odd blocks which are to
begin with a 2 and place a 3 as the beginning element in the v remaining odd blocks.
This choice can be made in (2v) ways.

In order to construct all of the sequences counted by A (s), it is now only necessary
to place 2,3 or 3,2 doubletons in the s - 1 blocks between consecutive l's with the
condition that the s - 1 - 2 v even blocks must contain at least one doubleton. If we
begin by making 2 s- ~-2v choices for assigning one doubleton to each even block, then
it remains only to assign the s-(v+s-1-2v)=v+ 1 remaining doubletons to the
s - 1 partially constructed blocks. There are [4, p. 92]

ways to make this final assignment.


Combining these remarks, we find that

A(s)= ~ ( s - 1 ) (2:) (s +v +vl- 1 ) (2.2)


v=0

Also, only a slight modification of this argument is necessary to show that

v=O

We summarize the results of this section as

T H E O R E M 1. Let M(s) denote the number of sequences comprisedof s of each of


three distinct classesof objects and with no two objectsfrom the sameclassadjacent. Then
M (s) = 3 { ~ (s -1) ( ~ ) (s +v+v -11 ) 2~-l-
v=O
(2.4)
+ ~ (2;)(2W)(s +;--1)2,_2v}.
v=0

3. The General Case

It will be convenient to allow M, (sl,..., sk) to denote the number of sequences of


the desired type in which there are r classes which consist of a single object and k
additional classes, the i-th of which contains st objects. That is, M~(s~,..., sk)=
M(il, ..., ik+,), where ij= 1 (1 <~j<~r)and i,+j=sj(1 <~j<~k). Using this notation, we

You might also like