[開設 07/03/23=MM/DD/YY]

集合族の例： k要素部分集合全体の族

これは，しばしば離散数学に現れる集合族である．

X を集合とし， k を 0 ≤ k ≤ |X| なる整数とする．このとき， X の k 要素部分集合全体からなる族を下式の左辺のように書く．

( X ) = {K | K⊆X, |K|=k}

k

たとえば，

( {a, b} ) = {∅}, ( {a, b} ) = {{a}, {b}}, ( {a, b} ) = {{a, b}},

0 1 2

( {a, b, c} ) = {∅}, ( {a, b, c} ) = {{a}, {b}, {c}}, ( {a, b, c} ) = {{a, b}, {a, c}, {b, c}}, ( {a, b, c} ) = {{a, b, c}}

0 1 2 3

であり，一般に

( X ) = {∅}, ( X ) = {{x} | x ∊X}

0 1

であって， |X|=n のとき

( X ) = {X}

n

である．
|X|=n のとき

|( X )| = ( n )

k k

が成り立つ（右辺は二項係数）．
二項係数の公式

_n (

n
k

)

∑ = 2ⁿ

^k=0

に対応して，下式が成り立つ．

_n (

X
k

)

∪ = 2^X

^k=0

1≤k≤n のとき，	(	X	)	は X の被覆である．特に k=1 のときと k=n のとき， X の分割になっている．
		k

(	{a, b, c}	)	= {∅},	(	{a, b, c}	)	= {{a}, {b}, {c}},	(	{a, b, c}	)	= {{a, b}, {a, c}, {b, c}},	(	{a, b, c}	)	= {{a, b, c}}
	0				1				2				3