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

[Steven Ellet]

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.

 

[mfb]

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?

 

[sysprog]

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.

 

[sysprog]

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.

 

[fresh_42]

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.

 

[mathman]

I must be missing something. 48?

 

[hutchphd]

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?)

I must be missing something. 48?

 

[nuuskur]

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 2^{mn}. But some of them would be isomorphic and at this point it gets hairy.

 

[sysprog]

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 2^{mn}. 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.

 

[nuuskur]

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.

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.

 

[sysprog]

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.

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.

 

[mfb]

Maybe we should wait for @Steven Ellet to clarify the question as all this is speculation for now.

 

[Steven Ellet]

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.

 

[sysprog]

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"?

 

[mfb]

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 2^x*y possible sets of lines if each line can be either on or off.