離散數(shù)學(xué)等價關(guān)系

發(fā)布時間：2025-12-10 | 來源：互聯(lián)網(wǎng)轉(zhuǎn)載和整理

***上每個等價關(guān)系對應(yīng)***的一種劃分,***的每一種劃分又對應(yīng)于該***的一個等價關(guān)系,不同的等價關(guān)系對應(yīng)于***的劃分也不同,因此***有多少不同劃分,就有多少不同等價關(guān)系,三個元素的***共有5種不同劃分,(含有1塊和3塊各有1種,含有2塊有3種),故含有三個元素的***，可以確定5種等價關(guān)系.

如A={1，2，3}，則5種不同劃分為

{{1},{2},{3}};{{1},{2,3}};{{1,3},{2}};{{1,2},{3}};{{1,2,3}};

對應(yīng)的等價關(guān)系為

R1={(1,1),(2,2),(3,3)};R2={(1,1),(2,2),(2,3),(3,2),(3,3)};

R3={(1,1),(1,3),(3,1),(2,2),(3,3)};

R4={(1,1),(1,2),(2,1),(2,2),(3,3)};

R5={(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2),(1,3),(3,1)};

一般地,對有n個元素的***有Bn種不同的劃分(等價關(guān)系),Bn稱為Catalan數(shù)

Bn=2n!/((n+1)n!n!),如4個元素的***，可以確定14種等價關(guān)系.