Analysis of Algorithms for Listing Equivalence Classes of k-ary Strings

Andrzej Proskurowski^{∗} Frank Ruskey^{†} Malcolm Smith^{‡}

May 28, 1996

Abstract

We give efficient algorithms for listing equivalence classes of k-ary strings under reversal and permutation of alphabet symbols. As representative of each equivalence class we choose that string which is lexicographically smallest. These algorithms use space O(n) and time O(\sqrt{k}N), where N is the total number of strings generated and n is the length of each string. For k = 2, we obtain a recursive decomposition of the set of binary strings that allows the strings to be generated without rejecting any strings. For k ≥ 3, some strings must be rejected. The algorithm is simple but its exact analysis is rather complicated. In the analysis we determine a quantity of independent interest: the average length of the common prefix of two randomly chosen infinite length “restricted-growth” strings.

Keywords: combinatorial generation, k-ary strings, Stirling numbers, restricted growth function, k-paths. AMS Classification: 05A15, 05C30, 60J10, 68Q25, 68R05, 68R15. Running Title: Listing k-ary strings.

∗Department of Computer and Information Science, University of Oregon, Eugene, Oregon 97403, USA, andrzej@cs.uoregon.edu. Research supported in part by grant NSF-CCR-9213431.

†Department of Computer Science, University of Victoria, Victoria, B.C., Canada V8W 3P6, fruskey@csr.uvic.ca. Research supported in part by NSERC grant OGP0003379.

‡Department of Computer Science, University of Victoria, Victoria, B.C., Canada V8W 3P6.

List of Symbols

(k)_{j}: falling factorial (k)_{j} = k(k − 1) ⋯ (k − j + 1). \left\{{n \atop k}\right\}: Stirling number of the second kind. B_{n,k}: all k-ary strings of length n. Also, B_{n} = B_{n,2}. B_{n,k} = |B_{n,k} | = k^{n}. Also, B_{n} = B_{n,2}. s: An element of B_{n,k}. can(s): The canonical (lexicographically least) string equivalent to s, by consi-

tently permuting symbols. mate(s): The “mate” of s, mate(s) = can(s^{R}). X_{n,k} = {s ∈ B_{n,k} | s = can(s)} X_{n,k} = {s_{1}s_{2} ⋯ s_{n} | s_{1} = 0, 0 ≤ s_{i} ≤ min(k − 1, 1 + max(s_{1}, s_{2}, …, s_{i−1}))} X_{n,k} = |X_{n,k} | = ∑ _{i=1}^{k} \left\{{n \atop i}\right\}. Y_{n,k} = {s ∈ X_{n,k} | s ≤ mate(s)}. Also, Y_{n} = Y_{n,2}. Y_{n,k} = |Y_{n,k} |. Also, Y_{n} = Y_{n,2}. π_{s}: The permutation of 0, 1, …, k − 1 that takes s into can(s). c(s): The length of the largest prefix common to both s and mate(s). X_{n,k,p} = {s_{1}s_{2} ⋯ s_{n} | s_{1} = p, 0 ≤ s_{i} ≤ min(k − 1, 1 + max(s_{1}, s_{2}, …, s_{i−1}))} X_{n,k,p} = |X_{n,k,p} |. X_{n,k}^{(c)} = {s ∈ X_{n,k} | c(s) = c}. X_{n,k}^{(c)} = |X_{n,k}^{(c)} | ℤ_{n}: Group of integers mod n. ℂ_{n}: Cyclic group of order n. 𝕊_{k}: Symmetric group of order k!.

1 Introduction

What are the most natural group actions on strings over a fixed alphabet? Three actions immediately suggest themselves: (a) leaving the string unchanged, (b) reversing a string, (c) rotating a string, and (d) permuting the symbols of the string by a permutation of the alphabet. The three groups giving rise to these actions are (a) ℤ_{1}, (b) ℤ_{2}, (c) the cyclic group ℂ_{n} and (d) the symmetric group 𝕊_{k}, assuming the alphabet consists of k symbols.

Each group action, or composition of group actions, partitions the set of k-ary strings into equivalence classes, namely the orbits of the action. To generate these equivalence classes, it is natural to choose as representative the lexicographically smallest string. With this representation, efficient algorithms are known for generating the equivalence classes of each of the actions (a), (b), (c), and (d). By “efficient” we mean that the amount of computation used in generating the objects is proportional to the number of objects generated. For (a) we are simply counting in base k which is known to be efficient for k ≥ 2. For (b) efficient algorithms were developed by Ruskey [15]. In case (c) the equivalence classes are usually called necklaces. Efficient algorithms for generating necklaces were developed by Fredericksen and Kessler [2] and Fredericksen and Maiorana [3]; these algorithms were proven to be efficient by Ruskey, Savage, and Wang [14]. In case (d) the representative strings are usually called restricted growth functions and efficient algorithms for generating them have been developed by Er [1], Kaye [8], and others.

In contrast to the case where our three non-trivial actions are considered in isolation, the composition of more than two of the actions gives rise to equivalence classes for which no efficient generation algorithms were previously known. For example, composing (b) and (c) results in the dihedral group, with the resulting equivalence classes known as bracelets. No more efficient algorithm is known than simply listing all necklaces and rejecting those that are larger than their reversals (i.e., are not representative of a bracelet). In this paper we compose (b) and (d) and develop efficient (for fixed k) algorithms for generating the resulting equivalence classes. It remains an interesting challenge to develop efficient algorithms for the other compositions.

Let us recast our problem. The problem is to list equivalence classes of k-ary strings under the transitive closure of the binary relation R defined on k-ary strings of length n by

x_{1} ⋯ x_{n} R y_{1} ⋯ y_{n} / / \begin{matrix}x_{1} ⋯ x_{n} = y_{n} ⋯ y_{1} or \\ x_{1} ⋯ x_{n} = π(y_{1}) ⋯ π(y_{n}) for some π ∈ 𝕊_{k} \end{matrix} (1)

As representative of each equivalence class we choose the lexicographically smallest string.

