dyskretna ola: Ile jest relacji zwrotnych na zbiorze n−elementowym A , tj. takich R⊂A² , że (a,a)∊R dla każdego a∊A ? Ile jest relacji przeciwzwrotnych na A ?

Pytający: Jest n² różnych par (a,b)∊A². Aby relacja była zwrotna, wszystkie pary postaci (a,a)∊A² muszą należeć do tej relacji. Takich par jest n. Pozostałe pary postaci (a,b)∊A², gdzie a≠b, do ów relacji zwrotnej należą lub nie, czyli są 2 możliwości dla każdej takiej pary. Dlatego relacji zwrotnych jest 2ⁿ²⁻ⁿ=2ⁿ⁽ⁿ⁻¹⁾. Analogicznie relacji przeciwzwrotnych również jest 2ⁿ⁽ⁿ⁻¹⁾.

iteRacj@: Ile relacji równoważności można określić w zbiorze n−elementowym A?

Pytający: Tyle, ile jest podziałów (partycji) zbioru n−elementowego, czyli: ∑_k=1ⁿ(S₂(n,k)) S₂(n,k) // liczba Stirlinga drugiego rodzaju Dla każdego takiego podziału składające się nań niepuste podzbiory zbioru n−elementowego można utożsamić z klasami abstrakcji danej relacji równoważności. Na rysunku zobrazowanie wszystkich tabelek relacji równoważności dla n=3. Od lewej do prawej kolejno podziały zbioru {1,2,3}: {{1},{2},{3}} {{1},{2,3}} {{2},{1,3}} {{3},{1,2}} {{1,2,3}}

iteRacj@: super, bardzo dziękuję za przejrzyste wytłumaczenie!

Pytający: W zasadzie jest to dobra odpowiedź jedynie dla n≥1. Przecież relacja pusta na zbiorze pustym też jest relacją równoważności. Poprawną odpowiedzią jest n−ta liczba Bella, czyli: B_n=∑_k=0ⁿ(S₂(n,k)). Teraz mogę powiedzieć "proszę bardzo".

iteRacj@: dziękuję : )