[seqfan] what are "sorted tuples" called?
Wouter Meeussen
wouter.meeussen at telenet.be
Tue May 5 19:04:21 CEST 2020
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.
More information about the SeqFan
mailing list