An important tool in listing sets of combinatorial objects consists of recurrence relations describing the sets. The typical operation on lists is concatenation (⊕) corresponding to addition (+) of cardinalities and to union of disjoint sets, (⊎). Strings are denoted using lower case bold letters. Sets and lists of strings are indicated by upper case bold letters, with their corresponding cardinalities indicated by upper case (non-bold) roman letters. Thus, as a trivial example, the set of all binary strings of length n will be denoted B_{n} fulfilling the recurrence relation

B_{n} = 0·B_{n−1} ⊎ 1·B_{n−1} for n > 0, (2)

where B_{0} = {ϵ}; the corresponding recurrence relation for its cardinality is B_{n} = 2B_{n−1} with B_{0} = 1, which has the closed form solution B_{n} = 2^{n}. Additionally, strings can be reversed. The reversal of a string s is denoted s^{R}; this notation is extended to sets of strings in the natural manner. For example, {0011, 0101}^{R} = {1100, 1010}. If s and t are strings then by s ≤ t we mean that s is lexicographically less than or equal to t; comparisons among strings are always with respect to lexicographic order.

An algorithm for generating combinatorial objects is said to be CAT, standing for \underline{C}onstant \underline{A}mortized \underline{T}ime, if it has running time O(p(n) + N), where N is the total number of objects generated, and p(n) is a polynomial in n, where n is the “size” of the object being generated. The term p(n) is meant to represent any time spent in preprocessing. In this paper N is exponential in n and so the p(n) term can be ignored. The algorithms that we consider are recursive and the underlying computation tree provides a great conceptual aid in analyzing the behavior of the algorithm. In many algorithms the total amount of computation is proportional to the number of nodes in the computation tree; the algorithms we present have this feature. A desirable property of a generation algorithm is that an object is produced at every leaf (terminal vertex) of the computation tree. We call this the BEST^{1} property (for \underline{B}acktracking \underline{E}nsuring \underline{S}uccess at \underline{T}erminals). The CAT principle states sufficient conditions for a BEST algorithm to run in constant amortized time. These conditions are: (a) in the computation tree, there are not “too many” nodes in the computation tree with a single child and (b) the total computation can be partitioned so that each node is assigned constant time computation. In particular, if the degree of each non-leaf is at least two, then there are more leaves than internal nodes and so condition (a) is met. The CAT principle is the most common way of showing that a recursive algorithm runs in constant amortized time.

1The CAT and BEST acronyms are due to the second author.

In Section 2 we present a BEST CAT algorithm for the binary case k = 2. In Section 3 we present a non-BEST algorithm that is CAT for fixed k ≥ 2; this algorithm is analyzed in Sections 4 and 5. The analysis of Section 4 provides an exact count of the number of operations used by the algorithm for k = 3 and k = 4. In principle this type of analysis could be extended to larger values of k. The asymptotic analysis of Section 5 is based on the expected length of the longest common prefix of two infinite canonical k-ary strings. This quantity, which turns out to be O(\sqrt{k}), is of independent mathematical interest. In Section 6 we indicate how our algorithms solve the problem of listing non-isomorphic k-paths, which was our initial motivation for studying the problem. The final section suggest some interesting open problems.

2 Generating Binary Strings

In order to analyze equivalence classes under the group actions of symbol permutations (i.e., complementation in the binary case) and under string reversal, we shall look first at the the problem of listing all equivalence classes under reversal only. That is to say, two bitstrings a_{1}a_{2} ⋯ a_{n} ≠ b_{1}b_{2} ⋯ b_{n} are considered equivalent if a_{1}a_{2} ⋯ a_{n} = b_{n} ⋯ b_{2}b_{1}. Given two equivalent bitstrings we will list the one that is lexicographically (i.e., numerically) smaller. Thus, for example, 1010011 is listed but 1100101 is not. Let the set of listed bitstrings be denoted M_{n}.

M_{n} =^{def} {s ∈ B_{n} | s ≤ s^{R}} (3)

The recurrence relation for this set follows the observation that only identical first and last bits allow for symmetry under reversal. Thus, M_{0} = {ϵ}, M_{1} = {0, 1}, and

M_{n} = 0M_{n−2}0 ⊎ 0B_{n−2}1 ⊎ 1M_{n−2}1. (4)

We use L_{n} to denote those elements of M_{n} that are non-palindromic.

L_{n} =^{def} {s ∈ B_{n} | s < s^{R}} = {s ∈ M_{n} | s ≠ s^{R}}

These sets of strings satisfy a recurrence relation of the same form as (4), but with different initial conditions. Here, L_{0} = L_{1} = ∅. The recurrence relation is

L_{n} = 0L_{n−2}0 ⊎ 0B_{n−2}1 ⊎ 1L_{n−2}1. (5)

If s is a bitstring then by \overline{s} we denote the complement of s. For example, \overline{1010011} = 0101100.

Observation 1: The operations of complement and reversal commute. That is, for all binary strings s, we have \overline{s^{R}} = \overline{s}^{R}

Observation 2: For all binary strings s and t, we have s ≤ t if and only if \overline{s} ≥ \overline{t}.

Observation 3: For all binary strings, if s ≤ s^{R} and s ≤ \overline{s}^{R}, then s ≤ \overline{s}. ^{2}

Observations 1 and 2 are trivial. To prove Observation 3, note that by Observation 2, if s ≤ s^{R}, then \overline{s} ≥ \overline{s}^{R}. Thus, \overline{s} ≥ \overline{s}^{R} ≥ s.

Let Y_{n} denote the set of all bitstrings of length n that are lexicographically smallest in the equivalence classes induced by relation R defined by (1) in the introduction. Let N_{n} be the set of all non-palindromic elements of Y_{n}. For example, N_{4} = {0010, 0001, 0011, 0101} and Y_{4} = N_{4} ∪ {0000, 0110}. More formally,

Y_{n} =^{def} \{s ∈ B_{n} | s ≤ \overline{s}, s ≤ s^{R}, and s ≤ \overline{s}^{R}\} and (6)

N_{n} =^{def} {s ∈ Y_{n} | s ≠ s^{R}}. (7)

The sets Y_{n} and N_{n} admit the following recursive decompositions.

