Printer Friendly

A combinatorial approach to the Tanny sequence.

1 Introduction

Let G = (V, E) be a simple, finite, undirected graph. For S [subset or equal to] V, G[S] denotes the subgraph of G induced by the vertices in S. Let T be a rooted tree. The depth of T is the number of nodes present in the longest path starting from the root and ending at a leaf. Let T = (V, E) be a tree rooted at a vertex r. For a vertex x [member of] V, all the vertices from r to x are called ancestors of x. If x is an ancestor of y then y is called a descendant of x. Note that x is a descendant of x itself.

A fibonacci sequence is a sequence of numbers defined by the recurrence relation a(n) = a(n - 1) + a(n - 2) with a(0) = 1 and a(1) = 1. In [11], Hofstadter defined the sequence Q(n) by

Q(n) = Q(n - Q(n - 1)) + Q(n - Q(n - 2)), n > 2

with Q(1) = Q(2) = 1. He remarked on the apparent parallel between Q(n) and the usual fibonacci recursion as follows: "Each new value is a sum of two previous values-but not of the immediately two values". Guy [6] reports that Malm called Q(n) a 'meta-Fibonacci sequence', motivated by the above observation.

In [18], Tanny defined a sequence recursively as T(n) = T(n - 1 - T(n - 1)) + T(n - 2 - T(n - 2)), T(0) = T(1) = T(2) = 1. This sequence is known as Tanny sequence which is a close relative of the Hofstadter sequence. He showed that in sharp contrast to the 'chaotic' behavior of Q(n), T(n) behaves in a completely predictable fashion. Jackson and Ruskey [13] were the first to give a combinatorial way to interpret some special meta-Fibonacci sequences.

A combinatorial interpretation of Tanny sequence similar to that given in [13] is developed in [2]. They used this interpretation to relate the Tanny sequence with the so called discrete connected isoperimetric problem on infinite complete binary trees. In this paper we will use the combinatorial interpretation developed in [2]. Next we describe the relevant results from [2] in detail.

[FIGURE 1 OMITTED]

Definition 1.1 Let T be a tree rooted at r and has k children, say [c.sub.1], [c.sub.2], ..., [c.sub.k]. Let [T.sub.1], [T.sub.2], ..., [T.sub.k] be the subtrees of T rooted at [c.sub.1], [c.sub.2], ..., [c.sub.k], respectively. The V LR-traversal of T (also known as pre-order traversal) is defined as follows:

1. Visit the root.

2. Visit [T.sub.1] in V LR-order.

k + 1. Visit [T.sub.k] in V LR-order.

The ordering of the vertices of T which is associated with the V LR-traversal is known as V LR-ordering.

Let [T.sub.2] be an infinite complete binary tree. See Figure 1 for illustration. We assume the leaf of [T.sub.2] to be at depth one. The depth of a vertex v, denoted as dep(v), is the number of vertices present in the shortest path starting from v and ending at a leaf. Let T' be a subtree of [T.sub.2]. A leaf of T' is called a true leaf if it is also a leaf of T2. The infinite path starting from the left most leaf of T2 to the root of T2 is called the back bone of T2. (It is shown in bold edges in Figure 1.)

Definition 1.2 For a given integer i, i > 0, let d be the integer such that [2.sup.d-1] [less than or equal to] i [less than or equal to] [2.sup.d] - 1 and [T.sup.d.sub.2] be the complete binary tree of depth d. Clearly there exists a subtree of [T.sub.2] isomorphic to [T.sup.d.sub.2] such that the leaves of this subtree are at depth one and its root situated on the backbone of [T.sub.2]. A V LR-tree of i nodes, denoted as V LR(i), is a subtree of [T.sub.2] induced by the set of first i vertices in the V LR-ordering of such a subtree of [T.sub.2] isomorphic to [T.sup.d.sub.2].

Note that, for a given i, V LR(i) is uniquely defined. The combinatorial interpretation of T(n) developed in [2] is summarized in the following theorem.

Theorem 1.1 ([2]) For a positive integer n, the number of true leaves of V LR(n) equals T (n), the Tanny value at n.

Definition 1.3 For S [subset or equal to] V, the edge boundary [delta](S, G) is the set of edges of G with exactly one end point in S. In other words,

[delta](S, G) = {(u, v) [member of] E : u [member of] S and v [member of] V - S}

