Numbering sequences under xd restriction

Let S be the set of nm distinct sequences where every sequence represents a possible arrangement of n objects in m spaces. The n objects are labeled from 0 to n-1. For example let n=2 and m=3, then:

S = {
{ 0, 0, 0 },
{ 1, 0, 0 },
{ 0, 1, 0 },
{ 1, 1, 0 },
{ 0, 0, 1 },
{ 1, 0, 1 },
{ 0, 1, 1 },
{ 1, 1, 1 } }

This article presents the numbering of sequences in the set S and in two subsets of S: denoted T1 and T2. These subsets are obtained by restricting sequences in S based on two values x and d. Precisely, a sequence in S is also in T1 if and only if its xth and (x+d)th elements are equal, otherwise it is in T2. This has been described as the xd restriction.

Numbering sequences in the set S

The sequences in S can be numbered (or indexed) from 0 to nm-1. Let s be a particular sequence of the form {s0, s1, s2, ..., sm-2, sm-1}. slevel in this sequence is an integer between 0 and n-1 inclusive. It is found at a certain level (there are m levels from 0 to m-1). s is numbered (or indexed) by the indexing number I. So I ranges from 0 to nm-1.

Below is an example of numbered (or indexed) sequences in order, for the case of n=2 and m=3:
 index I sequence S 0 0 0 0 1 1 0 0 2 0 1 0 3 1 1 0 4 0 0 1 5 1 0 1 6 0 1 1 7 1 1 1
Essentially, this article deals with a new way of understanding the base-n numeral system. The sequence s is actually the equivalent of the indexing number I when this I is expressed in the base n. For example in base n=2, I=5 is represented as 101.

Given s and n, I is given by:
I = s0*n0 + s1*n1 + s2*n2 + ... + sm-2*nm-2 + sm-1*nm-1
Proof:
Prooving that the relationship between the set S, and the set of values of I under the equation above, is one-to-one.

First it should be noted that the largest computation of I with respect to the equation is for the sequence {n-1, n-1, n-1, ... m times}. In this case I evaluates to nm-1 (that is I = nm-1).

Now let any two sequences {sa,0 , sa,1 , sa,2 , ..., sa,m-2 , sa,m-1} and {sb,0 , sb,1 , sb,2 , ..., sb,m-2 , sb,m-1} be numbered Ia and Ib respectively, such that Ia=Ib. Then
Ia-Ib=0  =>  (sa,0 - sb,0)*n0 + (sa,1 - sb,1)*n1 + (sa,2 - sb,2)*n2 + ... + (sa,m-2 - sb,m-2)*nm-2 + (sa,m-1 - sb,m-1)*nm-1 = 0 .

It turns out that for the above equation to hold, every term must evaluate to zero. Consider the worst case scenario where the term (sa,m-1 - sb,m-1)*nm-1 becomes equal to (1)*nm-1, meanwhile the terms (sa,0 - sb,0)*n0, (sa,1 - sb,1)*n1, (sa,2 - sb,2)*n2 , ... and (sa,m-2 - sb,m-2)*nm-2 are all negative. The later all add up to form the most negative possible value of -(nm-1-1). In this worst case the value of I is equal to ( nm-1 - (nm-1-1) ) = 1 , which is different from 0.

Only the values in brackets can evaluate to zero. Consequently the only way for the equation to hold is that: sa,0=sb,0 , sa,1=sb,1 , sa,2=sb,2 , ... , sa,m-2=sb,m-2 and sa,m-1=sb,m-1. So the two sequences must be the same. It follows that the relationship is indeed one-to-one.

Given I and n, slevel in s is given by:

slevel   =   [ I / nlevel ] - [ I / nlevel+1 ]*n   =   [ (I mod nlevel+1) / nlevel ]

where [x] = floor(x) = largest integer smaller than or equal to x.

Proof:
Consider true that I = s0*n0 + s1*n1 + s2*n2 + ... + sm-2*nm-2 + sm-1*nm-1.
This represents computing the index I from the sequence s.

Now let y such that (substituting for slevel in the equation for I above):
y = ([ I / n0 ] - [ I / n1 ]*n)*n0 + ([ I / n1 ] - [ I / n2 ]*n)*n1 + ([ I / n2 ] - [ I / n3 ]*n)*n2 + ... + ([ I / nm-2 ] - [ I / nm-1 ]*n)*nm-2 + ([ I / nm-1 ] - [ I / nm ]*n)*nm-1

Simplifying the expression,
=> y = [ I / n0 ]*n0 - [ I / n1 ]*n1 + [ I / n1 ]*n1 - [ I / n2 ]*n2 + [ I / n2 ]*n2 - [ I / n3 ]*n3 + ... + [ I / nm-2 ]*nm-2 - [ I / nm-1 ]*nm-1 + [ I / nm-1 ]*nm-1 - [ I / nm ]*nm

After massive cancellation, only the first and last terms remain,
=> y = [ I / n0 ]*n0 - [ I / nm ]*nm

But I < nm,
=> y = I - 0
=> y = I
Since y=I, it follows that slevel = [ I / nlevel ] - [ I / nlevel+1 ]*n.