Lemma 1 For all n > 1,

Y_{n} = 0Y_{n−2}1 ⊎ 0N_{n−2}^{R}1 ⊎ 0M_{n−2}0, and (8)

N_{n} = 0Y_{n−2}1 ⊎ 0N_{n−2}^{R}1 ⊎ 0L_{n−2}0 (9)

The initial values are Y_{0} = {ϵ}, Y_{1} = {0}, and N_{0} = N_{1} = ∅.

2Also, s ≤ \overline{s} and s ≤ s^{R} implies that s ≤ \overline{s}^{R}. However, the example of s = 0100 shows that s ≤ \overline{s} and s ≤ \overline{s}^{R} does not imply s ≤ s^{R}.

Proof: To prove (8), first note that a string s in Y_{n} cannot start with a 1. If s = 0t0, then s ≤ \overline{s} and s ≤ \overline{s}^{R}, so the only remaining condition that has to be satisfied is s ≤ s^{R}. This is true if and only if t ≤ t^{R}. Thus, a string of the form 0t0 is in Y_{n} if and only if t ∈ M_{n−2}. If s = 0t1, then s ≤ s^{R} and s ≤ \overline{s}, so the only remaining condition that has to be satisfied is s ≤ \overline{s}^{R}. By Observation 3, Y_{n} = \{s ∈ B_{n} | s ≤ s^{R}, s ≤ \overline{s}^{R}\}. By Observation 2, the condition s ≤ \overline{s}^{R} is equivalent to the condition s^{R} ≤ \overline{s}. Thus,

\{s ∈ B_{n} | s ≤ \overline{s}^{R}\} = \{s ∈ B_{n} | (s ≤ s^{R} and s ≤ \overline{s}^{R}) or (s^{R} ≤ s and s^{R} ≤ \overline{s})\}
= Y_{n} ∪ Y_{n}^{R}.

Hence, a string of the form 0t1 is in Y_{n} if and only if t ∈ Y_{n−2} ∪ Y_{n−2}^{R}. Recurrence relation (8) follows by partitioning Y_{n−2} ∪ Y_{n−2}^{R} into the two disjoint sets Y_{n−2} and N_{n−2}^{R}.

The proof of (9) is similar and is omitted. □

These equations allow us to write a program for listing the elements of Y_{n} that runs in constant amortized time. One could write separate procedures for listing the elements of Y_{n}, N_{n}, L_{n}, M_{n}, and B_{n}. Pascal code for Y_{n} is given in Figure 1. The array s[1..n] of bits is global. Each procedure has two parameters lo and hi indicating the subarray of s whose bits still remain to be set. The initial call is Y(1,n), with no initialization necessary. Note that, aside from the recursive calls, only a constant amount of computation is done within Y. Further, any non-leaf call to Y has at least two (in fact three) children in the computation tree. Since each of the recurrences (2), (4), (5), (8), and (9) has at least two terms these same observations apply to other procedures called by Y. Thus we can invoke the CAT principle to conclude that the algorithm runs in constant amortized time.

3 Generating k-ary strings for k > 2

In this section we develop an algorithm for generating the lexicographically smallest k-ary strings from each equivalence class induced by the actions of reversing a string and permuting the symbols of its alphabet. We first generate the lexicographically smallest k-ary strings from from each equivalence class induced only by the action of permuting alphabet symbols, and then reject those strings that are not also lexicographically smallest when both group actions are used.

procedure Y ( lo, hi : integer );
begin
  if lo = hi then begin
     s[lo] := 0;  {s[hi] := 0;}  PrintIt;
  end else
  if lo+1 = hi then begin
     s[lo] := 0;   s[hi] := 0;   PrintIt;
     s[lo] := 0;   s[hi] := 1;   PrintIt;
  end else begin
     s[lo] := 0;   s[hi] := 0;   Mr( lo+1, hi-1 );
    {s[lo] := 0;}  s[hi] := 1;   Nr( lo+1, hi-1 );
    {s[lo] := 0;} {s[hi] := 1;}   Y( lo+1, hi-1 );
  end
end {of Y};

Figure 1: Pascal code for generating Y_{n}.

Definition 1 If s is a k-ary string, then by can(s) we denote the lexicographically smallest string π(s), taken over all permutations π of {0, 1, …, k − 1}. If s = can(s), then we say that s is canonical. The set of canonical k-ary strings of length n is denoted X_{n,k}.

For example, can(660240032644) = 001231142033. There may be several permutations π for which π(s) = can(s) (we think of the permutation π as an element of a group acting on the string s). In the example above, π = (0 1 6)(2)(3 4)(5) and π = (0 1 5 6)(2)(3 4) are such permutations. In order to define a unique permutation π_{s} such that π_{s}(s) = can(s), we assume that all elements of 0, 1, …, k − 1 not used in s or in can(s) form 1-cycles in π_{s}. Thus π_{s} = (0 1 6)(2)(3 4)(5) in our example. We will write permutations in cycle notation, because it is the cycle structure of these permutations that will be of most importance to us in the ensuing discussion.

The following lemma, whose proof is immediate, characterizes canonical strings.

Lemma 2 A string s = s_{1}s_{2} …s_{n} is canonical if and only if s_{1} = 0 and for all i = 1, …, n − 1,

s_{i+1} ≤ min(k − 1, 1 + max{s_{1}, …, s_{i}}). (10)

Sequences satisfying the conditions of the Lemma 2 are sometimes called “restrictedgrowth” functions (e.g., Stanton and White [17]) and are studied in connection with set partitions. The Stirling number of the second kind, denoted \left\{{n \atop k}\right\} count the number of restricted growth functions of length n with maximal value k. Let X_{n,k} = |X_{n,k} |. It is well-known that

X_{n,k} = ∑_{i=1}^{k} \left|{n \atop i}\right∥ . (11)

What is the asymptotic value of X_{n,k} for fixed k and large n? Note that X_{n,k} is the number of ways of placing n labeled balls into k unlabeled boxes and thus that k^{n}/k! ≤ X_{n,k} since there are at most k! distinct ways of labeling the boxes once the balls have been placed. On the other hand, \left\{{n \atop i}\right\} ≤ i^{n}/i! since i!\left\{{n \atop i}\right\} is the number of surjective functions from an n-set onto an i-set. Thus

