Maybe $ 2^{k - n}$.. at any sequence $ a_1, a_2, \cdots, a_k$ in $ M$ Let $ b_i = \mid \{ j | a_j = i, 1 \leq j \leq k \} \mid$ we can change first $ b_i - 1$ $ i$'s to $ i$ or $ n + i$ randomly and last $ b_i$-th $ i$ to $ i$ or $ n + i$ for makes $ n + i$-th lamp off. This makes sequences in $ N$ from $ a_1, a_2, \cdots, a_k$ because $ \sum_{i = 1}^{n} (b_i - 1) = k-n$ the answer is $ 2^{k-n}$ ex) n = 3, k = 7 in M 1211322 in N 111 $ \rightarrow$ 111, 144, 414, 441 (from 11, 14, 41, 44 $ \rightarrow 2^2$) 222 $ \rightarrow$ 222, 255, 525, 552 (from 22, 25, 52, 55 $ \rightarrow 2^2$) 3 $ \rightarrow$ 3 ($ 2^0$) if we choose 144, 525, 3 $ \rightarrow$ 1544325 $ \Rightarrow 2^2 \times 2^2 \times 2^0 = 2^4 = 2^{7 - 3}$

I am getting 2^((k-n)/2) Let, P(x,y) be the number of ways we can put y steps in a sequence of length x So, we put n steps in k length sequence to turn the first n lamps on = P(k,n) Then we have to hit every lamp twice. So, we can pair up steps. and in each step we have 2n lamps to choose from(for N) and n lamps to choose from(for M). So, we have for N : (2n)^((k-n)/2) choices and for M : n^((k-n)/2) choices. Now we can put one hit from each pair in the sequence in P((k-n),(k-n)/2) ways and the other hit has just as many choices. So, N = P(k,n) * (P((k-n),(k-n)/2)^2) * (2n)^((k-n)/2) and, M = P(k,n) * (P((k-n),(k-n)/2)^2) * (n^((k-n)/2)) Tanvir Dhaka, Bangladesh

KuMing wrote: Maybe $ 2^{k - n}$.. at any sequence $ a_1, a_2, \cdots, a_k$ in $ M$ Let $ b_i = \mid \{ j | a_j = i, 1 \leq j \leq k \} \mid$ we can change first $ b_i - 1$ $ i$'s to $ i$ or $ n + i$ randomly and last $ b_i$-th $ i$ to $ i$ or $ n + i$ for makes $ n + i$-th lamp off. This makes sequences in $ N$ from $ a_1, a_2, \cdots, a_k$ because $ \sum_{i = 1}^{n} (b_i - 1) = k - n$ the answer is $ 2^{k - n}$ ex) n = 3, k = 7 in M 1211322 in N 111 $ \rightarrow$ 111, 144, 414, 441 (from 11, 14, 41, 44 $ \rightarrow 2^2$) 222 $ \rightarrow$ 222, 255, 525, 552 (from 22, 25, 52, 55 $ \rightarrow 2^2$) 3 $ \rightarrow$ 3 ($ 2^0$) if we choose 144, 525, 3 $ \rightarrow$ 1544325 $ \Rightarrow 2^2 \times 2^2 \times 2^0 = 2^4 = 2^{7 - 3}$ in N, what about sequence 1235555 ? as far as i see haven't counted it...

tanvirabs wrote: So, N = P(k,n) * (P((k-n),(k-n)/2)^2) * (2n)^((k-n)/2) and, M = P(k,n) * (P((k-n),(k-n)/2)^2) * (n^((k-n)/2)) You overcounted. You haven't accounted for repetitions of lamps chosen.

felixx wrote: KuMing wrote: Maybe $ 2^{k - n}$.. at any sequence $ a_1, a_2, \cdots, a_k$ in $ M$ Let $ b_i = \mid \{ j | a_j = i, 1 \leq j \leq k \} \mid$ we can change first $ b_i - 1$ $ i$'s to $ i$ or $ n + i$ randomly and last $ b_i$-th $ i$ to $ i$ or $ n + i$ for makes $ n + i$-th lamp off. This makes sequences in $ N$ from $ a_1, a_2, \cdots, a_k$ because $ \sum_{i = 1}^{n} (b_i - 1) = k - n$ the answer is $ 2^{k - n}$ ex) n = 3, k = 7 in M 1211322 in N 111 $ \rightarrow$ 111, 144, 414, 441 (from 11, 14, 41, 44 $ \rightarrow 2^2$) 222 $ \rightarrow$ 222, 255, 525, 552 (from 22, 25, 52, 55 $ \rightarrow 2^2$) 3 $ \rightarrow$ 3 ($ 2^0$) if we choose 144, 525, 3 $ \rightarrow$ 1544325 $ \Rightarrow 2^2 \times 2^2 \times 2^0 = 2^4 = 2^{7 - 3}$ in N, what about sequence 1235555 ? as far as i see haven't counted it... in M 1232222 in N 22222 $ \rightarrow$ 22222, 22255, $ \cdots$ 55552 (from 2222, 2225, $ \cdots$ 5555 $ \rightarrow 2^4$) if we choose 2555 $ \rightarrow$ 1235555

