Zadania z Matematyki Dyskretnej

[Student_matmy]

Witam

Zwracam się z prośbą o pomoc w rozwiązaniu lub wytłumaczeniu/naprowadzeniu w następujących zadaniach z matematyki dyskretnej. Z góry dzięki za jakąkolwiek pomoc.

1. Liczby Bella. Dla \(\displaystyle{ n \in N}\) niech \(\displaystyle{ B_{n}:= \sum_{k=0}^{n} S(n,k)}\)\(\displaystyle{ B_{n}}\) nazywamy liczbami Bella. Pokazać, że dla dowolnego \(\displaystyle{ n \in N}\) zachodzi \(\displaystyle{ B_{n+1}= \sum_{k=0}^{n} {n \choose k} B_{n-k}}\)

2. Niech \(\displaystyle{ n \ge 2}\) i niech \(\displaystyle{ A_{n}=\left\{ \sigma \in S_{n}|sgn \sigma=1 \right\}.}\) Pokazać, że \(\displaystyle{ A_{n}}\) jest podgrupą \(\displaystyle{ S_{n}}\) oraz znaleźć \(\displaystyle{ \left| A_{n} \right|.}\)

3. Udowodnić, że w każdej 10 osobowej grupie osób są 4 osoby, które się wzajemnie znają albo 3 osoby, z których żadne dwie się nie znają. Pokazać, że dla grup 8 osobowych powyższy wynik jest nieprawdziwy.

4. Pokazać, że \(\displaystyle{ R(m,n) \le R(m-1,n)+R(m,n-1)}\) dla dowolnych liczb naturalnych \(\displaystyle{ m,n \ge 3}\). Wskazówka: Niech \(\displaystyle{ p:=R(m-1,n), q:=R(m,n-1), r:=p+q}\) i rozważmy grupę osób \(\displaystyle{ G:=\left\{ 1,2,...,r\right\}.}\) Niech \(\displaystyle{ L_{1}:=\left\{ x \in G\left\{ 1\right\}|1 zna x \right\}, L_{2} :=\left\{ x \in G\left\{ 1\right\}|1 nie zna x \right\} .}\) Co można powiedzieć o liczebności zbiorów \(\displaystyle{ L_{1} i L_{2}}\)?

5. Permutację \(\displaystyle{ \sigma \in S_{n}}\) nazwiemy nieporządkiem, jeśli \(\displaystyle{ \sigma(i) \neq i}\) dla \(\displaystyle{ i=1,...n.}\) Niech \(\displaystyle{ \sigma \in S_{n} (n \ge 2)}\) będzie nieporządkiem i niech \(\displaystyle{ p}\) będzie liczbą pierwszą. Pokazać, że \(\displaystyle{ \sigma^{p} = id \Leftrightarrow \sigma}\) jest iloczynem rozłącznych cykli o długości \(\displaystyle{ p}\). Czy założenie o pierwszości liczby \(\displaystyle{ p}\) jest konieczne?

6. Udowodnić, że dla \(\displaystyle{ n \ge 3}\) mamy: \(\displaystyle{ S(n,3)=\frac{1}{2}( 3^{n-1}+1 )- 2^{n-1}}\)

7. Niech \(\displaystyle{ X=\left\{ 1,2,...,n\right\}}\) i \(\displaystyle{ \sigma \in S_{n}}\). W zbiorze \(\displaystyle{ X}\) określamy relację \(\displaystyle{ \sim}\) następująco \(\displaystyle{ x \sim y \Leftrightarrow \exists k \in \mathbb{N}_{0} : y= \sigma^{k}(x)}\). Pokazać, że jest to relacja równoważności na \(\displaystyle{ X}\) oraz opisać zbiór ilorazowy.

8. Znaleźć liczbę rozwiązań równania \(\displaystyle{ x_{1}+x_{2}+x_{3}+x_{4}+x_{5}=10}\) takich, że \(\displaystyle{ x_{1},...x_{5} \in \mathbb{N}_{0}}\) oraz \(\displaystyle{ x_{1} \le 3, x_{2} \le 4, x_{3} \le 5, x_{4} \le 6, x_{5} \le 7}\)

[Naed Nitram]

2. Funkcja:

\(\displaystyle{ \sigma:S_n\to\{-1,1\}}\)

jest homomorfizmem grup, to znaczy po zadaniu na zbiorze \(\displaystyle{ \{-1,1\}}\) działania grupowego, tu mnożenia. Wynika to np. stąd, że \(\displaystyle{ \sigma}\) to wyznacznik macierzy odpowiadającej permutacji. Zauważamy, że \(\displaystyle{ \ker(\sigma)=A_n}\), skąd \(\displaystyle{ A_n}\) jest podgrupą, nawet normalną, ponadto \(\displaystyle{ |A_n|=\frac{|S_n|}{|\{-1,1\}|}=\frac{n!}2}\).

