login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A229873
An enumeration of all k-tuples containing positive integers.
5
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.
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
KEYWORD
nonn,tabf
AUTHOR
Carl R. White, Oct 01 2013
STATUS
approved