Counts Of Orderings Containing At Most K Of The Kth Class

Question

This challenge is about the number of orderings which contain at most \$n\$ classes and at most \$k\$ of the \$k^{\text{th}}\$ class.

One way to represent such an ordering is as a sequence of positive integers with these three restrictions:

1. A number may only appear after all lower numbers have appeared
2. All numbers which appear must be less than or equal to \$n\$
3. Any number may only appear up to as many times as its own value

As such the number of such sequences is itself a sequence, \$a(n)\$ where:

\$a(0) = 1\$, since only the empty sequence, [], works;

\$a(1) = 2\$, since [1] now also works;

\$a(2) = 4\$, since both [1, 2] and [1, 2, 2] also work*;

\$a(3) = 16\$:

[], [1], [1, 2], [1, 2, 2], [1, 2, 3], [1, 2, 2, 3], [1, 2, 3, 2], [1, 2, 3, 3], [1, 2, 2, 3, 3], [1, 2, 3, 2, 3], [1, 2, 3, 3, 2], [1, 2, 3, 3, 3], [1, 2, 2, 3, 3, 3], [1, 2, 3, 2, 3, 3], [1, 2, 3, 3, 2, 3], [1, 2, 3, 3, 3, 2]

\$a(4) = 409\$:

[], [1], [1, 2], [1, 2, 2], [1, 2, 3], [1, 2, 2, 3], [1, 2, 3, 2], [1, 2, 3, 3], [1, 2, 3, 4], [1, 2, 2, 3, 3], [1, 2, 2, 3, 4], [1, 2, 3, 2, 3], [1, 2, 3, 2, 4], [1, 2, 3, 3, 2], [1, 2, 3, 3, 3], [1, 2, 3, 3, 4], [1, 2, 3, 4, 2], [1, 2, 3, 4, 3], [1, 2, 3, 4, 4], [1, 2, 2, 3, 3, 3], [1, 2, 2, 3, 3, 4], [1, 2, 2, 3, 4, 3], [1, 2, 2, 3, 4, 4], [1, 2, 3, 2, 3, 3], [1, 2, 3, 2, 3, 4], [1, 2, 3, 2, 4, 3], [1, 2, 3, 2, 4, 4], [1, 2, 3, 3, 2, 3], [1, 2, 3, 3, 2, 4], [1, 2, 3, 3, 3, 2], [1, 2, 3, 3, 3, 4], [1, 2, 3, 3, 4, 2], [1, 2, 3, 3, 4, 3], [1, 2, 3, 3, 4, 4], [1, 2, 3, 4, 2, 3], [1, 2, 3, 4, 2, 4], [1, 2, 3, 4, 3, 2], [1, 2, 3, 4, 3, 3], [1, 2, 3, 4, 3, 4], [1, 2, 3, 4, 4, 2], [1, 2, 3, 4, 4, 3], [1, 2, 3, 4, 4, 4], [1, 2, 2, 3, 3, 3, 4], [1, 2, 2, 3, 3, 4, 3], [1, 2, 2, 3, 3, 4, 4], [1, 2, 2, 3, 4, 3, 3], [1, 2, 2, 3, 4, 3, 4], [1, 2, 2, 3, 4, 4, 3], [1, 2, 2, 3, 4, 4, 4], [1, 2, 3, 2, 3, 3, 4], [1, 2, 3, 2, 3, 4, 3], [1, 2, 3, 2, 3, 4, 4], [1, 2, 3, 2, 4, 3, 3], [1, 2, 3, 2, 4, 3, 4], [1, 2, 3, 2, 4, 4, 3], [1, 2, 3, 2, 4, 4, 4], [1, 2, 3, 3, 2, 3, 4], [1, 2, 3, 3, 2, 4, 3], [1, 2, 3, 3, 2, 4, 4], [1, 2, 3, 3, 3, 2, 4], [1, 2, 3, 3, 3, 4, 2], [1, 2, 3, 3, 3, 4, 4], [1, 2, 3, 3, 4, 2, 3], [1, 2, 3, 3, 4, 2, 4], [1, 2, 3, 3, 4, 3, 2], [1, 2, 3, 3, 4, 3, 4], [1, 2, 3, 3, 4, 4, 2], [1, 2, 3, 3, 4, 4, 3], [1, 2, 3, 3, 4, 4, 4], [1, 2, 3, 4, 2, 3, 3], [1, 2, 3, 4, 2, 3, 4], [1, 2, 3, 4, 2, 4, 3], [1, 2, 3, 4, 2, 4, 4], [1, 2, 3, 4, 3, 2, 3], [1, 2, 3, 4, 3, 2, 4], [1, 2, 3, 4, 3, 3, 2], [1, 2, 3, 4, 3, 3, 4], [1, 2, 3, 4, 3, 4, 2], [1, 2, 3, 4, 3, 4, 3], [1, 2, 3, 4, 3, 4, 4], [1, 2, 3, 4, 4, 2, 3], [1, 2, 3, 4, 4, 2, 4], [1, 2, 3, 4, 4, 3, 2], [1, 2, 3, 4, 4, 3, 3], [1, 2, 3, 4, 4, 3, 4], [1, 2, 3, 4, 4, 4, 2], [1, 2, 3, 4, 4, 4, 3], [1, 2, 3, 4, 4, 4, 4], [1, 2, 2, 3, 3, 3, 4, 4], [1, 2, 2, 3, 3, 4, 3, 4], [1, 2, 2, 3, 3, 4, 4, 3], [1, 2, 2, 3, 3, 4, 4, 4], [1, 2, 2, 3, 4, 3, 3, 4], [1, 2, 2, 3, 4, 3, 4, 3], [1, 2, 2, 3, 4, 3, 4, 4], [1, 2, 2, 3, 4, 4, 3, 3], [1, 2, 2, 3, 4, 4, 3, 4], [1, 2, 2, 3, 4, 4, 4, 3], [1, 2, 2, 3, 4, 4, 4, 4], [1, 2, 3, 2, 3, 3, 4, 4], [1, 2, 3, 2, 3, 4, 3, 4], [1, 2, 3, 2, 3, 4, 4, 3], [1, 2, 3, 2, 3, 4, 4, 4], [1, 2, 3, 2, 4, 3, 3, 4], [1, 2, 3, 2, 4, 3, 4, 3], [1, 2, 3, 2, 4, 3, 4, 4], [1, 2, 3, 2, 4, 4, 3, 3], [1, 2, 3, 2, 4, 4, 3, 4], [1, 2, 3, 2, 4, 4, 4, 3], [1, 2, 3, 2, 4, 4, 4, 4], [1, 2, 3, 3, 2, 3, 4, 4], [1, 2, 3, 3, 2, 4, 3, 4], [1, 2, 3, 3, 2, 4, 4, 3], [1, 2, 3, 3, 2, 4, 4, 4], [1, 2, 3, 3, 3, 2, 4, 4], [1, 2, 3, 3, 3, 4, 2, 4], [1, 2, 3, 3, 3, 4, 4, 2], [1, 2, 3, 3, 3, 4, 4, 4], [1, 2, 3, 3, 4, 2, 3, 4], [1, 2, 3, 3, 4, 2, 4, 3], [1, 2, 3, 3, 4, 2, 4, 4], [1, 2, 3, 3, 4, 3, 2, 4], [1, 2, 3, 3, 4, 3, 4, 2], [1, 2, 3, 3, 4, 3, 4, 4], [1, 2, 3, 3, 4, 4, 2, 3], [1, 2, 3, 3, 4, 4, 2, 4], [1, 2, 3, 3, 4, 4, 3, 2], [1, 2, 3, 3, 4, 4, 3, 4], [1, 2, 3, 3, 4, 4, 4, 2], [1, 2, 3, 3, 4, 4, 4, 3], [1, 2, 3, 3, 4, 4, 4, 4], [1, 2, 3, 4, 2, 3, 3, 4], [1, 2, 3, 4, 2, 3, 4, 3], [1, 2, 3, 4, 2, 3, 4, 4], [1, 2, 3, 4, 2, 4, 3, 3], [1, 2, 3, 4, 2, 4, 3, 4], [1, 2, 3, 4, 2, 4, 4, 3], [1, 2, 3, 4, 2, 4, 4, 4], [1, 2, 3, 4, 3, 2, 3, 4], [1, 2, 3, 4, 3, 2, 4, 3], [1, 2, 3, 4, 3, 2, 4, 4], [1, 2, 3, 4, 3, 3, 2, 4], [1, 2, 3, 4, 3, 3, 4, 2], [1, 2, 3, 4, 3, 3, 4, 4], [1, 2, 3, 4, 3, 4, 2, 3], [1, 2, 3, 4, 3, 4, 2, 4], [1, 2, 3, 4, 3, 4, 3, 2], [1, 2, 3, 4, 3, 4, 3, 4], [1, 2, 3, 4, 3, 4, 4, 2], [1, 2, 3, 4, 3, 4, 4, 3], [1, 2, 3, 4, 3, 4, 4, 4], [1, 2, 3, 4, 4, 2, 3, 3], [1, 2, 3, 4, 4, 2, 3, 4], [1, 2, 3, 4, 4, 2, 4, 3], [1, 2, 3, 4, 4, 2, 4, 4], [1, 2, 3, 4, 4, 3, 2, 3], [1, 2, 3, 4, 4, 3, 2, 4], [1, 2, 3, 4, 4, 3, 3, 2], [1, 2, 3, 4, 4, 3, 3, 4], [1, 2, 3, 4, 4, 3, 4, 2], [1, 2, 3, 4, 4, 3, 4, 3], [1, 2, 3, 4, 4, 3, 4, 4], [1, 2, 3, 4, 4, 4, 2, 3], [1, 2, 3, 4, 4, 4, 2, 4], [1, 2, 3, 4, 4, 4, 3, 2], [1, 2, 3, 4, 4, 4, 3, 3], [1, 2, 3, 4, 4, 4, 3, 4], [1, 2, 3, 4, 4, 4, 4, 2], [1, 2, 3, 4, 4, 4, 4, 3], [1, 2, 2, 3, 3, 3, 4, 4, 4], [1, 2, 2, 3, 3, 4, 3, 4, 4], [1, 2, 2, 3, 3, 4, 4, 3, 4], [1, 2, 2, 3, 3, 4, 4, 4, 3], [1, 2, 2, 3, 3, 4, 4, 4, 4], [1, 2, 2, 3, 4, 3, 3, 4, 4], [1, 2, 2, 3, 4, 3, 4, 3, 4], [1, 2, 2, 3, 4, 3, 4, 4, 3], [1, 2, 2, 3, 4, 3, 4, 4, 4], [1, 2, 2, 3, 4, 4, 3, 3, 4], [1, 2, 2, 3, 4, 4, 3, 4, 3], [1, 2, 2, 3, 4, 4, 3, 4, 4], [1, 2, 2, 3, 4, 4, 4, 3, 3], [1, 2, 2, 3, 4, 4, 4, 3, 4], [1, 2, 2, 3, 4, 4, 4, 4, 3], [1, 2, 3, 2, 3, 3, 4, 4, 4], [1, 2, 3, 2, 3, 4, 3, 4, 4], [1, 2, 3, 2, 3, 4, 4, 3, 4], [1, 2, 3, 2, 3, 4, 4, 4, 3], [1, 2, 3, 2, 3, 4, 4, 4, 4], [1, 2, 3, 2, 4, 3, 3, 4, 4], [1, 2, 3, 2, 4, 3, 4, 3, 4], [1, 2, 3, 2, 4, 3, 4, 4, 3], [1, 2, 3, 2, 4, 3, 4, 4, 4], [1, 2, 3, 2, 4, 4, 3, 3, 4], [1, 2, 3, 2, 4, 4, 3, 4, 3], [1, 2, 3, 2, 4, 4, 3, 4, 4], [1, 2, 3, 2, 4, 4, 4, 3, 3], [1, 2, 3, 2, 4, 4, 4, 3, 4], [1, 2, 3, 2, 4, 4, 4, 4, 3], [1, 2, 3, 3, 2, 3, 4, 4, 4], [1, 2, 3, 3, 2, 4, 3, 4, 4], [1, 2, 3, 3, 2, 4, 4, 3, 4], [1, 2, 3, 3, 2, 4, 4, 4, 3], [1, 2, 3, 3, 2, 4, 4, 4, 4], [1, 2, 3, 3, 3, 2, 4, 4, 4], [1, 2, 3, 3, 3, 4, 2, 4, 4], [1, 2, 3, 3, 3, 4, 4, 2, 4], [1, 2, 3, 3, 3, 4, 4, 4, 2], [1, 2, 3, 3, 3, 4, 4, 4, 4], [1, 2, 3, 3, 4, 2, 3, 4, 4], [1, 2, 3, 3, 4, 2, 4, 3, 4], [1, 2, 3, 3, 4, 2, 4, 4, 3], [1, 2, 3, 3, 4, 2, 4, 4, 4], [1, 2, 3, 3, 4, 3, 2, 4, 4], [1, 2, 3, 3, 4, 3, 4, 2, 4], [1, 2, 3, 3, 4, 3, 4, 4, 2], [1, 2, 3, 3, 4, 3, 4, 4, 4], [1, 2, 3, 3, 4, 4, 2, 3, 4], [1, 2, 3, 3, 4, 4, 2, 4, 3], [1, 2, 3, 3, 4, 4, 2, 4, 4], [1, 2, 3, 3, 4, 4, 3, 2, 4], [1, 2, 3, 3, 4, 4, 3, 4, 2], [1, 2, 3, 3, 4, 4, 3, 4, 4], [1, 2, 3, 3, 4, 4, 4, 2, 3], [1, 2, 3, 3, 4, 4, 4, 2, 4], [1, 2, 3, 3, 4, 4, 4, 3, 2], [1, 2, 3, 3, 4, 4, 4, 3, 4], [1, 2, 3, 3, 4, 4, 4, 4, 2], [1, 2, 3, 3, 4, 4, 4, 4, 3], [1, 2, 3, 4, 2, 3, 3, 4, 4], [1, 2, 3, 4, 2, 3, 4, 3, 4], [1, 2, 3, 4, 2, 3, 4, 4, 3], [1, 2, 3, 4, 2, 3, 4, 4, 4], [1, 2, 3, 4, 2, 4, 3, 3, 4], [1, 2, 3, 4, 2, 4, 3, 4, 3], [1, 2, 3, 4, 2, 4, 3, 4, 4], [1, 2, 3, 4, 2, 4, 4, 3, 3], [1, 2, 3, 4, 2, 4, 4, 3, 4], [1, 2, 3, 4, 2, 4, 4, 4, 3], [1, 2, 3, 4, 3, 2, 3, 4, 4], [1, 2, 3, 4, 3, 2, 4, 3, 4], [1, 2, 3, 4, 3, 2, 4, 4, 3], [1, 2, 3, 4, 3, 2, 4, 4, 4], [1, 2, 3, 4, 3, 3, 2, 4, 4], [1, 2, 3, 4, 3, 3, 4, 2, 4], [1, 2, 3, 4, 3, 3, 4, 4, 2], [1, 2, 3, 4, 3, 3, 4, 4, 4], [1, 2, 3, 4, 3, 4, 2, 3, 4], [1, 2, 3, 4, 3, 4, 2, 4, 3], [1, 2, 3, 4, 3, 4, 2, 4, 4], [1, 2, 3, 4, 3, 4, 3, 2, 4], [1, 2, 3, 4, 3, 4, 3, 4, 2], [1, 2, 3, 4, 3, 4, 3, 4, 4], [1, 2, 3, 4, 3, 4, 4, 2, 3], [1, 2, 3, 4, 3, 4, 4, 2, 4], [1, 2, 3, 4, 3, 4, 4, 3, 2], [1, 2, 3, 4, 3, 4, 4, 3, 4], [1, 2, 3, 4, 3, 4, 4, 4, 2], [1, 2, 3, 4, 3, 4, 4, 4, 3], [1, 2, 3, 4, 4, 2, 3, 3, 4], [1, 2, 3, 4, 4, 2, 3, 4, 3], [1, 2, 3, 4, 4, 2, 3, 4, 4], [1, 2, 3, 4, 4, 2, 4, 3, 3], [1, 2, 3, 4, 4, 2, 4, 3, 4], [1, 2, 3, 4, 4, 2, 4, 4, 3], [1, 2, 3, 4, 4, 3, 2, 3, 4], [1, 2, 3, 4, 4, 3, 2, 4, 3], [1, 2, 3, 4, 4, 3, 2, 4, 4], [1, 2, 3, 4, 4, 3, 3, 2, 4], [1, 2, 3, 4, 4, 3, 3, 4, 2], [1, 2, 3, 4, 4, 3, 3, 4, 4], [1, 2, 3, 4, 4, 3, 4, 2, 3], [1, 2, 3, 4, 4, 3, 4, 2, 4], [1, 2, 3, 4, 4, 3, 4, 3, 2], [1, 2, 3, 4, 4, 3, 4, 3, 4], [1, 2, 3, 4, 4, 3, 4, 4, 2], [1, 2, 3, 4, 4, 3, 4, 4, 3], [1, 2, 3, 4, 4, 4, 2, 3, 3], [1, 2, 3, 4, 4, 4, 2, 3, 4], [1, 2, 3, 4, 4, 4, 2, 4, 3], [1, 2, 3, 4, 4, 4, 3, 2, 3], [1, 2, 3, 4, 4, 4, 3, 2, 4], [1, 2, 3, 4, 4, 4, 3, 3, 2], [1, 2, 3, 4, 4, 4, 3, 3, 4], [1, 2, 3, 4, 4, 4, 3, 4, 2], [1, 2, 3, 4, 4, 4, 3, 4, 3], [1, 2, 3, 4, 4, 4, 4, 2, 3], [1, 2, 3, 4, 4, 4, 4, 3, 2], [1, 2, 3, 4, 4, 4, 4, 3, 3], [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], [1, 2, 2, 3, 3, 4, 3, 4, 4, 4], [1, 2, 2, 3, 3, 4, 4, 3, 4, 4], [1, 2, 2, 3, 3, 4, 4, 4, 3, 4], [1, 2, 2, 3, 3, 4, 4, 4, 4, 3], [1, 2, 2, 3, 4, 3, 3, 4, 4, 4], [1, 2, 2, 3, 4, 3, 4, 3, 4, 4], [1, 2, 2, 3, 4, 3, 4, 4, 3, 4], [1, 2, 2, 3, 4, 3, 4, 4, 4, 3], [1, 2, 2, 3, 4, 4, 3, 3, 4, 4], [1, 2, 2, 3, 4, 4, 3, 4, 3, 4], [1, 2, 2, 3, 4, 4, 3, 4, 4, 3], [1, 2, 2, 3, 4, 4, 4, 3, 3, 4], [1, 2, 2, 3, 4, 4, 4, 3, 4, 3], [1, 2, 2, 3, 4, 4, 4, 4, 3, 3], [1, 2, 3, 2, 3, 3, 4, 4, 4, 4], [1, 2, 3, 2, 3, 4, 3, 4, 4, 4], [1, 2, 3, 2, 3, 4, 4, 3, 4, 4], [1, 2, 3, 2, 3, 4, 4, 4, 3, 4], [1, 2, 3, 2, 3, 4, 4, 4, 4, 3], [1, 2, 3, 2, 4, 3, 3, 4, 4, 4], [1, 2, 3, 2, 4, 3, 4, 3, 4, 4], [1, 2, 3, 2, 4, 3, 4, 4, 3, 4], [1, 2, 3, 2, 4, 3, 4, 4, 4, 3], [1, 2, 3, 2, 4, 4, 3, 3, 4, 4], [1, 2, 3, 2, 4, 4, 3, 4, 3, 4], [1, 2, 3, 2, 4, 4, 3, 4, 4, 3], [1, 2, 3, 2, 4, 4, 4, 3, 3, 4], [1, 2, 3, 2, 4, 4, 4, 3, 4, 3], [1, 2, 3, 2, 4, 4, 4, 4, 3, 3], [1, 2, 3, 3, 2, 3, 4, 4, 4, 4], [1, 2, 3, 3, 2, 4, 3, 4, 4, 4], [1, 2, 3, 3, 2, 4, 4, 3, 4, 4], [1, 2, 3, 3, 2, 4, 4, 4, 3, 4], [1, 2, 3, 3, 2, 4, 4, 4, 4, 3], [1, 2, 3, 3, 3, 2, 4, 4, 4, 4], [1, 2, 3, 3, 3, 4, 2, 4, 4, 4], [1, 2, 3, 3, 3, 4, 4, 2, 4, 4], [1, 2, 3, 3, 3, 4, 4, 4, 2, 4], [1, 2, 3, 3, 3, 4, 4, 4, 4, 2], [1, 2, 3, 3, 4, 2, 3, 4, 4, 4], [1, 2, 3, 3, 4, 2, 4, 3, 4, 4], [1, 2, 3, 3, 4, 2, 4, 4, 3, 4], [1, 2, 3, 3, 4, 2, 4, 4, 4, 3], [1, 2, 3, 3, 4, 3, 2, 4, 4, 4], [1, 2, 3, 3, 4, 3, 4, 2, 4, 4], [1, 2, 3, 3, 4, 3, 4, 4, 2, 4], [1, 2, 3, 3, 4, 3, 4, 4, 4, 2], [1, 2, 3, 3, 4, 4, 2, 3, 4, 4], [1, 2, 3, 3, 4, 4, 2, 4, 3, 4], [1, 2, 3, 3, 4, 4, 2, 4, 4, 3], [1, 2, 3, 3, 4, 4, 3, 2, 4, 4], [1, 2, 3, 3, 4, 4, 3, 4, 2, 4], [1, 2, 3, 3, 4, 4, 3, 4, 4, 2], [1, 2, 3, 3, 4, 4, 4, 2, 3, 4], [1, 2, 3, 3, 4, 4, 4, 2, 4, 3], [1, 2, 3, 3, 4, 4, 4, 3, 2, 4], [1, 2, 3, 3, 4, 4, 4, 3, 4, 2], [1, 2, 3, 3, 4, 4, 4, 4, 2, 3], [1, 2, 3, 3, 4, 4, 4, 4, 3, 2], [1, 2, 3, 4, 2, 3, 3, 4, 4, 4], [1, 2, 3, 4, 2, 3, 4, 3, 4, 4], [1, 2, 3, 4, 2, 3, 4, 4, 3, 4], [1, 2, 3, 4, 2, 3, 4, 4, 4, 3], [1, 2, 3, 4, 2, 4, 3, 3, 4, 4], [1, 2, 3, 4, 2, 4, 3, 4, 3, 4], [1, 2, 3, 4, 2, 4, 3, 4, 4, 3], [1, 2, 3, 4, 2, 4, 4, 3, 3, 4], [1, 2, 3, 4, 2, 4, 4, 3, 4, 3], [1, 2, 3, 4, 2, 4, 4, 4, 3, 3], [1, 2, 3, 4, 3, 2, 3, 4, 4, 4], [1, 2, 3, 4, 3, 2, 4, 3, 4, 4], [1, 2, 3, 4, 3, 2, 4, 4, 3, 4], [1, 2, 3, 4, 3, 2, 4, 4, 4, 3], [1, 2, 3, 4, 3, 3, 2, 4, 4, 4], [1, 2, 3, 4, 3, 3, 4, 2, 4, 4], [1, 2, 3, 4, 3, 3, 4, 4, 2, 4], [1, 2, 3, 4, 3, 3, 4, 4, 4, 2], [1, 2, 3, 4, 3, 4, 2, 3, 4, 4], [1, 2, 3, 4, 3, 4, 2, 4, 3, 4], [1, 2, 3, 4, 3, 4, 2, 4, 4, 3], [1, 2, 3, 4, 3, 4, 3, 2, 4, 4], [1, 2, 3, 4, 3, 4, 3, 4, 2, 4], [1, 2, 3, 4, 3, 4, 3, 4, 4, 2], [1, 2, 3, 4, 3, 4, 4, 2, 3, 4], [1, 2, 3, 4, 3, 4, 4, 2, 4, 3], [1, 2, 3, 4, 3, 4, 4, 3, 2, 4], [1, 2, 3, 4, 3, 4, 4, 3, 4, 2], [1, 2, 3, 4, 3, 4, 4, 4, 2, 3], [1, 2, 3, 4, 3, 4, 4, 4, 3, 2], [1, 2, 3, 4, 4, 2, 3, 3, 4, 4], [1, 2, 3, 4, 4, 2, 3, 4, 3, 4], [1, 2, 3, 4, 4, 2, 3, 4, 4, 3], [1, 2, 3, 4, 4, 2, 4, 3, 3, 4], [1, 2, 3, 4, 4, 2, 4, 3, 4, 3], [1, 2, 3, 4, 4, 2, 4, 4, 3, 3], [1, 2, 3, 4, 4, 3, 2, 3, 4, 4], [1, 2, 3, 4, 4, 3, 2, 4, 3, 4], [1, 2, 3, 4, 4, 3, 2, 4, 4, 3], [1, 2, 3, 4, 4, 3, 3, 2, 4, 4], [1, 2, 3, 4, 4, 3, 3, 4, 2, 4], [1, 2, 3, 4, 4, 3, 3, 4, 4, 2], [1, 2, 3, 4, 4, 3, 4, 2, 3, 4], [1, 2, 3, 4, 4, 3, 4, 2, 4, 3], [1, 2, 3, 4, 4, 3, 4, 3, 2, 4], [1, 2, 3, 4, 4, 3, 4, 3, 4, 2], [1, 2, 3, 4, 4, 3, 4, 4, 2, 3], [1, 2, 3, 4, 4, 3, 4, 4, 3, 2], [1, 2, 3, 4, 4, 4, 2, 3, 3, 4], [1, 2, 3, 4, 4, 4, 2, 3, 4, 3], [1, 2, 3, 4, 4, 4, 2, 4, 3, 3], [1, 2, 3, 4, 4, 4, 3, 2, 3, 4], [1, 2, 3, 4, 4, 4, 3, 2, 4, 3], [1, 2, 3, 4, 4, 4, 3, 3, 2, 4], [1, 2, 3, 4, 4, 4, 3, 3, 4, 2], [1, 2, 3, 4, 4, 4, 3, 4, 2, 3], [1, 2, 3, 4, 4, 4, 3, 4, 3, 2], [1, 2, 3, 4, 4, 4, 4, 2, 3, 3], [1, 2, 3, 4, 4, 4, 4, 3, 2, 3], [1, 2, 3, 4, 4, 4, 4, 3, 3, 2]

