[set theory] Stirling subset number (Stirling subset number concept | ball model | Stirling subset number recurrence formula | binary relationship refinement relationship of division)

One 、Stirling Number of subsets

---

Stirling Number of subsets :

take

n

n

n A different ball Put it in

k

k

k The same box in , No empty boxes , namely Put at least one ball in each box ;

The total number of different placement methods is :

{

n

k

}

\begin{Bmatrix} n \\ k \end{Bmatrix}

{ nk​} , This number is called Stirling Count ;

take

n

n

n The meta set is divided into

k

k

k A non empty subset Of Number of divisions ;

Divide And Equivalence relation The description of is equivalent , Every Divide Both with Equivalence relation One-to-one correspondence ;

Stirling Subset number function : Find how many different in the set Equivalence relation , That is, find how many different Divide ;

Two 、 Ball model

---

Ball model : Above Sterling Stirling Number of subsets , It's a small ball in a box , The ball is numbered , need Distinguish between different balls , The box has no number , There is no need to distinguish boxes ; Let's sort out different ball putting models :

• The ball has a number , The box has no number ( Different balls are put in the same box ) : This is to find the set Division problem , Stirling Count ; This belongs to the ball model ;
• The ball has no number , The box is numbered ( The same ball is put in different boxes ) : The problem of solving indefinite equations , Multiple set combinatorial problem , Positive integer partition problem ;
• The ball has a number , The box is numbered ( Different balls are put in different boxes ) : Multiset arrangement , Exponential function problem ;

{

n

k

}

\begin{Bmatrix} n \\ k \end{Bmatrix}

{ nk​} It means that you will

n

n

n The elements are divided into

k

k

k Number of subsets ;

(

n

k

)

\begin{pmatrix} n \\ k \end{pmatrix}

(nk​) From

n

n

n Of the elements

k

k

k The number of schemes of small balls ;

Reference resources : Baidu Encyclopedia - The problem of putting the ball

3、 ... and 、Stirling Recursive formula of subset number

---

common Stirling Number of subsets result :

{

n

0

}

=

0

\begin{Bmatrix} n \\ 0 \end{Bmatrix} = 0

{ n0​}=0

take

n

n

n Put a ball on the table

0

0

0 In a different box , Yes

0

0

0 Seed method ;

take

n

n

n The elements are divided into

0

0

0 class , Yes

0

0

0 Seed method ; Namely There is no way ;

{

n

1

}

=

1

\begin{Bmatrix} n \\ 1 \end{Bmatrix} = 1

{ n1​}=1

take

n

n

n Put a ball on the table

1

1

1 In a different box , Yes

1

1

1 Seed method ;

take

n

n

n The elements are divided into

1

1

1 class , Yes

1

1

1 Seed method ; amount to Global relations ;

{

n

2

}

=

2

n

−

1

−

1

\begin{Bmatrix} n \\ 2 \end{Bmatrix} = 2^{n -1} - 1

{ n2​}=2n−1−1

take

n

n

n Put a ball on the table

2

2

2 In a different box , Yes

2

n

−

1

2^n -1

2n−1 Seed method ;

n

n

n Meta set you

2

n

2^n

2n Different subsets , This is the number of power sets , Each subset , It is paired with its complement , therefore Yes

2

n

−

1

2^{n-1}

2n−1 The collection , Among them subtract Empty set And Full set The pair of , The end result is

2

n

−

1

−

1

2^{n -1} - 1

2n−1−1 ;

{

n

n

−

1

}

=

C

2

n

\begin{Bmatrix} n \\ n-1 \end{Bmatrix} = C^n_2

{ nn−1​}=C2n​

take

n

n

n Put a ball on the table

n

−

1

n-1

n−1 In a different box , Yes

C

2

n

C^n_2

C2n​ Seed method ;

take

n

n

n The elements are divided into

n

−

1

n-1

n−1 class , There are two elements in one class , Every other element has its own kind ; As long as

n

n

n Elements that belong to a class

2

2

2 Select the elements , How many winning ways , Just how many categories ;

{

n

n

}

=

1

\begin{Bmatrix} n \\ n \end{Bmatrix} = 1

{ nn​}=1

take

n

n

n Put a ball on the table

n

n

n In a different box , Yes

1

1

1 Seed method ;

take

n

n

n The elements are divided into

n

n

n class , Yes

1

1

1 Seed method ; amount to Identity ;

Stirling Number of subsets The recursive formula :

{

n

k

}

=

k

{

n

−

1

k

}

+

{

n

−

1

k

−

1

}

