Suma zbiorów

[arek1357]

Przed chwilą był tu zestawik zadań, które wylądowały w koszu...
I pewnie bym nad tym nie zapłakał, ale czasem lubię pogrzebać w koszu, jak mówi stara sentencja :"prawdziwe skarby znajduje się w koszu"...

Idąc za ciosem przykuło mnie jedno zadanie:

Dany jest zbiór:

\(\displaystyle{ N=\left\{ 1,2,3,...,n\right\} }\)

Pytanie brzmiało ile jest podzbiorów nie zawierających liczb sąsiednich, czyli np: dla :

\(\displaystyle{ N=\left\{ 1,2\right\} }\)

Będzie:

\(\displaystyle{ \left\{ 1\right\} \left\{ 2\right\} }\)

Dla:

\(\displaystyle{ N=\left\{ 1,2,3\right\} }\)

Będzie:

\(\displaystyle{ \left\{ 1\right\} \left\{ 2\right\} \left\{ 3\right\} \left\{ 1,3\right\} }\)

Czyli cztery dla \(\displaystyle{ N=4}\) będzie ich siedem...

I łatwo wyliczyć dla dowolnego \(\displaystyle{ N}\)...

Ale ja troszkę utrudnię to zadanie i sformułuję pytanie tak:

Ile jest rozkładów niezależnych zbioru \(\displaystyle{ N}\) takich, że suma ich daje \(\displaystyle{ N}\) a zbiory są parami rozłączne...

\(\displaystyle{ N= \bigcup_{}^{} A_{i} , A_{i} \cap A_{j}=\emptyset , i \neq j}\)

Oczywiście \(\displaystyle{ A_{i}}\) nie zawierają sąsiadów i nie są zbiorami pustymi....

[kerajs]

czyli np: dla :

\(\displaystyle{ N=\left\{ 1,2\right\} }\)

Będzie:

\(\displaystyle{ \left\{ 1\right\} \left\{ 2\right\} }\)

Dla:

\(\displaystyle{ N=\left\{ 1,2,3\right\} }\)

Będzie:

\(\displaystyle{ \left\{ 1\right\} \left\{ 2\right\} \left\{ 3\right\} \left\{ 1,3\right\} }\)

Czyli cztery dla \(\displaystyle{ N=4}\) będzie ich siedem...

I łatwo wyliczyć dla dowolnego \(\displaystyle{ N}\)...

Wzorując się na powyższej metodzie masz:
czyli np: dla :

\(\displaystyle{ N=\left\{ 1,2\right\} }\)

Będzie:

\(\displaystyle{ \left( \left\{ 1\right\} , \left\{ 2\right\} \right) }\)

Dla:

\(\displaystyle{ N=\left\{ 1,2,3\right\} }\)

Będzie:

\(\displaystyle{ \left( \left\{ 1,3\right\}, \left\{ 2\right\} \right), \left( \left\{ 1\right\} , \left\{ 2\right\} , \left\{ 3\right\} \right) }\)

Czyli cztery dla \(\displaystyle{ N=4}\) będzie ich pięć...

I łatwo wyliczyć dla dowolnego \(\displaystyle{ N}\)...

[arek1357]

Dla N=5 będzie 15 a jaki będzie ogólny wzór?

[kerajs]

Po raz kolejny się przekonuję, iż nie potrafię żartować.

Poważna odpowiedź na poważne pytanie to:
\(\displaystyle{ a_n= \sum_{k=0}^{n} \left\{ ^n _k \right\} }\)

[arek1357]

Przepraszam ale coś nie tak:

Tych rozkładów dla:

np: \(\displaystyle{ N=1}\)

\(\displaystyle{ \left\{ 1\right\} }\)

Jeden rozkład,

np: \(\displaystyle{ N=2}\) mamy:

\(\displaystyle{ \left\{ 1\right\} \left\{ 2\right\} }\) - czyli też jeden rozkład...


Dla: \(\displaystyle{ N=3}\)

\(\displaystyle{ \left\{ 1\right\} \left\{ 2\right\} \left\{ 3\right\} }\)

\(\displaystyle{ \left\{ 1,3\right\} \left\{ 2\right\} }\) - czyli dwa rozkłady


Dla:\(\displaystyle{ N=4}\)

\(\displaystyle{ \left\{ 1\right\} \left\{ 2\right\} \left\{ 3\right\} \left\{ 4\right\} }\)

\(\displaystyle{ \left\{ 1,3\right\} \left\{ 2,4\right\} }\)

\(\displaystyle{ \left\{ 1,3\right\} \left\{ 2\right\} \left\{ 4\right\} }\)

\(\displaystyle{ \left\{ 1\right\} \left\{ 3\right\} \left\{ 2,4\right\} }\)

\(\displaystyle{ \left\{ 1,4\right\} \left\{ 2\right\} \left\{ 3\right\} }\)

czyli pięć rozkładów...

I tak dalej...

dla: \(\displaystyle{ N=5}\) wychodzi mi \(\displaystyle{ 15}\) rozkładów...

Więc coś mi się tu nie zgadza...

[kerajs]

A konkretnie, to co się nie zgadza?
1, 2, 5, 15, 52, 203, 877, 4140, ....

[arek1357]

\(\displaystyle{ a_{3}=\left\{\begin{array}{l} 3\\0 \end{array}\right\}+\left\{\begin{array}{l} 3\\1 \end{array}\right\}+\left\{\begin{array}{l} 3\\2 \end{array}\right\}+\left\{\begin{array}{l} 3\\3 \end{array}\right\}=0+1+3+1=5}\)

a:

\(\displaystyle{ a_{3}=2}\)

\(\displaystyle{ \left\{ 1\right\} \left\{ 2\right\} \left\{ 3\right\} }\)

\(\displaystyle{ \left\{ 1,3\right\} \left\{ 2\right\} }\)

Tam chyba powinno być o jeden przesunięcie ?

\(\displaystyle{ a_{n}}\) to będzie rozkład dla \(\displaystyle{ n+1}\)

A czemu zaczynasz od zera?

\(\displaystyle{ \left\{\begin{array}{l} n\\0 \end{array}\right\}=0}\)

Dodano po 7 minutach 1 sekundzie:
Bo poza tym wygląda ok ładnie...

[kerajs]

Fakt, mea culpa.
Miałem mało czasu i tak się skupiłem jak znaleźć (co się mi nie udało) lub sensownie zapisać (co także się nie udało) symbol liczb Stirlinga, że zapomniałem o jedynce. Miało być:
\(\displaystyle{ a_{n+1}= \sum_{k=0}^{n} \left\{{\begin{matrix}n\\k\end{matrix}}\right\} }\)
Sorki.

[arek1357]

Tak wszystko hula fajnie ale wytłumacz mi czemu zaczynasz od zera?

Dodano po 4 minutach 18 sekundach:
Jednak sprawdziła się moja teza że prawdziwe diamenty matematyki znajduje się w koszu, problem jest fajny, wzór też, ale cały post był olany przez moderację. W Piśmie jednak pisze: "Kamień odrzucony przez budujących stał się kamieniem węgielnym"...