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

  • $\begingroup$ I think for (i) you can try inclusion-exclusion principle and count the sets with at least one neighbor connected with the nearest, at least two etc. Then you will subtract this number from $N!!$ $\endgroup$ – Lada Dudnikova Apr 17 at 19:50
  • $\begingroup$ @LadaDudnikova Can you please elaborate this? $\endgroup$ – user135580 Apr 17 at 19:57

(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)!! $$

  • $\begingroup$ For case one, I tried to apply for $N=6$ sites, I got totally 5 different ways of doing this. However, the formula mentioned above giving me 6. I couldn't get, please explain $\endgroup$ – user135580 Apr 18 at 5:12
  • 1
    $\begingroup$ @user135580 Hi, I realize what the problem is. If you take the convention that $(-1)!!=1$, then the formula works correctly, otherwise it is off by one. For example, with $n=6$, the result is$$\binom{6}05!!-\binom{5}13!!+\binom{4}21!!-\binom{3}3(-1)!!=1\cdot 15-5\cdot 3+6\cdot 1-1\cdot 1=5.$$It certainly seems weird to define $(-1)!!=1$, but this is not an uncommon convention. $\endgroup$ – Mike Earnest Apr 18 at 22:27

Let me point out the same thing I said on ResearchGate answering the same question:

Actually, both of these problems have an entry in the OEIS.

In the first problem, you are looking for the number of perfect matchings in K_n minus a path, given in the integer sequence A302750 (actually they treat maximum matchings so there are entries for odd n that you might want to ignore).

In the second problem you are looking for the total number of matchings in this same graph given by A170941.


https://oeis.org/A302750, https://oeis.org/A170941



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.