Looking for a formula (how many possible connections between 2 sets of objects?)

In summary: I am not at all convinced by those arguments, and I am inclined to disregard them as they are not convincing at all, but I think that is not a good idea.In summary, the conversation is discussing a formula for calculating the number of possible connections between two sets of objects. The formula given is ##2^{n\cdot m}##, where ##n## is the number of nodes on one side and ##m## is the number of nodes on the other side. The conversation also touches on the concept of isomorphism and the importance of labeling when considering different configurations.
  • #1
Steven Ellet
85
3
I am looking for a formula that will them me how many possible connections between 2 sets of objects.
Ex: 12 on left and 4 on right, how many possible states can it be in?
state one: top on left connected to top on right
state two: top on left connected to 2 on right
state three: top on left connected to top on right and 2 on right
state four: etc.
WIN_20200801_17_28_38_Pro.jpg
 
Last edited by a moderator:
Mathematics news on Phys.org
  • #2
Each of the 4 dots on the left has 4 connections and there are 12 of them. Am I missing something or is it that simple?
 
  • Like
Likes berkeman
  • #3
If I'm interpreting the question correctly, then for each node on the left, the number of connection possibilities for the nodes on the right (including not connected at all) is the number of subsets (including the empty set) of the nodes on the right, and the number of subsets in a set is ##2^n## (where ##n## is the number of members in the set), so the formula for all the possible connection nets would be: ##\text{left-nodes}^{(2^\text {right-nodes})} ##. In the example, that would be: ##12^{(2^4)}=12^{16}=184.884,258,895,036,000##.

Edit: Oops ##-##I said ##12^{16}## when I should have said ##16^{12}##. Please see post #5.
 
Last edited:
  • #4
Oops ##-##I said ##12^{16}## when I should have said ##16^{12}##. In the example there is a 12 digit hexadecimal number of possible configurations; not a 16 digit duodecimal number of possibilities. The correct formula would be ##(2^{\text {right-nodes}})^{\text {left-nodes}} = (2^4)^{12} =16^{12}= 2^{48}=281,474,976,710,656##.

With 4 nodes on the right, there are 16 possible connection patterns (right mode subsets) for each of the 12 nodes on the left: {empty}, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, and {1, 2, 3, 4}.

Each of the 12 nodes on the left has 4 connected or disconnected paths to the nodes on the right, and each of the 4 nodes on the right has 12 connected or disconnected paths to the nodes on the left, so there are 48 paths, each of which can be connected or disconnected, which means ##2^{48}## possible configurations.
 
Last edited by a moderator:
  • #5
I'm really bad at counting so I made a mistake and withdrew my previous post.

In order to get ##2^{n\cdot m}=2^{48}## possibilities, we need to label each edge from ##1## to ##48##. There will be less if the vertices on each side are indistinguishable, ##\binom{12}{5}## or so, number of vertices on the left having each ##0,1,2,3## or ##4## connections to any of the left.
 
  • #6
I must be missing something. 48?
 
  • #7
Steven Ellet said:
I am looking for a formula that will them me how many possible connections between 2 sets of objects.
Are you really asking how many lines there are on the picture (or similar pictures?)
mathman said:
I must be missing something. 48?
 
  • #8
My guess is, the question is how many ways there are to connect the nodes without there being edges between nodes of the same "part". It's a bipartite graph. For every edge it's either in the graph or not so it's got to be [itex]2^{mn}[/itex]. But some of them would be isomorphic and at this point it gets hairy.
 
Last edited:
  • #9
nuuskur said:
My guess is, the question is how many ways there are to connect the nodes without there being edges between nodes of the same "part". It's a bipartite graph. For every edge either in the graph or not so it's got to be [itex]2^{mn}[/itex]. But some of them would be isomorphic and at this point it gets hairy.
Each of the ##2^{48}## possible node-to-node connection configurations is a unique adjacency subset, just as the numbers ##0## to ##(2^{48}##-##1)## are, so there can be no bijective function between any two of them that preserves the adjacencies, wherefore by definition none of them could be isomorphic to any of the others ##-## each such configuration varies from every other by at least one node-to-node connected-or-not condition and so cannot be isomorphic to any other. For some configurations, isomorphisms could be created within the configuration by changing the crossing pattern of the edges; however, such changes would not affect the number of configurations.
 
Last edited:
  • #10
With [itex]|L|=2[/itex] and [itex]|R| =1[/itex] there are three non-isomorphic configurations, not four. The two 1-edge configurations are isomorphic. As I said, it gets hairy when the parts become larger.
sysprog said:
Each of the ##2^{48}## possible node-to-node connection configurations is a unique adjacency subset
Unique up to labelling. I understand that as set theoretic objects (relations), they are pairwise different. Formally different graphs can still be isomorphic.

I did some scouting. Even in the quite simple cases, the process becomes very.. involved. The general case is an open problem.
 
Last edited:
  • Like
Likes sysprog
  • #11
