Permutations for a set of rules The question is from - http://www.iarcs.org.in/inoi/2015/zio2015/zio2015-question-paper.pdf - Q.2
I tried solving it but I have no clue how to go about doing it.
The question says that a railway company occupied a new yard. Every train must enter the yard and leave it which happens when the yard manager gives the command 'enter' or 'leave'. The train leave in a first in last out manner.  There are N number of trains. The company requires that no train may wait at the yard for more than K instructions
Calculate the number of ways the yard manager can give the set of instruction.
For example if N=2 and K=0 then the only way to do it is enter,leave,enter,leave same if K=1
If k=2 then the other method possible is enter,enter,leave,leave
(a) N = 6 and K = 8.
(b) N = 8 and K = 4.
(c) N = 10 and K = 4.
 A: A general solution seems perhaps possible but not trivial. If you just want to solve those three cases without electronic aids, you can approach them individually.
The problem can be formulated as counting the number of strings with $N$ pairs of matching parentheses such that no parenthesis "stays open" longer than $K$.
(a) $N=6$, $K=8$. Here the $K$ constraint is rather weak; the only strings that violate it are the ones where the train that enters first leaves last. Thus the result here is the Catalan number $C_6$ of all strings with six pairs of matching parentheses minus the number $C_5$ that counts the ways in which the other $5$ trains can be instructed if the first one leaves last, yielding $C_6-C_5=132-42=90$.
(b) $N=8$, $K=4$ and (c) $N=10$, $K=4$. In both cases $K=4$, and for this case we can set up a manageable recurrence relation. Let $a_N$ be the desired numbers (for $K=4$), and consider the $N$-th train as the first in line. It can either enter and immediately leave, which leaves $a_{N-1}$ possibilities for the remaining $N-1$ trains. Or it can enter, then the second train enters, and then they both leave, which leaves $a_{N-2}$ possibilities for the remaining $N-2$ trains. Or it can enter, wait for two trains to enter and leave, and then leave. The two trains can enter and leave in $2$ different ways, and the remaining $N-3$ trains have $a_{N-3}$ possibilities. Thus, in total we have
$$a_N=a_{N-1}+a_{N-2}+2a_{N-3}$$
for $N\ge3$, with initial values $a_0=1$, $a_1=1$, $a_2=2$. The result is OEIS sequence A077947 (that page gives some interesting properties which might perhaps provide some indications for solving the general problem), and the desired values are $a_8=146$ and $a_{10}=585$. (I took them from the OEIS page but it would be easy enough to calculate them using the recurrence relation.)
