[seqfan] what are "sorted tuples" called?

[Wouter Meeussen]

hi Seqfanners,

I had a lot of fun trying to count the “sorted tuples” of length n from an alphabet of k letters (1<=k<=n) that are neighbour-free.

Example of “sorted tuples” of length n=3 chosen from a k=4 letter alphabet :

{1, 1, 1}, {1, 1, 2}, {1, 1, 3}, {1, 1, 4}, {1, 2, 2}, 
{1, 2, 3}, {1, 2, 4}, {1, 3, 3}, {1, 3, 4}, {1, 4, 4}, 
{2, 2, 2}, {2, 2, 3}, {2, 2, 4}, {2, 3, 3}, {2, 3, 4}, 
{2, 4, 4}, {3, 3, 3}, {3, 3, 4}, {3, 4, 4}, {4, 4, 4}

I’m sure these constructs have a proper name. Any hints?

As for counting the neighbour-free cases, it holds some surprises : links to Motzkin-numbers (A001006) and to fearsome ‘directed Animals’ (A005773), and also   A000124, A177787, A002417 pop up.

I counted up to n >= k = 14 and extended the table by trickery (generatingfunctionology) up to size 20.
I’ll wait with entering them in OEIS  until I understand more of the underlying combinatorics and know what to call them.

Wouter.