dblues wrote: tanvirabs wrote: So, N = P(k,n) * (P((k-n),(k-n)/2)^2) * (2n)^((k-n)/2) and, M = P(k,n) * (P((k-n),(k-n)/2)^2) * (n^((k-n)/2)) You overcounted. You haven't accounted for repetitions of lamps chosen. Yes. Sorry for the mistake. Completely wrong solution. Tanvir Dhaka, Bangladesh

KuMing wrote: felixx wrote: KuMing wrote: Maybe $ 2^{k - n}$.. at any sequence $ a_1, a_2, \cdots, a_k$ in $ M$ Let $ b_i = \mid \{ j | a_j = i, 1 \leq j \leq k \} \mid$ we can change first $ b_i - 1$ $ i$'s to $ i$ or $ n + i$ randomly and last $ b_i$-th $ i$ to $ i$ or $ n + i$ for makes $ n + i$-th lamp off. This makes sequences in $ N$ from $ a_1, a_2, \cdots, a_k$ because $ \sum_{i = 1}^{n} (b_i - 1) = k - n$ the answer is $ 2^{k - n}$ ex) n = 3, k = 7 in M 1211322 in N 111 $ \rightarrow$ 111, 144, 414, 441 (from 11, 14, 41, 44 $ \rightarrow 2^2$) 222 $ \rightarrow$ 222, 255, 525, 552 (from 22, 25, 52, 55 $ \rightarrow 2^2$) 3 $ \rightarrow$ 3 ($ 2^0$) if we choose 144, 525, 3 $ \rightarrow$ 1544325 $ \Rightarrow 2^2 \times 2^2 \times 2^0 = 2^4 = 2^{7 - 3}$ in N, what about sequence 1235555 ? as far as i see haven't counted it... in M 1232222 in N 22222 $ \rightarrow$ 22222, 22255, $ \cdots$ 55552 (from 2222, 2225, $ \cdots$ 5555 $ \rightarrow 2^4$) if we choose 2555 $ \rightarrow$ 1235555 ok, you're right, your solution is very very nice, very intelligent solution:)

Who proposed this problem?