\$a(5) = 128458\$;

\$a(6) = 612887198\$;

...and so on.

* Note, for example, that [2, 1, 2] violates (1) while [1, 1, 2] violates (3).

(Other interpretations of the underlying objects being counted no doubt exist too, feel free to comment regarding these, or, even better, explain them as part of an answer.)

The Challenge

Write a program or function which does any of the following:

• Takes a non-negative integer, \$n\$ and outputs either:
  • \$a(n)\$
  • \$[a(0),\cdots ,a(n)]\$
• Takes a positive integer, \$n\$ and outputs either:
  • \$a(n-1)\$
  • \$[a(0),\cdots ,a(n-1)]\$
• Takes no input and outputs the sequence \$a\$ forever

---

This is code-golf so try to achieve the shortest solution in your chosen language.

Also insightful answers that are not necessarily the shortest, so long as they are still well golfed, will probably be received well!

---

This sequence is not currently in the OEIS, and as far as I can tell neither is any trivially related sequence (e.g. [1,1,2,11,393,12442,...]) - if you spot any do comment.

Answer 1

JavaScript (ES6),  91 ... 76  74 bytes

A recursive approach. This is very fast up to \$n=5\$. Computing \$a(6)\$ takes approximately 2 minutes on my laptop.

n=>(g=a=>1+(h=i=>i&&h(i-1)+(a[i]^i&&a[i-1]?g(b=[...a,0],b[i]++):0))(n))`1`

