21
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:
- A number may only appear after all lower numbers have appeared
- All numbers which appear must be less than or equal to \$n\$
- 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.
1
Somewhat related sequences: A105748 and A192012
– Jonathan Allan – 2020-01-27T21:27:48.7536I find it unacceptable that you did not provide all the examples for
a(5)
. – RGS – 2020-01-27T21:58:08.943@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! – Jonathan Allan – 2020-01-27T22:24:02.2971I guess (it allows
0
to give[]
, but so does the second) - I can just remove it, thanks! – Jonathan Allan – 2020-01-27T22:28:59.7373This is a fun, novel question! Good job, thanks for posting it. – isaacg – 2020-01-28T01:19:34.580
Wonder if (6)=612887198 and further can be found mathematically instead of the brute forcey ways of the answers here. – Kjetil S. – 2020-01-28T08:57:56.110
@KjetilS. I should think so. – Jonathan Allan – 2020-01-28T09:00:33.577
Can we make the assumption that the input is $<10$ given how quickly the results grow, or should it (given enough time/resources) work for any input (in theory)? I think I already know the answer, but asking just in case I could save a byte. ;) – Kevin Cruijssen – 2020-01-29T14:31:03.310
@KevinCruijssen It should work in theory for unbounded $n$ or output $a$ for ever in theory - allowing for memory/precision/overflow issues in real world implementations. – Jonathan Allan – 2020-01-29T16:58:30.927