If you apply induction on k-n=2T k+2-n=2T+2 ( when k=n solution is 1) you obtain that whereas N increases 2n(k+1)^2) ( with respect to the induction step) M increases n(k+1)^2 so in each step the ratio N/M duplicates and the answer is 2^(k-n)/2 Note:the formula: 2n(k+1)^2 is obtained from: you have two more steps...the only posibility is to choose any lamp (2n) and turn it on and off. We can perform each operation in one of (k+1) times (suppose that in the induction step you had a valid sequence of steps..in each step you can add these two steps in _S_S_S_S_......S_S_ since que have k "S" we have k+1 places to put the extra movement... Hope it is ok and you understand it ( sorry about the presentation it is very messy) Daniel

Let $ S_N, S_M$ be the sets of sequences with the respective definitions given in the problem ($ |S_N| = N, |S_M| = M$). We show a $ 1$ to $ 2^{k-n}$ correspondence from $ S_M$ to $ S_N$. Take an arbitrary sequence in $ S_M$. Only the numbers $ 1$ through $ n$ appear and each appears an odd number of times. Given a number $ i$, $ 1 \leq i \leq n$, pick an even number of occurrences of that number in the sequence and replace them with $ n+i$. If $ i$ appears $ 2m_i+1$ times, there are \[ {2m_i+1 \choose 0} + {2m_i+1 \choose 2} + \ldots + {2m_i+1 \choose 2m_i} = 2^{2m_i}\] ways to do this. We can determine that $ \sum m_i = \frac{\sum ( 2m_i + 1) - n}{2} = \frac{k-n}{2}$. Then the total number of ways is $ \prod 2^{2m_i} = 2^{2 \sum m_i} = \boxed{2^{k-n}}$. No sequence in $ S_N$ is obtained twice in the way. Note that each element is invariant mod $ n$ in the correspondence. So if two sequences in $ S_M$ gave the same one in $ S_N$, they would be the same mod $ n$ and thus the same sequence. All sequences in $ S_N$ are also obtained; just take each element mod $ n$ again (using residue classes $ 1, 2, \ldots n$) and this gives a sequence in $ S_M$ which generates the one you picked in $ S_N$.

Yes, I have the same solution! Even the same notation: $ S_M,S_N,m_i \dots$

Here is my solution with generating functions If $ f(x)=(x+\frac{x^3}{3!}+\frac{x^5}{5!}+\cdots )(1+\frac{x^2}{2!}+\frac{x^4}{4!}+\cdots)=\frac{\sinh(2x)}{2}$, then $ N=k! * [x^k](f(x)^n)$ If $ g(x)=(x+\frac{x^3}{3!}+\frac{x^5}{5!}+\cdots )=\sinh(x)$, then $ M=k! * [x^k] (g(x)^n)$ Hence \[ \frac{N}{M}=\frac{[x^k] ((\frac{\sinh(2x)}{2})^n)}{[x^k] ((\sinh(x))^n)}=2^{-n} \times \frac{[x^k] ((\sinh(2x))^n)}{[x^k] ((\sinh(x))^n)}=2^{-n}\times 2^k=2^{k-n} \]

@SplashD: I used the same generating functions but was unable to show your last step (but guessed the answer...). can you explain in more detail? PS: Hola

basically you see $ sinh(x)$ as a generating function and think of $ sinh(2x)$ as putting $ 2x$ insteead of $ x$

We'll form a bijection between each $ M$-sequence with $ 2^{k-n} N$-sequences. First, pair up each "main" lamp with a "back up" lamp, (where no back up lamps are ever turned on during the $ M$-sequences.) For each $ N$-sequence, we can map to a $ M$-sequence by transferring all the moves on the back up lamps to their corresponding main lamps. Now for each $ M$-sequence, consider the $ k_i$ (odd) moves done to main lamp $ i$. We can transfer an arbitrary amount of those moves to the back up light ($ 2^{k_i}$ ways). But only half of them will transfer an even number of moves to the back up, hence keeping the main on and the back up off towards end. So there are only $ 2^{k_i-1}$ ways. We can do this to each pair of lamps independently, so for each $ M$ sequence, there are $ 2^{\sum\limits_{i=1}^n(k_i-1)} = 2^{k-n}$ corresponding $ N$ sequences.

Igor wrote: Who proposed this problem? It's a french problem, proposed by Bruno Le Floch and Ilia Smilga. Pierre.

Let $ P(\bar{x}) = (x_1 + x_2 + ... + x_{2n})^k$ which has the usual multinomial expansion. To compute $ M$, we want to compute the sum of the coefficients of the terms where the powers of $ x_1, x_2, ... x_n$ are odd and the powers of $ x_{n + 1}, x_{n + 2}, ... x_{2n}$ are zero. Recall that the sum of the odd terms of a polynomial $ Q(x)$ is given by $ \frac {Q(1) - Q( - 1)}{2}$ (in other words, a second roots-of-unity filter). Applying this filter over $ x_1, x_2, ..., x_n$ gives $ M = \frac {1}{2^n} \sum_{i = 0}^{n} ( - 1)^i {n \choose i} (n - 2i)^k$ where we have chosen $ i$ of the variables to be $ - 1$ and $ n - i$ of the variables to be $ 1$ in each term. To compute $ N$, we want to compute the sum of the coefficients of the terms where the powers of $ x_1, x_2, ... x_n$ are odd and the powers of $ x_{n + 1}, x_{n + 2}, ..., x_{2n}$ are even. Recall that the sum of the even terms of a polynomial $ Q(x)$ is given by $ \frac {Q(1) + Q( - 1)}{2}$. Applying the first filter over $ x_1, x_2, ..., x_n$ and the second over $ x_{n + 1}, x_{n + 2}, ..., x_{2n}$ gives \begin{eqnarray*} N & = & \frac {1}{2^n} \sum_{j = 0}^{n} {n \choose j} \left( \frac {1}{2^n} \sum_{i = 0}^{n} ( - 1)^i {n \choose i} (n - 2i + n - 2j)^k \right) \\ & = & \frac {1}{2^{2n}} \sum_{s = 0}^{2n} (2n - 2s)^k \sum_{i + j = s} ( - 1)^i {n \choose i} {n \choose j} \\ & = & \frac {2^k}{2^{2n}} \sum_{r = 0}^{n} (n - 2r)^k ( - 1)^r {n \choose r} \\ & = & 2^{k - n} M \\ \end{eqnarray*} where $ r = \frac {s}{2}$ and we note that $ \sum_{i + j = s} ( - 1)^k {n \choose i} {n \choose j} = [x^s](x - 1)^n (x + 1)^n = [x^s] (x^2 - 1)^n$. Interestingly enough, neither of these expressions makes it particularly clear that they evaluate to zero when $ k < n$. (The generalization when the lamps are not assumed to be binary but take on lighting values $ \bmod m$ is given by the Dirichlet characters $ \bmod m$.)

I think if this problem were the 2nd, the real 3rd one were the 5th and a combinatorics one were the 3rd, this exam would be a very nice IMO.

This is first combinatorics imo task I ever solved so if this solution was already posted I didn't see it my solution goes like this: first we count the N we first see that on lamps from 1..n was odd number of steps(on each of them not together) so we can see that there is $ {k\choose n}n!$ ways to arrange steps and we have $ {(2n)}^{k - n}x$ ways to rearrange the else where x is average number of ways to rearrange pairs of choosen ones. so $ N = {k\choose n}n! {(2n)}^{k - n}x$ and as well we can on pretty much the same way deduce that $ M = {k\choose n}n! {(n)}^{k - n}x$ and only difference is that we must rearange the rest in only n places. so ${ \frac {N}{M} = {2}^ {k - n}}$ I'm not 100%sure in this solution but everything looks good for me sorry for awful explanations but this was hard for me to write it on my language but on English it was twice as tricky.

excuse me what Note $N$ is the coefficient of $x^k$ in the power series $$k! \left( \frac{x}{1!}+\frac{x^3}{3!}+ \cdots \right)^n \left( \frac{1}{0!} + \frac{x^2}{2!} + \cdots \right)^n = k! \left( \frac{e^x-e^{-x}}{2} \right)^n \left( \frac{e^x+e^{-x}}{2} \right)^n = \frac{1}{4^n} \cdot k! \left( e^{2x}-e^{-2x} \right)^n$$If we let $f(x)=(e^x-e^{-x})^n$ then this is equal to $\frac{1}{4^n} \cdot \left. \frac{\text{d}^kf(2x)}{\text{d}x^k} \right\vert_{x=0}= f^k(0) \cdot \frac{2^k}{4^n}$ where $f^k$ is the $k$-th derivative of $f$. Similarly, note $M$ is the $x^k$ coefficient of $$k! \left( \frac{x}{1!}+\frac{x^3}{3!}+ \cdots \right)^n = k!\left( \frac{e^x-e^{-x}}{2} \right)^n = \frac{1}{2^n} \cdot k! \left( e^x-e^{-x} \right)^n$$which is just $\frac{f^k(0)}{2^n}$. So the answer is just $\frac{N}{M} = \boxed{2^{k-n}}.$

The answer should be $2^{k-n}$. In the following $M$ and $N$ denotes the set of all sequences satisfying the given conditions instead of the number of such sequences. We will show that we can construct $2^{k-n}$ sequences in $N$ for every sequence in $M$, which will imply the result. Take an arbitrary sequence in $M$. We denote by $l_{i}$ the number of times th$i$ appears in this sequence. Obviously $l_{i}$ is odd for $i=1,...,n$ and $\sum_{i=1}^{n} l_{i}=k$. For each $1\leq i\leq n$ we may replace an even number of $i$'s with $n+i$ to obtain a new sequence in $N$. There are $\binom{l_{i}}{0}$ possibilities to replace zero $i'$s, $\binom{l_{i}}{2}$ possibilities to replace two $i'$ and so on. In total, there are $$\sum_{k=0}^{\frac{l_{i}-1}{2}}\binom{l_{i}}{2k}=\frac{1}{2}\sum_{k=0}^{l_{i}}\binom{l_{i}}{k}=\frac{1}{2}\cdot 2^{l_{i}}=2^{l_{i}-1}$$possible choices for each $i$. Thus there are $$\prod_{i=1}^{n}2^{l_{i}-1}=2^{k-n}$$possibilities to transform this sequence and obtain a sequence in $N$. It remains to show that no two different sequences in $M$ can be tranformed into the same sequence and that every sequence in $N$ can actually be obtained from some sequence in $M$. This becomes clear when considering the 'opposite' transformation: Take any sequence in $N$ and replace any number $j>n$ in it with $j-n$. In this way, we get the unique sequence in $M$ from which we may generate the original sequence in $N$.

Genfunc bashers scare me. The answer is $2^{k-n}$. Call sequences described in $N$ boring and those in $M$ fancy. To prove the answer, I will stablish a one to $2^{k-n}$ correspondence between a single fancy sequence and $2^{k-n}$ boring sequences. Observe that we can represent a sequence of steps as a sequence of positive integers, with each representing the lamp toggled in the obvious way. If we have some sequence of positive integers represnting steps that only contains $1$ through $n$, with an odd number of occurrences for each (thus representing a fancy sequence), we can generate a unique boring sequence by replacing some even number of $1$'s with $(n+1)$'s, an even number of $2$'s with $(n+2)$'s, and so on. If we let $a_i$ denote the number of times $i$ appears in our fancy sequence for $1 \leq i \leq n$, the number of ways to replace $i$ with $n+i$ is: $$\binom{a_i}{0}+\binom{a_i}{2}+\cdots+\binom{a_i}{a_i-1}=2^{a_i-1},$$where the equality is from a well-known roots of unity filter argument. Hence, multiplying over all $i$ we get the total number of ways we can replace the elements of the old sequence is $2^{n-k}$, so the correspondence is established and we're done. $\blacksquare$

I claim the answer is $2^{k-n}$. We prove this with the following bijection. Take any sequence of flips in $M$ with $x_i$ flips in the $i$-th position. Then, it is well known that there are $2^{x_i-1}$ ways to choose an even number of elements from a set of $x_i$. Thus, if for each $i$ we choose an even number of flip to instead flip at $n+i$, a total of \[\prod_{i=1}^n 2^{x_i-1} = \frac{2^{\sum x_i}}{2^n}=2^{k-n}\]sequences are valid. Now the other direction is obvious because taking the sequence of flips in $N$ mod $n$ clearly gives exactly one sequence in $M$, so all sequences in $N$ can be generated by the described procedure. Thus, we have shown that there are exactly $2^{k-n}$ sequences in $N$ for every one in $M$, so \[\frac{N}{M}=2^{k-n}\]$\blacksquare$ $\textbf{Remark}$ This solution is motivated by the following approximations: N has $(2n)^k$ legal moves, with $\frac{2^{2n}}{2}$ legal positions it could end up at (parity gives $\frac12$). Similarly, M has $n^k$ legal moves, with $\frac{2^n}{2}$ legal positions it could end up at. Thus, as $k\to \infty$, the value of $\frac{N}{M}$ becomes \[\frac{N}{M} = \frac{\frac{(2n)^k}{2^{2n-1}} }{\frac{n^k}{2^{n-1}}} = \frac{2^k}{2^n}\]at which point we go look for a bijection

I will prove that $\frac{N}{M} = 2^{k-n}$. Let the first condition be called $X$ and the second condition be called $Y$. Also, define a sequence to have $x$ terms matching with another sequence if there exists exactly $x$ steps for each sequences where the same lamp is switched. For example, the sequences $\{1, 1, 2, 1\}$ and $\{1, 2, 2, 1\}$ have $3$ matching terms. Lemma: For odd $m$, $\binom{m}{0}+\binom{m}{2}+\ldots+\binom{m}{m-1} = 2^{m-1}$. Proof: A simple induction and the fact that $\binom{m}{k}+\binom{m}{k+1} = \binom{m+1}{k+1}$, or just a simple symmetry. The mapping $P$ which maps lamps $i$ and $i+n$ or $i-n$ depending on which one is less than in the range $[0, 2n]$. For some sequence of steps $Z$ that satisfies $Y$, let $Z_i$ denote the number of times the lamp $i$ has been switched. I will prove that we can map $2^{k-n}$ sequence of steps that satisfy $X$ to each distinct $Z$. We will call this map $Q$. Consider the set of sequences $S$ that satisfy $X$ such that for each sequence $s \in S$, $s$ and $Z$ have at least $n$ matching terms that involve all the lamps labelled $1, 2, \ldots n$. We now consider a specific lamp $i \le n$ and notice that $Z_i$ must be odd. Our mapping $P$ maps this lamp to $i+n$. Notice that if we switch any $2k < Z_i$ of these lamps in the sequence with the lamps $i+n$, we end up with a sequence that satisfies $X$. Therefore, for each individual lamp $i$, the total number of ways to change the $Z_i$ terms in the sequence is $$\binom{Z_i}{0}+\binom{Z_i}{2}+\ldots+\binom{Z_i}{Z_i-1} = 2^{Z_i-1}.$$If we now consider all the lamps, the total number of ways we can switch all these terms in this way is $2^{\left({\sum_{i = 1}^n{Z_i}-n}\right)} = 2^{n-k}$ as desired. It is clear that this mapping $Q$ is bijective, so $\frac{N}{M} = 2^{k-n}$. Remarks: I left out some small details but the reader should be able to figure it out.

The answer is $2^{k-n}$. The solution is to construct a mapping from the first set of sequences to the second as follows: Let $M$ be a sequence of second type. Then for $i=1,\dots,n$ take some even number of steps steps where we toggled $i$ and turn them into toggling $i+n$ instead. We get some sequence of second kind $N$ and say that it is a modification of $M$ $\bullet$ It is clear that any sequence of the first kind is a modification of exactly one sequence of second kind. $\bullet$ We now count the opposite thing. Suppose that $M$ had $a_1$ toggles for $1$, $\dots$ , $a_n$ toggles for $n$. Then there are $2^{a_i-1}$ subsets of even size of the set of toggles of $i$ (since a set of odd cardinality has as many even subsets as it has odd subsets). So, there is a total of $\prod{2^{a_i-1}}=2^{k-n}$ ways to generate $N$ from $M$. Those two arguments establish the answer.

We claim the answer is $2^{k-n}$, and prove via strong induction. $M(n, k)$ counts the number of sequences where each term is $1, ..., n$ and occurs an odd number of times. $N(n, k)$ counts the number of sequences where each term is $1, ..., 2n$ and $1$ through $n$ occur an odd number of times, $n+1$ through $2n$ an even number. Hence \begin{align*} M(n, k) = \sum_{\substack{a_1 + ... + a_n = k \\ a_i \textrm{ odd}}} {k \choose a_1, ..., a_n}. \end{align*}\begin{align*} N(n, k) = \sum_{\substack{a_1 + ... + a_{2n} = k \\ a_i \textrm{ odd for } i \le n \\ a_i \textrm{ even for } i > n}} {k \choose a_1, ..., a_{2n}}. \end{align*} Claim 1: $\sum_{i \textrm{ even}} {r \choose i} = \sum_{i \textrm{ odd}} {r \choose i} = 2^{r-1}$. Proof: Consider the generating function $G(x) = (1 + x)^r$. $G(1) = E + O = 2^r$, and $G(-1) = E - O = 0$. Hence $E = O = \frac{2^r}{2} = 2^{r-1}$. $\square$ Base case: $n$ = 1. Then $M(1, k) = 1$ since all terms in the sequence must be 1. Furthermore $N(1, k) = \sum_{a_2 \textrm{ even}} {k \choose a_2} = 2^{k-1}$. Inductive step: Assume $N(n-1, j) = 2^{j-n+1}M(n-1, j)$ for $j \le k$. \begin{align*} M(n, k) &= \sum_{\substack{a_1 \textrm{ odd}}} \left[{k \choose a_1} M(n-1, k-a_1)\right] \\ N(n, k) &= \sum_{\substack{a_1 + ... + a_{2n} = k \\ a_i \textrm{ odd for } i \le n \\ a_i \textrm{ even for } i > n}} {k \choose a_1} {k-a_1 \choose a_{2n}} {k - a_1 - a_{2n} \choose a_2, ..., a_{2n-1}} \\ &= \sum_{\substack{a_1 + a_{2n} = \lambda \\ a_1 \textrm{ odd} \\ a_{2n} \textrm{ even}}} \left[{k \choose a_1} {k - a_1 \choose a_{2n}} \sum_{\substack{a_2 + ... + a_{2n-1} = k - \lambda \\ a_i \textrm{ odd for } i \le n \\ a_i \textrm{ even for } i > n}} {k - \lambda \choose a_2, ..., a_{2n-1}}\right] \\ &= \sum_{\substack{a_1 + a_{2n} = \lambda \\ a_1 \textrm{ odd} \\ a_{2n} \textrm{ even}}} \left[{k \choose \lambda} {k - \lambda \choose a_1} N(n-1, k-\lambda) \right] \\ &= \sum_{\substack{a_1 + a_{2n} = \lambda \\ a_1 \textrm{ odd} \\ a_{2n} \textrm{ even}}} \left[{k \choose \lambda} {k - \lambda \choose a_1} 2^{k - \lambda - n + 1} M(n-1, k-\lambda) \right] \\ &= \sum_{\substack{\lambda \textrm{ odd}}} {k \choose \lambda} \sum_{a_1 \textrm{ odd}} \left[ {\lambda \choose a_1} 2^{k - \lambda - n + 1} M(n-1, k-\lambda)\right] \\ &= \sum_{\substack{\lambda \textrm{ odd}}} \left[{k \choose \lambda} 2^{k - \lambda - n + 1} M(n-1, k-\lambda) \sum_{a_1 \textrm{ odd}} {\lambda \choose a_1}\right] \\ &= \sum_{\substack{\lambda \textrm{ odd}}} \left[{k \choose \lambda} 2^{k - \lambda - n + 1} M(n-1, k-\lambda) 2^{\lambda - 1}\right] \\ &= 2^{k - n} \sum_{\substack{\lambda \textrm{ odd}}} \left[{k \choose \lambda} M(n-1, k-\lambda)\right] = 2^{k-n}M(n, k) \end{align*}where ${k \choose a_1} {k - a_1 \choose a_{2n}} = {k \choose \lambda} {\lambda \choose a_1}$ because both count the number of ways to choose $a_1$ to be 1 and $a_{2n}$ to be $2n$, in the left by choosing 1 then $2n$ and in the right by choosing those to be either first then choosing those to be 1. Furthermore $2 | k - n \iff 2 | (k-\lambda) - (n-1)$.

We claim that the answer is $2^{k-n}.$ Consider a sequence that satisfies the second condition. It must have switched the first $n$ lamps each an odd number of times, and the last $n$ lamps none. Let $a_i$ denote the number of times the $i$th lamp was switched in this sequence. We will construct a set of sequences that satisfies the first condition from this sequence. Suppose that some of the swaps of the $i$th lamp are moved to the $n+i$th lamp, such that the number of swaps of the $i$th lamp remains odd. There are $2^{a_i-1}$ ways to do this (since exactly half of the ways results in the $i$th lamp staying odd), so the number of sequences generated from this is $$\prod_{i=1}^n 2^{a_i-1}=2^{\sum_{i=1}^n a_i-1}=2^{k-n}.$$Obviously, each of these sequences satisfies the first condition (as we moved an even number to each of the later lamps). For a sequence that satisfies the first condition, the swaps on the later lamps can be moved back to the earlier lamps to form a sequence that satisfies the second condition, so all sequences that satisfies the first condition can be generated in this way, so we are done.

This generating functions solution is absolutely insane. Let $S$ be the set of all $2n$-tuples $(a_1, a_2, \dots, a_{2n})$ such that $a_1+a_2+\cdots+a_{2n} = k$ with $a_1, a_2, \dots, a_n$ odd and the rest even. Observe that this is the $X^k$ coefficient in the generating function \begin{align*} f(X) &= \sum_{(a_1, a_2, \cdots, a_{2n}) \in S} \frac{k!}{a_1a_2\cdots a_{2n}!} \\ &=k! \prod_{i=1}^{n} \left(\sum_{a_i \geq 0 \text { odd}} \frac 1{a_i!}X^{a_i}\right)\prod_{i=n+1}^{2n} \left(\sum_{a_i \geq 0 \text{ even}} \frac 1{a_i!}X^{a_i}\right) \\ &= k! \left(\frac{e^X - e^{-X}}2\right)^n\left(\frac{e^X + e^{-X}}2\right)^n \\ &= \left(\frac{e^{2X} -e^{-2X}}2\right)^n \cdot \frac 1{2^n}. \end{align*}Similarly, the generating function $g(X)$ for $M$ is $\left(\frac{e^X - e^{-X}}2\right)^n$. Thus $f(X) = g(2X)$, so the desired coefficient is that of $X^k$ in $\frac{f(2X)}{f(X)} \cdot \frac 1{2^n} = 2^{k-n}$ because all other terms cancel out.

Suppose $2a_1+1$, $2a_2+2$, $\dots$, $2a_{n}+1$, $2a_{n+1}$, $2a_{n+2}$, $\dots$, $2a_{2n}$ be the number of times we switched the state of lamps $1$, $2$, $\dots$, $2n$ respectively. Note that for each sequence in $M$, we can construct some amount of sequences in $N$ by taking an even number of moves on lamp $a_i$ and converting it to moves on lamp $a_{i+n}$ for $i=1$, $2$, $\dots$, $n$. Thus, for each sequence in $M$ we can use this method to construct \[\prod_{i=1}^{n}{\sum_{j=0}^{a_i}{\binom{2a_i-1}{2j}}}=\prod_{i=1}^{n}{2^{2a_1-2}}=2^{k-n}\]different sequences $N$. Now, to prove that each sequence $N$ can only be obtained from one $M$: note that the sum of number of switches of lamps $i$ and $n+i$ must stay constant using this method. Therefore, only one possible $M$ in which lamp $n+i$ is never switched. We have constructed a $1$ to $2^{k-n}$ correspondence; the answer is $2^{k-n}$.

The answer is $2^{k-n}$. Call a sequence for the $M$ case, $x$, and that for $N$, $y$. Consider each sequence as a string of length $k$ of integers from $1$ to $2n$ representing the lights switched on those steps. We will prove a claim that immediately finishes. Claim. We can map every $x$ to some $y$ such that each $y$ gets mapped to $2^{k-n}$ times. Proof. This mapping is changing every integer greater than $n$ to the integer $n$ less than it. It suffices to show that each $y$ gets mapped to $2^{k-n}$ times, and this is easy: for each integer from $1$ to $n$, say WLOG $1$, which occurs $a$ times, there are $2^{a-1}$ ways to change an even number of them to $n+1$. $\blacksquare$

We claim the answer is $\boxed{2^{n-k}}$ by showing that each sequence counted by $M$ can be corresponded with $2^{n-k}$ sequences counted by $N$. Simply use the transformation $\ell \mapsto n+\ell$, which gives each sequence counted in $N$ a unique image counted in $M$. We then compute that each sequence counted in $M$ has \[\sum_{y_1, \ldots, y_n \ge 0} \binom{x_1}{2y_1} \cdots \binom{x_n}{2y_n} = \prod_{i=1}^n 2^{x_i-1} = 2^{k-n}\] pre-images counted in $N$, where $x_i$ represents the frequency of $i$ in $N$. $\blacksquare$

The answer is $2^{k-n}.$ To show this, consider a sequence of toggles which results in a valid element of $M.$ Assume that, for $1 \le i \le n,$ the light has been toggled $2a_{i}+1$ times. Then, consider taking some even number of our $2a_{i}+1$ and transferring it to the $n+i$ light. There are $2^{2a_{i}}$ ways to do this. So, we get $$\prod_{i=1}^{n} 2^{2a_{i}} = \prod_{i=1}^{n} \frac{2^{2a_{i}}}{2} = \frac{2^{k}}{2^{n}}$$ways to make an element of $M$ an element of $N.$ Notice that, to go back from an element of $N$ to an element of $M,$ we simple take the number of toggles of the $i$th light to be the sum of the number of toggles of the $i$-th and $n+i$-th lights in the element of $N$. Thus, we get $2^{k-n},$ as desired.

Oops i did the genfunc I claim the answer is $\boxed{2^{k-n}}$. The generating function for $N$ is $x_1x_2\dots x_n (\sum_{1 \leq i \leq 2n} x_i)^k$ and the generating function for $M$ is $x_1x_2 \dots x_n (\sum_{1 \leq i \leq n x_i})^k$. In particular we want the terms with even exponents which can be done by ROUF on both. Let $$\frac{\sum_{x_j = \pm 1} x_1x_2 \dots x_n (\sum_{1 \leq i \leq n} x_i)^k }{2^n}$$be the answer for $M$. Now the answer for $N$ is $$\frac{\sum_{x_j = \pm 1} x_1x_2 \dots x_n (x_1+x_2+\dots+x_{2n})^k}{2^{2n}}$$which we ideally want to express as a degree one expression in terms of $M$ which seems very annoying to compute. The key idea is to consider the pairs $(x_1, x_{n+1}), (x_2, x_{n+2}), \dots (x_n, x_{2n})$. If a term of our summation has differing signs inside a pair then we can immediately kill it by considering the term with the pair switched around. Hence, we need only compute the terms in which all of the pairs are the same. Hence $$N = \frac{\sum_{x_j = \pm 1, 1 \leq j \leq n} x_1x_2 \dots x_n (2(x_1+x_2+\dots + x_n))^k}{2^{2n}} = \frac{2^k M \cdot 2^n}{2^{2n}}$$Dividing gives the desired answer.