[Student_matmy]

Naed Nitram dzięki za podpowiedź i wyjaśnienie.

Czy potrafi ktoś pomóc z innym zadaniem? Jakoś podpowiedzieć?

[Naed Nitram]

7. Zwrotność: \(\displaystyle{ \sigma^{n!}=\mathrm{id}}\), czyli \(\displaystyle{ a=\sigma^{n!}(a)}\), skad \(\displaystyle{ a\sim a}\).
Symetria: Jeśli \(\displaystyle{ \sigma^i(a)=b}\), to \(\displaystyle{ \sigma^{n!-i}(b)=\sigma^{-i}(b)=\sigma^{-i}(\sigma^i(a))=a}\).
Przechodniość: Jeśli \(\displaystyle{ \sigma^i(a)=b}\) oraz \(\displaystyle{ \sigma^j(b)=c}\), to \(\displaystyle{ \sigma^{i+j}(a)=c}\).

Opisywanie zbiorów mi nie leży. Jeśli \(\displaystyle{ \sigma}\) zapiszemy w postaci rozłącznych cykli, tak, by każdy element był w pewnym cyklu (to znaczy na siłę dopisujemy cykle 1-elementowe choć bo na ogół są one pomijane), to klasy abstrakcji, czyli elementy zbioru ilorazowego, można utożsamić z tymi cyklami. To znaczy np permutacja \(\displaystyle{ (1,2)(4,7,3)}\) zbioru \(\displaystyle{ \{1,...,8\}}\) daje klasy abstrakcji: \(\displaystyle{ (1,2), (4,7,3),(5),(6),(8)}\).

Rozumiem, że w 4. chodzi o liczby Ramsey'a. Wówczas jest to standardowy lemat do tw. Ramseya, dowód jest nietrudny, np. tutaj:

[Student_matmy]

W 6 zadaniu z tego co wiem to są liczby Stirlinga i dla \(\displaystyle{ n \ge 3}\) należy to udowodnić.

[Naed Nitram]

3. W tego typu zadaniach najlepiej skorzystać z zadania \(\displaystyle{ 4}\), inaczej sporo pisania. Chcemy więc pokazać, że:

\(\displaystyle{ 8<R(4,3)\le 10}\).

Najpierw pokazujemy, że \(\displaystyle{ R(3)=R(3,3)=6}\): W pokolorowanym \(\displaystyle{ K_6}\) wybieramy wierzchołek x. Wśród krąwędzi z tego wierzchołka istnieją trzy jednobarwne: xa,xb,xc, powiedzmy czerwone. Albo jedna z krawędzi trójkąta abc, powiedzmy ab, jest czerwona i mamy czerwony trójkąt axb, albo wszystkie są niebieskie i mamy niebieski trójkąt abc. Z kolei jeśli boki pieciokąta pomalujemy na czerwono a przekątne na niebiesko, to nie ma jednobarwnego trójkąta.

Rzecz jasna \(\displaystyle{ R(4,2)=4}\).


Stąd:

\(\displaystyle{ R(4,3)\le R(4,2)+R(3,3)=6+4=10}\).

Wystarczy więc wskazać pokolorowany \(\displaystyle{ K_8}\) bez czerwonych \(\displaystyle{ K_4}\) i bez niebieskich \(\displaystyle{ K_3}\). Tym razem realizujemy \(\displaystyle{ K_8}\) jako sześcian foremny ze wszystkimi krawędziami i przekątnymi. Krawędzie i przekątne sześcianu malujemy na niebiesko, co gwarantuje brak niebieskich trójkątów (przekątne są za długie, żeby być przeciwprostokątnymi w trójkątach o przyprostokątnych długości krawędzi sześcianu). Przekątne ścian natomiast na czerwono, co gwarantuje brak czerwonych \(\displaystyle{ K_4}\), bo wśród dowolnych czterech wierzchołków sześcianu istnieją dwa połączone krawędzią lub przekątną sześcianu.

[Kartezjusz]

8.Pozważmy słowo \(\displaystyle{ 10+4}\)literowe złożone z liter \(\displaystyle{ a}\)i \(\displaystyle{ b}\). Teraz to zadanie można przeformułować.Na ile sposobów można ułożyć to słowo. Isotnie. Jeśli każdą literę \(\displaystyle{ a}\) zamienimy na \(\displaystyle{ +}\), a liczby oznaczają ile jest liter\(\displaystyle{ b}\) przed poszczególnymi literami \(\displaystyle{ a}\). Na ile sposobów można postawić pierwsze\(\displaystyle{ a}\) , na ile drugie...

