Toufik Mansour
email: toufik@math.haifa.ac.il

On an open problem of Green and Losonczy: exact enumeration of freely braided permutations

Keywords: restricted permutations, freely braided permutations, generating functions

 introduced freely braided permutations as a special class of restricted permutations that has arisen in the study of Schubert varieties. They suggest as an open problem to enumerate the number of freely braided permutations in S n . In this paper, we prove that the generating function for the number of freely braided permutations in S n is given by 1

Introduction

Let α ∈ S n and τ ∈ S k be two permutations. Then α contains τ if there exists a subsequence 1 ≤ i 1 < i 2 < • • • < i k ≤ n such that (α i 1 , . . . , α i k ) is order-isomorphic to τ; in such a context τ is usually called a pattern; α avoids τ, or is τ-avoiding, if α does not contain such a subsequence. The set of all τ-avoiding permutations in S n is denoted by S n (τ). For a collection of patterns T , α avoids T if α avoids all τ ∈ T ; the corresponding subset of S n is denoted by S n (T ).

One important and often difficult problem in the study of restricted permutations is the enumeration problem: given a set T of permutations, enumerate the set S n (T ) consisting of those permutations in S n which avoid every element of T . The first systematic study was not undertaken until 1985, when Simion and Schmidt [START_REF] Simion | Restricted Permutations[END_REF] solved the enumeration problem for every T ⊆ S 3 . More recent work on various instances of the enumeration problem may be found in [START_REF] Atkinson | Permutations which are the union of an increasing and decreasing subsequence[END_REF], [START_REF] Barcucci | Permutations avoiding and increasing number of length-increasing forbidden subsequences[END_REF], [START_REF] Bóna | Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps[END_REF], [START_REF] Bóna | The permutation classes equinumerous to the smooth class[END_REF], [START_REF] Guibert | Permutations sans sous-séquence interdite[END_REF], [START_REF] Kremer | Permutations with forbidden subsequences and a generalized Schröder number[END_REF], [START_REF] Kremer | Finite transition matrices for permutations avoiding pairs of length four patterns[END_REF], [START_REF] Mansour | Permutations avoiding a pattern from S k and at least two patterns from S 3[END_REF], [START_REF] Mansour | Layered restrictions and Chebyshev polynomials[END_REF], [START_REF] Mansour | Avoiding maximal parabolic subgroups of S k , Discrete Math[END_REF], [START_REF] Mansour | Restricted 132-avoiding permutations[END_REF], [START_REF] Mansour | Restricted permutations and Chebyshev polynomials[END_REF] and the references therein, [START_REF] Stankova | Forbidden subsequences[END_REF], [START_REF] Stankova | Classification of forbidden subsequences of length 4[END_REF], [START_REF] Stankova-Frenkel | Explicit enumeration of 321-hexagon-avoiding permutations[END_REF], [START_REF] West | Generating trees and the Catalan and Schröder numbers[END_REF], and [START_REF] West | Generating trees and forbidden subsequences Discrete Math[END_REF].

Recently, a special class of restricted permutations has arisen in the study of Schubert varieties. Green and Losonczy [START_REF] Green | Freely braided elements in Coxeter groups[END_REF] defined, for any simply laced Coxeter group, a subset of "freely braided elements" (for details, see [START_REF] Green | Freely braided elements in Coxeter groups[END_REF] and [START_REF] Green | Freely braided elements in Coxeter groups II[END_REF]), and they suggest as an open problem to enumerate the number of freely-braided permutations in S n . In this paper we give a complete answer for the number of freely-braided permutations in F n . The main result of this paper can be formulated as follows.

Theorem 1.3. The generating function for the number of freely-braided permutations in F n is given by

1 -3x -2x 2 + (1 + x) √ 1 -4x 1 -4x -x 2 + (1 -x 2 ) √ 1 -4x = 1 1 -4x -x 2 (1 -3x -x 2 + x 3 -x 2 (1 + x) 2 C(x)), where C(x) = 1- √ 1-4x 2x
is the generating function for the Catalan numbers

(C n = 1 n+1 2n n
). The proof of the above theorem is presented in Section 2.

2 Proof Theorem 1.3

Given b 1 , b 2 , . . . , b m ∈ N, we define f n (b 1 , b 2 , . . . , b m ) = #{π = π 1 π 2 . . . π n ∈ F n | π 1 π 2 . . . π m = b 1 b 2 . . . b m }.
It is natural to extend f n to the case m = 0 by setting f n (∅) = f n = #F n . The following properties of the numbers f n (b 1 , . . . , b m ) can be deduced easily from the definitions. Lemma 2.1.

(1) Let m ≥ 1 and n -2 ≥ b 1 > b 2 > • • • > b m ≥ 1. Then, for all b m + 1 ≤ j ≤ n -2, f n (b 1 , . . . , b m , j) = 0. (2) Let m ≥ 2 and n -2 ≥ b 1 > b 2 > • • • > b m ≥ 1. Then, for all b m + 1 ≤ j ≤ n -1, f n (b 1 , . . . , b m , j) = 0. (3) Let m ≥ 1 and n -2 ≥ b 1 > b 2 > • • • > b m ≥ 1. Then f n (b 1 , . . . , b m , n) = f n-1 (b 1 , . . . , b m ). (4) Let m ≥ 1 and n -2 ≥ b 1 > b 2 > • • • > b m ≥ 1. Then f n (n, b 1 , . . . , b m ) = f n (n -1, b 1 , . . . , b m ) = f n-1 (b 1 , . . . , b m ). (5) Let m ≥ 1 and n -1 ≥ b 1 > b 2 > • • • > b m ≥ 1. Then f n (b 1 , n, . . . , b m ) = f n-1 (b 1 , . . . , b m ). Proof. For (1), observe that if π ∈ S n is such that π 1 . . . π m π m+1 = b 1 . . . b m j, then the entries b m , j, n -1,
n give an occurrence of the pattern 1234 or 1243 in π.

For [START_REF] Barcucci | Permutations avoiding and increasing number of length-increasing forbidden subsequences[END_REF], observe that if π ∈ S n is such that π 1 . . . π m π m+1 = b 1 . . . b m j, then either the entries b m-1 , b m , n -1, n give an occurrence of the pattern 2134 in π or the entries b m , j, n -1, n give an occurrence of 1234 or 1243 in π. Using similar arguments as in the proof of (3) we get that (4) and ( 5) hold.

For (3), observe that if π ∈ S n is such that π 1 . . . π m π m+1 = b 1 . . . b m n, where n -2 ≥ b 1 > • • • > b m ≥ 1,
Next we introduce objects A m (n), B m (n) and C m (n) which organize suitably the information about the numbers f n (b 1 , b 2 , ..., b m ) and play an important role in the proof of the main result.

Definition 2.2. For 1 ≤ m ≤ n set A m (n) = ∑ n-2≥b 1 >b 2 >•••>b m ≥1 f n (b 1 , b 2 , . . . , b m ), B m (n) = ∑ n-2≥b 1 >b 2 >•••>b m ≥1 f n (b 1 , n -1, b 2 , b 3 , . . . , b m ), and C m (n) = ∑ n-1≥b 1 >b 2 >•••>b m ≥1 f n (b 1 , b 2 , . . . , b m ).
As before, this definition is extended to the case m = 0 by setting A 0 (n) = C 0 (n) = f n and B 0 (n) = 0.

In the following two subsections we derive expressions for A m (n) and B 1 (n), which are used in subsection 2.3 to complete the proof of Theorem 1.3.

A recurrence for the f j , also involving B 1 (n)

In the following result we derive an expression for A m (n).

Proposition 2.3.

(1) For all n ≥ 2,

A 1 (n) = f n -2 f n-1 .
(2) For all n ≥ 3,

A 2 (n) = f n -3 f n-1 + f n-2 -B 1 (n). (3) For all 2 ≤ m ≤ n -2, A m (n) = A m+1 (n) + A m (n -1) + • • • + A 0 (n -1 -m).
Proof. For (1), Definition 2.2 for A 1 (n) gives that

A 1 (n) = n-2 ∑ b 1 =1 f n (b 1 ) = f n -f n (n -1) -f n (n).
Observe that if π ∈ S n is such that π 1 = n -1 or π 1 = n, then no occurrence of the patterns 1234, 1243, 1324, 2134 in π can involve the entry π 1 . So we get that the number of permutations in F n starting with n

(resp., n -1) is f n-1 . Hence, A 1 (n) = f n -2 f n-1 , as claimed in (1). For (2), Definition 2.2 for A 1 (n) and A 2 (n) gives that A 1 (n) = A 2 (n) + n-2 ∑ b 1 =1 n ∑ b 2 =b 1 +1 f n (b 1 , b 2 ).
Using Lemma 2.1, parts (1) and ( 5), and Definition 2.2 we obtain that

A 1 (n) = A 2 (n) + B 1 (n) + A 1 (n -1) + f n-1 (n -2).
Hence, by using the proof of (1) and Definition 2.2 we get the desired result.

For (3), let 2 ≤ m ≤ n -2. Definition 2.2 yields A m (n) = A m+1 (n) + ∑ n-2≥b 1 >b 2 >•••>b m ≥1 n ∑ j=b m +1 f n (b 1 , . . . , b m , j).
Using Lemma 2.1, parts ( 2) and ( 3), we have

A m (n) = A m+1 (n) + ∑ n-2≥b 1 >b 2 >•••>b m ≥1 f n (b 1 , b 2 , . . . , b m , n) = A m+1 (n) + ∑ n-2≥b 1 >b 2 >•••>b m ≥1 f n-1 (b 1 , b 2 , . . . , b m ) = A m+1 (n) +C m (n -1).
Definition 2.2 and Lemma 2.1 (4) give

C m (n) = A m (n) + ∑ n-2≥b 2 >•••>b m ≥1 f n (n -1, b 2 , . . . , b m ) = A m (n) + ∑ n-2≥b 2 >•••>b m ≥1 f n-1 (b 2 , . . . , b m ) = A m (n) +C m-1 (n -1). (2.1)
Hence, by induction on m together with (1) we get the desired result.

We next find an explicit expression for

A m (n) in terms of A 0 (n) = f n , A 1 (n) and A 2 (n). Theorem 2.4. For all n ≥ 5 and 2 ≤ m ≤ n -2, A m (n) = ∑ j≥0 (-1) j m -1 -j j A 2 (n -j) -∑ j≥0 (-1) j m -3 -j j (A 1 (n -2 -j) + A 0 (n -3 -j)),
with the usual convention that a b = 0 if a < b or a < 0.

B 1 (n) -B 1 (n -1) = A 0 (n -2) + A 1 (n -2) + • • • + A n-4 (n -2) for all n ≥ 4.
Proof. For (2.6), by Definition 2.2 we get that

B 1 (n) = f n (n -2, n -1) + ∑ n-3≥b 1 ≥1 f n (b 1 , n -1).
Observe that if a permutation π ∈ S n is such that π 1 = n -2 and π 2 = n -1, then no occurrence of the patterns 1234, 1243, 1324, 2134 can involve either the entry n -1 or the entry n. Thus,

f n (n -2, n -1) = f n-2 = C 0 (n -2)
, and for all n ≥ 3,

B 1 (n) = C 0 (n -2) + L 1 (n)
, where we define

L m (n) = ∑ n-3≥b 1 >•••>b m ≥1 f n (b 1 , n -1, b 2 , . . . , b m ) for m ≥ 1.
Using Lemma 2.1, parts ( 1) and ( 2), we get that

L m (n) = L m+1 (n) + ∑ n-3≥b 1 >•••>b m ≥1 f n (b 1 , n -1, b 2 , . . . , b m , n),
and by Lemma 2.1, parts (3) and ( 5), together with Definition 2.2 we arrive at

L m (n) = L m+1 (n) +C m (n -2)
for all m ≥ 1. Hence, by induction on m together with the fact that L n-1 (n) = 0 we have

B 1 (n) = C 0 (n -2) +C 1 (n -2) + • • • +C n-2 (n -2), as claimed. For (2.6)
, using Equation (2.1) together with (2.6) and

C n (n) = A n-1 (n) = 0 (see Definition 2.
2) we get the desired result. Theorem 2.7. For all n ≥ 4,

B 1 (n) -B 1 (n -2) = f n-1 -2 f n-2 + f n-3 -∑ j≥0 (-1) j n-3-j j A 2 (n -1 -j) + ∑ j≥0 (-1) j n-5-j j (A 1 (n -3 -j) + A 0 (n -4 -j)).
Proof. It is easy to check that the theorem holds for n = 4, 5, 6. Now, let n ≥ 7. By using Proposition 2.6 (2.6) and Theorem 2.4 we get that

