# [seqfan] Re: what are "sorted tuples" called?

W. Edwin Clark wclark at mail.usf.edu
Wed May 6 18:02:22 CEST 2020

```It seems nobody has mentioned that these are multisets (
https://en.wikipedia.org/wiki/Multiset) on the underlying set
[4]={1,2,3,4} of cardinality 3.

On Tue, May 5, 2020 at 1:04 PM Wouter Meeussen <wouter.meeussen at telenet.be>
wrote:

> 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.
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>
```