\frac{k^{n}}{k!} ≤ X_{n,k} ≤ ∑_{i=1}^{k} \frac{i^{n}}{i!} .

From these upper and lower bounds we obtain the following asymptotic expression for X_{n,k} (with k fixed and n large).

X_{n,k} ∼ \frac{k^{n}}{k!} (12)

Definition 2 If s is a canonical k-ary string, then by mate(s) we denote the string can(s^{R}). If s = mate(s), then we say that s is symmetric. Let c(s) denote the length of the longest prefix common to both of s and mate(s).

Since the first symbol of both s and mate(s) is a zero, 1 ≤ c(s) ≤ n, where n is the length of s. Continuing our example, if s = 001231142033, then mate(s) = can(330241132100) = 001234402411 and c(s) = 5 since the largest prefix on which they agree is 00123. An example of a symmetric string is 0010231011.

We define Y_{n,k} =^{def} {s ∈ X_{n,k} | s ≤ mate(s)}.

Lemma 2 gives rise to a simple-minded algorithm generating all canonical strings of length n. The algorithm, which we call gen, is given in Figure 2. A similar algorithm for generating all set partitions (i.e., when the maximum block size k is n) was given by Er [1], and other iterative algorithms are given by Hutchinson [7], Kaye [8], Semba [16], and Stanton and White [17].

The call gen(l,m) generates all sequences s[l], …, s[n] such that 0 ≤ s[i] ≤ min(k − 1, 1 + max{m, s[l], …, s[i − 1]}) for i = l, l + 1, …, n. Here, parameter m is

procedure gen( l, m : integer );
var i : integer;
begin
 if l > n (* and Check *) then PrintIt
 else begin
     for i := 0 to m do begin
        s[l] := i;
        gen( l+1, m );
     end;
     if m < k-1 then begin
        s[l] := m+1;
        gen( l+1, m+1 );
     end;
 end;
end {of gen};

Figure 2: Pascal procedure to generate X_{n,k} (and Y_{n,k}).

function Check : boolean;
var
i, last: integer;
pi : array[0..100] of integer;
begin
for i := 0 to k - 1 do pi[i] := maxint; {#1}
last := 0;
i := n;
pi[s[n]] := 0;
while (i >= 1) and (s[n-i+1] = pi[s[i]]) do begin
   i := i - 1;
   if pi[s[i]] > last then begin
      last := last + 1;
      pi[s[i]] := last;
   end;
end;
Check := (i = 0) or (s[n-i+1] < pi[s[i]]);
end {of Check};

Figure 3: The Pascal function Check. the maximum value of s[1..l-1]. Given n, the initial call is gen(1,0). Assuming k > 1, note that every call to gen(l,m) for which l ≤ n generates at least two calls to gen(l+1,i) for some value of i. Thus there are more leaves than internal nodes in the computation tree and so the CAT principle implies that the algorithm runs in constant amortized time. Observe that the algorithm is BEST.

In order to generate the elements of Y_{n,k} we use gen and check whether each generated string s satisfies s ≤ mate(s). This checking is done by the procedure Check of Figure 3. With the addition of Check, algorithm gen is no longer BEST. Clearly, the amount of computation done by Check(s) is O(k + c(s)). The term k comes from the initialization (marked #1 in Figure 3) but that term can be eliminated by using a constant-time array initialization as explained, for example, in Lewis and Denenberg [10]. With this modification the running time of Check is O(c(s)).

To find the amortized cost per string generated we need to determine the average value of c(s), taken over all strings s in X_{n,k}. Denoting by X_{n,k}^{(c)} the number of strings s ∈ X_{n,k} for which c(s) = c, we define the weighted sum

S_{n,k} =^{def} ∑_{c=1}^{n} c·X_{n,k}^{(c)} . (13)

Define

A_{n,k} =^{def} \frac{S_{n,k}}{X_{n,k}} . (14)

The quantity of interest is S_{n,k} /Y_{n,k}, which is at most 2A_{n,k}.

4 Exact analysis for small values of k

In this section we give a general classification scheme useful in deriving exact expressions for S_{n,k}. Given a canonical string s, this classification is based upon the value of c(s) relative to the length of s and the cycle structure of π_{s}. This scheme is then used to derive exact expressions for S_{n,3} and S_{n,4}. The details of these derivations may be found in [12].

We wish to count those strings s ∈ Y_{n,k} with a fixed value of c(s). Let us first make a couple of observations. Consider a fixed canonical string s and let c = c(s) and π = π_{s^{R}}. If c < n, then let x = s_{c+1} and y = s_{n−c}. Clearly, π(y) ≠ x. There are five basic cases to consider: [I] 1 ≤ c < (n − 1)/2, [II] n is odd and c = (n − 1)/2,

[III] n is even and c = n/2, [IV] n/2 < c < n, and [V] c = n.

α  x  β  y  γ

[I]: In this case x is to the left of y in s as illustrated above. We denote by α the string s_{1}s_{2} ⋯ s_{c}, β = s_{c+2} ⋯ s_{n−c−1} , and γ = s_{n−c+1} ⋯ s_{n}.

α  x  γ

[II]: In this case x = y as illustrated above. Clearly, we must have π(x) ≠ x. Here α = s_{1}s_{2} ⋯ s_{m} and γ = s_{m+2} ⋯ s_{n}, where n = 2m + 1.

[III]: In cases III and IV, x is to the right of y in s. We must have π(x) = y (and π(y) ≠ x. Thus there is a j-cycle, where j ≥ 3, in π of the form (... x π(x) π(π(x)) ...) = (... x y z ...) for some z distinct from x and y. Hence, we must have k ≥ 3 for case III or IV to occur.

α  y  β  x  γ

[IV]: This case is illustrated above. Let β denote the string of symbols between x and y, β = s_{n−c} ⋯ s_{c}. If a = s_{j} and b = s_{n−j+1} for some n − c < j < c, then we must have π(a) = b and π(b) = a. Thus a and b are either both in 1-cycles (a)(b) or a 2-cycle (a b) of π. Hence, in order for case IV to occur (i.e., β is non-empty), we must have k ≥ 4.

[V]: In case V the string is symmetric and π must consist of 1-cycles and 2-cycles.

4.1 Ternary strings

Here case [IV] cannot occur. For k = 3 and even n,

S_{n,3} = \frac{5}{16}3^{n} + \frac{1}{6}(2n − 3)3^{n/2} + \frac{n}{4} + \frac{3}{16}.

For odd n,

S_{n,3} = \frac{5}{16}3^{n} + \frac{1}{2}(n − 2)3^{(n−1)/2} + \frac{n − 1}{4} + \frac{9}{16}.

The above expressions, together with (12) for k = 3 show that the average value of c(s) tends to 3! · 5/16 = 15/8 = 1.875 as n gets large.

4.2 Quaternary Strings

We now show the results for k = 4. If n = 2m, then

S_{n,4} = \frac{26}{315}4^{n} + \frac{5}{12}m2^{n} + \frac{5}{18}2^{n} − \frac{15}{14}2^{m} + \frac{4}{3}m + \frac{32}{45}. (15)

If n = 2m + 1 is odd then we have

S_{n,4} = \frac{26}{315}4^{n} + \frac{1}{3}m2^{n} + \frac{7}{18}2^{n} − \frac{9}{7}2^{m} + \frac{4}{3}m + \frac{53}{45}. (16)

Thus, when k = 4, the average value of c(s) tends to 24·26/315 = 1.980952381... as n gets large.

In the next section we will show that asymptotically A_{n,k} is O(\sqrt{k}) as n ) .

5 Asymptotic Analysis

For fixed k, we now show how to determine the asymptotic value of A_{n,k}. We first show that, asymptotically, the average value of c(s) is the same as the expected position of the first mismatch between two canonic infinite length k-ary strings.

Lemma 3 Let s be chosen uniformly at random from X_{n,k}. With probability tending to 1 as n increases, c(s) < n/2.

Proof: If the mismatch occurs at a position greater than n/2, then the reversal of the last n/2 symbols of s is equivalent, under some permutation of the k alphabet symbols, to the first n/2 symbols of s. The number of such strings is thus at most k!X_{n/2,k} . By (12), the fraction of these strings in the set X_{n,k} is k! · k^{−n/2}, which tends to 0 when n grows. □

Denote by c(s, t) be the length of the longest prefix common to both s and t. The previously used c(s) is the same as c(s, mate (s)).

Lemma 4 Let s be chosen uniformly at random from X_{n,k} and t′ be chosen uniformly at random from B_{n,k}. Let t = can(t′). Then

lim ; n) A_{n,k} = ∑_{i≥1} i · Prob(c(s, t)) = i)

