[seqfan] Fun with subsequences

[Charles Greathouse]

Just like set inclusion partially orders the space of sets, the
subsequence relation preorders the space of sequences*.  I noticed
that this relation has a(n equivalence class of) top element(s):
sequences which contain each integer infinitely many times.  For
nonnegative integers the canonical choice is clearly A002262.  I
wonder if there is a similar natural representative for all integer
sequences?

Can anyone find a reasonable list of these sequences?  I imagine there
are many sequences which are top elements in this sense but for which
the proof is hard.  For an example, an old favorite of mine, A000319,
is probably a member but the proof seems hopeless.

Amusingly, the keyword "nonn" can be interpreted in light of the above
as marking precisely those which are subsequences of A002262.  I
wonder which other keywords or properties can similarly be interpreted
in unusual ways?

Finally, I've pondered ways to efficiently find subsequences (say, in
the OEIS).  Of course even without preprocessing this can be done in
linear time in the length of the sequence data, but could that be
improved?  Say, a data structure generated off-line that partitions
the sequences such that only a small part need be searched directly?
Also some sequence properties (e.g., being monotonic) could be used if
known to the algorithm, but I don't suspect these are common enough to
help much.

* Integer sequences and subsets of Z, of course, for the pedants.

Charles Greathouse
Analyst/Programmer
Case Western Reserve University