A229873 An enumeration of all k-tuples containing positive integers.

1, 2, 1, 1, 1, 2, 2, 1, 2, 2, 3, 1, 3, 2, 3, 3, 1, 3, 2, 3, 3, 1, 1, 1, 1, 1, 2, 1, 1, 3, 1, 2, 1, 1, 2, 2, 1, 2, 3, 2, 1, 1, 2, 1, 2, 2, 1, 3, 2, 2, 1, 2, 2, 2, 2, 2, 3, 3, 1, 1, 3, 1, 2, 3, 1, 3, 3, 2, 1, 3, 2, 2, 3, 2, 3, 3, 3, 1, 3, 3, 2, 3, 3, 3, 4

Offset

1,2

Comments

The sequence pattern is an integer, n, followed by all k-tuples containing n, then (k+1)-tuples, etc., up to the n-tuples that have not yet appeared in the sequence. Directly before the integer n+1, therefore, we find the first occurrence of n^n n-tuples which contain the n^n permutations of 1 to n in lexicographic order. The cases n = 1 and n = 2 are degenerate as no tuples precede them; 1 is followed not by a tuple, but by 2, and 2 is followed by the tuple (1, 1), rather than (1, n) as with all other integers.

k-tuple clusters later in the sequence (k<n, i.e., after the initial k^k) are in sizes n^k-(n-1)^k; for example, the 2-tuples, when they occur, always appear in odd number sized clusters (2n-1, excluding the first four), and excluding the first 3^3, 3-tuples occur in clusters of 3n^2-3n+1.

Essentially, at each stage an n-hypercube of elements of size n is completed for each dimension up to the (n-1)-th, building on previous occurrences of the dimension, and then a hypercube for dimension n is begun to be built upon later.

Tuple sizes are in A229895.

Links

Carl R. White, Table of n, a(n) for n = 1..1235

Carl R. White, Tabular layout of the sequence showing the k-tuples as they occur

Example

Sequence starts (1), (2), (1,1), (1,2), (2,1), (2,2), (3), (1,3), (2,3), (3,1), (3,2), (3,3), (1,1,1), ..., (3,3,3), (4), (1,4), etc.

Crossrefs

Cf. A001057. Sorted tuples only: A229874. Tuple sizes: A229895.

Sequence in context: A089641 A086995 A220492 * A135230 A117957 A145702

Adjacent sequences: A229870 A229871 A229872 * A229874 A229875 A229876

Keyword

nonn,tabf

Author

Carl R. White, Oct 01 2013

Status

approved