An edge which is present in [delta](S, G) is called an out going edge of S.

Definition 1.4 Let i be an integer where 1 [less than or equal to] i [less than or equal to] [absolute value of V]. For each i define the edge isoperimetric value [b.sub.e](i, G) of G at i as follows

[b.sub.e](i, G) = [min.sub.S[subset or equal to]V]; [absolute value of S]=i] [absolute value of [delta](S, G)]

The discrete isoperimetric problem on G is to find the value of [b.sub.e](i, G), for each i, 1 [less than or equal to] i [less than or equal to] i [absolute value of V(G)]. Discrete isoperimetric inequalities form a very useful and important subject in graph theory and combinatorics. See [1, 4, 16, 17] for more details.

Note that the subgraph G[S] induced by the set of vertices of S which gives the minimum edge boundary need not be connected in general. Next we define a special kind of isoperimetric value by putting some restriction on the set S.

Definition 1.5 Let i be an integer where 1 [less than or equal to] i [less than or equal to] [absolute value of V]. For each i define the connected edge isoperimetric value [b.sub.c](i, G) of G at i as follows:

[b.sub.c](i, G) = [min.sub.S[subset or equal to]V]; [absolute value of S]=i] [absolute value of [delta](S, G)]

The discrete connected isoperimetric problem on G is to find the value of [b.sub.c](i, G), for each i, 1 [less than or equal to] i [less than or equal to] [absolute value of V(G)].

In this paper we deal with infinite complete binary trees only. So, for convenience we denote [b.sub.c](i, [T.sub.2]) as [b.sub.c](i). Theorem 1.1 is used in [2] to relate the Tanny value to connected discrete isoperimetric problem on [T.sub.2].

Theorem 1.2 ([2]) For [T.sub.2], [b.sub.c](i) = i + 2 - 2T(i), for each i, i [greater than or equal to] 1, where T(i) is the Tanny value at i.

The following theorem is from [2] which relates the connected isoperimetric problem on [T.sub.2] with the boundary of the V LR tree.

Theorem 1.3 ([2]) Let [T.sub.2] be an infinite complete binary tree. Then for a positive integer n, [b.sub.c](n) = [absolute value of [delta](V LR(n),[T.sub.2])].

Remark 1. Since T2 is an infinite complete binary tree, [b.sub.c](n) [greater than or equal to] 1, for every positive integer n. Also, it is easy to see from Theorem 1.3 that 1 [less than or equal to] [b.sub.c](n) [less than or equal to] [log n].

Consider the tree V LR(i). Let [2.sup.d-1] [less than or equal to] i [less than or equal to] [2.sup.d] - 1. So, the depth of V LR(i) is d. Let the root of the tree V LR(i) be r and [r.sub.l] and [r.sub.r] be the left child and the right child of r, respectively. By the construction of V LR(i) and by the choice of d, it is easy to see that the descendants of r in V LR(i) form a complete binary tree of depth d - 1. When i > [2.sup.d-1], i - [2.sup.d-1] vertices of V LR(i) are present in the subtree (of V LR(i)) rooted at [r.sub.r].

[FIGURE 2 OMITTED]

Define a path [v.sub.1], [v.sub.2], ..., [v.sub.k] in V LR(i) starting from the root as follows: [v.sub.1] = r and [v.sub.j], 2 [less than or equal to] j [less than or equal to] k, is the right child of [v.sub.j-1] if the right child of [v.sub.j-1] is present in V LR(i), otherwise if only the left child of [v.sub.j-1] is present in V LR(i) then [v.sub.j] is the left child of [v.sub.j-1]. If both the children of [v.sub.j-1] are not present in V LR(i) then the path ends at [v.sub.j-1], that is [v.sub.j-1] = [v.sub.k]. This path is called the primary path of V LR(i). Note that when i = [2.sup.d-1], the primary path of V LR(i) consists of only one vertex, the root r of V LR(i). In Figure 2, the path a - b - c - d is the primary path of V LR(19).

