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

1 Answer

0 like 0 dislike
0 like 0 dislike
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].

Related questions

0 like 0 dislike
0 like 0 dislike
3 answers
RashidAbdalla asked Jun 21, 2022
[The article](https://www.reddit.com/r/statistics/comments/vh2ecs/analysis_of_russian_vaccine_results_suggests_they/) [Twitter summary](https://twitter.com/K_Sheldrick/st...
RashidAbdalla asked Jun 21, 2022
0 like 0 dislike
0 like 0 dislike
1 answer
MSR_Tlse asked Jun 21, 2022
Are the S3/S4 Edexcel Further Maths units useful to become an actuary? Topics include sampling, unbiased and biased estimators, confidence intervals and significance test...
MSR_Tlse asked Jun 21, 2022
0 like 0 dislike
0 like 0 dislike
20 answers
balkissoon asked Jun 21, 2022
Considering leaving the actuarial profession. What are some interesting fields you've heard of former actuaries going into? How did they get into the new field?
balkissoon asked Jun 21, 2022
0 like 0 dislike
0 like 0 dislike
9 answers
HilaryKHarper asked Jun 21, 2022
Has anyone successfully guessed on like half of the questions on an exam and still passed?
HilaryKHarper asked Jun 21, 2022
0 like 0 dislike
0 like 0 dislike
0 answers
RyanWCTV asked Jun 21, 2022
Range of two Discrete Random Variables
RyanWCTV asked Jun 21, 2022

33.4k questions

135k answers

0 comments

33.7k users

OhhAskMe is a math solving hub where high school and university students ask and answer loads of math questions, discuss the latest in math, and share their knowledge. It’s 100% free!