Numbering sequences in the set T1

The set T1 is made up of all sequences s that satisfy the xd restriction. This restriction is that the xth and (x+d)th elements must be equal, where d>0. There are a total of n(m-1) such sequences in T1. For n=m=3 the numbered sequences {s0, s1, s2} are as shown in the table below:

S   x=0 d=1      x=1 d=1      x=0 d=2
0 - 0 0 00 - 0 0 00 - 0 0 00 - 0 0 0
1 - 1 0 0 1 - 1 0 0
2 - 2 0 0 2 - 2 0 0
3 - 0 1 0 1 - 0 1 0
4 - 1 1 01 - 1 1 0
5 - 2 1 0
6 - 0 2 0 2 - 0 2 0
7 - 1 2 0
8 - 2 2 02 - 2 2 0
9 - 0 0 13 - 0 0 1
10- 1 0 1 3 - 1 0 1
11- 2 0 1
12- 0 1 1 3 - 0 1 1
13- 1 1 14 - 1 1 14 - 1 1 14 - 1 1 1
14- 2 1 1 5 - 2 1 1
15- 0 2 1
16- 1 2 1 5 - 1 2 1
17- 2 2 15 - 2 2 1
18- 0 0 26 - 0 0 2
19- 1 0 2
20- 2 0 2 6 - 2 0 2
21- 0 1 2
22- 1 1 27 - 1 1 2
23- 2 1 2 7 - 2 1 2
24- 0 2 2 6 - 0 2 2
25- 1 2 2 7 - 1 2 2
26- 2 2 28 - 2 2 28 - 2 2 28 - 2 2 2

A sequence in T1 can be numbered (or indexed) by an integer I, where 0 <= I <= n(m-1)-1.
Given:
- n >= 1
- m >= 2
- x where 0 <= x <= m-2
- d = any (equation does not depend on d)
- s = {s0, s1, s2, ..., sm-2, sm-1} ,

the equation below finds the corresponding value of I for the given sequence in T1. That is for example:
- if s={1, 1, 0}, n=m=3, x=0 and d=any, then I=1
- if s={0, 1, 1}, n=m=3, x=1 and d=any, then I=3
- if s={2, 1, 2}, n=m=3, x=0 and d=any, then I=7 Numbering sequences in the set T2

The set T2 is made up of all sequences s that do not satisfy the xd restriction. This restriction is that the xth and (x+d)th elements must be equal, where d>0. There are a total of (n-1)n(m-1) such sequences in T2. For n=m=3 the numbered sequences {s0, s1, s2} are as shown in the table below:

S   x=0 d=1      x=1 d=1      x=0 d=2
0 - 0 0 0
1 - 1 0 00 - 1 0 0 0 - 1 0 0
2 - 2 0 01 - 2 0 0 1 - 2 0 0
3 - 0 1 02 - 0 1 00 - 0 1 0
4 - 1 1 0 1 - 1 1 02 - 1 1 0
5 - 2 1 03 - 2 1 02 - 2 1 03 - 2 1 0
6 - 0 2 04 - 0 2 03 - 0 2 0
7 - 1 2 05 - 1 2 04 - 1 2 04 - 1 2 0
8 - 2 2 0 5 - 2 2 05 - 2 2 0
9 - 0 0 1 6 - 0 0 16 - 0 0 1
10- 1 0 16 - 1 0 17 - 1 0 1
11- 2 0 17 - 2 0 18 - 2 0 17 - 2 0 1
12- 0 1 18 - 0 1 1 8 - 0 1 1
13- 1 1 1
14- 2 1 19 - 2 1 1 9 - 2 1 1
15- 0 2 110- 0 2 19 - 0 2 110- 0 2 1
16- 1 2 111- 1 2 110- 1 2 1
17- 2 2 1 11- 2 2 111- 2 2 1
18- 0 0 2 12- 0 0 212- 0 0 2
19- 1 0 212- 1 0 213- 1 0 213- 1 0 2
20- 2 0 213- 2 0 214- 2 0 2
21- 0 1 214- 0 1 215- 0 1 214- 0 1 2
22- 1 1 2 16- 1 1 215- 1 1 2
23- 2 1 215- 2 1 217- 2 1 2
24- 0 2 216- 0 2 2 16- 0 2 2
25- 1 2 217- 1 2 2 17- 1 2 2
26- 2 2 2

A sequence in T2 can be numbered (or indexed) by an integer I, where 0 <= I <= (n-1)n(m-1)-1.
Given:
- n >= 1
- m >= 2
- x where 0 <= x <= m-2
- d where 1 <= d <= m-1-x
- s = {s0, s1, s2, ..., sm-2, sm-1} ,

the equation below finds the corresponding value of I for the given sequence in T2. That is for example:
- if s={2, 0, 0}, n=m=3, x=0 and d=1, then I=1
- if s={1, 2, 0}, n=m=3, x=1 and d=1, then I=4
- if s={2, 1, 1}, n=m=3, x=0 and d=2, then I=9 