Proof: The fraction of strings in X_{n/2,k} that do not use the symbol k is X_{n/2,k−1} /X_{n/2,k} . By (12), this is asymptotically k((k − 1)/k)^{n/2}, which tends to 0 as n grows. Thus, with probability tending to 1, every symbol 0, 1, …, k − 1 occurs among the first n/2 symbols of a string s chosen uniformly at random from X_{n,k}. Thus, asymptotically, the substring s_{n/2} ⋯ s_{n} of s is a random string in B_{n/2,k} . By the previous lemma, c(s) < n/2 with probability tending to 1. Therefore, comparing s with its mate is asymptotically equivalent to comparing it with any random string in B_{n,k}. □

It proves useful to have a notation X_{n,k,p} for the number of strings s = s_{1}s_{2} ⋯ s_{n} satisfying s_{1} = p and the restricted growth condition (10). Thus, X_{n,k,0} = X_{n,k}. These numbers have also been studied before in connection with ranking algorithms for restricted growth functions in lexicographic order (see Williamson [19], [20] where they are called “restricted tail coefficients”). These numbers satisfy the following recurrence relation for n > 0.

X_{n,k,p} = (p + 1)X_{n−1,k,p} + X_{n−1,k,p+1} (17)

Lemma 5 The following two limits hold.

lim ; n) \frac{X_{n,k,p}}{X_{n+1,k,p}} = \frac{1}{k} (18)

lim ; n) \frac{X_{n,k,p+1}}{X_{n+1,k,p}} = 1 − \frac{p + 1}{k} (19)

Proof: Recall that by (12), X_{n,k} ∼ k^{n}/k!. The lemma follows from the following asymptotic, which may be proven by induction using (17).

X_{n,k,p} ∼ \frac{(k)_{p+1}k^{n−1}}{k!}

Note: by (k)_{j} we denote the falling factorial power (k)_{j} = k(k − 1) ⋯ (k − j + 1). □

Lemma 6 Let s be an element of X_{n,k} chosen uniformly at random. Then

lim ; n) Prob_{n}(s_{i} = j | max(s_{1}, …, s_{i−1}) = p) = / \begin{matrix}1/k & if 0 ≤ j ≤ p \\ 1 − (p + 1)/k & if j = p + 1. \end{matrix}

Proof: The number of strings in X_{n,k} whose largest value in the first i−1 positions is p is \left\{{i−1 \atop p}\right\}X_{n−i+2,k,p} . The number of strings that, in addition, have a j in position i is \left\{{i−1 \atop p}\right\}X_{n−i+1,k,p} if 0 ≤ j ≤ p, and is \left\{{i−1 \atop p}\right\}X_{n−i+1,k,p+1} if j = p + 1. To complete the proof, divide each of the latter numbers by the first and apply Lemma 5 to the respective quotients. □

Let s′ be an infinite length k-ary string chosen uniformly at random and s = can(s′). Note that

Prob(s_{i} = j | max(s_{1}, …, s_{i−1}) = p) = / \begin{matrix}1/k & if 0 ≤ j ≤ p \\ 1 − (p + 1)/k & if j = p + 1. \end{matrix} ,

exactly the same as the probabilities given in Lemma 6 above.

Let s′ and t′ be two infinite k-ary strings chosen uniformly at random and let s = can(s′) = s_{1}s_{2}s_{3} ⋯ and t = can(t′) = t_{1}t_{2}t_{3} · · ·. We have proven that

