Dear Vigneshwaran Kannan ,

Is your lattice a line with N vertices?

And you want to connect them by forwarding paths? To make your question is clear. Assume that your lattice includes 4 vertices.

Sketch some graph, then attach it as a pdf file. Then we may help.

Best regards

Dear Vigneshwaran Kannan ,

Is your lattice a line with N vertices?

And you want to connect them by forwarding paths? To make your question is clear. Assume that your lattice includes 4 vertices.

Sketch some graph, then attach it as a pdf file. Then we may help.

Best regards

Issam Kaddoura I have attached for 4 lattice points on a line. It has one and only way to connect via wires. If I have more , how do I do that?

Dear Vigneshwaran Kannan ,

It is not clear from your conditions if the attached case included or not !!

Did you want that each vertex can join exactly one other vertex?

A1 and A4 cannot be included as it will lead to the connection of A3 and A2 which are nearest neighbor Issam Kaddoura .

Ok Vigneshwaran Kannan

Can we consider it as an electric flow, where the neighbor vertices should be isolated? And each node should be connected to only one node. If the number of nodes is 4, then your graph has only one possibility. Can you add another graph with more vertices and show how the possibilities of the connections they are. (This will help to understand your request exactly). Next, we tackle the general case.

Vigneshwaran Kannan Do I understand your problem correctly when I restate it in the following way?

(i) Find the number of partitions of {1,...,2n} into n sets of size 2, that do not consist of consecutive numbers.

(ii) Find the number of partitions of subsets of {1,...,n} into sets of size 2, that do not consist of consecutive numbers.

Or may it be possible (other than in the sketched solution in the first paragraph) that a point on your line is connected to more than one other point?

Felix Schröder You are right. we have to make that. I think we have to use inclusion /exclusion principle. I dont know how to use it.

Dear Vigneshwaran Kannan ,

If you agree with Felix Schröder formulation to your question.

Then the answer is

Case 1. If the number of vertices is 2N, then number of all possible connections

is (N-1)2 .

Case2. If the number of the Vertices is odd 2N - 1, then the number of connections is (2N-1)(N-2)2 , where one node remains free without any connection to satisfy your request.

Best regards

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.

Issam Kaddoura Your result is not the same as mine. Could you elaborate, where it comes from? Maybe we still have a somewhat different interpretation of the question.

Links:

https://oeis.org/A302750

https://oeis.org/A170941

Dear Felix Schröder ,

I agree with you; we still have a different interpretation of the question.  I checked the mentioned links, the structure of the problem there is not the same as what I assumed. I'm waiting for v. Kannan to show all possible connections for a lattice with at least 6 points.

Best regards

The numbers in proposed problem formulated as Problem (i) by Felix Schröder can be recursively “estimated” as follows.

Let a_n (n = 2, 3,…) denote the number of partitions of {1,...,2n} into n sets of size 2.

Obviously, a_2 =1. Moreover, by induction on n, it can be proved that

a_(n +1) ≥ (2n -1)a_n, for all n = 1, 2,....

Hence, a_n ≥ 1∙3∙∙∙(2n -1),

which is for n ≥ 3, greater than (n -1)^2, as asserted by Issam Kaddoura!?

(For example, if n = 3, then a_5 = 5, since the all required partitions of

{1, 2, 3, 4, 5, 6} (written in pairs) are (13)(25)(46), (14)(25)(36), (14)(26)(35),

(15)(24)(36) and (16)(24)(35), which is greater than (3 -1)^2 = 4)!

Romeo Meštrović ,

I don't like your style of following my answers.

(*) I answered your question about primes in other thread:

Dear Issam Kaddoura,

1) The author of the proposed problem Vigneshwaran Kannan wrote “Felix Schröder You are right. we have to make that. I think we have to use inclusion /exclusion principle. I dont know how to use it.”.

In view of this answer, I have discussed the problem (i) precisely formulated by Felix Schröder. I do not know what problem you are doing. Namely, I tried to solve the problem by induction and using the inclusion/exclusion principle, but I did not succeed.

2) I have recommended your answer concerning a contradiction for my question about commuting matrices. Moreover, I have discussed this your contradiction

together with Peter Breuer, where you were not involved!?

