# Is there a name for the infinite sequence of k-multisets with one element, two elements, etc.?

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?

## 1 Answer

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$