A_{k} = lim ; n) A_{n,k} = ∑_{i≥1} i · Prob(c(s, t) = i). (20)

Computing and analyzing A_{k} using (20) is the subject of the next two subsections.

5.1 The value of A_{k}

The purpose of this section is to prove the following rather attractive expression for A_{k} (below, the notation (k)_{j}^{2} means [(k)_{j}]^{2}, the square of the falling factorial).

Theorem 1  A_{k} = ∑_{j=1}^{k} \frac{(k)_{j}^{2}}{(k^{2} − 1)_{j}} .

Select s′ and t′ uniformly at random from the set of infinite length k-ary strings and let s = can(s′) and t = can(t′). Denote by β_{p} the probability that the first p symbols of s and t agree.

β_{i} =^{def} Prob(s_{1} = t_{1}, s_{2} = t_{2}, …, s_{i} = t_{i}) (21)

By classifying the prefix of the first i symbols of s′ and t′ according to j, the number of distinct symbols in that prefix, we obtain the following expression for β_{i}.

β_{i} = \frac{1}{k^{2i}} ∑_{j=1}^{k} (k)_{j}^{2}\left|{i \atop j}\right∥

By (20),

A_{k} = ∑_{i≥0} i · Prob(s_{1} = t_{1}, s_{2} = t_{2}, …, s_{i} = t_{i}, s_{i+1} ≠ t_{i+1})
= ∑_{i≥0} i · (β_{i} − β_{i+1})

= ∑_{i≥0} i ∑_{j=1}^{k} (k)_{j}^{2} (\frac{\left\{{i \atop j}\right\}}{k^{2i}} − \frac{\left\{{i+1 \atop j}\right\}}{k^{2i+2}} )

= ∑_{j=1}^{k} (k)_{j}^{2} ∑_{i≥0} \frac{1}{k^{2i}} \left|{i \atop j}\right∥  (22)

The inner sum of (22) can be simplified by using the following identity from Wilf [18] (equation (1.6.5) on page 19).

∑_{n} \left|{n \atop k}\right∥ x^{n} = \frac{x^{k}}{(1 − x)(1 − 2x) ⋯ (1 − kx)} (23)

Setting x to k^{−2} and k to j in (23) and substituting into (22) finishes the proof of Theorem 1. It is remarkable that A_{k} has such a simple expression; perhaps there is a direct combinatorial proof.

5.2 The Asymptotic Value of A_{k}

Our goal in this section is to prove the following theorem.

Theorem 2  A_{n} = \frac{1}{2}\sqrt{π · n} − \frac{1}{6} + o(1).

In this section we will use A_{n} instead of A_{k}, as is customary in the asymptotics literature. Our main technique is called “trading tails” in Graham, Knuth, and Patashnik [4] (starting at page 452). In principle, our techniques could be applied to obtain additional terms in the asymptotic expansion of A_{n}. With this in mind, some of the expressions below are given with greater generality than is strictly necessary to prove Theorem 2.

We start by presenting Taylor’s expansion of ln(1 − z) and an identity involving the Bernoulli numbers. The expansion below is valid for z ) 0 (e.g., page 438 of [4]). This is just Taylor’s expansion with remainder.

ln(1 − z) = − ∑_{k=1}^{p} \frac{z^{k}}{k} + O(z^{p+1}). (24)

From Concrete Mathematics [4] (exercise 9.30, page 477 with solution on page 570),

∑_{r≥0} r^{l−1}e^{−r^{2}/n} = \frac{1}{2}n^{l/2}Γ(\frac{l}{2}) − ∑_{k=0}^{p} \frac{(−1)^{k}B_{l+2k}}{n^{k}(l + 2k)!k!} + O(\frac{1}{n^{p+1}} ), (25)

where B_{0}, B_{1}, B_{2}, B_{3}, B_{4}, … = 1, −\frac{1}{2}, \frac{1}{6}, 0, −\frac{1}{30}, 0, … are the Bernoulli numbers (see, for instance, Section 6.5 of [4]) and Γ is the gamma function with Γ(1/2) = \sqrt{π}, Γ(3/2) = \frac{1}{2} \sqrt{π}, Γ(5/2) = \frac{3}{4} \sqrt{π}, and Γ(l) = (l − 1)! if l is an integer.

In particular, setting l = 1, 2, 4, 5 in (25) yields

∑_{r≥1} e^{−r^{2}/n} = \frac{1}{2}\sqrt{πn} − \frac{1}{2} + o(1), (26)

\frac{1}{n} ∑_{r≥1} re^{−r^{2}/n} = \frac{1}{2} + o(1), (27)

\frac{1}{n^{2}} ∑_{r≥1} r^{3}e^{−r^{2}/n} = \frac{1}{2} + o(1), (28)

\frac{1}{n^{3}} ∑_{r≥1} r^{4}e^{−r^{2}/n} = o(1). (29)

Recall that

A_{n} = ∑_{r=1}^{n} \frac{(n)_{r}^{2}}{(n^{2} − 1)_{r}} = ∑_{r=1}^{n} ∏_{x=0}^{r−1} \frac{(n − x)^{2}}{n^{2} − x − 1} ,

and define

T(n, r) =^{def} \frac{n^{2}}{n^{2} − r} ∏_{x=1}^{r−1} \frac{(n − x)^{2}}{n^{2} − x} = \frac{1}{1 − \frac{r}{n^{2}}} ∏_{x=1}^{r−1} \frac{(1 − \frac{x}{n})^{2}}{1 − \frac{x}{n^{2}}}. (30)

For any small fixed ϵ > 0 we may write A_{n} as

A_{n} = ∑_{r=1}^{n} T(n, r) = ∑_{r=1}^{n^{1/2+ϵ}} T(n, r) + ∑_{r=1+n^{1/2+ϵ}}^{n} T(n, r) (31)

Take logarithms of T(n, r) as expressed in the right hand side of (30) and then use (24) to obtain the following equality, valid for any r, r/n ) 0 and any natural numbers p and q,