[Naed Nitram]

6. Lemat: \(\displaystyle{ S(n+1,k)=kS(n,k)+S(n,k-1)}\) dla \(\displaystyle{ k>0}\), o ile położymy \(\displaystyle{ S(0,0)=1}\), \(\displaystyle{ S(m,0)=0}\) dla \(\displaystyle{ m>0}\).

Dowód lematu: Każdą \(\displaystyle{ k}\)-partycję zbioru \(\displaystyle{ (n+1)}\)-elementowego \(\displaystyle{ X}\) z wyróżnionym jednoelementowym blokiem \(\displaystyle{ \{x\}}\) można otrzymać jednoznacznie z \(\displaystyle{ (k-1)}\)-partycji (<- liczba mnoga) zbioru \(\displaystyle{ n}\)-elementowego \(\displaystyle{ X\setminus \{x\}}\). Z kolei dodając do jednego z \(\displaystyle{ k}\) bloków \(\displaystyle{ k}\)-partycji zbioru \(\displaystyle{ X\setminus\{x\}}\) element \(\displaystyle{ x}\), co można wykonać na \(\displaystyle{ k}\) sposobów, otrzymujemy wszystkie \(\displaystyle{ k}\)-partycje zbioru \(\displaystyle{ X}\) nie zawierające bloku \(\displaystyle{ \{x\}}\).

Z lematu mamy:

\(\displaystyle{ S(n,2)=2S(n-1,2)+S(n,1)=2S(n-1,2)+1}\)

skąd \(\displaystyle{ S(n,2)=2^{n-1}-1}\) (najszybciej to przez indukcję pokazać).

Ponownie stosujemy lemat:

\(\displaystyle{ S(n+1,3)=3S(n,3)+S(n+1,2)=3S(n,3)+2^n-1}\).

Mamy więc krok indukcyjny:

\(\displaystyle{ S(n+1,3)=3S(n,3)+2^n-1=3\cdot \left(\frac{1}{2}( 3^{n-1}+1 )- 2^{n-1}\right)+2^n-1=}\)

\(\displaystyle{ =\frac 12\cdot 3^n+\frac 12-2^n=\frac 12(3^n+1)-2^n}\).

[Kartezjusz]

W czwartym Ci się coś pokićkało z texem, bo nie wiem jak rozumieć \(\displaystyle{ G \{ 1 \}}\)

[Student_matmy]

Rzeczywiście, jest tam błąd. Powinno być: \(\displaystyle{ G \setminus \left\{ 1\right\}}\)

[Naed Nitram]

5. Każdą permutację \(\displaystyle{ \sigma}\) można zapisać w postaci rozłącznych. Na mocy zadania 7. cykle te można utożsamić z klasami abstrakcji relacji \(\displaystyle{ \sim}\), czyli orbitami działania \(\displaystyle{ \sigma}\) poprzez lewostronne mnożenie.

Wynikanie w prawo:

Rząd orbity jest dzielnikiem rzędu \(\displaystyle{ \sigma}\) więc każda orbita ma albo \(\displaystyle{ 1}\) albo \(\displaystyle{ p}\) elementów. Jednoelementowych orbit nie ma, bo \(\displaystyle{ \sigma}\) jest nieporządkiem, więc każda orbita ma \(\displaystyle{ p}\) elementów, czyli jest cyklem długości \(\displaystyle{ p}\).

Wynikanie w lewo:

Niech nieporządek \(\displaystyle{ \sigma}\) będzie iloczynem rozłącznych cykli długości \(\displaystyle{ p}\). Niech \(\displaystyle{ x\in S_n}\). Do klasy abstrakcji elementu \(\displaystyle{ x}\), czyli jego orbity przy działaniu \(\displaystyle{ \sigma}\) należą parami różne elementy \(\displaystyle{ x=\sigma^0(x),\sigma(x),\sigma^2(x),...,\sigma^{p-1}(x)}\). Stąd \(\displaystyle{ \sigma^p(x)}\) jest jednym z elementów \(\displaystyle{ \sigma^i(x)}\) dla pewnego \(\displaystyle{ i\in\{0,1,...,p-1\}}\). Wówczas \(\displaystyle{ p|(p-i)}\), czyli \(\displaystyle{ i=0}\) oraz \(\displaystyle{ \sigma^p(x)=x}\). Wobec dowolności wyboru \(\displaystyle{ x}\) mamy więc \(\displaystyle{ \sigma^p=\mathrm{id}}\).

Założenie pierwszości \(\displaystyle{ p}\) jest konieczne dla wynikania w prawo. Przykład \(\displaystyle{ (1\; 2\; 3\; 4)(5\; 6)\in S_6}\).