OEIS A333017, or something else entirely?

Question

I am trying to find out how to calculate the number of different relationships there are between all the non-empty cliques that can be made of a given number 'n' of individuals.

Doing this manually (there may be a mistake),

Given a group of 2 people [A,B], I find 1 relation 
1 1:1 rels.: A-B

Given a group of 3 people [A,B,C], I find 6
3 1:1 rels.: A-B,  A-C,  B-C, 
3 1:2 rels.: A-BC, B-AC, C-AB

Given a group of 4 people [A,B,C,D], I find 25
6  1:1 rels. (A-B ... C-D)
12 1:2 rels. (A-BC ... D-BC)
4  1:3 rels. (A-BCD, B-ACD ... D-ABC)
3  2:2 rels. (AB-CD, AC-BD, AD-BC)

Given a group of 5 people [A,B,C,D,E], I find 90
10 1:1 rels. (A-B ... D-E)
30 1:2 rels. (A-BC ... E-CD)
20 1:3 rels. (A-BCD ... E-BCD)
 5 1:4 rels. (A-BCDE ... E-ABCD)
15 2:2 rels. (AB-CD ... BE-CD)
10 2:3 rels. (AB-CDE ... DE-ABC)

OEIS A333017 seems to correspond with my calculations. Is my problem an analog of "twice the total area of all (open or closed) Deutsch paths of length n", or have I made a mistake in my numbers, or is this a novel sequence?

Answer 1

Your calculations are correct, but guessing that you have the OEIS sequence A333017 is premature. There are several matches, and the correct sequence is A000392, whose nonzero terms begin $1, 6, 25, 90, 301, 966, 3025, \dots$.

This sequence indicates that the number of "relations between two cliques" from a group of $n$ people is a Stirling number of the second kind: $$\left\{\!{n+1 \atop 3}\!\right\} = \frac{3^n - 2 \cdot 2^n + 1}{2}$$ Combinatorially, this counts the number of partitions of $\{1, 2, 3, \dots, n+1\}$ into $3$ nonempty groups. If we ignore the group containing $n+1$, we get two nonempty disjoint subsets of $\{1,2,\dots,n\}$, which are precisely the thing you're counting.

The formula I gave for $\left\{\!{n+1 \atop 3}\!\right\}$ comes from the inclusion-exclusion principle:

1. For each of the $n$ people, you have $3$ choices: the first clique, the second clique, or no clique. This gives us $3^n$ outcomes total.
2. There are $2^n$ outcomes in which the first clique is empty, and $2^n$ more where the second clique is empty. We don't want to count these, so we subtract $2 \cdot 2^n$.
3. There is $1$ overlapping outcome between the two cases in the previous point: the outcome where both cliques are empty. We add it back in, because we don't want to subtract it twice.
4. Switching the two nonempty cliques shouldn't produce a different outcome, so we divide by $2$.