"Number of possible orders" problem using on-off lightbulbs.

There are (n;k) ways to choose k of n colors to be lit, (n;k) ways to choose k positions of n slots to place them, and k! ways to order the lit colored bulbs. Any number k of the total n bulbs can be lit, so the number of arrangements is a[n] = ∑k!(n;k)^(2). The first few values for a[0..4] are [1, 2, 7, 34, 209].

If you have a list of all numbered slots s[1..n] and all colors c[1..n], each arrangement is a partial (because some can be off) injective (because a bulb can have at most one color) map of slots to colors. And if you iterate this map, each slot belongs to _either_ a circular or linear graph (because no two bulbs can have the same color). That means the combinatorial class of arrangements has a labelled construction:

SET(CYC(z) + SEQ^(≥1)(z))

which corresponds to the exponential generating function

f(z) = (1-z)^(-1)exp((1-z)^(-1)-1)

f(z) is holonomic, and satisfies the differential equation (1-z)\*f(z)-(1-z)^(2)f'(z) + f(z) = 0, which we can use to derive a recurrence:

a[n] = 2n\*a[n-1] - (n-1)^(2)\*a[n-2], a[0..1] = [1, 2]

This recurrence is a fast method for calculating large a[n].

0 like 0 dislike