By the definition of the primary path it is easy to see that if e is an outgoing edge of V LR(i) then it is incident on some vertex of the primary path. If u is a vertex in the primary path such that an outgoing edge of V LR(i) is incident on u then either the next node after u in the path is the left child of u or u is the last vertex of the primary path and it is not a true leaf. A vertex of the primary path on which an outgoing edge is incident is called an active vertex. It is easy to see that the first vertex of the primary path, that is the root of the tree V LR(i) is always an active vertex. The end vertex of the primary path is called the terminal vertex. Note that, the terminal vertex need not be an active vertex. The active vertex on the primary path which is situated at the least depth is called the tip of the primary path. In a primary path, the terminal vertex and the tip vertex need not be same, in particular if the terminal vertex is a true leaf, then it cannot be the tip. In V LR(19), the terminal vertex and the tip of the primary path are same. See Figure 2 for illustration.

Observation 1. Let P be the primary path of V LR(i), [2.sup.d-1] < i < [2.sup.d] - 1, and [v.sub.tip], [v.sub.t] be the tip and the terminal vertex of P, respectively. If [v.sub.tip] = [v.sub.t], then in V LR(i + 1), the primary path P' is the path P [union] [v.sub.l], where [v.sub.l] is the left child of [v.sub.tip] in [T.sub.2]. If [v.sub.tip] and [v.sub.t] are not same, then the primary path P' of V LR(i + 1) is the path P [union] [v.sub.r], where [v.sub.r] is the right child of [v.sub.tip] in [T.sub.2].

Observation 2. Let P be the primary path of V LR(i). If the tip of P is at depth two, then V LR(i + 1) contains one more true leaf than V LR(i), otherwise number of true leaves in V LR(i) and V LR(i + 1) are same.

Observation 3. Let P be the primary path of V LR(i) for some i and v be the terminal vertex of P. If [absolute value of V(P)] [greater than or equal to] 2 and v is not a true leaf then v is an active vertex and moreover two outgoing edges of V LR(i) are incident on v.

