1
$\begingroup$

Say you write down all $k$-multisets with elements taken from {0}. (Obviously there's just one, which is $k$ repetitions of "0".) Then list all $k$-multisets taken from {0,1} that haven't been listed, in lexicographical order. Then list $k$-multisets taken from {0,1,2} not yet listed, {0,1,2,3}, and so on. In other words, all $k$-multisets are listed with new elements added "one at a time." Is there a name for this sequence? It seems like it would be useful, such as for finding sequences of $k$ natural numbers with some property, but I haven't found the sequence referred to explicitly.

Example with $k=3$: 000 001 011 111 002 012 112 022 122 222 003 013 113 023 123 223 033 133 233 333 ...

Alternately: in the previous list, if you replace each multiset with the list of permutations of that multiset in lexicographical order, is there a name for the resulting list of permutations?

$\endgroup$
1
$\begingroup$

I found a partial answer. In The Art of Computer Programming 7.2.1.3, Knuth calls this generating multicombinations. In fact, the $d_0d_1d_2$ column of Table 1 is exactly my example but with the strings reversed! Knuth's Algorithms L or T (T is a faster version of L) enumerates all combinations in lexicographical order (what my list is with the strings reversed). Actually, it generates all combinations of $n+k-1$ elements taken $k$ at a time without replacement, which is equivalent to my list of $k$-combinations of $n$ elements with replacement, and many other equivalent representations. It's not too hard to adapt Algorithm L or T to enumerate multicombinations.

That seems to settle combinations, but I haven't found a name for the sequence of permutations I mentioned, generated by:

  • for each $n$ = 0,1,2,...
    • for each multicombination $c$ of natural numbers up to $n$ taken $k$ at a time in lexicographical order:
      • for each permutation $p$ of $c$ in lexicographical order:
        • visit $p$
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.