分类集及极大分类集的计数

Ｍ是（１，２，…，ｎ）的一些子集合的集合。若Ｍ中任意两个子集，或者它们无共同元素，或者一个是另一个的子集，这样的Ｍ称为分类集。若不存在（１，２，…，ｎ）的一个分类集包含Ｍ，称Ｍ为极大分类集。给出分类集及极大分类集个数ｔｎ及Ｔｎ的计算，并由Ｔｎ的两个递推关系式得到一些组合恒等式。

ENUMERATION OF CERTAIN SETS OF PERMUTATIONS

Ⅰ. INTRODUCTION Let Zn = {1, 2, …, n}, and Pn be the set of n. permutations π = a1a2…an of Zn.We define the following conditions （ⅰ）—（ⅲ）:

某些排列集合的计数问题

令Zn={1,2,…,n},Pn是Zn的n.个排列π=a1a2…an的集合.今定义排列π的三个条件: （ⅰ）对1≤i<n,πi=a1a2…ai不是Zi的排列,或者说; （ⅱ）对1≤i<n,ai+1≠ai+1; （ⅲ）对1≤i<n,ai+1≠ai-1. 令Cn是满足条件（ⅰ）的所有排列的集合;Gn是满足条件（ⅰ）、（ⅱ）的所有排列的集合;G′n是满足条件（ⅰ）、（ⅲ）的所有排列的集合;Hn是满足条件（ⅰ）、（ⅱ）、（ⅲ）的所有排列的集合。