I have $N$ lattice points which are arranged linearly and equally spaced. I want to make connections(say with some wire or thread) with each lattice site with another. The first one has $N-1$ possibilities and the second one has $N-3$ as each one cannot make connections itself and the first one has already formed one. So the total possibility is $$(N-1)(N-3)(N-5)(N-7).....$$ and so on. Now I want to impose two conditions.
Case(i): If I impose a condition that each site cannot be connected with the nearest neighbor, how many ways I can make the connections. How do complete this counting problem with this condition?
Case(ii): Apart from the above condition(immediate neighbors should not be connected), If I impose a further condition that each site can be connected with other or it can also be left unconnected. How do I count the number of ways doing this?
I know both case(i) and case(ii) will have different answers. I really don't know where to start this problem at all
(i) can be solved with the principle of inclusion exclusion. Take all pairings, subtract the ones which include an adjacent pairs, then add back in the doubly subtracted pairings with two adjacent pairs, etc. The result is $$ \sum_{k=0}^{\lfloor n/2\rfloor }(-1)^k \binom{n-k}k (n-2k-1)!! $$ The $\binom{n-k}k$ counts the number of $k$-way intersections of the "bad" conditions where $k$ pairs of adjacent numbers are joined together. These correspond to tilings of a $1\times n$ rectangles with dominoes (adjacent pairs) and squares. For each of these tilings, the number of pairings where each adjacent pair corresponding to a domino is paired together is $(n-2k-1)!!$, which is just short hand for $(n-2k-1)(n-2k-3)(n-2k-5)\cdots$.
For (ii), let us first ignore the adjacency condition, and count arrangements where some but not necessarily all of the points are paired off. These are the telephone numbers, equal to $$ \sum_{k=0}^{\lfloor n/2\rfloor} \binom{n}{2k}(2k-1)!! $$ Combining this with the inclusion exclusion argument, the number of partial pairings with no adjacent pairs is $$ \sum_{k=0}^{\lfloor n/2\rfloor}(-1)^k\binom{n-k}k\sum_{j=0}^{\lfloor (n-2k)/2\rfloor} \binom{n-2k}{2j}(2j-1)!! $$