ln(T(n, r)) = 2 ∑_{x=1}^{r−1} ln(1 − \frac{x}{n}) − ∑_{x=1}^{r} ln(1 − \frac{x}{n^{2}} )
= (−2 ∑_{k=1}^{p} \frac{1}{kn^{k}} ∑_{x=1}^{r−1} x^{k} + O(\frac{r^{p+2}}{n^{p+1}} )) + (∑_{k=1}^{q} \frac{1}{kn^{2k}} ∑_{x=1}^{r} x^{k} + O(\frac{r^{q+2}}{n^{2q+2}} ))

Setting p = 2 and q = 0 in the above expression, we obtain

ln(T(n, r)) = (−\frac{r(r − 1)}{n} − \frac{r(r − 1)(2r − 1)}{6n^{2}} + O(\frac{r^{4}}{n^{3}} )) + (O(\frac{r^{2}}{n^{2}} ))
= −\frac{r^{2}}{n} + \frac{r}{n} − \frac{r^{3}}{3n^{2}} + O(\frac{r^{4}}{n^{3}} ).

Thus, exponentiating the above and using the power series expansion of e^{x},

T(n, r) = exp(−\frac{r^{2}}{n} ) exp(\frac{r}{n} ) exp(−\frac{r^{3}}{3n^{2}} ) exp(O(\frac{r^{4}}{n^{3}} ))
= exp(−\frac{r^{2}}{n} )(1 + \frac{r}{n} + O(\frac{r^{2}}{n^{2}} ))(1 − \frac{r^{3}}{3n^{2}} + O(\frac{r^{6}}{n^{4}} ))(1 + O(\frac{r^{4}}{n^{3}} ))
= exp(−\frac{r^{2}}{n} )(1 + \frac{r}{n} − \frac{r^{3}}{3n^{2}} + O(\frac{r^{4}}{n^{3}} )).

Substituting the four expressions (26–29) into the sum ∑ _{r} T(n, r) and using the last derived expression for T(n, r), we obtain

∑_{r≥1} T(n, r) = ∑_{r≥1} exp(−\frac{r^{2}}{n} )(1 + \frac{r}{n} − \frac{r^{3}}{3n^{2}} + O(\frac{r^{4}}{n^{3}} ))  (32)
= \frac{1}{2}\sqrt{nπ} − \frac{1}{6} + o(1).

For any fixed integer j, small ϵ > 0, n^{1/2+ϵ} ≤ r ≤ n, and large enough n, note that

r^{j}e^{−r^{2}/n} < e^{−r^{2}/(2n)} .

Thus (following [4], page 474),

∑_{r>n^{1/2+ϵ}} r^{j}e^{−r^{2}/n} < ∑_{r>n^{1/2+ϵ}} e^{−r^{2}/(2n)}
< exp(−⌊n^{1/2+ϵ} ⌋^{2}/(2n))(1 + e^{−1/(2n)} + e^{−2/(2n)} + ⋯)
= O(e^{− \frac{1}{2} n^{2ϵ}} ) · O(n)
= O(n^{−M} ) for any fixed M.

Substituting j = 0, 1, 3, 4 into (32), we get

∑_{r=1}^{n^{1/2+ϵ}} T(n, r) = \frac{1}{2}\sqrt{nπ} − \frac{1}{6} + o(1). (33)

It remains only to show that the second sum on the right hand side of (31) is o(1). Lemma 7 For all j ≥ 0 and ϵ > 0,

lim ; n) n^{j} (1 − \frac{1}{n} )^{n^{1+ϵ}} = 0.

Proof: Rewriting and exploiting continuity, we obtain

exp( lim ; n) ln (n^{j} (1 − \frac{1}{n} )^{n^{1+ϵ}} ))

= exp( lim ; n) (j lnn + n^{1+ϵ}(ln(n − 1) − lnn) )

= exp( lim ; n) \frac{jn^{−(1+ϵ)} lnn + ln(n − 1) − lnn}{n^{−(1+ϵ)}} )

The limit may now be evaluated by using L’Hopital’s rule.

= exp( lim ; n) \frac{j(n^{−(2+ϵ)} − (1 + ϵ)n^{−(2+ϵ)} lnn) + \frac{1}{n−1} − \frac{1}{n}}{−(1 + ϵ)n^{−(2+ϵ)}} )

= exp( lim ; n) (−\frac{j}{1 + ϵ} + j lnn − \frac{n^{2+ϵ}}{n(n − 1)(1 + ϵ)} ))

= exp( lim ; n) (O(1) + o(n^{ϵ}) + \frac{n^{ϵ}}{(n − 1)(1 + ϵ)} − \frac{n^{ϵ}}{1 + ϵ}))

= exp( lim ; n) (o(n^{ϵ}) − \frac{n^{ϵ}}{1 + ϵ})) = 0

□

Lemma 8 If r ≥ n^{1/2+ϵ} where ϵ > 0, then

T(n, r) = O(n^{−M} ), for any fixed M.

Proof: Note that the quantities T(n, r) are monotonically decreasing in r, and thus we need only consider T(n, n^{1/2+ϵ} ). First, split the definitional product (30) into two factors and then bound each factor.

T(n, n^{1/2+ϵ} ) = \frac{n^{2}}{n^{2} − n^{1/2+ϵ}} ∏_{x=1}^{⌊ \frac{1}{2} n^{1/2+ϵ} ⌋} \frac{(n − x)^{2}}{n^{2} − x} ∏_{x=⌊ \frac{1}{2} n^{1/2+ϵ} ⌋+1}^{n^{1/2+ϵ}} \frac{(n − x)^{2}}{n^{2} − x} ·

T(n, n^{1/2+ϵ} ) ≤ 2 (\frac{(n − \frac{1}{2}n^{1/2+ϵ} )^{2}}{n^{2} − \frac{1}{2}n^{1/2+ϵ}} )^{\frac{1}{2} n^{1/2+ϵ}}
= 2 (1 − \frac{n^{3/2+ϵ} − \frac{1}{4}n^{1+2ϵ} − \frac{1}{2}n^{1/2+ϵ}}{n^{2} − \frac{1}{2}n^{1/2+ϵ}} )^{\frac{1}{2} n^{1/2+ϵ}}