3) I have not responded to your solution of my Diophantine equation x^3+y^3+z^3=p+3xyz because you did not indicate the result/theorem on which there are infinitely many prime numbers written as the quadratic form/polynomial P(x ,y,1- x - y) = 3(xy - y - x + x² + y²)+1 given in your answer.

Accordingly, I agree with your sentence: “We share knowledge and answers to help if possible, with full respect and appreciation to each other!”

Thank you everyone for your input. For the six lattice points I have got 5 different possibilities of pairint which ignores the nearest neighbor connection All the lattice points are with one and only other lattice point and none of the lattice points remain unconnected.For 8 lattice points I have got 36 ways of pairing. By the way I considered only even number of lattice points. By the way, I posted a similar question in Math stack exchange and got a reply.However, I am really finding it hard to understand the explanation that has been given Can someone help with this.?

https://math.stackexchange.com/questions/3191496/how-do-i-solve-this-combinatorics-problem-with-conditions/3191545?noredirect=1#comment6570767_3191545

Inclusion-Exclusion Principle works the following way: Suppose you have a ground set X, where some elements have some property 1, let's say all elements in the set A_1. For properties 2 to n you get the sets A_2 to A_n. In your case, X is the set of (perfect) matchings of K_n and the properties are 1: the first two vertices of K_n (say 1 and 2) have a matching edge in the matching, up until property n-1, that the last two have a matching edge in the matching. Now the general formula for Inclusion-Exclusion principle is

|X\(A_1\cup ... \cup A_n)|=\sum_{I\subset [n]} (-1)^{|I|} |\bigcap_{i\in I} A_i|,

that is, the number of elements having none of the properties can be calculated using the number of elements having at least some subset of the properties. In this case, the different elements of the sum for the same cardinality of I are grouped together, taking k= |I| and summing over k.

In (i), for given k, the question is how many perfect matchings there are such that at least k edges are on the forbidden path (that is, between consecutive vertices). To count this number you first count the number of possibilities to choose k matchings on the path. For k>n/2, the sum becomes 0, as it is impossible to find a matching having more than n/2 edges. For other k, this number is precisely n-k choose k. Imagine choosing k elements of an n-k element set, then expanding the chosen elements to an edge that connects two adjacent elements. You get a matching of the path covering exactly 2k elements with n-2k (unchosen) elements remaining so the path has n vertices and the matching consists of exactly k edges. Coming from a k-element matching of an n-vertex path, contract the edges of the matching and color the contracted vertices differently than the non-contracted ones. You get a two-colored n-k-element set, where k elements have one color, the rest has the other color. So you get one possible choice of k elements from an n-k element set. This illustrates that there is a bijection between the k-element subsets of an n-k-element set and matchings of size k in an n-vertex path, i.e. the latter has the same number of elements as the former. Further, since we are talking about perfect matchings, we need to complete the matching that has k edges on the path. The number of perfect matchings on the rest of the graph, K_{n-2k}, is, as you already pointed out, (n-2k-1)!!. So the first formula follows:

|X\(A_1\cup ... \cup A_n)|=\sum_{k \in [\floor{n/2}]} (-1)^k {n-k choose k} (n-2k-1)!!

In (ii), almost the same arguments occur, but the number of possibilities to complete our matching is much higher, because we do not need to cover all the elements. The telephone numbers count the number of matchings of K_n. Basicly, you choose 2k elements to be covered by the matching, then apply your known formula of (2k-1)!! perfect matchings on these elements, obtaining:

#matchings of complete graph K_n=\sum_{k\in[\floor{n/2}]} {n choose 2k} (2k-1)!!

So instead of (n-2k-1)!! in our last formula, we now need this number to complete the formula:

|X\(A_1\cup ... \cup A_n)|=\sum_{k \in [\floor{n/2}]} (-1)^k {n-k choose k}\sum_{i\in[\floor{(n-2k)/2}]} {n-2k choose 2i} (2i-1)!!

Answer to case (i) https://oeis.org/A302750

Answer to case (ii) https://oeis.org/A170941

Dear Felix Schröder ,

It seems that Tapas Chatterjee agrees with your answer posted before 15 days.

So, he repeats the same mentioned sequences!

Is there any paper that shows the details?

Best regards

Dear Issam Kaddoura ,

The answer that OP got on Math-Stackexchange is quite good in explaining the solution. I am not aware of any paper on this.

Regards