流互模拟方法解决计数问题：使用无限自动机，最小化被计数对象，统一解决计数问题

286理论计算机科学电子笔记65第1期（2002）URL：http://www.elsevier.nl/locate/entcs/volume 65. html19页s共感应计数：枚举组合学中的互模拟（扩展摘要）JJM RuttenCWI和阿姆斯特丹自由大学tten@cwi.nl摘要最近发展起来的流的共归纳演算在这里找到了计数组合学中的进一步应用。本文提出了一种通用的方法，以统一的方式解决各种基本计数问题：（1）用无限（加权）自动机计数被计数的对象，（2）用流互模拟的定量概念最小化自动机，（3）用流互模拟的方法最小化被计数的对象，（4）用流互模拟的方法最小化被计数的对象，（5）用流互模拟的方法最小化被计数的对象。(3)最小化自动机用于计算表示所有计数的流的表达式（根据流常数和运算符）1动机我们首先通过一个例子来说明共归纳计数的方法，然后在第2节中变得更加正式，然后我们继续更多的例子。下面的计数问题取自[6，p.291]。雄蜂被称为雄蜂，雌蜂被称为蜂后。雄蜂是由蜂后所生，没有父亲;蜂后是由雄蜂父亲和蜂后母亲所生。无人机谱系的前几个级别（颠倒绘制）如下：DssQ，ss sss，，QDcc，QDQ、、、cc，cc，QD Q QD每架无人机都有一个母亲，一个祖母，两个曾祖母，三个曾曾祖母，等等。对于任意k≥0，·2002年由ElsevierSc ie nceB出版。 V. 操作访问根据C CB Y-NC-N D许可证进行。吕滕287ZZk级的女性祖先的sk？共归纳计数的关键思想是使用枚举雄蜂的所有（女性）祖先的树，作为无限流σ =（s0，s1，s2，.的表示的基础。. ）包含所有答案。为此，树被转换成自动机，其中箭头指示转换，并且其中所有皇后状态都是输出状态：DJQQ，otc，，c，Dc，，zDJQc，QczJtczDQ QD这种自动机的流行为将被定义为共归纳的，并且可以用转换序列来表示。在本自动机中，数字sk被编码为从初始（最顶部）雄蜂状态到输出女王状态的长度为k的路径的数量，因为存在 这样的序列的数量与级别k处的皇后的数量一样多。因此，我们已经将原来的计数问题转化为关于流及其自动机表示的问题，从而进入流演算的共归纳世界[7]。流演算的一个重要组成部分是流互模拟的概念，借助它，上述自动机可以通过识别所有等价状态来简化，如下所示。每个无人机状态都相当于状态q0和每个皇后状态与以下两个状态自动机的状态q1q0，，zq1，s直觉上，任何皇后状态和状态q1都有相同的转换条件：两者都可以经过两次转换，再分别转换到等价的状态。类似地对于drone状态和q0，它们只有一个转变。因此，这个新的自动机（的状态q0）是我们的答案流σ的等价表示：sk再次对应于从q0到（仅在这种情况下）输出状态的长度为kq1.一个经典的和方便的方式来捕捉有限序列的手段，一个单一的表达，是使用生成函数，或更一般地说，形式幂级数在流演算中，由状态q 0表示的无限答案流σ的这种Xσ=1−X−X2可以说，这个表达式对所有k≥0的数sk进行编码，Q吕滕288其可以被检索为第k个流导数的初始值：Xsk=（21−X−X）（k）（0）（结果是第k个斐波那契数）。然而，在本文中，我们抛开了一个明确的公式SK的计算，并考虑上述分数，这是制定在流常数和运营商，作为一个令人满意的答案，我们的问题。综上所述，我们区分共归纳计数过程中的三个阶段：(i) 在一个无限的树形自动机中枚举要计数的对象。(ii) 使用互模拟识别(iii) 用流常量和运算符表示计数的结果流。正如我们很快会看到的，整个方法本质上是定量的：转换和输出状态通常都用权重（实数）来标记，这些权重被流互模拟（和互模拟-直到）的概念所考虑。共归纳计数的方法既非常简单，又令人惊讶地普遍，这将通过许多进一步的例子来说明。同时，到目前为止，它还没有导致以前没有解决的计数问题的新解决方案。我们认为，目前关于计数的共归纳观点仍然可以做出一些贡献- 共归纳计数法是一种非常通用和灵活的方法，它可以统一和简单地对许多完全不同的结构进行计数。这与枚举组合学学科中许多不同方法的使用形成对比，例如上下文无关语言，竞赛树，符号计数，转移矩阵方法等等。此外，共归纳计数导致在一些情况下，现有的解决方案的新表示- 该方法的核心是将无限加权自动机简化为结构更好的（通常是有限的）自动机，使用双模拟关系来进行必要的状态识别。因此，该方法提供了另一个说明的基本性质的互模拟在数学中，一个概念最初源于世界的模态逻辑和语义的并行编程语言。- 该方法包含了一些元素，似乎是新的加权自动机理论。值得注意的是，通常不太受关注的有限加权自动机起着至关重要的作用。此外，广泛使用的概念，流衍生物的基础上，一般化的Brzozowski的概念的输入衍生物，都去从加权自动机流，反之亦然。最后，吕滕289∈⊆×∈∼∼共归纳计数为许多所谓的特殊数序列产生了许多结构相当优美的无限加权自动机关于我们所有的例子计数问题都源于以下文本之一，从中我们学到了我们所知道的关于枚举组合学的大部分内容：[6]，[4，5]和[9，10]。连分数的使用受到[3]的启发。关于加权自动机的基本参考文献是[2]。本文是一篇正在准备中的全文的扩展摘要[8]。2流演算的基本事实本文对文[7]中需要补充的部分作了简要的总结。所有流的集合由IR ω={σ|σ：{0，1，2，.. . } →IR}。各 个 流将由σ =（σ（0），σ（1），σ（2），. . ）=（s0，s1，s2，.. . 我们称σ（0）为σ的初始值。流σ的导数定义为：通过σJ=（s1，s2，s3，. . ）. 关于IRω的互模拟是关系RIRω IRω使得对于IRω中的所有σ和τ：如果σ R τ，则σ（0）=τ（0）且σJR τJ。双相似性是所有互模拟关系的联合，表示为 .我们有通常的共归纳原理：对于所有的σ，τIRω，如果σ τ，则σ=τ。共归纳定义是用导数和初值来表述的，被称为行为微分方程。对于任何rIR，我们表示恒定流（r，0，0，0，. . 再一次，R。另一恒定流是X =（0，1，0，0，.. . ），它扮演着形式变量的角色。 注意rJ= 0且XJ= 1。 我们将在流上使用以下运算符，所有 其中，通过行为微分方程来定义行为微分方程初始值名称（σ+τ）J=σJ+τJ（σ×τ）J=（σJ×τ）+（σ（0）×τJ）（σ−1）J=−σ（0）−1×（σJ×σ−1）（<$σ）J=σJ×<$（0）+<$σ）−1（σ（σ<$τ）J=（σj <$τ）+（σ<$τJ）（σ−1）J=−σJ<$（σ−1<$σ−1）Σ Σ（i∈Iσi）J=i∈I（σi）J（σ+τ）（0）=σ（0）+τ（0）（σ×τ）（0）=σ（0）×τ（0）（σ−1）（0）=σ（0）−1σ（0）=（στ）（0）=σ（0）×τ（0）σ−1（0）=σ（0）−1Σ Σ（i∈Iσi）（0）=i∈Iσi（0）和积平方根倒数shu_e积shu_e逆总和在[7]中讨论了上述方程解的唯一存在性，最终是由于初值和流导数运算的组合构成了上的最终余代数结构，吕滕290IRω。我们将自由地使用在[7]中证明的这些算子的恒等式，其中许多是熟悉的（如σ×τ=τ×σ和σ×σ=σ）。简单微分方程通常可以用代数方法求解，吕滕291× × × − ××J→···≤≤{∈|}所谓的(1)σ=σ（0）+（X×σJ）例如，考虑σ∈IRω，使得σ（0）= 1且σJ= 2×σ。这意味着σ=σ（0）+（X σ）= 1 +（X2σ）。由此得出（1（2X））σ= 1，其中σ=1= 20 + 21X + 22X2 += （20，21，22，.. . ）1−（2×X）（注意，在流演算中，所有这些都是形式恒等式，而不是使用生成函数作为纯粹的一个互模拟-上至是一个关系R <$IR ω× IR ω，使得对于所有的σ，τ ∈ IR ω：如果σR τ，则σ（0）= τ（0），并且存在n ≥ 0和流α0，. ，α n和β0，. ，β n，使得σJ= α0+···+ α n和τ J=β0+···+ β n对于所有0我n：α i= β i或α i R β i。 书里有这样一加强了共归纳证明原理，称为共归纳直到：如果σ R τ和R是一个双模拟直到，那么σ=τ。对于一个简单但典型的例子，考虑流σ，τ和ρ，使得σ（0）=τ（0）=ρ（0）=1，σJ= 2×σ，并且τJ=ρJ=τ+ρ。则{，}是一个双模拟，(noteσJ= 2×σ =σ+σ），σ=τ由余诱导直到。一个流可以用一个加权自动机Q =（Q，Q →Q，t）来表示，它包含一个（一般来说是无限的）集合Q，集合Q有一个输出函数o：Q → IR和一个转移函数t：Q →（Q →IR）（后一个集合包含有限支持的函数φ：Q→ IR，也就是说，使得qQ φ（q）= 0是有限的）。输出函数o为Q中的每个状态q分配IR中的实数o（q）。 转移函数t分配给Q中的状态q一个函数t（q）：QIR，它为Q中的任何状态qJ指定IR中的实数t（q）（qJ）。这个数可以被认为是从q到qJ的转变发生的权重或重数。 以下符号将是使用：q−→rqJ表示st（q）（qJ）=r。S（q）∈IRω是一个状态的等价条件q在一个weig ht edauto maton（Q，to，to）中，可以被定义为woequivalenttways。首先，对于任何k≥0，有以下公式：（二）ΣS（q）（k）={1，1，···lL|q= ql0qL1 ···lk−1qO（q）=l}0 1k−10−→1−→−−→k k它用从q开始的转移序列的标号来表示流S（q），并给出了清晰的操作直观。与此同时，它并不产生S（q）的任何紧凑表示，因此并不非常适合于实际的推理。幸运的是，它等价于下面的（共归纳）定义，即行为微分方程系统（其中一个是eachstateinQ）。 Let{q1， . . . ，qn}是statesqJ的st，其中whicht（q）（qJ）=第0章：狄氏方程初始值S（q）J=t（q）（q1）×S（q1）+···+t（q）（qn）×S（qn）S（q）（0）=o（q）利用上面的（1），这样的系统通常可以很容易地求解。在考虑一个小例子之前，我们引入一些进一步的符号约定：吕滕292−→- − −- -- -- -2、、. ..Cz轴t（q）（qJ）= 1我们通常简单地写为q qJ。对于o（q）= 1，我们写q，并称q为输出状态。我们在图片中只包含非零的输出值和带有非零标签的箭头现在考虑自动机q0，，zq1，s这发生在第1节的计数示例中。我们有S（ q0）（0）= 0，S（ q1）（0）= 1，S（ q0） J=S（ q1），S（ q1）J=S（ q0）+S（ q1）.利用公式（1），可以得到S（q0）=X/ 1−X−X2。在上面，我们已经解释了如何从自动机到流。相反的情况也是可能的，通过一个我们称之为“导数分裂”的过程计算例如流X/1的相应导数X我们刚刚得到的X 2，我们发现（X/1XX2）J=1/ 1XX2和（1/1XX2） J=（1/1XX2）+（X/1XX2）。我们现在可以把表达式1/ 1X X2和X/1X X2作为以下自动机的状态，其中转换由衍生物：X11−X−X2，，1−X−X2注意，1/ 1−X−X2的导数由一个和组成的事实，产生了两个转换，每个被加数。（1/ 1−X−X2）（0）= 1的事实决定了1/ 1−X−X2是输出状态。因此，从X/1X X，即上面自动机中状态q0的行为，我们找到了相同的自动机（直到状态的重命名3自然数一个自然数k≥0的复合是一个自然数序列n1···nl使得k=n1+···+nl。 对于任意k≥0，k的合成数sk是多少？下面的自动机列举了所有自然数的所有组合（在这里和下面的内容中，图片只显示了被理解为无限自动机的前几个层次εJ，，，、、2，，，o，、、 ，z11mm. . . . .3，c.、，zz21Cc12sJc、、、、111c，c，c，公司简介cJc，vzcJc，vz，s，z431 22 21113 121112 1111请注意，我们只有1-transitions（标签被省略），所有状态（除了第一个）都是输出状态。这个自动机的第k层包含了自然数k的所有合成.因此，公式（2）的直接结果是，初始状态ε表示流、、、、吕滕293、、CCCC{}{|{\fn方正粗倩简体\fs12\b1\bord1\shad1\3cH2F2F2F }∈∗0σ =（s0，s1，s2，. . ）的答案：S（ε）=σ。接下来，我们通过定义我们的加权自动机（以下重复）和微小的2状态（表示的流）之间自动机如下：ε0J1sssss31，sssc，，1、、21，，o，，zz211、、、、z111C121Jc......，z1111CC，zzCC、、、，zzCC、、、，zzSJ，z41311 22121111311211 1121111112q01 q1，s我们在自动机的状态上添加的上标表示它们与小自动机中的哪个状态相关。 或者，更明确地说，上面的图像表明关系R<$IR ω×IR ω的定义为R=S（ε），S（q0）S（w），S（q1）wIN，w= ε。 很容易检查R实际上是一个双向模拟：所有初始值匹配;S（ε）J=S（1），它与S（q1）=S（q0）J有关;对于所有的词vINn和自然数n，将v和n的连接记为vn，我们有S（vn）J=S（v（n+ 1））+S（vn1），其中每个分量都与S（q1）有关，因此匹配S（q1）J= 2×S（q1）=S（q1）+S（q1）。由上诱导直到σ=S（ε）=S（q0）。后者可以很容易地计算：XS（q）=（=（0，20，21，22，.. . ））1 −2X值得强调的是双模拟概念的定量方面：由非空词w标记的原始加权自动机的任何状态都可以通过两次转换到类似的状态，这一事实由从q1到自身的2步来4满射什么是，对于任何自然数k≥ 0，从集合{1，.，k}到集合{1，2，3}上（定义s0为0）？下面我们将看到如何将答案推广到集合{1，.，n}，对于固定但任意的n≥ 1。让我们表示函数f：{1，.，k} → {1，2，3}，通过f（1）···f（k）这个词。下面的自动机枚举在、、、、、、吕滕294、、、、、Ss、Ss、J， z2S3S、每个级别k所有这些功能：，，、、1，s““，J2，，，，......，z3，、、、，“o“J，，zJ，，zJ，，z11 12 13 21，第 22 23 31，第 32， 33$$，，，%，，，，，，%$$，，z%%，，%%，s$J123，o%Jz，o，o%J121122， 221 222223，，三三一三三二三三三，““、、““、、““、、，o“Jz，o“Jz，o“Jz12311232123322312232223333313332 3333请注意，所有由表示满射的单词标记的状态（即至少包含一个1，一个2和一个3）都被定义为输出状态。还要注意的是，我们不仅将图像限制在第一个五层，而且由于空间不足，没有包括所有的过渡。如前所述，从（2）可以得出，初始状态ε表示流σ =（s0，s1，s2，. . 我们感兴趣的答案。 自动机可以通过识别所有包含一个相同数量的不同符号，如下面的上标所示：，ε0，，，，11，s，J1......，z1#、、ss，ss，111，sJ2z$22，ssJ1z$22，ssJ2z$1十二， 十三21 22 2331（，32、（33%%，，（（，，（，%o%J，z，（（s（J，z、、 ，（（s（J1212122212332212222122323312，o，2333112313，o、、333，o、、J，，z3322、、J，， z2112321233223122322233333133323333如果将上面的所有i上标状态与下面的自动机中的状态qi相1不2 3t%%q q1第二季第三321我们得到一个互模拟-up-to，由此S（ε）=S（q0）接着是共诱导-up-to。后一个流可以很容易地计算，三个！X3σ=S（q0）=（1−X）（1− 2X）（1− 3X）在集合{1，.，n}，对于任意n≥ 1，无需做更多的工作，也可以找到：n！Xn/（1−X）（1− 2X）···（1 −nX）。5概率计数考虑一个不一定公平的硬币，正面出现的概率为p，反面出现的概率为q=1−p。对于任意k≥0，、、22，o0吕滕295TT$、、、、、、2，z“，z，z，%op概率sk，通过将硬币翻转k次，得到一个头和尾的序列（长度为k），而没有两个连续的头，但对于最后两个结果，这是必须的头？下面是一个描述所有可能场景的加权自动机：p，ε，q，，p h，q，p“t，qhh，o，z&、“s“，zp ht，qp. th，qp$，qSJphth，vzhtt，q，。 S.THHp，ztht$ （美元）tth，q，，zttt，q%%q p，$$q p，p，，o%JJ z，s$JJzJz&hthh htht htth htt thth thtt tthh ttht ttth tttt所有以两个头结束的状态（用序列标记）都是输出状态，并且没有进一步的转换。国家可以根据最终元首的数量来确定：p，ε0，q......1，s，......，z0，pssh2，sssQ，zpt得双曲余切值.，q，zhhht0，th1，tt0，p2，q，22秒，hth1htt0p（，，qp，q，“o“，2tht0p%，q%，tth1ttt0，，q，，q（，（（sqp，，%qpJ，，p，，hthh2J0J1z01，o%J02 z0J1z0hththtthhttthth thtttthhTTHTttth tttt产生以下自动机和相应的公式，用于我们的答案流σ =（s0，s1，s2，. . ）：qzq）zq_pq2p2X20，_ 1Qσ=S（q0）=1−qX−pqX26括号内的词语、%p吕滕296到目前为止，我们的自动机的最小化总是导致一个有限自动机产生，由一个众所周知的一般结果（参见。7、Thm。13.3]），一个合理的流。这里有一个例子，其中流的计数不是理性的，但代数。考虑由左括号和右括号组成的两个字母表{（，）}。对于任意k≥0，在这个字母表上，长度为k的括号内的词的个数sk是多少？以下自动机的输出状态为k级吕滕297u2z_Q2不，.... J. J.....（（2z3≥≥（）（（（（）（（（（（−准确地对应于所有这些词：εJ. . . （，. .（）、c.J（）（、、z（（.，。S（（），z（（（.，s.（）（）.，s.（（））.，s.J（）（）（（））（））（我们根据状态包含的左括号的数量来识别状态，而没有匹配的右括号：ε01J. （. .（）0，s.J（）（%%......，z我的天(()1，o%%%、、（（（%%（）（）0，%oJ2（（））0，%oJ2（（）2，o%J4这产生了以下结构良好，但仍然是有限自动机：1q0，_11zq1_，_11zq2_，_1z···作为第7节中的公式（3）的结果，其将专用于这种类型的自动机，获得答案流S（q0）的以下表达式：S（q0）=1−1 2X2=1+ 1 4X2X21−X21 −。 ..其等于流（1，0，1，0，2，0，5，0，14，0，.. . ）与加泰罗尼亚数字在偶数位置。7流和连分数设li和ui（对于i0）和di（对于i1）是作为标签的实数，人们可能想将其发音为以下自动机的level，up和downl0l1l2q%%u0zq_tu1z、、1吕滕2980，_1，_· · ·d1d2d3吕滕299√对于由状态q0表示的流，存在以下连分数：（三）S（q0）=1（u×X）×（d×X）1−（l0 ×X）−01−（l1×X）−1（u1×X）×（d2×X）. ..这个σi= 1 −（li×X）−（ui1×X）×σi+1×（d一期+1×X）S（ q0）=σ0的一个形式证明很容易，用共归纳法，见[7，Thm.17.1]。S（ q0 ） 的 公 式 可 以 通 过 结 合 以 下 一 般 事 实 直 观 地 理 解 ： 1/1 −τ = 1+τ+τ2+··· （=τ），对任意τ∈IRω，τ（0）=0，观察到状态q0可以在向自身迈出l0步或向q1迈出u0步之间进行重复选择，那么q1可以做任何事情，即σ1，然后通过 d1步回到 q0。对于第6节末尾的自动机，标签是li=0，ndui=di+1=1，对所有i≥0。因此，σ0=σ1，σ0= 1/1 −X2σ0，或者等价地，代数方程X2σ2−σ0+ 1 = 0。0这个方程的解实际上是2/1+ 1 − 4X2。在我们的一些例子中，我们还将遇到以下类型的自动机，没有向下转换，但所有状态都可能有一个非平凡的输出值ri∈IR：l0q，ru0L1q，ru1L2q，ru20或01r12R2· ··由q0表示的流由以下“向上”连续分数给出.r2+（u2×X）×1−（l ×X）（四）r10的S（q0）=+（u0×X）×r1+（u1×X）×1−（l131−（l2×X）×X）1−（l0×X）这种类型的自动机尚未处理[7]。再一次，连分数表示一个无限方程组，其解可以证明等于S（q0）。最后，下一种类型的自动机概括了上述两类自动机：l0l1l2q，ru0zq，ru1zq，ru2z0r0，D11对1，D22r2，D3···吕滕300、、“，，%..流S（q0）由下面的疯狂表达式给出，它由向上和向下增长的（嵌套的）连分数组成（五）r0+（u0×X）×A1−（l0×X）−（u0×X）×A×（d1×X）其中，为了便于标记，A是以下的简写：A=r1+（u1×X）×（···）1−（l1×X）−（u1×X）×（···）×（d2×X）请注意，我们在本文中看到的所有早期（最小化）自动机都是最后一种自动机的特殊实例，并且S（q0）的所有相应表达式都是（非常简单）特殊的在上述公式（5）的实例中，例如S（q0）=p2X2/ 1-qX-pqX2，第5章举个例子第8章更多的好词有时有各种方法来枚举要计数的结构，通过不同的自动机，这通常会导致表达计数流的新方法作为一个例子，我们再次处理第6节的计数问题，以稍微不同的形式：对于任何k≥0，由k个匹配的左括号和右括号组成的好括号单词的数量sk是多少下面是列举所有这些词的一种方法：，ε，、、（）、_。，，，z（·）#“，s“、我的天啊、、()()J（（）），o，oJz（）（·），（（·））（（）·），““，，，，“，sJz，，zJz，oJ，z，，z_（）（（））（（））（））（）（）任何没有点的单词w（标记为a的状态）都被认为是输出状态（因此带下划线），并且有两个孩子;任何有一个或多个点的单词都有四个孩子，通过以四种不同的方式替换最左边的点来产生。这里有一种关于我们的自动机的“成长”的语法ww1·w2c、，. .、、/c/cW，，zzw（）w ，_，，.、、（·）吕滕301.，s.J，，z·w（）w（·）1 2w1w2w1（）·w2w1（·）2吕滕302、、，，−···{} → {}其中w和w1不包含任何点。接下来可以根据它们包含的点的数量来识别，ε0，、、、、、（）0，t，，，，，，，，，，，z（·）1，22、、、、()(）0，sJ1（（））0，t））2，sJ z（）（·）（（·1 （（）·）1（（·）·）2，.，，，，，，，......、、、. . .、、 、、，0s J1z，zJz&.得双曲余切值.J z，z（）（（））（）（（·））（）（（）·）1（）（（·）·）2（（））（）（（））（·）1（））·）1（·））·）2（）·）·）2（·）·）3生成以下自动机：1 2q%%1zq_t21zq_t1z0，_11、_12、_1···以及用于答案流S（q0）的以下表达式：1S（q0）=1−X−X2X21 −2X−X22=1+ 1014X11− 2X−. . .=X1−X1−X1 −。.（=（1，1，2，5，14，. . ），加泰罗尼亚数字）。第一个等式由公式（3）得出，第二个和第三个等式由某种一般流演算得出。9排列和循环置换（双射）p：1、...，k1、...，k可以由相应的图像序列p=（p（1）p（k））表示。另一种非常常见的等价表示，也就是我们将要使用的表示，用构成置换的（唯一的）循环序列来描述置换例如，置换p=（532461），其中p（1）= 5，p（2）= 3，p（3）= 2，p（4）= 4，p（5）= 6，并且p（6）= 1，也可以由以下序列表示：、、、.吕滕303p=（156）（23）（4）。 这里，循环c =（x1···xk）表示{x1，.，xk}定义为：c（x i）= x i+1，对于所有1≤i≤k− 1，且c（xk）=x1。我们从一个小问题开始，对于任何吕滕304--k≥ 0：集合{1，.，k}（定义s0= 1）？以下自动机通过列出所有可能的循环序列来枚举所有排列：εJ，（1），......(12)，t，，，，，，，，z（1）（2）. .、、、（（）、、，。 S.Jz，（s） J z（132） (123)（十二）（三）（十三）（二） （一）（二十三）（一）（二）（三），，. .、、、（（（，，.得双曲余切值. Jzz，s（ J Z Z_（1432）（1342）（1324）（132）（4）（14）（23）（1）（234）（1）（23）（4）在级别k处的任何状态表示集合1，. k，因此是输出状态。它可以转换到下一个级别的状态，或者通过将数字k+ 1添加到现有的循环之一，或者通过添加新的循环（k+ 1）。（对于所有k级的状态）第一种跃迁正好有k次，第二种跃迁只有一次，总共有k+ 1次跃迁。这解释了上面自动机的结构，同时表明每个层次的所有状态都可以被识别，产生下面的自动机：q01q12q23···应用公式（4），其中对于所有k≥0，l k = 0和uk=k+1，我们得到S（q0）= 1 + 1！X+ 2！X2+ 3！X3+···对于流（s0，s1，s2，.. . 我们追求的是一个数。 换句话说，国王！集合{1，.，k}，这并不奇怪。我们选择在上面的自动机中用循环序列来表示置换，因为它可以很容易地适应于处理各种相关的计数问题。第一个简单的变化是跟踪每个排列中的循环总数。 我们可以通过固定任何实数（变量）u来做到这一点，我们将其用作表示添加新循环的所有转换的标签（记住，所有其他转换都有标签1，通常被省略）：εJu，（1），......（12），t，，u，，，z（1）（2）.，，u，（（，u，。S.J，z，（s（J，，z（132） (123)（十二）（三）（十三）（二） （一）（二十三）（一）（二）（三），，. .、，，u，，，（（（，，u，，s. JZZ，s（ J z，z_（1432）（1342）（1324）（132）（4）（14）（23）（1）（234）（1）（23）（4）吕滕305联系我们、、..、、、、、oo、、2（十二）（三）（四）再次识别相同级别的所有状态给出以下等价的自动机：q0uq1 u+1q2u+2···如前所述，公式（4）可以被应用于其，现在产生S（q0）= 1 +u×X+u（u+1）×X2+u（u+1）（u+2）×X3+···（用一些基本的流演算可以证明它等于（1−X）−u，即（1−X）−1与自身的shu乘积，u倍）。 该流可以被认为具有u作为参数。它对所有的数sk，n进行编码，k，n0，计数1的所有排列，.，n由k个循环组成（这些数被称为第一类斯特林数）。另一种方法是将X和u都视为形式变量。这将把我们带到多元流演算，这里省略了。什么是，移动到下一个问题，对于任何k≥ 0，{1，.，k}使得p≠p= 1（即所谓的对合）。为此，我们回到本节的第一个自动机，现在我们从其中删除所有状态，但只包含1-和2-循环的状态εJ，，（1），、、(12)，s，，z（一）（二）、、......J，，s Jz（12）（3）（13）（2）（1）（23）（1）（2）（3）.，，，，，，，、、、.，。SJ，，、，s，J，，，z（十二）（三十四）（十二）（三）（四） （十四）（二）（三） （1）（24）（3）（1）（2）（34）（1）（2）（3）（4）状态可以根据1-循环的数量来识别，它们仍然可以变成2-循环，它们包含，如下面的上标所示ε0J1（一）、、0，s，（十二）、、，，z（一）（二）（三）、、......J1J1z3（十二）（三）（十三）（二）（一）（二十三）（一）（二）（三）哦，，、、、O（12）（34）0， so、、