I have a little bit of a complex question and I don't know anything about combinatorics, but I'm working on software problem and I'm trying to figure out how my algorithm will scale. I'm having to ask a question like the following, and it has two parts:
Part one:
If I've got n objects, how many different way can I take combinations of those objects? For example:
In a set A and B, I could take:
1) A
2) B
3) A and B
In a set A, B, and C, I could take:
1) A
2) B
3) C
4) A and B
5) A and C
6) C and B
7) A, B and C
Part two:
In addition, if I take those subsets, how many different ways can they link up to the other remaining objects, for example, allowed links would be:
A and B <-> C
A <-> C
A <-> B
A <-> B and C
But not:
A <-> A and C
The first part is easier, but I don't know where to start for the second. Basically, as n scales to infinity, how does the complexity of the subsets and links with remaining block scale (big-O, worst case scenario)? Also, is it possible to find the expected average of links or some sort of profile for the for the graph?
EDIT
Firstly, many thanks for the help.
I'll try to clerify the second part:
Biderectional links are between the new "objects". These new objects are created from either the original objects or groups, i.e. for set {A,B,C}, (A) is an "object" in this case and so is (B,C).
An object cannot be on both sides of the link, but does not necessarily have to be on either side (it can be a bistander). All combinations of links for a 3 object set {A,B,C} are the following:
(A) <-> (B) [note: C is a bystander]
(A) <-> (C) [note: B is a bystander]
(A) <-> (B,C)
(B) <-> (A) [note: C is a bystander]
(B) <-> (C) [note: A is a bystander]
(B) <-> (A,C)
(C) <-> (A) [note: B is a bystander]
(C) <-> (B) [note: A is a bystander]
(C) <-> (A,B)
What would NOT be valid, however, is a link like this:
(A) <-> (A,B)
since A cannot link to itself. An object cannot be on both sides of the link.
This would get more complex for 4 objects since valid links would look something like this:
(A,B) <-> (C,D)
(A) <-> (B,C,D)
(A) <-> (C,D) [note: B is a bystander]
... and many more
again, an example of an INVALID link would be:
(B,C) <-> (A,C)
because in this case, C is on both sides of the link. (A)
Let me first treat part one, since this is the easiest part
Part 1: the number of subsets of a given set $X$ is $2^{|X|}-1$, where $|X|$ is the number of elements in $X$. I had to substract the $1$ because you are not interested in the empty subset $\emptyset$. A way to see why this is the number of options is the following: consider a set of $|X|$ slots, with a slot for each of the elements of your set $X$. To make subsets, you can either put the corresponding element in the slot or leave it empty. Therefore we have $|X|$ slots which can all be in two states: filled or empty. The total number of options is $2^{|X|}$, but since you do not want to consider the case with all slots empty, the answer is $2^{|X|}-1$.
Part 2: The second part is indeed a lot more complicated. Luckily the situation is not as complicated as it could have been, since you seem to be assuming from the start that all the objects in the set $X$ are distinct. Links are always between subsets that have distinct elements and if $Y,Z$ are subsets of $X$, $Y\cup Z$ is also a subset of $X$ and it has to have at least $2$ elements. We can make use of this fact to count the number of possible links:
Given a subset $Y$ with cardinality $|Y|$, we can try to find all the ways to split it into two groups. This is given by the formula $$ N(|Y|)= \sum_{j=1}^{|Y|-1} {|Y|\choose j} = 2^{|Y|}-2, $$ where I have used the usual "choose" symbol. We are simply choosing a subset of $Y$ with at least $1$ element not being the whole of $Y$, which then is the first group. The remaining elements form the second group. So given $Y$, $N(|Y|)$ is the number of ways we can make a link between two parts of $Y$ such that their union is $Y$. Notice that for 2 subsets $Y,Z\subseteq X$ the links that are considered for $Y$ are all different from the ones considered for $Z$ if $Y\neq Z$. Therefore all we need to do now is to sum over all possible subsets of $X$ with at least $2$ elements. This is given by $$ \sum_{n=2}^{|X|} {|X| \choose n} N(n) = \sum_{n=2}^{|X|} {|X| \choose n} \left(2^n-2\right) = 3^{|X|}-2|X|-1 -2\left(2^{|X|}-1-|X|\right) = \\ 3^{|X|}-2^{|X|+1}+1. $$ This is the total number of possible links between subsets of $X$, which I think is what you were looking for.