组合数学中常见的计数方法

沈阳理工大学学士学位论文

摘 要

组合数学是研究离散结构的存在、计数、分析和优化等问题的一门学科，它是计算机出现以后迅速发展起来的一门数学分支。近年来，组合数学不仅在软件技术中有着重要的应用价值，而且在企业管理，交通规划，战争指挥，金融分析等领域都有着重要的应用。组合数学在国外早已成为十分重要的学科，甚至可以说是计算机科学的基础。 本文通过对几类常见组合数的整理归纳,主要介绍了Catalan数、第一类、第二类Stirling、Fine数、Pólya计数等计数方法的历史起源、定义、基本性质等,研究组合数学及概率论有关知识，并根据组合计数和概率之间内在的联系，进而研究组合数学的组合意义在生活中某些领域的应用。组合数学所讨论的问题来源于实际。因此从内容来看确实丰富多彩,以至于很难用一句话来概括什么叫“组合数学”,本文只能就它所研究的若干问题进行介绍。

关键词:组合数学;概率论;组合意义;应用

I

沈阳理工大学学士学位论文

Abstract

Combinatorial mathematics is a discipline contains the existence of discrete structures, counting, analysis and optimization, which is a branch of mathematics developed rapidly since the advent of the computer. In recent years, the combination of mathematics not only has important applications in software technology, but also has important applications in the field of business management, transportation planning, command of the war, and financial analysis. Combinatorial Mathematics in the countries has already become a very important subject, and can even be said to be the basis of computer science.

This article summarized by the finishing of some common combinations of numbers, mainly Catalan numbers, the first category, the second Stirling Fine number, the Polya counting method, historical origins, definition, basic properties, research and combinatorial mathematics and probability of relevant knowledge, and according to the combination of count and an intrinsic link between the probability and then study a combination of mathematical meaning in some areas of the life.

The issues discussed by the combination of mathematics from real and the content point of view is really colorful, so it is difficult to summarize in one sentence what is called \this paper can only be described a number of issues’ studies.

Keywords: combinatorial mathematics; probability theory; combination of significance; application

II

沈阳理工大学学士学位论文

目 录

1 绪论 ........................................................................................................................................ 1

1.1组合数学的研究背景和意义 ....................................................................................... 1 1.2国内外研究现状 ........................................................................................................... 1 2 Catalan数 ............................................................................................................................. 3

2.1 Catalan产生的历史 ..................................................................................................... 3 2.2 Catalan数的定义 .......................................................................................................... 5 2.3 关于Catalan数的几种求法 ........................................................................................ 6

2.3.1 引言 .................................................................................................................... 6 2.3.2 组合模型及求法 ................................................................................................ 6 2.3.3 路径模型及求法 ................................................................................................ 7 2.3.4 生成函数法 ........................................................................................................ 8 2.4 Catalan数的性质 ......................................................................................................... 9 2.5 Catalan数的组合意义及应用 .................................................................................... 10

2.5.1 Catalan数的组合意义 ..................................................................................... 10 2.5.2 Catalan数的应用 ............................................................................................. 12

3 Stirling数 ......................................................................................................................... 16

3.1 Stirling产生的历史 .................................................................................................... 16 3.2 第二类Stirling数 ...................................................................................................... 16

3.2.1 定义 .................................................................................................................. 16 3.2.2 几个计算公式 .................................................................................................. 17 3.2.3 性质 .................................................................................................................. 18 3.3 第一类Stirling数 ...................................................................................................... 18

3.3.1 定义 .................................................................................................................. 18 3.3.2 几个计算公式 .................................................................................................. 19 3.3.3 性质 .................................................................................................................. 20 3.4 第一类Stirling和第二类Stirling数的关系式 ........................................................ 20 3.5 Stirling数的组合意义及应用 .................................................................................... 21

3.5.1 引言 .................................................................................................................. 21 3.5.2 预备知识 .......................................................................................................... 21 3.5.3 Stirling数的概率表示 ...................................................................................... 22 3.5.4 渐进与估计 ...................................................................................................... 26 3.5.5 Stirling数的组合意义 ..................................................................................... 27

4 其他几种常见的组合数 ...................................................................................................... 28

4.1 Fine数 ......................................................................................................................... 28

4.1.1引言 ................................................................................................................... 28 4.1.2 Dyck格路与Catalan数 ................................................................................... 28 4.1.3 Fine数的基本性质和概念 ............................................................................... 29 4.1.4 Fine数的几个重要的恒等式 ........................................................................... 30 4.1.5 Fine数的组合意义 ........................................................................................... 31 4.2 Pólya计数 ................................................................................................................... 31

III

沈阳理工大学学士学位论文

4.2.1 Pólya计数产生的历史 ..................................................................................... 31 4.2.2预备知识 ........................................................................................................... 32 4.2.3 Pólya计数定理 ................................................................................................. 33 4.2.4 Pólya计数的例子与性质 ................................................................................ 33

5 总结 ...................................................................................................................................... 37 致谢 .......................................................................................................................................... 38 参考文献 .................................................................................................................................. 39 附录A 英文原文 .................................................................................................................... 40 附录B 中文翻译 .................................................................................................................... 46

IV