Try it online!

How?

Instead of explicitly building the sequences, we just keep track of how many times each value appears. This gives us enough information to decide which values are allowed to be added at any given time, assuming they're always added at the end of the sequence.

Commented

n => (                     // n = input
  g = a =>                 // g is a recursive function taking an array a[] holding
                           // how many times each value appears in the sequence
  1 + (                    // increment the final result
    h = i =>               // h is a recursive function taking i = next value to try
      i &&                 //   stop if i = 0
      h(i - 1) + (         //   otherwise, do a recursive call to h with i - 1
        a[i] ^ i &&        //   if i does not appear i times (rule #3)
        a[i - 1] ?         //   and i - 1 appears at least once (rule #1):
          g(               //     add the result of a recursive call to g:
            b = [...a, 0], //       define b[] as a copy of a[] with an extra '0'
                           //       so that b[i] is guaranteed to be defined
                           //       (at this point, we know that a[0] to a[i-1] exist)
            b[i]++         //       increment b[i]
          )                //     end of recursive call to g
        :                  //   else:
          0                //     add nothing
      )                    //
  )(n)                     // initial call to h with the maximum value i = n (rule #2)
)`1`                       // initial call to g with a[0] = '1', which is required to
                           // to allow i = 1 to be added as per rule #1

Answer 2

Pyth, 13 bytes

lfUI{T{.ysmRh

Try it online!

Let's go through this step by step, starting at the end:

• mRh: This autoexpands to mRhdQ. This means "Map the function m with right input hd over the input Q."

  • Q is an integer (e.g. 3) so it gets automatically cast to a range (e.g. [0, 1, 2]).
  • The m function is the map function.
  • d is defined to be the input to the map function.
  • h is the + 1 function (head).
  • m with two numeric inputs just replicates the left input a number of times equal to the right input.
  • As a result, mRh outputs a list like this: [[0], [1, 1], [2, 2, 2]].
• s: Flatten (sum). Now we have a list like [0, 1, 1, 2, 2, 2].
• .y: All permuted subsets.
• {: Uniquify (remove duplicates). Now we have a list like [[], [0], [1], [2], [0, 1], ... ]
• fUI{T: Filter that list on the function UI{T.
  • T is the input to the filter.
  • {: Uniquify the list to be filtered. Uniquify orders the unique elements in the order they first appear.
  • UI: Invariant under the function U:
    • U: Cast to range. So the unique elements must be [], or [0], or [0, 1], etc. to pass this test.
• l: Length. The result is implicitly printed.

To see the orderings, just remove the l.

Answer 3

Jelly, 18 bytes

x`€FŒ!QJƑ$Ƈ¹Ƥ€ẎQL‘

Try it online!

An initial attempt at a Jelly answer. A monadic link taking an integer and returning an integer. Too slow for n>3 on TIO.

Explanation

x`€                | Repeat each of 1..n itself times
   F               | Flatten
    Œ!             | Permutations
         $Ƈ        | Keep those where the following is true:
      Q            | - Uniquify
       JƑ          | - Check whether invariant when a sequence along the list is generated
           ¹Ƥ€     | Prefixes of each
              Ẏ    | Join outer lists
               Q   | Uniquify
                L  | Length
                 ‘ | Add one (to account for the empty list)

Longer but handles \$n=5\$ in under 25 seconds on TIO

Jelly, 24 bytes

ċⱮṀ$;0ḣ³<J$T;€)Ẏ
“”WÇƬẈS

Try it online!

Thanks to @JonathanAllan for improving the final bit of the faster version!

Answer 4

R, 113 106 98 bytes

g=function(n,N=1:n,B=N*0){for(e in N[c(1,B)[-n-1]>0&(F=all(B<=N))])F=F+g(n,,'[<-'(B,e,B[e]+1));+F}

Try it online!

• -9 bytes thanks to @RobinRyder
• -2 bytes using @Arnauld idea of storing occurrences table only (I just noticed that basically I was using the same approach, but creating the actual list too)

Answer 5

Ruby, 100 bytes

Relatively simple answer similar to the Jelly solution, but it's able to calculate for n=4 without timing out on TIO (albeit taking 30 seconds to do so), which Jelly can't at time of writing.

->n{r=(1..n).flat_map{|j|[j]*j};i=0;r.sum{r.permutation(i+=1).uniq.count{|a|a.uniq==[*1..a.max]}}+1}

Try it online!

Answer 6

Raku, 94 bytes

{1+set map ~*,grep {all .unique Z==^$_},.permutations>>[[\,] ^$_][*;*]}o{(^$_ Zxx 1..$_)[*;*]}

Try it online!

Times out for \$n>3\$, mostly since it is running the same filter for all prefixes of all permutations of the largest list (i.e. [1,2,2,3,3,3,...n]). This results in a lot of duplicates that have to filtered out later.

Answer 7

05AB1E, 19 18 17 bytes

ÝDÅΓœ€Œ€`ÙʒÙāQ}g>

Pretty slow (\$n=3\$ in about 5.5 0.5 seconds on TIO), but it works.

Inspired by @isaacg's Pyth answer.
I have the feeling this can definitely be golfed by at least a few bytes, though.
-1 byte thanks to @ExpiredData.
-1 byte and sped up by changing the order of some operations thanks to @Grimmy.

Try it online or verify a few more test cases.

Explanation:

Ý                  # Push a list in the range [0, (implicit) input]                        
                   # (NOTE: `L` cannot be used here, because input=0 would become [1,0])
 D                 # Duplicate this list
  ÅΓ               # Run-length encode the lists, to have each value repeat itself that
                   # many times (i.e. [1,2,3,4] → [1,2,2,3,3,3,4,4,4,4])
    œ              # Take all permutations of this list
     ʒ             # Filter this list of lists by:
      Ù            #  Uniquify it
       ā           #  Push a list in the range [1, length] (without popping the list itself)
        Q          #  Check if both lists are equal
         }€η       # After the filter: take the prefixes of each remaining permutation
            €`     # Flatten one level
              Ù    # Uniquify the list of lists
               g   # After the filter: get the amount of remaining lists by taking the length
                >  # + 1 for the missing `[]`
                   # (after which this is output implicitly)

Minor (but even slower) alternative: $ÝDÅΓœ€Œ€`ÙvyÙāQO: Try it online or verify a few more test cases.

$                  # Push 1 and the input
 ÝDÅΓœ             # Same as above
      €Œ           # Get all sublists of each permutation
        €`Ù        # Same as above
           v       # Loop over each inner list `y`
            y      #  Push list `y`
             ÙāQ   #  Same as above
                O  #  Take the sum of the stack
                   # (after the loop, the result is output implicitly)

Answer 8

Charcoal, 34 bytes

Ｎθ⊞υυＦυＦθＦ∧∨¬κ№ι⊖κ‹№ικ⊕κ⊞υ⁺ι⟦κ⟧ＩＬυ

Try it online! Link is to verbose version of code. Builds up all a(n) lists in memory, so TIO will only go up to n=5. Explanation:

Ｎθ

Input n.

⊞υυ

Start with a sequence with no digits. (Alternatively, I could start with a list containing -1; this would cost 3 bytes here and then save 3 bytes because I don't need to special case the first digit below.)

Ｆυ

Loop through each sequence as it is discovered.

Ｆθ

Loop through each available digit. (These are 0-indexed, so each digit i must be less than n and can be added if there are no more than i digits i so far.)

Ｆ∧∨¬κ№ι⊖κ‹№ικ⊕κ

Check that the digit is legal.

⊞υ⁺ι⟦κ⟧

If so then append this sequence to the list.

ＩＬυ

Output the total number of sequences found.

Answer 9

Perl 5, 150 bytes

sub f{my$n=pop;$n?do{my%e;@f=f($n-1);push@f,map{$f=$_;grep!$e{$_}++,map$f=~s/.{$_}/$&$n/r,$n==1?0:index($f,$n-1)+1||9e9..length$f}@f for 1..$n;@f}:''}

Try it online!

Produces the correct output in about two seconds for up to n=5.

Out of memory for n=6. And would not work anyway for n>9 (two digit numbers).

Thought about using a permutation solution like @Value Ink's Ruby answer, but could'nt find a core perl function or module that generated perm's and including a permutation function would probably add just way too many bytes.

With indentation, comments and test run:

sub f {
    my $n = pop;
    $n == 0 ? ('')
  : $n == 1 ? ('',1)
  : do {
      my %e;                                   #keep track of existing elements (strings)
      @f = f($n-1);                            #start with f(n-1) array
      push @f, map{                            #expand f array n times
        $f = $_;                               #f = current @f element
        grep !$e{$_}++,                        #don't add if already exists
          map $f =~ s/.{$_}/$&$n/r,            #insert n char at current position
            index($f,$n-1)+1||9e9 .. length$f  #loop positions from first occurence of n-1 to end
      } @f
        for 1..$n;
      @f                                       #return expanded @f array (string sequences)
    }
}

# test:
for my $n (0..5){
  my @f = f($n);
  my $list = $n<5 ? '['.join(',',map"'$_'",@f).']' : '';
  print "$n: ".@f." $list\n";
}

Output:

0: 1 ['']
1: 2 ['','1']
2: 4 ['','1','12','122']
3: 16 ['','1','12','122','123','1232','1223','1233','12332','12323','12233','12333','123332','123323','123233','122333']
4: 409 ['','1','12','122','123','1232','1223','1233','12332','12323','12233','12333','123332','123323','123233','122333','1234','12342','12324','12234','12343','12334','123432','123342','123324','123423','123243','123234','122343','122334','123433','123343','123334','1234332','1233432','1233342','1233324','1234323','1233423','1233243','1233234','1234233','1232433','1232343','1232334','1223433','1223343','1223334','12344','123442','123424','123244','122344','123443','123434','123344','1234432','1234342','1234324','1233442','1233424','1233244','1234423','1234243','1234234','1232443','1232434','1232344','1223443','1223434','1223344','1234433','1234343','1234334','1233443','1233434','1233344','12344332','12343432','12343342','12343324','12334432','12334342','12334324','12333442','12333424','12333244','12344323','12343423','12343243','12343234','12334423','12334243','12334234','12332443','12332434','12332344','12344233','12342433','12342343','12342334','12324433','12324343','12324334','12323443','12323434','12323344','12234433','12234343','12234334','12233443','12233434','12233344','123444','1234442','1234424','1234244','1232444','1223444','1234443','1234434','1234344','1233444','12344432','12344342','12344324','12343442','12343424','12343244','12334442','12334424','12334244','12332444','12344423','12344243','12344234','12342443','12342434','12342344','12324443','12324434','12324344','12323444','12234443','12234434','12234344','12233444','12344433','12344343','12344334','12343443','12343434','12343344','12334443','12334434','12334344','12333444','123444332','123443432','123443342','123443324','123434432','123434342','123434324','123433442','123433424','123433244','123344432','123344342','123344324','123343442','123343424','123343244','123334442','123334424','123334244','123332444','123444323','123443423','123443243','123443234','123434423','123434243','123434234','123432443','123432434','123432344','123344423','123344243','123344234','123342443','123342434','123342344','123324443','123324434','123324344','123323444','123444233','123442433','123442343','123442334','123424433','123424343','123424334','123423443','123423434','123423344','123244433','123244343','123244334','123243443','123243434','123243344','123234443','123234434','123234344','123233444','122344433','122344343','122344334','122343443','122343434','122343344','122334443','122334434','122334344','122333444','1234444','12344442','12344424','12344244','12342444','12324444','12234444','12344443','12344434','12344344','12343444','12334444','123444432','123444342','123444324','123443442','123443424','123443244','123434442','123434424','123434244','123432444','123344442','123344424','123344244','123342444','123324444','123444423','123444243','123444234','123442443','123442434','123442344','123424443','123424434','123424344','123423444','123244443','123244434','123244344','123243444','123234444','122344443','122344434','122344344','122343444','122334444','123444433','123444343','123444334','123443443','123443434','123443344','123434443','123434434','123434344','123433444','123344443','123344434','123344344','123343444','123334444','1234444332','1234443432','1234443342','1234443324','1234434432','1234434342','1234434324','1234433442','1234433424','1234433244','1234344432','1234344342','1234344324','1234343442','1234343424','1234343244','1234334442','1234334424','1234334244','1234332444','1233444432','1233444342','1233444324','1233443442','1233443424','1233443244','1233434442','1233434424','1233434244','1233432444','1233344442','1233344424','1233344244','1233342444','1233324444','1234444323','1234443423','1234443243','1234443234','1234434423','1234434243','1234434234','1234432443','1234432434','1234432344','1234344423','1234344243','1234344234','1234342443','1234342434','1234342344','1234324443','1234324434','1234324344','1234323444','1233444423','1233444243','1233444234','1233442443','1233442434','1233442344','1233424443','1233424434','1233424344','1233423444','1233244443','1233244434','1233244344','1233243444','1233234444','1234444233','1234442433','1234442343','1234442334','1234424433','1234424343','1234424334','1234423443','1234423434','1234423344','1234244433','1234244343','1234244334','1234243443','1234243434','1234243344','1234234443','1234234434','1234234344','1234233444','1232444433','1232444343','1232444334','1232443443','1232443434','1232443344','1232434443','1232434434','1232434344','1232433444','1232344443','1232344434','1232344344','1232343444','1232334444','1223444433','1223444343','1223444334','1223443443','1223443434','1223443344','1223434443','1223434434','1223434344','1223433444','1223344443','1223344434','1223344344','1223343444','1223334444']
5: 128458