nuuskur said:
With |L|=2 and |R|=1 there are three non-isomorphic configurations, not four. The two 1-edge configurations are isomorphic. As I said, it gets hairy when the parts become larger.
sysprog said:
Each of the ##2^{48}## possible node-to-node connection configurations is a unique adjacency subset
Unique up to labelling. I understand that as set theoretic objects, they are pairwise different.

I did some scouting. Even in the quite simple cases, the process becomes very.. involved.
The configuration [R1##\leftrightarrow##L1 L2] is not isomorphic to [R1##\leftrightarrow##L2 L1], because the adjacencies are not the same. From a graph-theoretic perspective, I am by that assertion restricting isomorphism in this context to automorphism, which is equivalent to disallowing relabeling in the determination of isomorphicity, which is in this context justified by the fact that, as you put it:
. . . the question is how many ways there are to connect the nodes without there being edges between nodes of the same "part".
Also, I am viewing each configuration as inclusive of all 12+4 nodes, whether connected or not.

I have a practical bias in that when a client asks me to rewire a network patch bay to eliminate 'spaghetti' cabling, if the protocol or service to or from one node is not always the same as that to or from another (e.g. the PSERVIC value for Jack's GDDM terminal differs from that for Jill's 3270 Mod 5 terminal), I make sure to physically attach a unique label to each end of each cable (as remarked upon by @fresh_42 above), along with connection node labels at each end, and to log each of the connections in a mapping file, whereupon I can assert that the new tidy cable bundles are 'isomorphic' (by which I would in this context mean functionally equivalent) to their predecessor 'spaghetti' version ##-## in point of fact, they are the automorphic species of isomorphic, but I don't make that distinction in such a context ##-## if I'm then asked to 'clone' the configuration e.g. at a disaster recovery site, I can replicate the configuration, and it will be node-for-node edge-for-edge isomorphic to its also-tidily-bundled predecessor, but the cable crossings will probably differ.​

I looked briefly at your 'involved' link ##-## yep ##-## you called it. 🤔
 
Last edited:
  • Like
Likes nuuskur
  • #12
Maybe we should wait for @Steven Ellet to clarify the question as all this is speculation for now.
 
  • #13
These are examples of potential connections. The number of circles on the left and right can be changed. I am looking for a formula where x=left and y=right making z=total number of possible outcomes.

WIN_20200803_18_51_51_Pro.jpg
WIN_20200803_18_51_50_Pro.jpg
WIN_20200803_18_51_48_Pro.jpg
WIN_20200803_18_51_43_Pro.jpg
WIN_20200803_18_51_40_Pro.jpg
 
Last edited:
  • Like
Likes sysprog
  • #14
Steven Ellet said:
These are examples of potential connections. The number of circles on the left and right can be changed. I am looking for a formula where x=left and y=right making z=total number of possible outcomes.

View attachment 267252View attachment 267253View attachment 267254https://www.physicsforums.com/attachments/267255View attachment 267256View attachment 267257
Your question has inspired some interesting digressions; however, I think that at this point the consensus is clear: the number of possibilities, in accordance with the ##x##, ##y##, and ##z## format suggested in your post, is ##z=2^{(x \times y)}##, based on 2 states (connected or not connected) to the power of 'the number of circles on the left times the number of circles on the right' being the number of possible arrangements of left-circle-to-right-circle connected or not connected conditions ##-## I, and perhaps others, would be interested to learn: "what's this inquiry for"?
 
  • #15
Steven Ellet said:
These are examples of potential connections.
Is a single connection a single line, or a given set of lines?

There are x*y possible individual lines and 2x*y possible sets of lines if each line can be either on or off.
 
  • Like
Likes sysprog

Related to Looking for a formula (how many possible connections between 2 sets of objects?)

1. How do you determine the number of possible connections between two sets of objects?

The number of possible connections between two sets of objects can be determined using the formula nm, where n represents the number of objects in one set and m represents the number of objects in the other set. This formula assumes that each object in one set can be connected to any object in the other set.

2. Can the number of possible connections be greater than the number of objects in either set?

Yes, the number of possible connections can be greater than the number of objects in either set. This is because the formula nm takes into account all possible combinations of connections between the two sets, even if some connections may be repeated.

3. How does the number of possible connections change if the sets have different sizes?

If the sets have different sizes, the number of possible connections will still be determined by the formula nm. However, the total number of connections may be limited by the smaller set, as it will have fewer objects to connect to.

4. Can the number of possible connections be negative?

No, the number of possible connections cannot be negative. The formula nm only produces positive values, as it represents the total number of potential connections between two sets.

5. Are there any other factors that can affect the number of possible connections between two sets?

Yes, there are other factors that can affect the number of possible connections between two sets. For example, if the objects in the sets are not distinguishable, the number of possible connections may be reduced. Additionally, if there are any restrictions or limitations on the connections between the sets, the number of possible connections may also be affected.

Similar threads

Replies
2
Views
437
  • General Math
2
Replies
45
Views
3K
  • General Math
Replies
8
Views
1K
Replies
7
Views
1K
Replies
3
Views
1K
Replies
2
Views
655
Replies
9
Views
2K
Replies
3
Views
394
Replies
6
Views
1K
Replies
17
Views
3K
Back
Top