请输入您要查询的字词:

 

单词 EnumerativeCombinatorics
释义

enumerative combinatorics


Enumerative combinatorics deals with the question: if we knowthat a set S is finite, how can we determine the exact number ofelements that S contains?

Basic principles and techniques of enumerative combinatorics include:

  • the addition principle;

  • the multiplication principle;

  • the involution principle;

  • the inclusion-exclusion principleMathworldPlanetmath; and

  • the use of generating functions.

The principles listed above are disarmingly simple and seeminglyobvious. Nonetheless, when used properly they are powerfultools for producing bijective proofs of combinatorial identitiesPlanetmathPlanetmathPlanetmathPlanetmath. Onthe other hand, while generating functions can frequently be used togive quick proofs of identities, it is sometimes difficult to extractcombinatorial proofs from such proofs.

The most fundamental principle of enumerative combinatorics and thebasis of all counting is the addition principle. It says thatif S is a finite setMathworldPlanetmath, then

|S|=xS1.

More generally, if S=AB, then

|S|=xAB1=xA1+xB1=|A|+|B|.

By inductionMathworldPlanetmath on n, we also get

|i[n]Si|=i[n]|Si|.

As an application of the addition principle, we prove themultiplication principle.

Proposition 1.

Multiplication principle. If S and T are finite sets, then

|S×T|=|S||T|.
Proof.

By the addition principle,

|S×T|=(x,y)S×T1.

But we can write S×T as the disjoint unionMathworldPlanetmath

S×T=yTS×{y}.

The projection map S×{y}S is a bijection, so|S×{y}|=|S|. Hence it follows that

|S×T|=yT|S×{y}|
=yT|S|
=|S|yT1
=|S||T|,

which completesPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath the proof.∎

The involution principle says that if φ:SS isan involution, then for any XS, |X|=|φ(X)|. Thefollowing example illustrates the involution principle.

Proposition 2.

Enumerating elements of the powerset.Let [n]={1,2,,n} and let 2[n] be the powerset of [n].Then the cardinality of 2[n] is 2n.

Proof.

Define a function φ:2[n]2[n] by the formulaMathworldPlanetmathPlanetmath

φ(S)=SΔ{n}.

In other words, φ(S) is the symmetric differenceMathworldPlanetmathPlanetmath of S and{n} — if n is an element of S, we remove it, and if n isnot an element of S, we insert it. The function φ is aninvolution, hence a bijection. Now notice that 2[n-1]2[n] and φ(2[n-1])=2[n]2[n-1]. Inother words,

2[n]=2[n-1]φ(2[n-1]).

Since φ is a bijection, this implies that

|2[n]|=2|2[n-1]|.

By induction on n we obtain

|2[n]|=2n|2[0]|.

Now [0]=, so 2[0]={}. Thus|2[0]|=1, implying that

|2[n]|=2n,

which is what we wanted to show.∎

As we have seen above, it is possible to use the addition principle tocount the number of elements in the disjoint union of finite sets.But what if we want to count the number of elements in a non-disjointunion of finite sets? The inclusion-exclusion principle givesus a way to do this. A common way of stating the inclusion-exclusionprinciple is as the following propositionPlanetmathPlanetmath.

Proposition 3.

Inclusion-exclusion principle.Let S1,,Sn be finite sets. Then

|i[n]Si|=T2[n](-1)|T||iTSi|.

The formula in this proposition uses negative numbers. But the coreof the inclusion-exclusion principle is a statement about naturalnumbersMathworldPlanetmath.

Proposition 4.

Let S and T be finite sets. Then

|S|+|T|=|ST|+|ST|.

Thus the latticeMathworldPlanetmath of finite subsets of N is a modular latticeMathworldPlanetmath.

Proof.

By the addition principle,

|S|+|T|=|(ST)(ST)|+|(TS)(ST)|
=|ST|+|ST|+|TS|+|ST|.

Now observe that ST=(ST)(ST)(TS). So by a second application of the addition principle,

|ST|+|ST|=|ST|+|ST|+|TS|+|ST|.

Hence |S|+|T|=|ST|+|ST|.∎

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 7:20:41