Given $N$ light switches ,do total $P$ flips such that $Q$ are lit at the end. Find the number of ways to do this.

Question

We are given total $N$ switches (all of them are off in the beginning). Now we have to flip the switches exactly $P$ times such that $Q$ switches are lit up at the end.

When $P$ = $Q$ then the solution is just $^NP_Q$. When $P$ < $Q$ then the answer is obviously zero.

When $P$ > $Q$ and their difference is odd, the answer is again obviously zero.

I am unable to solve for the remaining case : $P$ > $Q$ and $P$ - $Q$ is a multiple of two.

Example: 5 switches, 3 should be lit up while doing 7 flips.

This becomes:

$a + b + c + d + e = 7$

Now the solutions here are $(1,1,1,0,4), (1,1,1,2,2), (1,1,3,0,2), (1,3,3,0,0)$

For each of these cases I have to find the number of solutions.

$(1,1,1,0,4)$ would be: $\frac{7!}{4!} *\frac{5!}{3!}$

$(1,1,1,2,2)$ would be: $\frac{7!}{2!2!} *\frac{5!}{3!2!}$

$(1,1,3,0,2)$ would be: $\frac{7!}{3!2!} *\frac{5!}{2!}$

$(1,3,3,0,0)$ would be: $\frac{7!}{3!3!} *\frac{5!}{2!2!}$

The total would be the sum of the above numbers. I was able to successfully calculate all the solutions because the values for N, P and Q were simple. How can I generally solve this ?

I might be wrong but I feel like I have to somehow make use of multinomial theorem here.

Edit: You can flip a switch as many times as you want under the constraint that the total flips have not exceeded P.

Answer 1

Here is an incomplete answer.

Let $f(n, p, q)$ be the function in question - the number of ways to make $p$ flips on $n$ lights with $q$ of them on in the end.

Let $D = \min(N, P)$.

We know that, in the course of making $P$ flips on $N$ switches, we will never encounter a state when there are more than $D$ lights on.

Let $v_p$ be the $D+1$ dimensional vector whose coordinates are zero-indexed and defined by $v_p(q) \equiv f(N, p, q)$. We have the recursion $v_{p}(q) = (q-1)v_{p-1}(q-1) + (q+1)v_{p-1}(q+1)$

Let $M$ be the $D+1 \times D+1$ matrix whose upper diagonal is $(1, 2, ..., D)$ and whose lower diagonal is $(N, N-1, ..., N-(D-1))$. For example if $P = 4, N = 6, (D = 4)$,

$M = \begin{bmatrix} & 1 \\ 6 & & 2 \\ & 5 & & 3 \\ & & 4 & & 4 \\ & & & 3 & \\ \end{bmatrix}$

You can see $v_{p+1} = M v_p$.

Using $e_k$ as the $k^{th}$ standard unit basis vector, $f(N, P, Q) = e_Q^T M^P e_0$.

I suspect $M$ can always be diagonalized, in which case the expression reduces to a degree $P$ polynomial in the eigenvalues of $M$. This yields a closed form if one can solve the eigenvalues in closed form.

If it cannot be diagonalized, then we end up with a more complicated method described here https://arxiv.org/pdf/1512.00136.pdf

Something interesting is that we also get a probabilistic interpretation. Setting $N = \frac 1 {D+1} M$, we get a stochastic matrix corresponding to a discrete birth death process. If there are $q$ lights currently on, turn one of them off with probability $\frac q {D+1}$, or turn a new light on with probability $1 - \frac q {D+1}$. The isomorphic question is, "What is the probability that at the $P^{th}$ stage, we will have $Q$ lights on?

Answer 2

When the numbers get bigger, I don't think there will be any way to disguise the ugliness. With that sense of defeatism, I suggest that a family of recursive relations at least describes the process in a clear way.

With a fixed number of lightbulbs $N$, let $X_b(f)$ represent the number of ways to flip the lightbulbs a total of $f$ times such that $b$ of them are bright at the end. Since each flip is either turning off a bright bulb or turning on an unlit bulb, the recurrence relation is $$X_b(f)=(b+1)X_{b+1}(f-1)+(N-b+1)X_{b-1}(f-1)$$ with $X_0(0)=1$.