Observation 4. Let P = [v.sub.1], [v.sub.2], ..., [v.sub.p], ..., [v.sub.q] be the primary path of V LR(i), for some positive integer i such that [v.sub.q] is a true leaf and [v.sub.p] is the tip of P. Let P' = [v.sub.1], [v.sub.2], ..., [v.sub.p] and S = {[v.sub.1], [v.sub.p]} [union] {[v.sub.i] [member of] V(P') - {[v.sub.1], [v.sub.p]}|[v.sub.i] is not an active vertex of P'}. Note that, since the tip of the primary path can never be a true leaf, we have dep([v.sub.p]) [greater than or equal to] 2. Now, clearly V LR(i) contains exactly [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] number of true leaves. Let t be the smallest integer such that V LR(t) has N number of true leaves, where N is a given positive integer. For [v.sub.h] [member of] S, let left([v.sub.h]) denote the complete subtree rooted at the left child of [v.sub.h]. Since V(P') does not contain any true leaf, the set of true leaves of V LR(t) is exactly the union of true leaves of the complete binary trees {left([v.sub.h]) : [v.sub.h] [member of] S}. A careful look at V LR(t) will reveal that the vertices of V LR(t) is exactly union of all the vertices in the complete sub-trees {left([v.sub.h]) : [v.sub.h] [member of] S} and V(P'). That is, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Observation 5. Let N be a positive integer and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let t be the smallest positive integer such that V LR(t) contains N number of true leaves and P = [v.sub.1], [v.sub.2], ..., [v.sub.r] be the primary path of V LR(t). Since t is the smallest such number, the terminal vertex of P is the last vertex in the V LR ordering of V LR(i) and [v.sub.r] is a true leaf in V LR(t). Let [v.sub.tip] be the tip of P. By Observation 4, it is clear that the depth of [v.sub.tip is [k.sub.1] + 2. Now, it is easy to see that for j [member of] {t, t + 1, ..., t + [k.sub.1]}, V LR(j) has also N number of true leaves. Moreover, V LR(t + [k.sub.1] + 1) has N + 1 true leaves. That is, t + [k.sub.1] + 1 is the smallest integer such that V LR(t + [k.sub.1] + 1) contains N + 1 number of true leaves.

2 Graph theoretic proof of properties of T(n)

In this section we reprove the results of [18] combinatorially using Theorem 1.1 and the properties of V LR(i). In most of the cases we have also generalized the results.

Let T(n) be the Tanny sequence which is defined by the recurrence relation T(n) = T(n - 1 - T(n - 1)) + T(n - 2 - T(n - 2)), T(0) = T(1) = T(2) = 1.

The following Proposition of [18] follows from Observation 2.

Proposition 2.1 ([18]) For T(n) defined as above,

(a) T(n + 1) = T(n) or T(n + 1) = T(n) + 1.

(b) For n [greater than or equal to] 2, if T(n) is odd, T(n + 1) = T(n) + 1.

We can generalize Proposition 2.1(b) as follows:

Proposition 2.2 If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The following theorem follows from Observation 2.

Theorem 2.3 Let P be the primary path of V LR(n). Then, T(n + 1) = T(n) + 1 if and only if the tip of P is at depth 2.

Let [rho](N) = {n : T(n) = N}. By Proposition 2.1, the elements of [rho](N) consist of a sequence of consecutive integers. Let [absolute value of [rho](N)] denotes the cardinality of the set [rho](N).

Proposition 2.4 ([18]) If N > 1 is odd, then [absolute value of rho(N)] = 1. If N is even, then [absolute value of [rho](N)] [greater than or equal to] 2.

Proof: By the construction of the V LR tree it is easy to see that for any positive integer N, we can construct a V LR tree such that it contains exactly N number of true leaves. Hence for any N [greater than or equal to] 1, [rho](N) [not equal to] 0, that is the Tanny sequence hits every positive integer.

If N is odd, then [absolute value of [rho](N)] = 1 by Proposition 2.1. Next suppose that N is even. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since N is even, [k.sub.1] [greater than or equal to] 1. By Observation 5, V LR(t + 1) also contains N number of leaves. Hence [[rho](N)] [greater than or equal to] 2.

It is easy to find the elements of p(N) when N is of certain special form. For example, if N = [2.sup.x] for some x [greater than or equal to] 1, it is easy to find out the elements of [rho](N).

Proposition 2.5 ([18]) For every non-negative integer x, [rho]([2.sup.x]) = {[2.sup.x+1] - 1, [2.sup.x+1], ..., [2.sup.x+1] + x} and [absolute value of [rho]([2.sup.x])] = x + 2.

Proof: Let N = [2.sup.x], for some positive integer x and n = [2.sup.x+1] - 1. It is easy to see that n is the smallest positive integer such that the number of true leaves in V LR(n) is N. Also the tree V LR(n + 1 = [2.sup.x+1]) has N number of true leaves. The depth of the tree V LR([2.sup.x+1]) is x + 2. Let t = [2.sup.x+1] + (x + 1). By the property of the V LR tree, it is easy to see that t is the smallest integer such that V LR(t) contains N + 1 number of true leaves. So, t - 1 is the largest integer j such that the tree V LR(j) contains N number of true leaves. Hence, [rho]([2.sup.x]) = {[2.sup.x+1] - 1, [2.sup.x+1] ..., [2.sup.x+1] + x} and [absolute value [rho]([2.sup.x])] = x + 2.

A formula for [absolute value of [rho](N)] for the remaining values of N is given by the following theorem which follows immediately from Observation 5.

Theorem 2.6 Let N be a positive integer and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that p [greater than or equal to] 2 and 0 [less than or equal to] [k.sub.1] < [k.sub.2] < ... < [k.sub.p]. Then, [absolute value of [rho](N)] = [k.sub.1] + 1.

The following proposition present in [18] is an immediate consequence of Theorem 2.6

Proposition 2.7 ([18]) Let [alpha] be any even integer, 2 [less than or equal to] [alpha] [less than or equal to] [2.sup.x] - 2, where x [greater than or equal to] 2. Then [absolute value of [rho]([2.sup.x] + [alpha])] = [absolute value of P([2.sup.x-1] + [alpha]/2)] + 1.

Proof: Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. By Theorem 2.6, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. By Theorem 2.6, [absolute value of [rho]([2.sup.x-1] + [alpha]/2)] = [k.sub.1]. Hence, [absolute value of [rho]([2.sup.x] + [alpha])] = [absolute value of [rho] ([2.sup.x-1] + [alpha]/2)] + 1.

In fact we can easily generalize Proposition 2.7 as following in view of Theorem 2.6.

Theorem 2.8 Let [N.sub.1] and [N.sub.2] be two positive integers such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then, [absolute value of [rho]([N.sub.1])] = [absolute value of [rho]([N.sub.2])] if and only if [[alpha].sub.1] = [[beta].sub.1].

Proof: Suppose [absolute value of [rho]([N.sub.1])] = [absolute value of [rho]([N.sub.2])]. By Theorem 2.6, [absolute value of [rho]([N.sub.1])] = [[alpha].sub.1] + 1 and [absolute value of [rho]([N.sub.2])] = [beta]1 + 1. That is, [[alpha].sub.1] = [[beta].sub.1].

Next suppose [[alpha].sub.1] = [[beta].sub.1] = k. By Theorem 2.6, [absolute value of [rho]([N.sub.1])] = [[alpha].sub.1] + 1 = k + 1 and [absolute value of [rho]([N.sub.2])] = [[beta].sub.1] + 1 = k + 1. That is, [absolute value of [rho]([N.sub.1])] = [absolute value of [rho]([N.sub.2])]. Hence the theorem.

Proposition 2.9 ([18]) Let N be a positive integer and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that p [greater than or equal to] 2 and 0 [less than or equal to] [[alpha].sub.1] < [[alpha].sub.2] < ... < [[alpha].sub.p]. The greatest element in [rho](N) is given by 2N + [[alpha].sub.p] - p +1.

Proof: Let t be the smallest integer such that V LR(t) contains N number of true leaves. Let P = [v.sub.1], [v.sub.2], ..., [v.sub.m], ..., [v.sub.q] be the primary path of V LR(t). Since t is smallest, [v.sub.q] is a true leaf. Let [v.sub.m] be the tip of P. Let P' = [v.sub.1], [v.sub.2], ..., [v.sub.m] and S = {[v.sub.1], [v.sub.m]} [union] {[v.sub.i] [member of] V(P') - {[v.sub.1], [v.sub.m]}|[v.sub.i] is not an active vertex of P'}. By Observation 4, t is the number of vertices in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. By Observation 5, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. It is easy to see that dep([v.sub.1]) = [[alpha].sub.p] + 2 and dep([v.sub.m]) = [[alpha].sub.1] + 2. So, [absolute value of V(P')] = [[alpha].sub.p] - [[alpha].sub.1] + 1. Hence t = 2N + [[alpha].sub.p] - p - [[alpha].sub.1] + 1. By Theorem 2.6, t + [[alpha].sub.1] is the largest integer such that V LR(t + [[alpha].sub.1]) contains N number of leaves. Hence the greatest element in [rho](N) is t + [[alpha].sub.1] = 2N + [[alpha].sub.p] - p + 1.

