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 x

- Numbering sequences in the set S
- Numbering sequences in the set T1
- Numbering sequences in the set T2

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 |

I = s

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 n

Now let any two sequences {s

I

It turns out that for the above equation to hold, every term must evaluate to zero. Consider the worst case scenario where the term (s

Only the values in brackets can evaluate to zero. Consequently the only way for the equation to hold is that: s

s

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

Consider true that I = s

This represents computing the index I from the sequence s.

Now let y such that (substituting for s

y = ([ I / n

Simplifying the expression,

=> y = [ I / n

After massive cancellation, only the first and last terms remain,

=> y = [ I / n

But I < n

=> y = I - 0

=> y = I

Since y=I, it follows that s

S | x=0 d=1 | x=1 d=1 | x=0 d=2 | |
---|---|---|---|---|

0 - 0 0 0 | 0 - 0 0 0 | 0 - 0 0 0 | 0 - 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 0 | 1 - 1 1 0 | |||

5 - 2 1 0 | ||||

6 - 0 2 0 | 2 - 0 2 0 | |||

7 - 1 2 0 | ||||

8 - 2 2 0 | 2 - 2 2 0 | |||

9 - 0 0 1 | 3 - 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 1 | 4 - 1 1 1 | 4 - 1 1 1 | 4 - 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 1 | 5 - 2 2 1 | |||

18- 0 0 2 | 6 - 0 0 2 | |||

19- 1 0 2 | ||||

20- 2 0 2 | 6 - 2 0 2 | |||

21- 0 1 2 | ||||

22- 1 1 2 | 7 - 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 2 | 8 - 2 2 2 | 8 - 2 2 2 | 8 - 2 2 2 |

A sequence in T1 can be numbered (or indexed) by an integer I, where 0 <= I <= n

Given:

- n >= 1

- m >= 2

- x where 0 <= x <= m-2

- d = any (equation does not depend on d)

- s = {s

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

S | x=0 d=1 | x=1 d=1 | x=0 d=2 |
---|---|---|---|

0 - 0 0 0 | |||

1 - 1 0 0 | 0 - 1 0 0 | 0 - 1 0 0 | |

2 - 2 0 0 | 1 - 2 0 0 | 1 - 2 0 0 | |

3 - 0 1 0 | 2 - 0 1 0 | 0 - 0 1 0 | |

4 - 1 1 0 | 1 - 1 1 0 | 2 - 1 1 0 | |

5 - 2 1 0 | 3 - 2 1 0 | 2 - 2 1 0 | 3 - 2 1 0 |

6 - 0 2 0 | 4 - 0 2 0 | 3 - 0 2 0 | |

7 - 1 2 0 | 5 - 1 2 0 | 4 - 1 2 0 | 4 - 1 2 0 |

8 - 2 2 0 | 5 - 2 2 0 | 5 - 2 2 0 | |

9 - 0 0 1 | 6 - 0 0 1 | 6 - 0 0 1 | |

10- 1 0 1 | 6 - 1 0 1 | 7 - 1 0 1 | |

11- 2 0 1 | 7 - 2 0 1 | 8 - 2 0 1 | 7 - 2 0 1 |

12- 0 1 1 | 8 - 0 1 1 | 8 - 0 1 1 | |

13- 1 1 1 | |||

14- 2 1 1 | 9 - 2 1 1 | 9 - 2 1 1 | |

15- 0 2 1 | 10- 0 2 1 | 9 - 0 2 1 | 10- 0 2 1 |

16- 1 2 1 | 11- 1 2 1 | 10- 1 2 1 | |

17- 2 2 1 | 11- 2 2 1 | 11- 2 2 1 | |

18- 0 0 2 | 12- 0 0 2 | 12- 0 0 2 | |

19- 1 0 2 | 12- 1 0 2 | 13- 1 0 2 | 13- 1 0 2 |

20- 2 0 2 | 13- 2 0 2 | 14- 2 0 2 | |

21- 0 1 2 | 14- 0 1 2 | 15- 0 1 2 | 14- 0 1 2 |

22- 1 1 2 | 16- 1 1 2 | 15- 1 1 2 | |

23- 2 1 2 | 15- 2 1 2 | 17- 2 1 2 | |

24- 0 2 2 | 16- 0 2 2 | 16- 0 2 2 | |

25- 1 2 2 | 17- 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

Given:

- n >= 1

- m >= 2

- x where 0 <= x <= m-2

- d where 1 <= d <= m-1-x

- s = {s

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