B 1 (n) -B 1 (n -1) = A 0 (n -2) + A 1 (n -2) + n-4 ∑ m=2 ∑ j≥0 (-1) j m-1-j j A 2 (n -2 -j) - n-4 ∑ m=3 ∑ j≥0 (-1) j m-3-j j (A 1 (n -4 -j) + A 0 (n -5 -j)) = A 0 (n -2) + A 1 (n -2) -A 2 (n -2) + n-4 ∑ m=1 ∑ j≥0 (-1) j m-1-j j A 2 (n -2 -j) - n-4 ∑ m=3 ∑ j≥0 (-1) j m-3-j j (A 1 (n -4 -j) + A 0 (n -5 -j)) = A 0 (n -2) + A 1 (n -2) -A 2 (n -2) + ∑ j≥0 n-5-j ∑ i= j (-1) j i j A 2 (n -2 -j) -∑ j≥0 n-7-j ∑ i= j (-1) j i j (A 1 (n -4 -j) + A 0 (n -5 -j)).
Therefore, using the identity p p + p+1 p + • • • + q p = q+1 p+1 gives that

B 1 (n) -B 1 (n -1) = A 0 (n -2) + A 1 (n -2) -A 2 (n -2) + A 2 (n -1) -A 1 (n -3) -A 0 (n -4) -∑ j≥0 (-1) j n-3-j j A 2 (n -1 -j) + ∑ j≥0 (-1) j n-5-j j (A 1 (n -3 -j) + A 0 (n -4 -j)).
Hence, using Proposition 2.3, parts (1) and ( 2), we obtain the desired identity.

Proof of Theorem 1.3

We start by showing the following result.

Lemma 2.8. Let t(x) be the generating function for the sequence

(t n ) n≥0 , that is, t(x) = ∑ n≥0 t n x n . Then ∑ n≥m x n ∑ j≥0 (-1) j n -m -j j t n-s-j = x s (1 -x) m-s t(x(1 -x)) - m-s-1 ∑ j=0 t j x j (1 -x) j .
Proof. We have

∑ n≥m x n ∑ j≥0 (-1) j n-m-j j t n-s-j = ∑ n≥0 n ∑ j=0 (-1) j n j x n+m+ j t n+m-s = ∑ n≥0 t n+m-s x n+m (1 -x) n = x s (1-x) m-s t(x(1 -x)) - m-s-1 ∑ j=0 t j x j (1 -x) j ,
as claimed.

Now we are ready to prove the main result of this paper, namely Theorem 1.3, which is restated here for easy reference.

Theorem 1.3. The generating function for the number of freely-braided permutations in F n is given by

1 -3x -2x 2 + (1 + x) √ 1 -4x 1 -4x -x 2 + (1 -x 2 ) √ 1 -4x .
Proof. We denote the generating function for the number of freely-braided permutations in F n by F(x), that is, F(x) = ∑ n≥0 f n x n . Also, we denote the generating function for the sequence {B

1 (n)} n≥0 by B(x), that is, B(x) = ∑ n≥0 B 1 (n)x n . Theorem 2.5 gives ∑ j≥0 (-1) j n -3 -j j ( f n-j -3 f n-1-j + f n-2-j -B 1 (n-j)) = 1+ ∑ j≥0 (-1) j n -5 -j j ( f n-2-j -f n-3-j ),
for all n ≥ 5. Multiplying by x n and summing over all n ≥ 5 together with using Lemma 2.8 we arrive at

-x 4 + 1 (1-x) 3 (1 -3x(1 -x) + x 2 (1 -x) 2 )F(x(1 -x)) -1 + 2x(1 -x) -B(x(1 -x)) = x 5 1-x + x 2 (1-x) 3 (F(x(1 -x)) -1 -x(1 -x) -2x 2 (1 -x) 2 ) + x 2 (1-x) 2 (F(x(1 -x)) -1 -x(1 -x)),
or equivalently,

F(x(1 -x)) - 1 (1 -x) 3 B(x(1 -x)) = 1 1 -x . (2.2)
Theorem 2.7 gives

B 1 (n) -B 1 (n -2) = f n-1 -2 f n-2 + f n-3 -∑ j≥0
(-1) j n-3-j j A 2 (n -1j) + ∑ j≥0 (-1) j n-5-j j (A 1 (n -3j) + A 0 (n -4j)), for all n ≥ 4. Multiplying by x n and summing over all n ≥ 4 together with using Lemma 2.8 we arrive at

(1x 2 )B(x) - (2.3) Using Equations 2.2 and 2.3 we get that

x 3 = x (1-x) 2 F(x) -x + x 2 (1 -x) -x (1-x) 2 ((1 -3x(1 -x) + x 2 (1 -x) 2 )F(x(1 -x)) -1 + 2x(1 -x) -B(x(1 -x))) + x 3 (1-x) 2 (F(x(1 -x)) -1 -x(1 -x)) -x
B(x(1 -x)) = (1 -x) 3 F(x(1 -x)) -(1 -x) 2 (1 + x)B(x) = -x + x(1 -x)F(x),
or equivalently,

B(x) = 1 -1- √ 1-4x 2 3 F(x) -(1 -1- √ 1-4x 2 ) 2 (1 + x)B(x) = -x + x(1 -x)F(x)
.

The rest is easy to check.

  then no occurrence of the patterns 1234, 1243, 1324, 2134 in π can involve the entry π m+1 = n. Hence, there is a bijection between the set of permutations π ∈ F n with π 1 . . . π m π m+1 = b 1 . . . b m n and the set of permutations σ ∈ F n-1 such that σ 1 . . . σ m = b 1 . . . b m .

4 1 -

 1 x (F(x(1x) -1), or equivalently,(1x 2 )B(x) = x 2x(1x)F(x(1x)) + x(1x) 2 F(x) + x (1x) 2 B(x(1x)).

  1365-8050 c 2004 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France Definition 1.1. A permutation π is said to be freely-braided if and only if π avoids each of the four patterns 1234, 1243, 1324, and 2134. We denote the set of all freely-braided permutations in S n by F n , i.e., F n = S n (1234, 1243, 1324, 2134). In[START_REF] Green | Freely braided elements in Coxeter groups[END_REF], a permutation π is "freely braided" if and only if π avoids each of the four patterns 4321, 3421, 4231, and 4312. Note, however, that a permutation π avoids these four patterns if and only if r(π) avoids each of the four patterns 1234, 1243, 1324, and 2134, where r : π 1 π 2 . . . π n → π n . . . π 2 π 1 .

	Remark 1.2. So,
	for all n ≥ 0,	#S n (1234, 1243, 1324, 2134) = #S n (4321, 4231, 4312, 3421).

Acknowledgements

I would like to thank R.M. Green and J. Losonczy for bringing to my attention the problem of finding an explicit formula for #S n (4321, 3421, 4231, 4312). Special thanks to J. Losonczy for his helpful comments.

Proof. For m = 2 we have that A 2 (n) = A 2 (n), so the theorem holds. Assume the theorem for m and all appropriate n, and let us prove the equality for m + 1. Using Proposition 2.3(3) we get that

and by the induction hypothesis, we arrive at

Using the familiar identity p 0 -p 1 + • • • + (-1) q p q = (-1) q p-1 q we obtain that

and by using the identity p q = p-1 q + p-1 q-1 we get that

Hence, by induction on m we get the desired result.

Using Theorem 2.4 for m = n -2, together with Proposition 2.3, parts (1) and ( 2), and A n-2 (n) = 1 (see Definition 2.2) we get the main result of this subsection. Theorem 2.5. For all n ≥ 5,

A recursive formula for B 1 (n)

We next we find a recurrence for B 1 (n) in terms of f n .

Proposition 2.6. We have

) for all n ≥ 3.


Josef Pieprzyk

Xian-Mo Zhang

Characterisations of Ideal Threshold Schemes

Keywords: Secret Sharing, Perfect Threshold Schemes, Ideal Threshold Schemes

Introduction

Since 1979 when threshold schemes were introduced by Blakley (Bla79) and Shamir [START_REF] Shamir | How to share a secret[END_REF], many papers in this area have been published. These papers are mostly about particular designs and applications of threshold schemes.

In this work, we are interested in characterisations of ideal threshold schemes rather than particular constructions. Of course, these characteristic properties do not depend on any form of any ideal threshold scheme. This enables us to look at any ideal threshold scheme from new points of view, and further find new results on ideal threshold schemes.

This work is structured as follows. The basic concepts of threshold schemes, and more generally, secret sharing schemes are introduced in Section 2.

In Section 3, we describe (weakly and strongly) perfect secret sharing schemes using defining matrices. By the original definition (BS92), an ideal threshold scheme is a strongly perfect threshold scheme for which the set of secrets and the set of shares have the same cardinality.

In Sections 4 and 5, we derive a series of properties of weakly perfect threshold schemes that are helpful for us to characterise ideal threshold schemes in Section 6 from different points of view. Consequently "strongly perfect" in the original definition of ideal threshold schemes can be replaced by "weakly perfect".

We further obtain more results on ideal threshold schemes in Section 7 including an application in cheating prevention. As shown in (BD91) and (BS92), we can describe secret sharing with the access structure Γ by an m × (n + 1) matrix M * in which no two rows are identical. The matrix M * has n + 1 columns indexed by 0, 1. . . . , n. The number m of rows of M * depends on a particular scheme. We index the m rows by 1, . . . , m. For a row of M * , the entry in the 0th position holds a secret and the entry in the ith position (i = 1, . . . , n) contains the corresponding share of P i . Denote the entry on the ith row and the jth column of M * by M * (i, j).

The matrix M * is called a defining matrix of secret sharing with the access scheme Γ. The matrix M obtained from M * by removing the 0th column is called the associated matrix of the scheme.

The dealer works in two stages. In the first stage, it creates the defining matrix M * for secret sharing with the access structure Γ. The matrix is made public. In the second stage, the dealer randomly chooses a row of the matrix M * . Let the row chosen be indexed by the integer i (1 ≤ i ≤ m). The secret is K = M * (i, 0) and shares are s j = M * (i, j), j = 1, . . . , n. The shares are distributed to the corresponding participants via secure channels.

Note that a defining matrix uniquely determines a secret sharing scheme but a secret sharing scheme has more defining matrices.

Permuting the rows of a defining matrix of secret sharing does not give a new scheme.

Permuting the columns of defining matrices of secret sharing is equivalent to changing the indices of participants.

It should be pointed out once again that a defining matrix of a secret sharing scheme is public.

The dealer chooses at random a single row of the matrix. The shares are communicated to the corresponding participants via secure channels so the share s i is known to the participant P i only (i = 1, . . . , n).

An access structure Γ = {A | #A ≥ t} is called a (t, n)-threshold access structure, where #X denotes the cardinality of the set X (i.e. the number of elements in the set X) and the integer t is called the threshold of secret sharing, where t ≤ n.

Secret sharing schemes with the (t, n)-threshold access structure are called (t, n)-threshold schemes.

Threshold schemes were first introduced by Blakley (Bla79) and Shamir (Sha79). Ito et al (ISN87) generalised threshold schemes for arbitrary access structure.

Perfect Secret Sharing And Ideal Secret Sharing

We say that secret sharing with the access structure Γ is perfect if the following two conditions are satisfied:

(1) If A ∈ Γ then the participants in A can uniquely determine the secret by pooling their shares together.

(2) If A ∈ Γ then the participants from A can determine nothing about the secret (in an information theoretic sense).

As mentioned in (BS92), Conditions (1) and (2) can be translated into conditions that need to be satisfied in the context of the defining matrix. We list the translations as follows.

(a) Let A ∈ Γ. If M * (i, j) = M * (i ′ , j) for every P j ∈ A then M * (i, 0) = M * (i ′ , 0). (b) Let A ∈ Γ.
For any 1 ≤ i 0 ≤ m and any K ∈ K, there exists some i with 1 ≤ i ≤ m such that M * (i, j) = M * (i 0 , j) for all P j ∈ A and M * (i, 0) = K.

(b') Let A = {P j 1 , . . . , P j ℓ } ∈ Γ. For any s j 1 , . . . , s j ℓ ∈ S and any K ∈ K, For the case of a (t, n)-threshold scheme, Conditions (a), (b), and (b') can be rewritten as follows:

#{i | M * (i, j u ) = s j u for all P j u ∈ A and M * (i, 0) = K} is independent to the choice of K.
(c) Let #A ≥ t. If M * (i, j) = M * (i ′ , j) for every P j ∈ A then M * (i, 0) = M * (i ′ , 0). (d) Let #A < t.
For any 1 ≤ i 0 ≤ m and any K ∈ K, there exists some i with 1 ≤ i ≤ m such that M * (i, j) = M * (i 0 , j) for all P j ∈ A and M * (i, 0) = K.

(d') Let A = {P j 1 , . . . , P j ℓ } with ℓ < t. For any s j 1 , . . . , s j ℓ ∈ S and any K ∈ K,

#{i | M * (i, j u ) = s j u for all P j u ∈ A and M * (i, 0) = K} is independent to the choice of K.

Similarly, (d') implies (d).

The following definition is due to (BS92).

Definition 1 A secret sharing scheme satisfying (a) and (b) is called weakly perfect. Alternatively, a (t, n)-threshold scheme satisfying (c) and (d) is called weakly perfect.

In (BS92) the following definition is given.

Definition 2 A secret sharing scheme satisfying (a) and (b') is called strongly perfect, or more briefly perfect if no confusion occurs. Alternatively, a (t, n)-threshold scheme satisfying (c) and (d') is called strongly perfect, or more briefly perfect if no confusion occurs.

As mentioned in (BS92), for any strongly perfect secret sharing scheme, we have #K ≤ #S. In particular, if #K = #S holds for a strongly secret sharing scheme, from (BS92), we have the following definition.

Definition 3 An ideal secret sharing scheme is a strongly perfect secret sharing scheme satisfying #K = #S. Alternatively, an ideal threshold scheme is a strongly perfect threshold scheme satisfying #K = #S.

In this work we pay our attention to ideal threshold schemes. New results on weakly perfect threshold schemes in this work are helpful for characterising ideal threshold schemes.

Properties of Weakly Perfect Threshold Schemes (I)

It should be noted that the inequality #K ≤ #S also holds for any weakly perfect secret sharing scheme. The proof can be found from (PZ02). Then we state as follows.

Lemma 1 #K ≤ #S holds for any weakly perfect secret sharing scheme.

Lemma 2 Let a (t, n)-threshold scheme be weakly perfect. If #K = #S then its defining matrix M * has the following property. For any given t -

1 integers, 1 ≤ j 1 < • • • < j t-1 ≤ n, if M * (i 0 , 0) = M * (i ′ , 0), M * (i 0 , j 1 ) = M * (i ′ , j 1 ), . . ., M * (i 0 , j t-1 ) = M * (i ′ , j t-1 ) then M * (i 0 , j) = M * (i ′ , j), j = 0, 1, . . . , n. Proof Set M * (i 0 , 0) = M * (i ′ , 0) = K, M * (i 0 , j 1 ) = M * (i ′ , j 1 ) = s j 1 , . . . , M * (i 0 , j t-1 ) = M * (i ′ , j t-1 ) = s j t-1
(1)

Let #K = #S = b. Write K = {K 1 , . . . , K b } and S = {ε 1 , . . . , ε b }.
Let M * contain precisely m rows. Thus M * be an m × (n + 1) matrix. We index the rows of M * by 1, . . . , m, and index the columns by 0, 1, . . . , n. Consider the m × t matrix M 0 , consisting of the t columns of M * indexed by 0, j 1 , . . . , j t-1 .

Let j t be an integer satisfying 1 ≤ j t ≤ n and j t ∈ { j 1 , . . . , j t-1 }. Without loss of generality, we assume that j t > j t-1 . Let M 1 denote a m × (t + 1) matrix consisting of the t + 1 columns of M * indexed by 0, j 1 , . . . , j t-1 , j t .

Let ℜ i , i = 1, . . . , b, denote the subset of S such that ε ∈ ℜ i if and only if (K i , s j 1 , . . . ,

s j t-1 , ε) is a row of M 1 .
Since (K, s j 1 , . . . , s j t-1 ) is a row of M 0 , due to Condition (d), we know that (K i , s j 1 , . . . , s j t-1 ) is a row of M 0 , i = 1, . . . , b, and thus #ℜ i > 0, i = 1, . . . , b. Due to Condition (c), we have

ℜ i ∩ ℜ j = / 0, if j = i
where / 0 denotes the empty set. Thus we have #(

ℜ 1 ∪ • • • ∪ ℜ b ) = #ℜ 1 + • • • + #ℜ b ≥ b. On the other hand ℜ 1 ∪ • • • ∪ ℜ b ⊆ S and then #(ℜ 1 ∪ • • • ∪ ℜ b ) ≤ #S = b. Therefore we know that b = #S = #ℜ 1 + • • • + #ℜ b . Recall that #ℜ i > 0, i = 1, . . . , b. Then we have #ℜ i = 1, i = 1, . . . , b (2)
From (2) and (1), we know that M * (i 0 , j t ) = M * (i ′ , j t ). Since j t is an arbitrary integer with 1 ≤ j t ≤ n and j t ∈ {0, j 1 , . . . , j t-1 }, we have proved that M * (i 0 , j) = M * (i ′ , j), j = 0, 1, . . . , n. ✷ Lemma 3 Let a (t, n)-threshold scheme be weakly perfect. If #K = #S then its defining matrix M * has the following property. For any given t integers

1 ≤ j 1 < • • • < j t ≤ n, if M * (i 0 , j 1 ) = M * (i ′ , j 1 ), . . ., M * (i 0 , j t ) = M * (i ′ , j t ) then M * (i 0 , j) = M * (i ′ , j), j = 0, 1, . . . , n.
Proof Due to the equalities in the lemma, by using Condition (c), we know that M * (i 0 , 0) = M * (i ′ , 0). According to Lemma 2, the equalities in the lemma and M * (i 0 , 0) = M * (i ′ , 0) together imply that M * (i 0 , j) = M * (i ′ , j), j = 0, 1, . . . , n. ✷ Summarising Lemmas 2 and 3, we conclude as follows.

Corollary 1 Let a (t, n)-threshold scheme be weakly perfect. If #K = #S then its defining matrix M * has the following property. For any t given integers, 0 ≤ j 1 < • • • < j t ≤ n, the submatrix M ′ of M * , consisting of t columns indexed by j 1 , . . . , j t , does not contain two identical rows.

Proof We prove the corollary by contradiction. Assume that M ′ contains two identical rows then there exist integers i 0 and i ′ such that i 0 = i ′ and M * (i 0 , j 1 ) = M * (i ′ , j 1 ), . . . , M * (i 0 , j t ) = M * (i ′ , j t ). According to Lemmas 2 and 3, M * (i 0 , j) = M * (i ′ , j), j = 0, 1, . . . , n. On the other hand, M * , as a defining matrix of a secret sharing, does not contain two identical rows. The contradiction proves that all the rows of M ′ are mutually distinct. ✷

Properties of Weakly Perfect Threshold Schemes (II)

Weakly perfect threshold schemes have further properties.

Lemma 4 Let a (t, n)-threshold scheme be weakly perfect. If #K = #S then its defining matrix M * has the following property. For any t given integers, 1 ≤ j 1 < • • • < j t ≤ n, the submatrix M ′ of M * , consisting of t columns indexed by j 1 , . . . , j t , contains any given row vector (s j 1 , . . . , s j t ) where each s j ∈ S. Thus M * be an m × (n + 1) matrix. We index the rows of M * by 1, . . . , m, and index the columns by 0, 1, . . . , n.

Proof

Consider the 1st row of M * . Write M * (1, 0) = K, M * (1, j 1 ) = a j 1 , . . ., M * (1, j t-1 ) = a j t-1 . Let M ′′ be the submatrix of M * , consisting of t + 1 columns indexed by 0, j 1 , . . . , j t . Let ℜ i , i = 1, . . . , b, denote the subset of S such that ε ∈ ℜ i if and only if (K i , a j 1 , . . . ,

a j t-1 , ε) is a row of M ′′ .
From the proof of Lemma 2, we know that #ℜ i = 1, i = 1, . . . , b, and then it is easy to find that ℜ 1 ∪ • • • ∪ ℜ b = S. Thus there exists some i t with 1 ≤ i t ≤ b such that ℜ i t = {s j t }. By the definition of ℜ i t , we know that (K i t , a j 1 , . . . , a j t-1 , s j t ) is a row of M ′′ .

Using the same arguments as above, we can prove that there exists some i t-1 with 1

≤ i t-1 ≤ b such that (K i t-1 , a j 1 , . . . , a j t-2 , s j t-1 , s j t ) is a row of M ′′ .
Repeatedly, we can prove that there exists some i 1 with 1 ≤ i 1 ≤ b such that (K i 1 , s j 1 , . . . , s j t-2 , s j t-1 , s j t ) is a row of M ′′ . Therefore we have proved that (s j 1 , . . . , s j t ) is a row of M ′ . ✷ Lemma 5 Let a (t, n)-threshold scheme be weakly perfect. If #K = #S then its defining matrix M * has the following property. For any given t -1 integers, 1 ≤ j 2 < • • • < j t ≤ n, the submatrix M ′ of M * , consisting of t columns indexed by 0, j 2 , . . . , j t , contains any given row vector (K, s j 2 , . . . , s j t ) where K ∈ K and each s j ∈ S.

Proof Let M 1 denote the m × (t -1) matrix, consisting of the t -1 columns of M * indexed by j 2 , . . . , j t . According to Lemma 4, M 1 contains the row (s j 2 , . . . , s j t ). Due to Condition (d), M ′ contains a row (K, s j 2 , . . . , s j t ). ✷

Combining Lemmas 4 and 5, we get the following corollary.

Corollary 2 Let a (t, n)-threshold scheme be weakly perfect. If #K = #S then its defining matrix has the following property. For any given t integers, 0 ≤ j 1 < • • • < j t ≤ n, the submatrix of M * , consisting of t columns indexed by j 1 , . . . , j t , contains any given row vector (s j 1 , . . . , s j t ) (when j 1 > 0) and any given row vector (K, s j 2 , . . . , s j t ) (when j 1 = 0), where each s j ∈ S and K ∈ K.

Characteristic Properties of Ideal Threshold Schemes

Combing Corollaries 1 and 2, we formulate the following statement.

Theorem 1 Let a (t, n)-threshold scheme be weakly perfect. If #K = #S then its defining matrix M * has the following property. For any given t integers, 0 ≤ j 1 < • • • < j t ≤ n, the submatrix of M * , consisting of t columns indexed by j 1 , . . . , j t , contains any given row vector (s j 1 , . . . , s j t ) (when j 1 > 0) and any given row vector (K, s j 2 , . . . , s j t ) (when j 1 = 0), where each s j ∈ S and K ∈ K, precisely once.

We can prove the converse of Theorem 1. However we have a stronger statement as follows.

Theorem 2 Let a defining matrix M * of a (t, n)-threshold scheme satisfy the following property. For any given t integers, 0 ≤ j 1 < • • • < j t ≤ n, the submatrix of M * , consisting of t columns indexed by j 1 , . . . , j t , contains any given row vector (s j 1 , . . . , s j t ) (when j 1 > 0) and any given row vector (K, s j 2 , . . . , s j t ) (when j 1 = 0), where each s j ∈ S and K ∈ K, precisely once. Then (i) the scheme is strongly perfect, (ii) #K = #S, and then the scheme is ideal.

Proof

(i) Let {P j 1 , . . . , P j ℓ } be the set of currently active participants. We first verify Condition (c). Let ℓ ≥ t.

If M * (i, j 1 ) = M * (i ′ , j 1 ), . . . , M * (i, j ℓ ) = M * (i ′ , j ℓ ), due to the property of M * , it follows that i = i ′ . Clearly (c) is satisfied.

We next verify Condition (d'). Let ℓ < t and M 1 denote the submatrix of M * , consisting of the ℓ + 1 columns of M * indexed by 0, j 1 , . . ., j ℓ . Let K ∈ K and s j 1 , . . . , s j ℓ ∈ S. Since ℓ < t, we know that 1 + ℓ ≤ t. There are two cases to be considered: 1 + ℓ < t and 1 + ℓ = t

Case 1: 1 + ℓ < t.

Then t -ℓ ≥ 2 and then there are t -ℓ-1(> 0) integers, 1 ≤ j ℓ+1 < • • • < j t-1 ≤ n, such that { j ℓ+1 , . . . , j t-1 } ∩ { j 1 , . . . , j ℓ } = / 0. Without loss of generality, we assume that j ℓ < j ℓ+1 < • • • < j t-1 . Let M 2 denote the submatrix of M * , consisting of t columns of M * indexed by 0, j 1 , . . ., j ℓ , j ℓ+1 , . . ., j t-1 . According to the property of M * , for any given a j ℓ+1 , . . . , a j t-1 ∈ S, M 2 contains (K, s j 1 , . . . , s j ℓ , a j ℓ+1 , . . . , a j t-1 ) precisely once. Since (a j ℓ+1 , . . . , a j t-1 ) has precisely b t-ℓ-1 different choices, we know that M 1 , as a submatrix of M 2 , contains the row (K, s j 1 , . . . , s j ℓ ) precisely b t-ℓ-1 times. Clearly the value of b t-ℓ-1 is independent to the choice of K. We have verified condition (d') in Case i1.

For any (n, R, d) b code, the following inequality holds and it is known as the Singleton bound (MS78), (PH98), [START_REF] Roman | Coding and information theory[END_REF],

N b (n, d) ≤ b n-d+1
(3)

t = #℧ ≤ N b (n, d) ≤ b n-d+1 and then t ≤ n -d + 1. From t ≤ n -d + 1 and d ≥ n -t + 1, we conclude that d = n -t + 1. This proves that ℧ is an (n, b t , n -t + 1) b code.
We next prove the sufficiency of the lemma. Assume that all the b t rows of matrix O form an (n, b t , nt + 1) b code. Then the Hamming distance between any two distinct row vectors is at least nt + 1, in other words, any two distinct row vectors are the same in at most t -1 coordinates. Therefore, all the b t row vectors of any b t × t submatrix O 1 of O are mutually distinct, in other words, O 1 contains all b t possible row vectors each precisely once. This proves that O is an orthogonal array (b t , n, b,t) of index unity. ✷

Theorem 12 in Chapter 11 of (MS78) is a special case of Lemma 9 when both orthogonal array and code are linear. This implies that the entries in both array and code should be certain algebraic elements. Also the proof is based on coding theory. In contrast, Lemma 9 is more general and its proof does not require the set B to have any algebraic properties.

There exist many known optimal codes, for instance, cyclic codes of prime length, (some) global quadratic residue codes, Reed-Solomon codes, and more generally, MDS codes. The detailed description of such codes can be found from (MS78), (PH98), [START_REF] Roman | Coding and information theory[END_REF]. It should be noted that an optimal code is not necessarily an MDS code, as an MDS code is a special optimal code when all its codewords form a linear space. This requires the elements in the set B to have certain algebraic properties.

Lemma 10 There exists an ideal (t, n)-threshold scheme if and only if there exists an orthogonal array (b t , n + 1, b,t) of index unity where b = #K = #S.

Proof Due to (iv) of Theorem 3, the sufficiency is obvious. We only need to prove the necessity. Assume that there exists an ideal (t, n)-threshold scheme. Since #S = #K, there exists a mapping χ from K to S such that χ(K) = S, and χ(k ′ ) = χ(k ′′ ) if k ′ = k ′′ . Thus we obtain a new ideal threshold scheme from the given one by changing each k to χ(k). We note that in the new ideal threshold scheme the set of secrets is identical with the set of shares. According to (iv) of Theorem 3, any defining matrix M * of the new scheme is an orthogonal array (b t , n + 1, b,t). ✷

According to Theorem 3, Lemma 9 and Lemma 10, we can state as follows.

Theorem 4 The following statements are equivalent:

(i) there exists an ideal (t, n)-threshold scheme,

  1365-8050 c 2004 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

Condition ( 1 )

 1 is corresponding to Condition a. Condition (2) has two translations: Condition (b) and Condition (b'). It is easy to verify that (b') implies (b).

  Let #K = #S = b. Write K = {K 1 , . . . , K b } and S = {ε 1 , . . . , ε b }. Let M * contain precisely m rows.

Lemma 9

 9 A b t × n matrix O with entries from b-set B is an orthogonal array (b t , n, b,t) of index unity if and only if all the b t row vectors of O form an (n, b t , nt + 1) b (optimal) code. Proof We first indicate that an (n, b t , n-t +1) b code ℑ must be optimal. In fact, #ℑ = b t and d = n-t +1. Thus #ℑ = b n-d+1 . According to (3), we have b n-d+1 = #ℑ ≤ N b (n, d) ≤ b n-d+1 . Thus #ℑ = N b (n, d) and thus we have proved that (n, b t , nt + 1) b code is optimal. We now prove the necessity of the lemma. Assume that O is an orthogonal array (b t , n, b,t) of index unity. It is easy to verify that any two rows of O are the same in at most t -1 corresponding coordinates. In other words, any two rows of O differ in at least nt + 1 corresponding coordinates. Thus all the b t row vectors of O form an (n, b t , d) b code ℧ where d ≥ nt + 1. On the other hand, from (3), we have b

Case 2: 1 + ℓ = t.

According to the property of M * , M 1 contains the row (K, s j 1 , . . . , s j ℓ ), where ℓ = t -1, precisely once. Thus condition (d') is satisfied in Case i2.

Summarising cases i1 and i2, we conclude that the scheme is strongly perfect. (i) has been proved.

(ii) Let M ′ be the submatrix of M * , consisting of t columns indexed by 1, . . . , t, M 0 be the submatrix of M * , consisting of t columns indexed by 0, 1, . . . , t -1, and M ′ 0 be the submatrix of M * , consisting of t -1 columns indexed by 1, . . . ,t -1. We fix a 1 , . . . , a t-1 ∈ S. Due to the property of M * , for each s ∈ S, M ′ contains the row (a 1 , . . . , a t-1 , s) precisely once. Thus M ′ 0 contains the row (a 1 , . . . , a t-1 ) precisely #S times. On the other hand, due to the property of M * , for each K ∈ K, M 0 contains the row (K, a 1 , . . . , a t-1 ) precisely once. Thus M ′ 0 contains the row (a 1 , . . . , a t-1 ) precisely #K times. It follows that #K = #S. We have proved (ii).

By definition, (i) and (ii) together imply that the scheme is ideal. ✷ Theorem 3 For a (t, n)-threshold scheme, the following statements are equivalent:

(i) the scheme is ideal, (ii) the scheme is weakly perfect and #K = #S, (iii) the scheme is strongly perfect and #K = #S, (iv) its defining matrix M * has the following property. For any given t integers, 0

the submatrix of M * , consisting of t columns indexed by j 1 , . . . , j t , contains any given row vector (s j 1 , . . . , s j t ) (when j 1 > 0) and any given row vector (K, s j 2 , . . . , s j t ) (when j 1 = 0), where each s j ∈ S and K ∈ K, precisely once.

Proof According to Theorem 1, (ii) implies (iv). Due to Theorem 2, (iv) implies (i). By definition, (i) implies (iii). It is obvious that (iii) implies (ii). The proof is completed. ✷

From Lemma 1, #K ≤ #S holds for any weakly perfect threshold scheme. Thus due to Theorem 3, ideal threshold schemes are a critical case of weakly perfect threshold schemes when #K = #S. Therefore it is interesting that "strongly perfect" in Definition 3 can be replaced by "weakly perfect".

From (iv) of Theorem 3, we formulate the following conclusion:

Corollary 3 A defining matrix of any ideal (t, n)-threshold scheme has the size b t × (n + 1) where b = #K = #S. In other words, any ideal (t, n)-threshold scheme has precisely b t possible shares vectors.

Other Properties with Applications

From the proof of Theorem 2, we know Corollary 4 If a (t, n)-threshold scheme is ideal then its defining matrix M * has the following property. For any ℓ (0 < ℓ ≤ t) integers, 0 ≤ j 1 < • • • < j ℓ ≤ n, the submatrix of M * , consisting of ℓ columns indexed by j 1 , . . . , j ℓ , contains all b ℓ possible rows each precisely b t-ℓ times, where #K = #S = b. In particular, the jth ( j = 1, . . . , n) column of M * contains all elements in S each precisely b t-1 times, and the 0th column of M * contains all elements in K each precisely b t-1 times.

Corollary 5 If a (t, n)-threshold scheme is ideal then its defining matrix M * has the following property. Any two row vectors of M * are the same in at most t -1 corresponding coordinates, or equivalently, any two row vectors of M * differ in at least nt + 2 corresponding coordinates.

Proof Due to Theorem 3, M * is a b t × (n + 1) matrix, where #K = #S = b. Let i ′ and i 0 be two integers with 1 ≤ i 0 < i ′ ≤ b t . Then the i 0 th row vector of M * is (M * (i 0 , 0), M * (i 0 , 1), . . . , M * (i 0 , n)), and the i ′ th row vector of

According to (iv) of Theorem 3, there exist at most t -1 integers, 0

). In other words, the i 0 th row vector and the i ′ th row vector differ in at least nt + 2 coordinates. ✷

The next corollary immediately follows Corollary 5.

Corollary 6 Let M * be a defining matrix of an ideal (t, n)-threshold scheme, ℓ be any integer with t ≤ ℓ ≤ n and M 1 be any b t × ℓ submatrix of matrix M * where b = #K = #S. Then any two row vectors of M 1 are the same in at most t -1 corresponding coordinates, or equivalently, any two row vectors of M 1 differ in at least ℓt + 1 corresponding coordinates.

In this section we show an application of Corollary 6. Consider an ideal (t, n)-threshold scheme with its defining matrix M * and associated matrix M. Assume that the dealer chooses the i 0 th row vector (s 1 , . . . , s n ) of M and assigns s 1 , . . . , s n to participants P 1 , . . . , P n , respectively. Let {P j 1 , . . . , P j ℓ } with t ≤ ℓ ≤ n be a subset of active participants. Let M 1 be the b t × ℓ submatrix of M, consisting of ℓ columns indexed by j 1 , . . . , j ℓ .

Denote the ith row vector of M 1 by L i . Clearly, the row i 0 of M 1 is L i 0 = (s j 1 , . . . , s j ℓ ). Let there exist u cheaters, among the active participants P j 1 , . . ., P j ℓ , who submit modified shares to the combiner while the honest active participants submit correct shares to the combiner. Assume that the combiner receives the shares s ′ j 1 , . . . , s ′ j ℓ sent by P j 1 , . . ., P j ℓ , where s ′ j i = s j i if and only if P j i is honest. Write L ′ = (s ′ j 1 , . . . , s ′ j ℓ ). Clearly, dist(L ′ , L i 0 ) = u, where dist(X,Y ) denotes the number of coordinates in which vectors X and Y differ. We call dist(X,Y ) the Hamming distance between vectors X and Y .

Let

We first prove that u = 0 if and only if d m = 0. The necessity is obvious. We next prove the sufficiency. Let d m = 0. We now prove that u = 0 by contradiction. Assume that u = 0. Clearly d m = 0 implies that L ′ must be identical with a row of M 1 . Thus

The contradiction proves that u = 0. Therefore, in the case of u ≤ ℓt, the combiner (recovery algorithm) calculates d m , then it can conclude that L ′ = (s ′ j 1 , . . . , s ′ j ℓ ) is correct or incorrect (i.e. u = 0 or u = 0) according to d m = 0 or d m = 0.

We further indicate that the correct shares can be found and the cheaters can be identified when 1 ≤ u ≤ ⌊ 1 2 (ℓt)⌋, where ⌊ 1 2 (ℓt)⌋ denotes the greatest integer not larger than 1 2 (ℓt). The combiner can find a row L i 2 of M 1 such that dist(L ′ , L i 2 ) = d m where d m has been defined in this section. We now prove that L i 2 is identical with L i 0 = (s j 1 , . . . , s j ℓ ). Assume otherwise, then

The contradiction proves that L i 2 = L i 0 . Thus the correct vector L i 2 = L i 0 = (s j 1 , . . . , s j ℓ ) has been found. Comparing L ′ with L i 0 (i.e. L i 2 ), the combiner (recovery algorithm) can determine who are cheaters.

It should be noted that such ability of ideal threshold schemes in cheating prevention is not based on particular constructions or particular descriptions.

More Characteristic Properties

If we simplify the condition #S = #K by S = K, the properties of ideal threshold schemes will be more interesting.

Orthogonal arrays were introduced more than fifty years ago as a combinatorial problem [START_REF] Bush | Orthogonal arrays of index unity[END_REF]. Clearly m = λb t . The parameters m, t and λ are called the size, the strength and the index of the orthogonal array, respectively, while n is called the number of constraints and b is called the number of levels.

Lemma 6 An orthogonal array (m, n, b,t) with an index λ is an orthogonal array (m, n, b, ℓ) with an index λb t-ℓ where ℓ is any integer with 1 ≤ ℓ ≤ t.

In particular, we can formulate the following corollary. (m,n,b,t) with entries from a b-set B contains each element of B precisely λb t-1 times, where λ is the index of the orthogonal array.

Corollary 7 Each column of an orthogonal array

Lemma 7

Let O 1 be an m × n 1 submatrix of an orthogonal array (m, n, b,t) with an index λ. If n 1 ≥ t then O 1 is an orthogonal array (m, n 1 , b,t) with an index λ.

In particular, orthogonal arrays with index λ = 1 are used in this work.

Definition 5 An orthogonal array with index λ = 1, i.e, an orthogonal array (b t , n, b,t) is called an orthogonal array (b t , n, b,t) of index unity.

Orthogonal arrays (b t , n, b,t) of index unity have many interesting properties. The following bounds on the number of constraints for orthogonal arrays (b t , n, b,t) were proved by Bush (Bus52):

Lemma 8 For an orthogonal array (b t , n, b,t) of index unity, we have

According to (iv) of Theorem 3, a defining matrix of an ideal (t, n)-threshold scheme with K = S, is an orthogonal array (b t , n + 1, b,t) of index unity.

We next briefly recall the concept of codes. Let B = {ε 1 , . . . , ε b } be a finite set and B n be the set of all strings of length n over B. (ii) there exists a weakly perfect threshold scheme with #K = #S, (iii) there exists a strongly perfect threshold scheme with #K = #S, (iv) there exists an orthogonal array (b t , n + 1, b,t) of index unity where b = #K = #S, (v) there exists an (n + 1, b t , nt + 2) b (optimal) code.

According to Theorem 4, the existence of orthogonal arrays and the existence of optimal codes ensure the existence of ideal threshold schemes. Theorem 4 is helpful for us to examine ideal threshold schemes from different points of view.

On Parameters of Ideal Threshold Schemes

According to Lemma 8 and Theorem 4, there are some bounds on the parameters of ideal threshold schemes.

Theorem 5 Ideal (t, n)-threshold schemes exist only when

Proof Assume that there exists an ideal (t, n)-threshold scheme. From Theorem 4, there exists an orthogonal array (b t , n + 1, b,t) of index unity where b = #K = #S. By using Lemma 8, it is easy to verify (i) and (ii). For the case of b ≤ t, by using Lemma 8, we know that n + 1 ≤ t + 1 i.e. n ≤ t. On the other hand, for a (t, n)-threshold scheme, we always have t ≤ n. Therefore we conclude that n = t and then (iii) is true. ✷

We note that n ≥ t always holds. However we usually need (t, n)-threshold schemes with n > t. According to Theorem 5, for clarity, we state as follows.

Corollary 8 Ideal (t, n)-threshold schemes with n > t exist only when b > t where #S = #K = b.

Remarks

We now compare this work with other previous results.

A characterisation of perfect threshold schemes can be found from (SV88). More precisely, (SV88) proved that there exists a perfect (t, w)-threshold scheme with v shares and m secrets if and only if there exist m mutually t-compatible w-uniform hypergraphs on v points. It is not hard to verify that the "perfect" defined in (SV88) is equivalent to the "strongly perfect", or more briefly the "perfect", defined in [START_REF] Brickell | Some improved bounds on information rate of perfect sharing schemes[END_REF]. A basic difference between this work and (SV88) is that in this paper we work on characterisations of ideal threshold schemes.

All the results on ideal threshold schemes discussed in (PZ02) depend on a particular description of schemes by orthogonal arrays. However this does not automatically mean that these results are available for all ideal threshold schemes. To do so, it should be proved that the existence of orthogonal arrays is necessary for the existence of ideal threshold schemes. This needs much more work as done in this paper.

Conclusions

We have found a series of properties of weakly perfect threshold schemes. Based on this, we have derived a number of necessary and sufficient conditions for ideal threshold schemes from different approaches. Therefore we have examined ideal threshold schemes from new points of view and obtained new results on ideal threshold schemes.


Hon-Chan Chen
email: chenhc@chinyi.ncit.edu.tw

Optimal Sequential and Parallel Algorithms for Cut Vertices and Bridges on Trapezoid Graphs †

Keywords: cut vertex, bridge, trapezoid graph, algorithm

In this paper, we will propose new O(n) algorithms for finding cut vertices and bridges of a trapezoid graph, assuming the trapezoid diagram is given. Our algorithms can be easily parallelized on the EREW PRAM computational model so that cut vertices and bridges can be found in O(log n) time by using O( n log n ) processors.

Introduction

Let G = (V, E) be a graph with vertex set V and edge set E.

A graph H = (V ′ , E ′ ) is a subgraph of G if V ′ ⊆ V and E ′ ⊆ E. If H is a maximal connected subgraph, then H is a component of G. Let G -v, v ∈ V ,
be the graph obtained by deleting v and all edges incident to v from G. A vertex v is called a cut vertex of G if κ(Gv) > κ(G), where κ(G) is the number of components in G. Similarly, let Ge, e ∈ E, be the graph obtained by deleting e from G, and an edge e is a bridge of G if κ(Ge) > κ(G).

The class of trapezoid graphs is introduced by Dagan et al. [START_REF] Dagan | Trapezoid Graphs and Their Coloring[END_REF] and independently by Corneil et al. [START_REF] Corneil | Extensions of Permutation and Interval Graphs[END_REF]. It is a superclass of interval graphs and permutation graphs. A trapezoid graph G can be represented by a trapezoid diagram. In the diagram, a trapezoid i is defined by four corner points a i , b i , c i , and d i , which stand for the upper left, the upper right, the lower left, and the lower right corner of i, respectively. We assume that trapezoids are labeled in increasing order of their b corner points. Each trapezoid in the diagram corresponds to a distinct vertex of G, and (i, j) is an edge of G if and only if trapezoid i intersects trapezoid j in the diagram. Figure 1 shows an example of a trapezoid graph. A trapezoid graph can be recognized in O(n 2 ) time by Ma and Spinrad's algorithm [START_REF] Ma | On the 2-Chain Subgraph Cover and Related Problems[END_REF]. Applying their algorithm, the corresponding trapezoid diagram can be constructed. It is easy to see that for any three vertices i, j, and k of a trapezoid graph, where i < j < k, if i is adjacent to k, then j is adjacent to i or k. Generally, the input for a trapezoid graph is O(n), according to the number of vertices. The number of edges could be more, but it is generally not an issue for algorithms in this class of graphs.

The problem of finding cut vertices and bridges on graphs is well-known. It can be solved sequentially in O(n + m) time by a depth-first search algorithm [START_REF] Tarjan | Depth-First Search and Linear Graph Algorithms[END_REF], where n is the number of vertices and m the number of edges. Parallel algorithms for this problem on general graphs can be found in [START_REF] Tarjan | An Efficient Parallel Biconnectivity Algorithm[END_REF][START_REF] Tsin | Efficient Parallel Algorithms for a Class of Graph Theoretic Problems[END_REF]. If we restrict ourselves to special types of graphs, the complexity of finding cut vertices and bridges can be reduced. For example, in [START_REF] Sprague | Optimal Parallel Algorithms for Finding Cut Vertices and Bridges of Interval Graphs[END_REF], Sprague et al. presented optimal parallel algorithms for this problem on interval graphs. The complexity of their algorithms is O(log n) time using O( n log n ) processors on the EREW PRAM computational model if the endpoints of intervals are sorted. Optimal parallel algorithms for finding cut vertices and bridges on permutation graphs were proposed by Arvind et al. [START_REF] Arvind | Efficient Parallel Algorithms for Permutation Graphs[END_REF], which also take O(log n) time with O( n log n ) processors on the EREW PRAM model. An O(n) time algorithm for the depth-first search on trapezoid graphs was proposed by Chen et al. [START_REF] Chen | A Linear Time Algorithm for Finding Depth-First Spanning Trees on Trapezoid Graphs[END_REF], but they did not describe the way to find cut vertices. Recently, Hota et al. have presented optimal sequential and parallel algorithms to compute all cut vertices on trapezoid graphs [START_REF] Hota | Optimal Sequential and Parallel Algorithms to Compute All Cut Vertices on Trapezoid Graphs[END_REF]. The complexities of their algorithms are O(n) time for sequential computation and O(log n) time with O( n log n ) processors on the EREW PRAM model for parallel computation. However, their algorithms are not simple because they recognize a cut vertex by many types of connectivity. Moreover, they did not address how to find bridges by cut vertices. In this paper, we propose a simpler O(n) algorithm for finding cut vertices and the first O(n) algorithm for finding bridges on a trapezoid graph, assuming the trapezoid diagram is given. Our algorithms can be easily parallelized on the EREW PRAM model so that cut vertices and bridges can be found in O(log n) time by using O( n log n ) processors. The algorithms on this paper use the properties of vertex adjacency instead of the corner points. These properties are new and interesting.

The rest of this paper is organized as follows. In Section 2, we introduce an easy way to find a dominat-ing path of a trapezoid graph. In Sections 3 and 4, the algorithms of finding cut vertices and bridges are presented respectively. The parallelization of our algorithms is shown in Section 5. Finally, in Section 6, we give the concluding remarks of this paper.

Preliminaries

Let G be a connected trapezoid graph of n vertices which are labeled by 1, 2, • • • , n in increasing order of their b corner points. A path P of G is a dominating path if every vertex v of G, v ∈ P, is adjacent to at least one vertex of P. It is obvious that any vertex v ∈ P is not a cut vertex since graph Gv remains connected. There may be many different dominating paths in G, and the minimum dominating path can be found in O(n) time by Köhler's algorithm [START_REF] Köhler | Connected Domination and Dominating Clique in Trapezoid Graphs[END_REF]. However, for a trapezoid graph, a path connecting vertices 1 and n is also a dominating path. We call such a path a (1, n)-path. The following describes an easy way to find a (1, n)-path.

Let v be a vertex of G. The maximal neighbor (minimal neighbor, respectively) of v, denoted by For example, in Figure 1, the maximal label of a corner point left to b 5 is 5, and the maximal label of c corner point left to d 5 is 6. Then, N max [START_REF] Hota | Optimal Sequential and Parallel Algorithms to Compute All Cut Vertices on Trapezoid Graphs[END_REF] = max{5, 6} = 6. Moreover, N min [START_REF] Hota | Optimal Sequential and Parallel Algorithms to Compute All Cut Vertices on Trapezoid Graphs[END_REF] = min{4, 1} = 1 since the minimal label of b corner point right to a 5 is 4 and the minimal label of d corner point right to c 5 is 1. Trivially, all maximal and minimal neighbors can be determined in O(n) time if we record each latest maximal label and minimal label respectively during our scanning.

N max [v] (N min [v], respectively), is the vertex in N[v]
For any vertex v of G, the superior pair of v, denoted by A v , is the pair

[i, N max [i]] such that i = max{ j|N max [ j] = max{N max [1], N max [2], • • • , N max [v]}, 1 ≤ j ≤ v}. A (1, n)-
path can be constructed by some or all superior pairs, and a superior pair on the (1, n)-path is called a dominating pace (DP). Let [l i , r i ] be a dominating pace DP i . The dominating paces of G can be determined by the following manner:

Step 1. Let DP 1 = [l 1 , r 1 ] = A 1 and let i = 1.

Step 2. While r i = n, do loop: let i = i + 1 and

DP i = [l i , r i ] = A r i-1 .
In the example of Figure 1, the dominating paces are

DP 1 = A 1 = [1, 5], DP 2 = A 5 = [4, 8], DP 3 = A 8 = [8, 9]
, and DP 4 = A 9 = [9, 10] as shown in Table 1.

Suppose there are k dominating paces in G. With vertices

l 1 , r 1 , l 2 , r 2 , • • • , l k , r k , we can construct a (1, n)-path, denoted by l 1 -r 1 -l 2 -r 2 -. . .-l k -r k . Note that if r i = l i+1 , 1 ≤ i ≤ k -1,
we omit one of r i and l i+1 . The correctness of our method to find a (1, n)-path can be proved as follows.

Lemma 1 Let [l i , r i ] and [l i+1 , r i+1 ], 1 ≤ i ≤ k -1,
be two consecutive dominating paces. If r i = l i+1 , then r i must be adjacent to l i+1 .

Proof. Assume to the contrary that r i = l i+1 and r i is not adjacent to l i+1 . Since r i = l i+1 , we obtain l i+1 < r i according to Step 2. Moreover, since l i+1 < r i < r i+1 and r i is not adjacent to l i+1 , vertices r i and

pace of [l i , r i ]. It is a contradiction. ✷ Lemma 2 A (1, n)-path can be constructed by vertices l 1 , r 1 , l 2 , r 2 , . . . , l k , r k .
Proof. It is clear that l 1 = 1 and r k = n by Steps 1 and 2. By definitions, we have l i < l i+1 and r i < r i+1 and l i is adjacent to r i .

Case 1.

r i = l i+1 for all i, 1 ≤ i ≤ k -1. Then, l 1 -r 1 -l 2 -r 2 -. . .-l k -r k is the same as l 1 -l 2 -. . .-l k -r k , which is trivially a (1, n)-path. Case 2. r i = l i+1 for some i, 1 ≤ i ≤ k -1. By Lemma 1, r i is adjacent to l i+1 . Since l i < l i+1 and r i < r i+1 , there is no cycle in l 1 -r 1 -l 2 -r 2 -. . .-l k -r k , and it is a (1, n)-path.

✷

The (1, n)-path in our example is 1-5-4-8-9-10. It is easy to see that the (1, n)-path can be found in O(n) time. We will use the dominating paces to find cut vertices and bridges in the following sections. For the sake of computational boundary, we add two dummy dominating paces DP 0 = [0, 1] and DP k+1 = [n, n+1].

Finding cut vertices

Cut vertices of a trapezoid graph are in the vertices of the (1, n)-path. However, not all vertices of the (1, n)-path are cut vertices. We need to examine each vertex of the (1, n)-path.

Let array S = (s 1 , s 2 , • • • , s n ) be the prefix maxima of all maximal neighbors; i.e. 1, we obtain arrays S = (5, 5, 6, 8, 8, 8, 8, 9, 10, 10) and T = (1, 1, 1, 1, 1, 3, 4, 4, 8, 9).

s i = max{N max [1], N max [2], • • • , N max [i]} for i = 1, 2, • • • , n. Similarly, let array T = (t 1 ,t 2 , • • • ,t n ) be the suffix minima of all minimal neighbors; i.e. t i = min{N min [i], N min [i + 1], • • • , N min [n]} for i = 1, 2, • • • , n. From Table

Observation 3 A trapezoid graph is connected if and only if

(i) s i > i for all i, i = 1, 2, • • • , n -1, and (ii) t i < i for all i, i = 2, 3, • • • , n. Observation 4 A trapezoid graph is disconnected if and only if (i) s i = i for some i, 1 ≤ i ≤ n -1, and (ii) t i = i for some i, 2 ≤ i ≤ n. Assume trapezoid graph G is connected. Let S v = (s ′ 1 , s ′ 2 , • • • , s ′ n ) be the prefix maxima of all N ′ max [i], i = 1, 2, • • • , n, where N ′ max [i] = i if i = v and N ′ max [i] = N max [i] otherwise. Obviously, in S v , s ′ i = s i for all i < v and s ′ v = s ′ v-1 = s v-1 .
For example, S 4 = [START_REF] Hota | Optimal Sequential and Parallel Algorithms to Compute All Cut Vertices on Trapezoid Graphs[END_REF][START_REF] Hota | Optimal Sequential and Parallel Algorithms to Compute All Cut Vertices on Trapezoid Graphs[END_REF][START_REF] Jájá | Introduction to Parallel Algorithms[END_REF][START_REF] Jájá | Introduction to Parallel Algorithms[END_REF][START_REF] Jájá | Introduction to Parallel Algorithms[END_REF][START_REF] Jájá | Introduction to Parallel Algorithms[END_REF][START_REF] Ma | On the 2-Chain Subgraph Cover and Related Problems[END_REF][START_REF] Sprague | Optimal Parallel Algorithms for Finding Cut Vertices and Bridges of Interval Graphs[END_REF][START_REF] Tarjan | Depth-First Search and Linear Graph Algorithms[END_REF][START_REF] Tarjan | Depth-First Search and Linear Graph Algorithms[END_REF] since

N ′ max [4] = 4. We will use S v to determine if v is a cut vertex. Lemma 5 Let [l i , r i ], 2 ≤ i ≤ k, be a dominating pace of G. Then, vertex l i is a cut vertex if and only if there exists some v, l i ≤ v ≤ l i+1 -1, such that s ′ v = v in S l i . Proof. Since N ′ max [l i ] = l i in S l i ,
vertex l i is assumed to be adjacent to vertices whose labels are not greater than l i . We denote the new graph by G ′ . By Observation 3, we know s

′ v > v in S l i for all v, 1 ≤ v ≤ l i -1. Moreover, l i+1 -r i+1 -l i+2 -r i+2 -. . .-l k -n
is a path connecting vertices l i+1 and n. Vertices from l i+1 to n are connected, and

s ′ v > v in S l i for all v, l i+1 ≤ v ≤ n -1. Thus, if there exists some v, l i ≤ v ≤ l i+1 -1, such that s ′ v = v in S l i , then G ′ is disconnected. It means that the removal of edges (l i , x), l i < x, makes G
disconnected, and l i is certainly a cut vertex.

For the other part of the proof, since l i is a cut vertex, Gl i is disconnected. Since l i ≤ r i-1 and 1-r 1 -l 2r 2 -. . .-l i-1 -r i-1 is a path, vertices from 1 to r i-1 are connected, and the removal of any edge (l i , x), x < l i , still remains these vertices connected. Thus, we only consider the removal of edge (l i , x), l i < x, and we set

N ′ max [l i ] = l i . Since l i+1 -r i+1 -l i+2 -r i+2 -• • •-l k -n is a path connecting vertices from l i+1 to n, we have s ′ v > v in S l i for all v, l i+1 ≤ v ≤ n -1. Thus, if l i is a cut vertex, then there exists some v, l i ≤ v ≤ l i+1 -1, such that s ′ v = v in S l i . ✷ Similarly, we can let T v = (t ′ 1 ,t ′ 2 , • • • ,t ′ n ) be the suffix minima of all N ′ min [i], i = 1, 2, • • • , n, where N ′ min [i] = i if i = v and N ′ min [i] = N min [i] otherwise; then determine if v is a cut vertex by T v . Lemma 6 Let [l i , r i ], 1 ≤ i ≤ k -1,

be a dominating pace of G. Then, vertex r i is a cut vertex if and only if there exists some v, r

i-1 + 1 ≤ v ≤ r i , such that t ′ v = v in T r i . Corollary 7 Vertex 1 is a cut vertex if and only if there exists some v, 2 ≤ v ≤ l 2 -1, such that s ′ v = v in S 1 .

Moreover, vertex n is a cut vertex if and only if there exists some v, r k

-1 + 1 ≤ v ≤ n -1, such that t ′ v = v in T n .
For any two dominating paces [l i , r i ] and [l j , r j ], the examination of l i and l j uses mutually independent vertex sets, and so does the examination of r i and r j . It is reasonable to design a linear time algorithm for finding all cut vertices. Given S = (s

1 , s 2 , • • • , s n ), T = (t 1 ,t 2 , • • • ,t n ), and all dominating paces [l i , r i ], 1 ≤ i ≤ k, define p v and q v , v = 1, 2, • • • , n, as follows: p v =    1 if v = 1; s v-1 if v ∈ {l 2 , l 3 , • • • , l k }; N max [v]
otherwise;

(

and

q v =    n if v = n; t v+1 if v ∈ {r 1 , r 2 , • • • , r k-1 }; N min [v]
otherwise.

(

) Let S * = (s * 1 , s * 2 , • • • , s * n ) be the prefix maxima of all p v and T * = (t * 1 ,t * 2 , • • • ,t * n ) be the suffix minima of all q v for v = 1, 2, • • • , n. 2
In our example, S * = (1, 2, 6, 6, 6, 6, 8, 8, 9, 10) and T * = (1, 1, 1, 3, 3, 3, 4, 8, 9, 10). For any dominating pace

[l i , r i ] with S l i = (s ′ 1 , s ′ 2 , • • • , s ′ n ) and T r i = (t ′ 1 ,t ′ 2 , • • • ,t ′ n ), we can find that s ′ v = s * v , l i ≤ v ≤ l i+1 -1, and t ′ v = t * v , r i-1 + 1 ≤ v ≤ r i .
Thus, all cut vertices can be found directly from S * and T * . The following is our algorithm to find cut vertices.

Algorithm A (Finding cut vertices of a trapezoid graph)

Input: The dominating paces of a trapezoid graph G

Output: All cut vertices of G Step 1. Compute S = (s 1 , s 2 , • • • , s n ) and T = (t 1 ,t 2 , • • • ,t n ). Step 2. Compute S * = (s * 1 , s * 2 , • • • , s * n ) and T * = (t * 1 ,t * 1 , • • • ,t * n ). Step 3. For each dominating pace [l i , r i ], 1 ≤ i ≤ k, do case: Case 1. i = 1. If there exists some v, 2 ≤ v ≤ l 2 -1, such that s * v = v, then vertex 1 is a cut vertex. Case 2. 2 ≤ i ≤ k. If there exists some v, l i ≤ v ≤ i+1 -1, such that s * v = v, then vertex l i is a cut vertex.
Step 4. For each dominating pace

[l i , r i ], 1 ≤ i ≤ k, do case: Case 1. 1 ≤ i ≤ k -1. If there exists some v, r i-1 + 1 ≤ v ≤ r i , such that t * v = v, then vertex r i is a cut vertex. Case 2. i = k. If there exists some v, r k-1 + 1 ≤ v ≤ n -1, such that t * v = v, then vertex n is a cut vertex.
We use dominating pace [START_REF] Arvind | Efficient Parallel Algorithms for Permutation Graphs[END_REF][START_REF] Hota | Optimal Sequential and Parallel Algorithms to Compute All Cut Vertices on Trapezoid Graphs[END_REF] of our example to explain Steps 3 and 4. Vertex 1 is a cut vertex since s * 2 = 2; however, vertex 5 is not a cut vertex since there exists no vertex v, 2 ≤ v ≤ 5, such that t * v = v. The cut vertices in our example are vertices 1, 4, 8, and 9.

Theorem 8 Algorithm A finds all cut vertices of a trapezoid graph in O(n) time.

Proof. Since cut vertices are in {l 1 , r 1 , l 2 , r 2 , • • • , l k , r k } and Algorithm A examines l i and r i for each dominating pace [l i , r i ], 1 ≤ i ≤ k, all cut vertices can be found by Algorithm A. By the computation of prefix maxima and suffix minima, Steps 1 and 2 can be done in O(n) time. Steps 3 and 4 can also be done in O(n) time totally. The complexity of Algorithm A is therefore O(n). ✷

Finding bridges

An edge e is a bridge of G if Ge is disconnected. A bridge must be incident to one or two cut vertices. However, we cannot conclude that an edge incident to any cut vertices is a bridge. In this section, we will find bridges by cut vertices. We use the same notation as in the previous section. A vertex is isolated if it is not adjacent to any other vertices in the graph. From Observation 4, we can make the following observation.

Observation 9 Let i be a vertex of a disconnected trapezoid graph. Then, (i) vertex i, 2 ≤ i ≤ n -1, is isolated if and only if s i-1 = i -1 and s i = i (or if t i = i and t i+1 = i + 1);

(ii) vertex 1 is isolated if and only if s 1 = 1 (or t 2 = 2); (iii) vertex n is isolated if and only if s n-1 = n -1 (or t n = n).
An edge is a pendant edge if its removal makes one vertex isolated. A pendant edge is certainly a bridge, which is incident to one cut vertex. Lemmas 10 and 11 will show how to use dominating paces, S * , and T * to determine pendant edges. Their correctness is directly from the above observation.

Lemma 10 Suppose l i , 1 ≤ i ≤ k, is a cut vertex of G. Then, edge (l i , v), l i < v < l i+1 , is a pendant edge if and only if s * v-1 = v -1 and s * v = v. Moreover, edge (l k , n) is a pendant edge if and only if s * n-1 = n -1. Lemma 11 Suppose r i , 1 ≤ i ≤ k, is a cut vertex of G. Then, edge (r i , v), r i-1 < v < r i , is a pendant edge if and only if t * v = v and t * v+1 = v + 1. Moreover, edge (1, r 1
) is a pendant edge if and only if t * 2 = 2. A pendant edge is a bridge; however, not all bridges are pendant edges. A bridge, not a pendant edge, must be incident to two cut vertices. Let C m be a cycle of m vertices without any chord. By the definition of trapezoid graphs [START_REF] Dagan | Trapezoid Graphs and Their Coloring[END_REF], a trapezoid graph G may contain only C 3 or C 4 , and we have the following lemma.

Lemma 12 An edge e incident to two cut vertices of G is a bridge if and only if it is an edge of the (1, n)-path and not contained in any C

3 or C 4 .
Proof. It is trivial that a bridge cannot be contained in a cycle. Let e = (u, v). Since u and v are cut vertices, they are vertices of the (1, n)-path. Assume to the contrary that e is not an edge of the (1, n)-path, then the path connecting u and v forms a cycle with edge (u, v). It contradicts that e is a bridge. ✷

To determine if an edge of the (1, n)-path is contained in a cycle, we need to know what vertices edge (l i , r i ) and (r i , l i+1 ) may be incident to, respectively. Lemma 13 Suppose l i and r i , 1 ≤ i ≤ k, are two cut vertices of G, and let v be a vertex other than l i and r i .

(i) If v is adjacent to r i , then v > r i-1 when l i = r i-1 or v > l i-1 when l i = r i-1 ; (ii) If v is adjacent to l i , then v < l i+1 no matter r i = l i+1 or r i = l i+1 .
Proof. Consider the following two cases for condition i:

Case 1. l i = r i-1 . If v < r i-1
, then v must be adjacent to some l j or r j , 1 ≤ j ≤ i -1. Without loss of generality, assume v is adjacent to r j . Then, andl i cannot be a cut vertex.

l 1 -r 1 -l 2 -r 2 -. . .-l j -r j -v-r i -l i+1 -r i+1 -. . .-l k -r k is a (1, n)-path, and it contradicts that l i is a cut vertex. Case 2. l i = r i-1 . If v < l i-1 , then v must be adjacent to l i-1 since v < l i-1 < r i-1 < r i and v is adjacent to r i and l i-1 is not adjacent to r i . We can find that l 1 -r 1 -l 2 -r 2 -. . .-l i-1 -v-r i -l i+1 -r i+1 -. . .-l k -r k is a (1, n)-path,
For condition ii, we need to consider the following two cases: Case 1.

r i -1 l i v l i +1 r i (a) l i -1 v l i = r i -1 r i (b) l i +1
r i = l i+1 . If v > l i+1
, then v must be adjacent to some l j or r j , i + 1 ≤ j ≤ k, and it will contradict that r i is a cut vertex.

Case 2.

r i = l i+1 . Since v is adjacent to l i , we have v < N max [l i ] = r i = l i+1 .

✷

Lemma 14 Suppose r i and l i+1 , 1 ≤ i ≤ k -1, are two distinct cut vertices of G, and let v be a vertex other than r i and l i+1 .

(i) If v is adjacent to l i+1 , then v > r i-1 ; (ii) If v is adjacent to r i , then v < l i+2 .
Proof. For condition (i), if v < r i-1 , then v must be adjacent to some l j or r j , 1 ≤ j ≤ i -1, and it will contradict that r i is a cut vertex. For condition (ii), if v > l i+2 , then v must be adjacent to some l j or r j , i + 2 ≤ j ≤ k, and l i+1 cannot be a cut vertex. ✷

The following lemmas show the ways to determine whether an edge incident to both cut vertices is contained in a cycle.

Lemma 15 Suppose l i and r i , 1 ≤ i ≤ k, are two cut vertices of G. If edge (l i , r i ) is contained in a C 3 , then one of the following conditions holds: (i) When l i = r i-1 , there exists some vertex v, r i-1 < v < l i+1 , such that v is adjacent to l i and r i ;

(ii) When l i = r i-1 , there exists some vertex v, l i-1 < v < l i+1 , such that v is adjacent to l i and r i .

Proof. The correctness is from Lemma 13. (See Figure 2.) Lemma 16 Suppose l i and r i ,

✷ r i -1 l i u l i +1 r i (a) u +1 r i -1 l i u l i +1 r i (b) N max [ u ] l i = r i -1 l i -1 u l i +1 r i (c) N max [ u ]
1 ≤ i ≤ k, are two cut vertices of G. If edge (l i , r i ) is contained in a C 4 ,
then one of the following conditions holds:

(i) No matter l i = r i-1 or l i = r i-1 , there exist two consecutive vertices v and v + 1, r i-1 < v < l i+1 -1, such that v (v + 1, respectively) is adjacent to r i (l i , respectively) but not adjacent to l i (r i , respectively);

(ii) When l i = r i-1 , there exist two vertices v and

N max [v], r i-1 < v ≤ N max [v] < l i+1 , such that v (N max [v],
respectively) is adjacent to l i (r i , respectively) but not adjacent to r i (l i , respectively);

(iii) When l i = r i-1 , there exist two vertices v and N max [v], l i-1 < v ≤ N max [v] < l i+1 , such that v (N max [v],
respectively) is adjacent to l i (r i , respectively) but not adjacent to r i (l i , respectively).

Proof. We assume that no one vertex is adjacent to both l i and r i to form a C 3 . Let u and v be two adjacent vertices such that u, v, l i , and r i form a C 4 . Without loss of generality, assume u < v. Consider the following two cases:

Case 1. u is adjacent to r i and v is adjacent to l i . Assume v > u + 1. If vertex u + 1 is adjacent to l i , then u, u + 1, l i , and r i form a C 4 ; otherwise, u + 1 is adjacent to r i and we let u be vertex u + 1. Similarly, if vertex v -1 is adjacent to r i , then v -1, v, l i , and r i form a C 4 ; otherwise, v -1 is adjacent to l i and we let v be vertex v -1. With this argument, we can deduce that vertices u, v = u + 1, l i , and r i form a C 4 . Since u is adjacent to r i and v is adjacent to l i , we obtain

r i-1 < u < v < l i+1 if l i = r i-1 and l i-1 < u < v < l i+1 if l i = r i-1 by Lemma 13. However, in the case of l i = r i-1 , if l i-1 < u < l i = r i-1 , then u must be adjacent to l i-1 since l i-1 is adjacent to r i-1 and u is not adjacent to l i = r i-1 . It contradicts that l i is a cut vertex since l 1 -r 1 -l 2 -r 2 -. . .-l i-1 -u-r i -l i+1 -r i+1 - . . .-l k -r k is a (1, n)-path. Thus, we have r i-1 < u < v < l i+1 no matter l i = r i-1 or l i = r i-1 . (See Figure 3 (a).) Case 2. u is adjacent to l i and v is adjacent to r i . Since u is adjacent to v, we have v ≤ N max [u]. If N max [u] is adjacent to l i , then v, N max [u]
, l i , and r i form a C 4 , which is in Case 1. Thus, N max [u] is adjacent to r i , and we can let v be andr i cannot be a cut vertex. Therefore, we have N max [u] < l i+1 . Consider the following two subcases: Subcase 1. l i = r i-1 . If u < r i-1 , then u must be adjacent to some l j or r j , 1 ≤ j ≤ i -1, and it will contradict that l i is a cut vertex. We obtain r i-1 < u ≤ N max [u] < l i+1 . (See Figure 3 (b).) Subcase 2. l i = r i-1 . Since N max [u] is adjacent to r i , we have l i-1 < N max [u] by Lemma 13.

N max [u]. If N max [u] > l i+1 , then N max [u] must be adjacent to some l j or r j , i + 1 ≤ j ≤ k. Without loss of generality, assume N max [u] is adjacent to l j . Then, l 1 -r 1 -l 2 -r 2 - . . .-l i -u-N max [u]-l j -r j -. . .-l k -r k is a (1, n)-path,
Moreover, l i-1 cannot be adjacent to

N max [u]; otherwise, l 1 -r 1 -l 2 -r 2 -. . .-l i-1 -N max [u]- r i -l i+1 -r i+1 -. . .-l k -r k is a (1, n)-path which contradicts that l i is a cut vertex. If u < l i-1 , then u must be adjacent to l i-1 since u < l i-1 < N max [u] and l i-1 is not adjacent to N max [u]. However, this contradicts that l i is a cut vertex since l 1 -r 1 -l 2 -r 2 -. . .-l i-1 -u- N max [u]-r i -l i+1 -r i+1 -. . .-l k -r k is a (1, n)-path. Thus, we have l i-1 < u ≤ N max [u] < l i+1 .
(See Figure 3 (c).)

✷

Lemma 17 Suppose r i and l i+1 ,

1 ≤ i ≤ k -1, are two distinct cut vertices of G. (i) If edge (r i , l i+1
) is contained in a C 3 , then there exists some vertex v, r i-1 < v < l i+2 , such that v is adjacent to r i and l i+1 ;

(ii) If edge (r i , l i+1 ) is contained in a C 4 , then there exist two vertices v and N max [v], where r i-1 < v < l i+1 and r i < N max [v] < l i+2 , such that v (N max [v], respectively) is adjacent to r i (l i+1 , respectively) but not adjacent to l i+1 (r i , respectively).

Proof. Condition i is directly from Lemma 14. (See Figure 4 (a).) In condition ii, we assume that no one vertex is adjacent to both r i and l i+1 to form a C 3 . Let u and v be two adjacent vertices such that u, v, r i , and l i+1 form a C 4 . Without loss of generality, assume u < v. Consider the following two cases:

Case 1. u is adjacent to r i and v is adjacent to l i+1 . If u < r i-1 , then u must be adjacent to some l j or r j , 1 ≤ j ≤ i -1, and it will contradict that r i is a cut vertex. Note that u < l i+2 by Lemma 14 and u is not adjacent to l i+1 . If u > l i+1 , then u must be adjacent to r i+1 since l i+1 < u < l i+2 ≤ r i+1 and u is not adjacent to l i+1 . This will contradict that l i+1 is a cut vertex since l 1 -r 1 -l 2 -r 2 -. . .-l i -r i -u-r i+1 -. . .-l k -r k is a (1, n)-path. Therefore, r i-1 < u < l i+1 . Similarly, we can obtain

r i < v < l i+2 . Since u is adjacent to v, v ≤ N max [u].
It is easy to see that N max [u] < l i+2 ; otherwise, N max [u] is adjacent to some l j or r j , l i+2 < j < k, and l i+1 cannot be a cut vertex. Thus, we have

r i < v ≤ N max [u] < l i+2 .
It means that if u, v, r i , and l i+1 form a C 4 , then u, N max [u], r i , and l i+1 also form a C 4 . (See Figure 4 (b).) At first, we can use the parallel algorithms of prefix maxima and suffix minima [START_REF] Jájá | Introduction to Parallel Algorithms[END_REF] to find the maximal and minimal neighbors for each vertex of G. These parallel algorithms take O(log n) time with O( n log n ) processors on the EREW PRAM model.

l i +1 r i -1 u l i +2 r i (a) l i r i +1 ( b ) l i +1 r i -1 u r i l i r i +1 N max [ u ] l i +2
Secondly, we need to find the dominating paces of G in parallel. Using the parallel computation of prefix maxima on [l i , r i ], i = 1, 2, • • • , n, we can obtain all superior pairs A i . For each superior pair

A i = [p i , q i ], i = 1, 2, • • • , n -1, let A q i be the successor (or parent) of A i if q i = n.
It is trivial that these superior pairs form a rooted tree (or forest) which has O(n) nodes and O(n) edges. The (1, n)-path is identical to the chain from A 1 to its root A k = [p k , q k ], 1 ≤ k ≤ n -1, where q k = n. Figure 5 shows the rooted tree formed by the superior pairs in Table 1. Applying the technique of list ranking [START_REF] Jájá | Introduction to Parallel Algorithms[END_REF], all dominating paces can be determined in O(log n) time with O( n log n ) processors on the EREW PRAM model. Also by the parallel algorithms of prefix maxima and suffix minima, arrays S, T , S * , and T * of G can be obtained. Steps 3 and 4 of Algorithm A find cut vertices by using l i and r i . It is easy to see that there is no concurrent memory access in these two steps, and Algorithm A can be done in O(log n) time using O( n log n ) processors on the EREW PRAM model. In Algorithm B, Step 1 can be done in O(1) time with O(1) processor. In Step 2, we can first simultaneously examine if s * v-1 = v -1 for all vertices v, l i < v < l i+1 , then simultaneously examine if s * v = v for the same vertices. Step 3 can use the similar way to examine if t * v = v and t * v+1 = v + 1 for all vertices v, r i-1 < v < r i . Since there is no concurrent memory access in these three steps, all pendant edges can be found in O(log n) time with O( n log n ) processors on the EREW PRAM model. To transform Lemmas 15, 16, and 17 into parallel steps, we need some additional variables to avoid concurrent memory access. Lemma 15 has two conditions. In condition (i), we can let x v = l i and y v = r i for each vertex v, r i-1 < v < l i+1 , then examine if v is adjacent to both x v and y v . There is no concurrent read and write in condition (i). Condition (ii) can be implemented by two stages for avoiding concurrent memory access. The first stage uses vertices v, l i-1 < v < r i-1 , while the second stage uses vertices v, r i-1 < v < l i+1 . We examine if v is adjacent to both x v and y v for the first stage then for the second stage, where x v = l i and y v = r i . Thus, all dominating paces of l i = r i-1 can be done without any concurrent read and write.

Lemma 16 has three conditions. In condition (i), we can let x v = l i , y v = r i , and z v = v + 1 for all vertices v, r i-1 < v < l i+1 -1, then examine if v is adjacent to y v and z v is adjacent to x v . In condition (ii), we can let x v = l i , y v = r i , and z v = N max [v] for all vertices v, r i-1 < v < l i+1 , then examine if v is adjacent to x v and z v is adjacent to y v . In condition (iii), we need two stages for parallel computation. The first stage uses vertices v, l i-1 < v < r i-1 , and the second stage uses vertices v, r i-1 < v < l i+1 . Then, we examine if v is adjacent to x v and z v is adjacent to y v for these two stages respectively, where x v = l i , y v = r i , and

z v = N max [v].
Condition (i) of Lemma 17 also needs two stages: vertices v, r i-1 < v < l i+1 , are for the first stage and vertices v, l i+1 < v < l i+2 are for the second stage. Let x v = r i and y v = l i+1 , then we examine if v is adjacent to both x v and y v for each stage. In condition (ii), we can let x v = r i , y v = l i+1 , and z v = N max [v] for all vertices v, r i-1 < v < l i+1 , then examine if v is adjacent to x v and z v is adjacent to y v , where r i < N max [v] < l i+2 . Therefore, Lemmas 15, 16, and 17 can be implemented in O(log n) time using O( n log n ) processors on the EREW PRAM model. We have the following theorem. Theorem 19 All cut vertices and bridges of a trapezoid graph can be found in parallel in O(log n) time with O( n log n ) processors on the EREW PRAM computational model.

Concluding remarks

In this paper, we use dominating paces [l i , r i ] to find cut vertices and bridges. This idea is different from other proposed algorithms for trapezoid graphs, which almost use the corner points. The properties of l i and r i are new and interesting.

Using the properties of the dominating paces, we presented O(n) time algorithms to find cut vertices and bridges on trapezoid graphs. Our algorithms can be easily parallelized so that cut vertices and bridges can be found in O(log n) time using O( n log n ) processors on the EREW PRAM computational model. Since the lower bound of complexity for finding cut vertices and bridges on trapezoid graphs is Ω(n), our algorithms are optimal.

a 1 a 2 b 1 b 2 b 3 a 3 a 5 a 4 b 4 b 5 a 6 b 6 a 7 a 8 a 9 b 7 b 9 b 8 a 10 b 10 c 2 c 1 d 2 c 3 d 1 c 5 c 6 d 3 c 4 d 5 d 6 c 8 c 7 d 4 d 8 d 7 c 9 c 10 d 10 d 9 Fig. 1 :

 1091 Fig. 1: A trapezoid graph and the corresponding diagram.

  with the maximal label (minimal label, respectively), where N[v] is the set of vertices adjacent to v and v itself. To determine N max [v], we need to scan a and c corner points from left to right respectively on the trapezoid diagram. Let x v (y v , respectively) be the maximal label of a (c, respectively) corner point left to b v (d v , respectively), then N max [v] = max{x v , y v }. Similarly, we can determine N min [v] by scanning b and d corner points from right to left respectively on the trapezoid diagram then choosing the minimal label among those whose b or d corner points are right to a v or c v .

Fig. 2 :

 2 Fig. 2: The illustration of Lemma 15. (a) condition i. (b) condition ii.

Fig. 3 :

 3 Fig. 3: The illustration of Lemma 16. (a) condition i. (b) condition ii. (c) condition iii.

Fig. 4 :Fig. 5 :

 45 Fig. 4: The illustration of Lemma 17. (a) condition i. (b) condition ii.

Tab. 1: The

  process of determining the dominating paces. i+1 are adjacent. By the definition of a superior pair, [r i , r i+1 ] is a superior pair and is the next dominating

	vertex i	1	2	3	4	5	6	7	8	9	10
	N max [i]	5	2	6	8	6	6	8	9	10	10
	N min [i]	1	1	1	4	1	3	4	4	8	9
	[i, N max [i]]	1,5 2,2 3,6 4,8 5,6 6,6 7,8 8,9 9,10 10,10
	A i	1,5 1,5 3,6 4,8 4,8 4,8 7,8 8,9 9,10 10,10
	dominating paces 1,5				4,8			8,9 9,10

r

† This work was supported by National Science Council, Republic of China, under contract NSC89-2218-E-022-002.

Case 2. u is adjacent to l i+1 and v is adjacent to r i . By Lemma 14, r i-1 < u and v < l i+2 . If r i-1 < u < r i , then u must be adjacent to l i since l i ≤ r i-1 < u < r i and u is not adjacent to r i . We can find that l 1 -r 1 -l 2 -r 2 -. . .-l i -u-l i+1 -r i+1 -. . .-l k -r k is a (1, n)-path, and it contradicts that r i is a cut vertex. Thus, r i < u. Similarly, we can obtain v < l i+1 . However, it contradicts u < v since v < l i+1 < r i < u. Case 2 cannot hold.

✷

Algorithm B below describes the steps of finding bridges of a trapezoid graph.

Algorithm B (Finding bridges of a trapezoid graph)

Input: Dominating paces, S * , T * , and cut vertices of G.

Output: All bridges of G.

Step

Step 4. For i = 1 to k, if both l i and r i are cut vertices, then (l i , r i ) is a bridge if none of the conditions in Lemmas 15 and 16 holds.

Step 5. For i = 1 to k -1, if both r i and l i+1 are cut vertices, then (r i , l i+1 ) is a bridge if none of the conditions in Lemma 17 holds.

We use our example again to illustrate Algorithm B. The dominating paces are [START_REF] Arvind | Efficient Parallel Algorithms for Permutation Graphs[END_REF][START_REF] Hota | Optimal Sequential and Parallel Algorithms to Compute All Cut Vertices on Trapezoid Graphs[END_REF], [START_REF] Dagan | Trapezoid Graphs and Their Coloring[END_REF][START_REF] Ma | On the 2-Chain Subgraph Cover and Related Problems[END_REF], [START_REF] Ma | On the 2-Chain Subgraph Cover and Related Problems[END_REF][START_REF] Sprague | Optimal Parallel Algorithms for Finding Cut Vertices and Bridges of Interval Graphs[END_REF], [9, 10], and vertices 1, 4, 8, 9 are cut vertices. In dominating pace [START_REF] Arvind | Efficient Parallel Algorithms for Permutation Graphs[END_REF][START_REF] Hota | Optimal Sequential and Parallel Algorithms to Compute All Cut Vertices on Trapezoid Graphs[END_REF], since s * 1 = 1 and s * 2 = 2, edge (1, 2) is a pendant edge. In dominating pace [START_REF] Sprague | Optimal Parallel Algorithms for Finding Cut Vertices and Bridges of Interval Graphs[END_REF][START_REF] Tarjan | Depth-First Search and Linear Graph Algorithms[END_REF], since s * 9 = 9, edge (9, 10) is a pendant edge. In Step 4, (4, 8) and [START_REF] Ma | On the 2-Chain Subgraph Cover and Related Problems[END_REF][START_REF] Sprague | Optimal Parallel Algorithms for Finding Cut Vertices and Bridges of Interval Graphs[END_REF] are the edges of (l i , r i ) incident to two cut vertices. Edge (4, 8) is not a bridge since vertex 7 is adjacent to vertices 4 and 8, while edge (8, 9) is a bridge since none of the conditions in Lemmas 15 and 16 holds. In Step 5, only [START_REF] Hota | Optimal Sequential and Parallel Algorithms to Compute All Cut Vertices on Trapezoid Graphs[END_REF][START_REF] Dagan | Trapezoid Graphs and Their Coloring[END_REF] is the edge of (r i , l i+1 ). Since vertex 5 is not a cut vertex, (5, 4) is not a bridge. All bridges in our example are (1, 2), [START_REF] Ma | On the 2-Chain Subgraph Cover and Related Problems[END_REF][START_REF] Sprague | Optimal Parallel Algorithms for Finding Cut Vertices and Bridges of Interval Graphs[END_REF], and (9, 10).

Theorem 18 Algorithm B finds all bridges of a trapezoid graph in O(n) time.

Proof. A bridge is an edge incident to one cut vertex (a pendant edge) or two cut vertices (an edge of the (1, n)-path). Since cut vertices are in {l 1 , r 1 , l 2 , r 2 , • • • , l k , r k } and the (1, n)-path is composed of (l i , r i ) and (r i , l i+1 ), all bridges can be found by Algorithm B. It is trivial that each step of Algorithm B takes O(n) time, thus the complexity of Algorithm B is O(n). ✷

The parallel algorithms

In this section, we will parallelize algorithms A and B so that the problem of finding cut vertices and bridges of a trapezoid graph G can be solved in O(log n) time using O( n log n ) processors on the EREW PRAM model.


M D Atkinson

Some equinumerous pattern-avoiding classes of permutations

Keywords: permutation, pattern, enumeration

Suppose that p, q, r, s are non-negative integers with m = p + q + r + s. The class X(p, q, r, s) of permutations that contain no pattern of the form αβγ where |α| = r, |γ| = s and β is any arrangement of {1, 2, . . . , p}∪{m-q+1, mq + 2, . . . , m} is considered. A recurrence relation to enumerate the permutations of X(p, q, r, s) is established. The method of proof also shows that X(p, q, r, s) = X(p, q, 1, 0)X(1, 0, r, s) in the sense of permutational composition.

In their paper [START_REF] Mansour | Avoiding maximal parabolic subgroups of S k[END_REF] Mansour and Vainshtein enumerated a three-parameter family of pattern-avoiding classes of permutations using fairly complex recurrence equations and generating functions. We shall derive a generalisation of their results by a very simple argument. Finally we observe that our proof gives a structure theorem for the pattern-avoiding classes in question.

To make this note self-contained we recall the notion of pattern-avoiding class. A permutation π is said to be contained as a pattern in another permutation σ if σ has a subseqence order isomorphic to π (its terms are ordered in the same relative way as π). If σ does not contain π it is said to avoid π. A pattern-avoiding class is a set of permutations defined by the property of avoiding some set of patterns. A central problem in the theory of pattern-avoiding classes is to enumerate them, i.e. to determine the number of permutations of each length in the class.

Let p, q, r, s be non-negative integers and let A(p, q, r, s) be the set of (p + q)!(r + s)! permutations of length p + q + r + s which have the form αβγ where |α| = r, |γ| = s and β is any arrangement of the p smallest and q largest values in the set {1, 2, . . . , p + q + r + s}.

Let X(p, q, r, s) be the class of permutations that avoid all the permutations of this set. The following lemma gives a recursive characterisation of the permutations of this class and shows how they can be constructed.

Lemma 1 1. Let π = π 1 • • • π n ∈ X(p, q, r, s).
Then there is at least one position i of π among the first r or last s positions whose value π i is among the p smallest or q largest values. If this term is removed from π the resulting permutation π ′ (after appropriate renumbering) also lies in X(p, q, r, s). and has degree λ. The numerator can be ascertained from the initial terms of the sequence (t n ) which, for n < u + v, are equal to n!. After some algebraic manipulation we obtain

p(x) = λ-1 i=0 x i i! i j=0 (-1) j u j v j i j + (-1) λ x λ λ! µ-λ-1 i=0 x i i! µ -i -1 λ .
This generating function is the same as the one given in the main theorem of [START_REF] Mansour | Avoiding maximal parabolic subgroups of S k[END_REF] for the enumeration of another pattern-avoiding set of permutations. This is no coincidence since, by putting q = 0, we can obtain that theorem as follows. The permutations of A(p, 0, r, s) are precisely those where the values 1, 2, . . . , p occur (in any order) at positions r + 1, r + 2, . . . , r + p. The inverses of these permutations are those where positions 1, 2, . . . , p contain the values r + 1, r + 2, . . . , r + p (in any order); this is exactly the set of avoided permutations considered in [START_REF] Mansour | Avoiding maximal parabolic subgroups of S k[END_REF] (see the discussion following Lemma 2.1 of that paper). However, permutation inversion is a symmetry of the pattern-avoidance relation and so the classes X(p, 0, r, s) have the same enumerations as the classes in [START_REF] Mansour | Avoiding maximal parabolic subgroups of S k[END_REF].

Finally we give a structural property of X(p, q, r, s). Lemma 1 shows that every permutation π ∈ X(p, q, r, s) can be generated as the output of a certain process that has the sequence 1, 2, . . . , n as input. This process has n steps in each of which one value from the remaining input is moved to a position of the output permutation. The input value moved is chosen from among the p smallest and q greatest values remaining. The position where it is placed is chosen from among the first r and last s positions still undefined.

This process can be regarded as taking place in two stages. In the first stage the sequence of values is chosen and placed, from left to right, in a permutation γ. In the second stage the terms of γ are processed sequentially and inserted according to how the output positions are chosen. The permutation γ generated by the first stage lies in X(p, q, 1, 0) while the permutation corresponding to the second stage lies in X(1, 0, r, s). It follows that X(p, q, r, s) = X(p, q, 1, 0)X(1, 0, r, s) in the sense of composition of permutations (see [START_REF] Albert | Compositions of pattern restricted sets of permutations[END_REF] for an account of the composition operation on pattern-avoiding classes).

  1365-8050 c 2005 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

Proof: To prove the first part, suppose no such position existed. Then all of the values 1, 2, . . . , p, nq + 1, nq + 2, . . . , n would occur among the positions r + 1, r + 2, . . . ns + 1. Therefore the subsequence defined by the first r and last s positions together with the positions where the values 1, 2, . . . , p, nq + 1, nq + 2, . . . , n occur would be order isomorphic to a member of A(p, q, r, s). Hence π has such a position. If the term at this position was removed the resulting permutation would still avoid the patterns of A(p, q, r, s).

The second part follows by observing that the insertion of y into π ′ cannot create a subsequence order isomorphic to one in A(p, q, r, s). ✷ Theorem 2 Let t n be the number of permutations of length n that avoid all the permutations of A(p, q, r, s).

Proof: Consider permutations of length n that avoid all the permutations of A(p, q, r, s). We shall call the p smallest and q largest values the critical values of the permutation and the r initial and s final positions the critical positions. Furthermore, we call a critical value that occurs in a critical position a critical term. Lemma 1 shows that the permutations of X(p, q, r, s) are precisely those with at least one critical term which, if removed, results in a permutation of X(p, q, r, s).

Since there are u critical values and v critical positions there are u k v k t n-k permutations with exactly k critical terms which, if removed, result in a permutation of X(p, q, r, s). Therefore, by inclusionexclusion, there are

permutations with at least one such critical term. ✷

The recurrence relation given in this theorem has λ = min(u, v) terms on the right hand side and is valid for all n ≥ µ = max(u, v). We may apply the standard method for deriving the ordinary generating function t n x n ; that is to say, we multiply the recurrence by x n and sum over all n ≥ µ. Such a calculation expresses the generating function as a rational function in the form

where the denominator is directly obtained from the recurrence as