This last expression grows like

2 (1 − \frac{1}{n^{1/2−ϵ}} )^{\frac{1}{2} n^{1/2+ϵ}}

which by Lemma 7 is O(n^{−M} ) for any fixed M. □

From Lemma 8 it follows that

∑_{r=1+n^{1/2+ϵ}}^{n} T(n, r) = O(n^{−M} ), for any fixed M.

This last equation, together with (33) proves Theorem 2.

6 Application: generating k-paths

A generalization of trees yields the notion of k-trees as the skeletons of acyclic simplicial complexes for dimensions higher than 2: For a fixed k, the complete graph with k + 1 vertices, K_{k+1}, is a k-tree, and every k-tree with more vertices can be constructed from a smaller k-tree by adding a new node and making it adjacent to all vertices of a K_{k} subgraph. Thus, every k-tree has at least two vertices of degree

[figure: 1; 1; 1; 1; 1; 0; 0; 0; 0; 0]

Figure 4: The 2-path corresponding to the binary string 0011011001.

k, k-leaves, and every minimal separator (a set of vertices disconnecting the graph, minimal with respect to set inclusion) consists of k mutually adjacent vertices [13]. (We will say that this set induces K_{k}.) In the simplest case of a k-tree with exactly two k-leaves, we have a generalization of a path, namely a k-path. The two k-leaves of a k-path (say, u and v) are connected by k unique vertex-disjoint paths and every minimal separator contains exactly one vertex of each path [11]. One can view the construction process of such a graph as starting with one k-leaf, say u, of K_{k+1}, and then adding vertices until the other desired k-leaf, say v, is added, completing the construction. Recording which of the (eventual) vertex disjoint paths are augmented during the process, gives the unique string over an alphabet of k symbols corresponding to the particular construction process (see Figure 4). A given k-path can be constructed in this manner from either of its ends (from u or from v) and vertex disjoint paths can be identified by any of the k! permutations of symbols 0, 1, …, k − 1. Thus the problem of listing all non-isomorphic k-paths can be dealt with as the problem of listing all equivalence classes of strings of k symbols, under the group actions of string reversal and/or symbol permutation.

7 Final Remarks

We list below some open problems that are inspired by or related to the problems considered in this paper.

1. Is there a direct combinatorial proof of the simple expression in Theorem 1 for A_{k}?

2. Is there a CAT BEST algorithm for generating the elements of Y_{n,k} when k > 2? The results of Section 2 show that Y is a context-free language for k = 2 and it is an unambiguous grammar for this language that leads us to the CAT algorithm. Can such a grammar be found for larger values of k?

3. Can these results be extended to generate all non-isomorphic k-trees? Here, even the counting problem is unsolved. Related enumeration (counting) results are reported in Harary and Palmer [5] and Hering, Read, and Shephard [6].

4. Does there exist a CAT algorithm to generate all k-ary strings where the group acting on the string contains rotations as well as permutations of the symbols and/or reversal of the string? The lexicographically smallest strings in classes of strings equivalent under rotations are referred to as necklaces. These are useful, for example, in generating de Bruijn sequences.

8 Acknowledgement

We wish to thank Andrew Odzlyko, and also Philippe Flajolet and Bruno Salvy for their help in proving Theorem 2. They responded to a query posted to the internet newsgroup sci.math.research. We also wish to thank Peter Winkler for helpful discussions and the referees for carefully reading the paper and making many useful suggestions.

References

[1] M.C. Er, “A Fast algorithm for generating set partitions”, The Computer Journal 31 (1988) 283-284.

[2] H. Fredricksen and I.J. Kessler, “An algorithm for generating necklaces of beads in two colors”, Discrete Mathematics, 61 (1986) 181-188.

[3] H. Fredricksen and I.J. Maiorana, “Necklaces of beads in k colors and k-ary de Bruijn sequences”, Discrete Mathematics, 23 (1978) 207-210.

[4] R.L. Graham and D.E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1989.

[5] F. Harary and E.M. Palmer, “On acyclic simplicial complexes”, Mathematika, 15 (1968) 115-122.

[6] F. Hering, R.C. Read, and G.C. Shephard, “The enumeration of stack polytopes and simplicial clusters”, Discrete Mathematics, 40 (1982) 203-217.

[7] G. Hutchinson, “Partitioning algorithms for finite sets”, CACM, 6 (1963) 613-614.

[8] R.A. Kaye, “A Gray code for set partitions”, Information Processing Letters, 5 (1976) 171-173.

[9] D.E. Knuth, The Art of Computer Programming, vol. I, Fundamental Algorithms, 2nd Ed., Addison-Wesley, 1973.

[10] H. R. Lewis and L. Denenberg, Data Structures & Their Algorithms, Harper-Collins, New York, 1991.

[11] A. Proskurowski, “Separating subgraphs in k-trees: Cables and Caterpillars”, Discrete Math. 49(1984), 275-285.

[12] A. Proskurowski, F. Ruskey, and M. Smith, “Analysis of algorithms for generating k-paths”, DCS-178, Tech. Report, Univ. of Victoria, 1992.

[13] D.J. Rose, “Triangulated graphs and the elimination process”, J. Math. Anal. Appl. 32 (1970) 597-609.

[14] F. Ruskey, C.D. Savage, and T. Wang, “Generating necklaces”, J. Algorithms, 13 (1992) 414-430.

[15] F. Ruskey, “Listing all bitstrings inequivalent under reversal”, unpublished manuscript, 1990.

[16] I. Semba, “An efficient algorithm for generating all partitions of the set {1, 2, …, n}”, Journal of Information Processing, 7 (1984) 41-42.

[17] D. Stanton and D. White, Constructive Combinatorics, Springer-Verlag, 1986.

[18] H.S. Wilf, Generatingfunctionology, Academic Press, 1990.

[19] S. G. Williamson, Combinatorics for Computer Science, Computer Science Press, 1985.

[20] S. G. Williamson, “Ranking algorithms for lists of partitions”, SIAM J. Computing, 5 (1976) 602-617.