\begin{Bmatrix} n \\ k \end{Bmatrix} = k\begin{Bmatrix} n-1 \\ k \end{Bmatrix} + \begin{Bmatrix} n-1 \\ k-1 \end{Bmatrix}

{ nk​}=k{ n−1k​}+{ n−1k−1​}

take

n

n

n Each element is divided into

k

k

k class ,
First pick out an element , Put it aside , And then there were

n

−

1

n-1

n−1 Elements ;

The selected elements are merged into other classes : Will this

n

−

1

n-1

n−1 Each element is divided into

k

k

k class , Add the selected elements to

k

k

k Class ; The total result is

n

n

n Each element is divided into

k

k

k class , The selected elements are added to

k

k

k Class , Yes

k

k

k In a different way , That is, add to the low

1

,

2

,

3

,

⋯
 

,

k

1,2,3, \cdots , k

1,2,3,⋯,k Class ;

The selected elements are of their own kind : take

n

−

1

n-1

n−1 Each element is divided into

k

−

1

k-1

k−1 class , Each class is not empty , then Let the selected elements form a class , The class that calls itself a class And Previous

k

−

1

k-1

k−1 Classes , The combination is

k

k

k Classes ;

Consider the above two situations at the same time , Namely Stirling Recursive formula of subset number ;

k

{

n

−

1

k

}

k\begin{Bmatrix} n-1 \\ k \end{Bmatrix}

k{ n−1k​} meaning : take

n

−

1

n-1

n−1 The elements are divided into

k

k

k A subset of

{

n

−

1

k

}

\begin{Bmatrix} n-1 \\ k \end{Bmatrix}

{ n−1k​} , Again Add... To

n

n

n Elements to one of them Yes

k

k

k Kind of plan , Multiply by

k

k

k ;

{

n

−

1

k

−

1

}

\begin{Bmatrix} n-1 \\ k-1 \end{Bmatrix}

{ n−1k−1​} meaning : take

n

−

1

n-1

n−1 The elements are divided into

k

−

1

k-1

k−1 A subset of

{

n

−

1

k

−

1

}

\begin{Bmatrix} n-1 \\ k-1 \end{Bmatrix}

{ n−1k−1​} , The rest

n

n

n Elements naturally become a subset ( There is only one solution ) ;

Four 、Stirling Example of subset number ( Number of quaternion set equivalence relations )

---

Find the number of equivalent relations on the quaternion set , namely

4

4

4 Each element is divided into

1

,

2

,

3

,

4

1, 2,3,4

1,2,3,4 The division and addition of classes ;

{

4

1

}

+

{

4

2

}

+

{

4

3

}

+

{

4

4

}

=

1

+

(

2

4

−

1

−

1

)

+

C

2

4

+

1

=

1

+

7

+

6

+

1

=

15

\begin{Bmatrix} 4 \\ 1 \end{Bmatrix} + \begin{Bmatrix} 4 \\ 2 \end{Bmatrix}+ \begin{Bmatrix} 4 \\ 3 \end{Bmatrix}+\begin{Bmatrix} 4 \\ 4 \end{Bmatrix} = 1 + ( 2^{4-1} - 1 ) + C^4_2 +1 =1+7+6+1 = 15

{ 41​}+{ 42​}+{ 43​}+{ 44​}=1+(24−1−1)+C24​+1=1+7+6+1=15

On quaternion The number of ordered pairs is

4

×

4

=

16

4 \times 4 = 16

4×4=16 individual ;

On quaternion The number of relationships is

2

16

=

65536

2^{16} =65536

216=65536 individual ; Include the following , contain

0

0

0 An orderly pair of , contain

1

1

1 An orderly pair of ,

⋯

\cdots

⋯ , contain

16

16

16 An orderly pair of ;

above

65536

65536

65536 There are two binary relationships

15

15

15 One is equivalence ;

5、 ... and 、 Binary relation of division Refinement relation

---

Set family

A

\mathscr{A}

A and Set family

B

\mathscr{B}

B All are aggregate

A

A

A Division ,
If

A

\mathscr{A}

A Each partition in It's all contained in

B

\mathscr{B}

B A partition of in , said

A

\mathscr{A}

A Divide yes

B

\mathscr{B}

B Divide The refinement of ;

Refine It's a binary relationship , Is the binary relationship between partitions ;

The refinement relation has :

• Self reflection : Each division is its own refinement
• Transitivity :$\mathcal{A}$

  C The refinement of

• No symmetry : Refinement does not have symmetry
• There is no global relationship : Some divisions are not detailed with each other