Proposition 2.10 ([18]) Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. If p = 1, then T(n) = n for all [[alpha].sub.1] + 2 consecutive integers [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. If p [greater than or equal to] 2 then T(n) = N for all ([[alpha].sub.1] + 1) consecutive integers from n = 2N + ([[alpha].sub.p] - [[alpha].sub.1]) - p + 1 to n = 2N + [[alpha].sub.p] - p + 1.

Proof: Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. If p = 1, then the result follows from Proposition 2.5. If p [greater than or equal to] 2, then the result follows from Theorem 2.6 and Proposition 2.9.

Proposition 2.11 ([18]) 1/2 - (1/n) log(n+1/2) [less than or equal to] T(n)/n [less than or equal to] 1/2 + 1/2n, and T(n)/n [right arrow] 1/2 as n [right arrow] [infinity].

By Remark 1, we have 1 [less than or equal to] [b.sub.c](i) [less than or equal to] [log n]. This immediately allows us to derive a statement which is slightly better than Proposition 2.11.

Proposition 2.12 1/2 - [log n] - 2/2 [less than or equal to] T(n)n/n [less than or equal to] 1/2 + 1/2n.

Proof: From Theorem 1.2, we have T(n) = n+2/2 - [b.sub.c](n)/2. By Remark 1, 1 [less than or equal to] [b.sub.c](n) [less than or equal to] [log n]. So, T(n)/n [less than or equal to] 1/2 + 1/2n and T(n)/n [greater than or equal to] 1/2 - [log n]/2-2.

3 New results about T(n)

We know from Theorem 1.2 that T(i) [less than or equal to] i+1/2 and in fact for any i, i+1/2 - T(i) = j/2, for some j, 0 [less than or equal to] j [less than or equal to] [log i] - 1. Keeping this in mind, we ask the following related question: Given a j, 0 [less than or equal to] j [less than or equal to] d-1, can we characterize the set {i : i+2/2 - T(i) = j/2}. In view of Theorem 1.2, this is exactly the set {i : [b.sub.c](i) = j + 1}.

From Theorem 1.2, we have

T(i) = i+1/2 - [b.sub.c](i) - 1/2 (1)

Recall from Remark 1 that [b.sub.c](i) takes the values between 1 and [log i]. Since the depth of V LR(i) is d, where [2.sup.i-1] [less than or equal to] d [less than or equal to] [2.sup.d] - 1, [log i] = d and thus 1 [less than or equal to] [b.sub.c](i) [less than or equal to] d. So, 0 [less than or equal to] [b.sub.c](i) - 1 [less than or equal to] d - 1. From Equation 1 we have,

i + 1/2 - T(i) = j/2 (2)

where 0 [less than or equal to] j = [b.sub.c](i) - 1 [less than or equal to] d - 1. For a given value of j, 0 [less than or equal to] j [less than or equal to] d - 1, it is interesting to characterize the values of i for which i+1/2 - T(i) = j/2. The following theorem gives a characterization of the values of i such that i+1/2 - T(i) = j/2, for small values of j.

Theorem 3.1 (1) T(i) = i+1/2 if and only if i = [2.sup.d] - 1, for some d [greater than or equal to] 1.

(2) T(i) = i/2 if and only if i = [2.sup.d] - [2.sup.t], for some 1 [less than or equal to] t [less than or equal to] d - 1.

Proof: (1) From Equation 2 we have T(i) = i+1/2 if and only if j = 0. That is, [b.sub.c](i) = 1. But [b.sub.c](i) = 1 only when i = 2d - 1 , for some d [greater than or equal to] 1.

(2) From Equation 2 it is easy to see that T(i) = i/2 if and only if j = 1. That is, [b.sub.c](i) = 2. Note that the root of V LR(i) is always an active vertex and therefore one out going edge is always incident on the root. Let P be the primary path of V LR(i). If P consists of one vertex, i.e., the root of V LR(i) only then [b.sub.c](i) = 2. In this case i = [2.sup.d-1] - 1 + 1 = [2.sup.d-1]. Other than this case, [b.sub.c](i) = 2 when P contains exactly one more active vertex (except the root) and exactly one out going edge is incident on this active vertex. This means that the terminal vertex of P is a true leaf by Observation 3. So, P contains d vertices in this case. Let t' be the depth of the active vertex (other than the root of V LR(i)) of P. Clearly 2 [less than or equal to] t' [less than or equal to] d - 1. Now, it is easy to see that i = ([2.sup.d] - 1) - ([2.sup.t'-1]-1) = 2d - [2.sup.t'-1]. Putting t' - 1 = t, we have i = [2.sup.d] - [2.sup.t], 1 [less than or equal to] t [less than or equal to] d - 2. Now, combining both the cases, we have i = [2.sup.d] - [2.sup.t] for some t, 1 [less than or equal to] t [less than or equal to] d - 1. ?

For a given j let [S.sub.j] represent the i's such that i+1/2 - T(i) = j/2. That is, [S.sub.j] = {i : i+1/2 T(i) = j/2}. The above result can be generalized as follows:

Lemma 3.2 Let [S.sub.j] = {i : - i+1/2 - T(i) = j/2}. For a given j, i [member of] [S.sub.j] if and only if there exist integers d, [t.sub.1], [t.sub.2], ..., [t.sub.j] such that d - 2 [greater than or equal to] [t.sub.1] > [t.sub.2] > ... > [t.sub.j-1] > [t.sub.j] [greater than or equal to] 1 and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Moreover, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: From Equation 2 it is easy to see that T(i) = i+1-j/2 if and only if [b.sub.c](i) = j + 1. Let P be the primary path of V LR(i). We consider the following case:

The terminal vertex of P is a true leaf. In this case P contains d vertices and has exactly j active vertices other than the root. Clearly these j active vertices can be any of the vertices of P other than the root of V LR(i) and the terminal vertex of P. So there are [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where d = [log i], different ways to choose these j active vertices on the primary path. Let [a.sub.1], [a.sub.2], ..., [a.sub.j] be these active vertices of P and [t'.sub.1], [t'.sub.2], ..., [t'.sub.j] be their depths, respectively. Clearly d - 1 [greater than or equal to] [t'.sub.1] > [t'.sub.2] > ... > [t'.sub.j-1] > [t'.sub.j] [greater than or equal to] 2. Now, it is easy to see that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Taking [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The terminal vertex of P is not a true leaf. By Observation 3, the terminal vertex of P is an active vertex and two outgoing edges of V LR(i) are incident on it. Since the root of V LR(i) is always an active vertex, P will contain exactly j - 2 active vertices other than the root and the terminal vertex. Since the terminal vertex of P is not a true leaf, except the root and the terminal vertex, P can contain at most d - 3 vertices. These j - 2 active vertices can be chosen in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] many different ways provided t is the length P. Now, noting that t can vary from j to d - 3, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] many distinct i's such that V LR(i) has j + 1 out going edges and the primary path of V LR(i) is not a true leaf. Let [a.sub.1], [a.sub.2], ..., [a.sub.j-2] be these active vertices of P and [t'.sub.1], [t'.sub.2], ..., [t'.sub.j-2] be their depths, respectively. Clearly d - 1 [greater than or equal to] [t'.sub.1] > [t'.sub.2] > ... > [t'.sub.j-2] [greater than or equal to] 3. Let [t'.sub.j-1] be the depth of the terminal vertex of P. Note that [t'.sub.j-1] [greater than or equal to] 2. Now, it is easy to see that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Combining both the above cases, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where d - 2 [greater than or equal to] [t.sub.1] > [t.sub.2] > ... > [t.sub.j-1] [greater than or equal to] [t.sub.j] [greater than or equal to] 1.

From the above discussion, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Claim 1. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

See [19] (Chapter 5) for proof of Claim 1.

Now, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Hence the theorem.

Though [S.sub.j] is an infinite set, the distribution of the elements of [S.sub.j] over the integers is nice. As shown in Lemma 3.2, The following theorem allows us to get the number of integers i [member of] [S.sub.j] that are strictly below 2d.

Theorem 3.3 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: It is easy to see that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. By

Claim 1 of Lemma 3.2, we have, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Hence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Given two integers i and k it is interesting to know whether T(i) = k or not. In [18], Tanny has already given a nice solution to this question (see Proposition 2.6 in [18]). In the following theorem we give a different way of looking at it. The answer to the question whether T(i) = k is encoded in the bit pattern of the binary representation of [2.sup.[log i]] - 2k.

In the following theorem we characterize such numbers.

Theorem 3.4 Let x = [2.sup.d] - 2k where d = [log i] and let t be the number of 1's in the bit representation of x. Let t' be the greatest integer such that [2.sup.t'] divides x. Then, T (i) = k if and only if t' [greater than or equal to] i + 1 - 2k - t.

Proof:

Suppose

T(i) = k (3)

= i + 1/2 - i + 1 -2k/2 (4)

= i + 1/2 - j/2 (5)

In equation 5, j = i + 1 - 2k. From Lemma 3.2, we know that for a given j, i [member of] [S.sub.j] if and only if there exists integers d, [t.sub.1], [t.sub.2], ..., [t.sub.j] such that d - 2 [greater than or equal to] [t.sub.1] > [t.sub.2] > ... > [t.sub.j_1] [greater than or equal to] [t.sub.j] [greater than or equal to] 1 and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

= [2.sup.d] - i + (i + 1 - 2k - 1) (7)

= [2.sup.d] - 2k (8)

Let x = 2d - 2k, where d = [log i]. Suppose [(x).sub.2] be the binary representation of x and t be the number of 1's present in [(x).sub.2]. Now, we have the following three cases:

Case 1. t > j.

Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where d - 2 [greater than or equal to] [t.sub.1] > [t.sub.2] > ... > [t.sub.j-1] [greater than or equal to] [t.sub.j] [greater than or equal to] 1, it is easy to see that the number of 1's in [(x).sub.2] can be at most j. That is, t [less than or equal to] j. So, in this case T(i) cannot be equal to k.

Case 2. t = j.

If t = j, then it is easy to see that T(i) = k.

Case 3. t < j.

In this case T(i) may or may not be equal to k. Let t' be the smallest positive integer such that [2.sup.t'] divides x. Note that t' [greater than or equal to] 1 (since x(= [2.sup.d] - 2k) is even). That is, there is a 1 in t'th position of [(x).sub.2]. Since t' is largest such number, all the bits after t' in [(x).sub.2] are 0. So, if after t'th position in [(x).sub.2] there are enough bits, namely j - t bits, then the rest (j - t) number of 1's can be accommodated in [(x).sub.2] after the t'th bit. That is, we can find [t.sub.1] > [t.sub.2] > ... > [t.sub.j-1] > [t.sub.j], which are nothing but the integers corresponding to the position of the j 1's in [(x).sub.2] such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. So, T(i) = k if and only if t' [greater than or equal to] j - t. But j = i + 1 - 2k. So, T(i) = k if and only if t' [greater than or equal to] i + 1 - 2k - t.

4 Conclusion

In [12], Isgur et. al. have given a combinatorial interpretation in terms of infinite binary trees to certain meta-Fibonacci sequences which can be seen as a generalization of Tanny sequence. As of now we do not know to which other meta-Fibonacci sequences our iso-perimetric analogue can be applied. It would be interesting to explore whether those meta-Fibonacci sequences also can be related to discrete iso-perimetric inequalities.

References

[1] N. Alon and V. D. Millman, A1, isoperimetric inequalities for graphs and super concentrators, Journal ofCombinatorial Theory, Series. B, 38 (1985), pp. 73-88.

[2] B. V. S. Bharadwaj, L. Sunil Chandran, Anita Das, Isoperimetric Problem and Meta-Fibonacci Sequences, In the Proceeding of 14th Annual International Computing and Combinatorics Conference 2008, Dalian, China. LNCS 5092, pp. 22-30.

[3] L. S. Chandran and C. R. Subramanian, Girth and treewidth, Journal of combinatorial theory, Series B, 93 (2005), pp. 23-32.

[4] F. R. K. Chung and P. Tetali, Isoperimetric inequalities for cartesian product of graphs, Combinatorics, Probability and Computing, 7 (1998), pp. 141-148.

[5] R. Diestel, Graph Theory, vol. 173, Springer Verlag, New York, 2 ed., 2000.

[6] R. K. Guy, Some suspiciously simple sequences, Amer. Math. Monthly, 93 (1986), pp. 186-190.

[7] L. Harper, Optimal assignments of numbers to vertices, Jour. Soc. Indust. Appl. Math., 12 (1964), pp. 131-135.

[8] --, Optimal numberings and isoperimetric problems on graphs, Journal of Combinatorial Theory, 1 (1966), pp. 385-393.

[9] --, On an isoperimetric problem for hamming graphs, Discrete Applied Mathematics, 95 (1999), pp. 285-309.

[10] L. H. Harper, Global Methods for Combinatorial Isoperimetric Problems, Cambridge University Press, 2004.

[11] D. Hofstadter, Godel, Escher, Bach. An eternal golden braid, (Basic Books, New Work, 1979).

[12] A. Isgur, D. Reiss, S. Tanny, Trees nad Meta-Fibonacci sequences, The Electron. J. Combin. 16 (2009), Research Paper 129, 40 pp.

[13] B. Jackson, F. Ruskey, Meta-Fibonacci sequences, binary trees and extremal compact codes, Electron. J. Combin. 13 (2006), no. 1, Research Paper 26, 13 pp.

[14] G. O. H. Katona, The hamming-sphere has minimum boundary, Studia Sci. Math. Hungar., 10 (1975), pp. 131-140.

[15] I. Leader, Discrete isoperimetric inequalities, Proc. Symp. Appl. Math., 44 (1991), pp. 57-80.

[16] G. A. Margulis, Explicit construction of expander, Problemy Peredachi Informatsii, 9 (1973), pp. 71-80.

[17] D. W. Matula and F. Shahrokhi, Sparset cuts and bottlenecks in graphs, Discrete Applied Mathematics, 27 (1998), pp. 113-123.

[18] S. M. Tanny, A well-behaved cousin of the Hofstadter sequence, Discrete Mathematics, 105 (1992), pp. 227-239.

[19] A. Tucker, Applied Combinatorics, 5th edition, John Wiley and Sons, 2007.

Anita Das ([dagger])

Department of Computer Science and Automation, Indian Institute of Science Bangalore, India.

received 29th May 2009, revised 15th April 2011, accepted 7th June 2011.

([dagger]) Email: anita@csa.iisc.ernet.in
COPYRIGHT 2011 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2011 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Das, Anita
Publication:Discrete Mathematics and Theoretical Computer Science
Article Type:Report
Geographic Code:9INDI
Date:Jun 1, 2011
Words:6558
Previous Article:Sturmian sequences and invertible substitutions.
Next Article:Generation of cubic graphs.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters