21
\$\begingroup\$

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 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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Somewhat related sequences: A105748 and A192012 \$\endgroup\$ – Jonathan Allan Jan 27 at 21:27
  • 6
    \$\begingroup\$ I find it unacceptable that you did not provide all the examples for a(5). \$\endgroup\$ – RGS Jan 27 at 21:58
  • \$\begingroup\$ @NickKennedy it's meant to represent the first \$n\$ elements, so 0 gives [], while 3 gives [1,2,4]... is there better notation I could employ? Thanks! \$\endgroup\$ – Jonathan Allan Jan 27 at 22:24
  • 1
    \$\begingroup\$ I guess (it allows 0 to give [], but so does the second) - I can just remove it, thanks! \$\endgroup\$ – Jonathan Allan Jan 27 at 22:28
  • 3
    \$\begingroup\$ This is a fun, novel question! Good job, thanks for posting it. \$\endgroup\$ – isaacg Jan 28 at 1:19
8
\$\begingroup\$

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
\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ I don't understand your code yet, but double() can be 1[0] for -4 bytes. It seems that setting x=0 also works, for -7 bytes instead. \$\endgroup\$ – Robin Ryder Jan 29 at 19:31
  • \$\begingroup\$ @RobinRyder I'm really rusty... thanks! :D \$\endgroup\$ – digEmAll Jan 29 at 19:36
  • 1
    \$\begingroup\$ Welcome back! 102 bytes \$\endgroup\$ – Robin Ryder Jan 29 at 19:56
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ Why do you need to sort the list of suffixes? Since permutations for any ordering of the same list should be the same shouldn't they? \$\endgroup\$ – Expired Data Jan 28 at 12:56
  • 1
    \$\begingroup\$ @ExpiredData Oops, you're completely right, thanks. The sort was still there from a previous attempt of generating all permutations of all lengths, for which 05AB1E unfortunately doesn't have any builtins a.f.a.i.k., unlike Pyth. \$\endgroup\$ – Kevin Cruijssen Jan 28 at 13:00
  • 1
    \$\begingroup\$ @Grimmy ÝD×S would fail for inputs \$>9\$, though. I've asked OP whether we can assume the input is \$<10\$, although I have the feeling I know the answer already. I will edit to add the sped up though, thanks! \$\endgroup\$ – Kevin Cruijssen Jan 29 at 14:33
  • 1
    \$\begingroup\$ Oh whoops. You can use ÝDÅΓ then. \$\endgroup\$ – Grimmy Jan 29 at 15:28
  • 1
    \$\begingroup\$ @Grimmy That works, thanks! \$\endgroup\$ – Kevin Cruijssen Jan 29 at 17:15
1
\$\begingroup\$

Charcoal, 34 bytes

Nθ⊞υυFυFθF∧∨¬κ№ι⊖κ‹№ικ⊕κ⊞υ⁺ι⟦κ⟧ILυ

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:

Nθ

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.)

Fυ

Loop through each sequence as it is discovered.

Fθ

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.)

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

Check that the digit is legal.

⊞υ⁺ι⟦κ⟧

If so then append this sequence to the list.

ILυ

Output the total number of sequences found.

\$\endgroup\$
1
\$\begingroup\$

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 
\$\endgroup\$
  • \$\begingroup\$ Is there a fix you can make to have this work (at least in theory given enough resources) for any \$n\$? Otherwise it's not currently a valid answer (I still up-voted it as it is a nice method), \$\endgroup\$ – Jonathan Allan Jan 29 at 17:01
  • \$\begingroup\$ It DO work for any n in theory – even though the computer needed would quickly grow beyond the size of the universe and run the age of it as n grows. I think your comment also apply at least as much for at least a couple of the other answers here as well (I see permutation methods), with more up-votes and ability to do lesser n's. So unfair...go figure :-) \$\endgroup\$ – Kjetil S. Jan 30 at 7:47
  • \$\begingroup\$ I'm talking about the fact that there is a limit to numbers which are less than 10 due to you use of grep & the like. \$\endgroup\$ – Jonathan Allan Jan 30 at 8:01

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.