正整数n人集合中无三元团与独立集的友谊关系计数问题（n<6）

嘿，这个问题其实对应图论里的经典Ramsey数相关场景——我们可以把人与人的友谊关系建模成简单无向图：每个人是图的顶点，两个人是朋友就对应顶点间有一条边，非朋友则无边。你提到的“既无三元团（两两互为朋友的三人组）也无独立三元集（两两均非朋友的三人组）”，就是要找不含三角形且不含大小为3的独立集的图。已知Ramsey数R(3,3)=6，所以n≥6时确实没有这样的图，数量为0。下面我们逐个计算n=1到5的情况：

只有1个人，不存在任何友谊关系的可能，满足条件的关系只有1种（空关系）。

两个人的友谊关系只有两种可能：是朋友，或者不是朋友。由于凑不出三个人，这两种情况都不会形成三元团或独立三元集，所以满足条件的关系数量是2种。

总共有2^(C(3,2))=8种可能的友谊关系（C(3,2)是3个人中选2对的组合数）。我们需要排除两种不符合条件的情况：

• 三人两两都是朋友（三元团）：1种
• 三人两两都不是朋友（独立三元集）：1种

剩下的8-2=6种关系都满足条件，具体是：恰好有1条友谊（3种），或者恰好有2条友谊（3种）。所以数量是6种。

我们需要找无三角形且无3独立集的4点标记图，通过枚举和容斥原理计算，满足条件的关系有三类：

1. 两个不相邻的友谊（2边匹配）：把4人分成两对朋友，分法有3种
2. 4人连成一条链（路径图P4）：标记数为12种（4个点的无向路径，排除方向重复后的排列数）
3. 完全二分图K2,2：把4人分成两组，组内无友谊、组间全是友谊，分法有3种

三类加起来3+12+3=18种，所以满足条件的关系数量是18种。

n=5时，唯一满足条件的图结构是5点环（C5）：每个人恰好和另外两个人是朋友，形成一个闭合的环。这种图既没有三角形（任意三个点中最多有两对朋友），也没有3独立集（任意三个点中至少有一对朋友）。

5点环的标记图数量计算：无向环的标记数为(n-1)!/2，n=5时即4!/2=12种。另外，C5的补图和自身同构（补图也是一个5点环），不需要额外计数。所以满足条件的关系数量是12种。

内容的提问来源于stack exchange，提问作者oobarbazanoo