Matematyka.pl

całkiem fajne zadanko

\(\displaystyle{ P_n}\) jest zbiorem podzbiorów \(\displaystyle{ \{1,2,...,n\}}\).
\(\displaystyle{ c(n,m)}\) jest liczbą funkcji \(\displaystyle{ f: \ P_n \to \{1,2,...,m\}}\) spełniających \(\displaystyle{ f(A \cap B)=\min (f(A),f(B))}\)

wersja trudniejsza: wyznacz \(\displaystyle{ c(n,m)}\)
wersja oryginalna: udowodnij że \(\displaystyle{ c(n,m)=}\) Powodzenia i miłej zabawy

Ale ja tu czegoś nie rozumiem załóżmy że n=6
A={1,2} B={3,4}
A1={3,4} B1={5,6}

czyli f(A*B)=f(pusty)=min(f(A),f(B))

oraz: f(A1*B1)=f(pusty)=min(f(A1),f(B1))

No i co z tego ? : >

Właśnie co z tego czy nic czy ma to jakoweś konsekwencje bo śmiem przypuszczać że może się zdarzyć , że f(pusty) może przybrać kilka wartości a czy to będzie dalej funkcja ??
a jak nie przybierze to co wtedy???

Oczywiście pociąga to jakieś konsekwencje, ale nie czyni zadania źle sformułowanym ani nic w tym stylu

arek1357 pisze:Właśnie co z tego czy nic czy ma to jakoweś konsekwencje bo śmiem przypuszczać że może się zdarzyć , że f(pusty) może przybrać kilka wartości a czy to będzie dalej funkcja ??
a jak nie przybierze to co wtedy???

bo właśnie o to chodzi w zadaniu aby zliczyć tylko te funkcje w których nie mamy żadnych "podwójnych wartości"

tak znaczy że albo f nie jest funkcją albo będzie stałą dla każdego argumentu?

wiesz, zamiast zaśmiecać temat takimi głupotami może wczytaj się porządnie w treść zadania

Hmm jeśli moje pytania uważasz za głupoty to gratulacje i dziękuję za jasną odpowiedź pozdrawiam...

arek1357 - gdybyś w przedostatnim swoim poście napisał na końcu "?" zamiast "!!!!", to Dumel raczej inaczej by Ciebie odebrał - po co krzyczeć?

no to przykład:
weźmy m=2 i n=3
f({1,2,3})=f({2,3})=2
f(pozostałe)=1

Pomyślałem trochę i napiszę o moich spostrzeżeniach jak to widzę więc:
Najpierw zauważmy , że dla podzbiorów jednoelementowych a więc przecięcie puste, wartości na tych podzbiorach muszą być co najwyżej dwie np jeśli f(pusty)=a to:
f(A1)=f(A2)=.....j , gdzie j=a lub b i a<b ,oraz b występuje co najwyżej 1 raz , Ai- jednoelementowe
zresztą dorzucę tabelkę reprezentującą te funkcje dla n=2 i m=2 ...
\(\displaystyle{ \ \ I \ \ \ \ II \ \ \ \ \ \ \ \ III }\)

\(\displaystyle{ \emptyset \ | \ \lbrace 1 \rbrace \ \lbrace 2 \rbrace \ | \ \lbrace 1,2 \rbrace}\)
\(\displaystyle{ 1 \ | \ 1 \ \ \ \ 1 \ \ \ | \ \ \ \ \ 1}\)
\(\displaystyle{ 1 \ | \ 1 \ \ \ \ 1 \ \ \ | \ \ \ \ \ 2}\)
\(\displaystyle{ 1 \ | \ 2 \ \ \ \ 1 \ \ \ | \ \ \ \ \ 2}\)
\(\displaystyle{ 1 \ | \ 1 \ \ \ \ 2 \ \ \ | \ \ \ \ \ 2}\)
\(\displaystyle{ 2 \ | \ 2 \ \ \ \ 2 \ \ \ | \ \ \ \ \ 2}\)

na dole mamy wszystkie możliwe funkcje wypisane w wierszach spełniające warunki naszego zadania
dla n=2,m=2.
widać ,że ilość tych funkcji c(n,m)=5=1*1+2*2 co się zgadza.
Będziemy teraz zwiększać m a n zostanie =2.
dla m=3 mamy zbiór wartości={1,2,3}.
tabelkę podzieliłem na kolumny(Panele I,II,III) żeby było łatwiej obserwować wartości funkcji...

Spróbujmy teraz zliczać funkcje ,Zobaczmy ,że funkcji przyjmujących pojedyncze wartości ,
a więc (1), (2) jest dwie-2 , funkcji przyjmujących dwie wartości ,a więc(1,2) jest trzy -3
co da nam wyrażenie:
2*1+1*3=5
a teraz połóżmy: m=3 czyli zbiór wartości wynosi: {1,2,3}

I znowu dzielmy wszystkie funkcje na klasy , te co przyjmują jedną wartość a więc (1), (2), (3)
dwie wartości (1,2) (1,3) (2,3), i te co przyjmują 3 wartości (1,2,3)
co będzie:

3*1+3*3+1*2=14, analogicznie dla m=4 postępujemy itd...
Zauważmy jeszcze, że w tym przypadku funkcja nie może na raz przyjmować więcej nić 3 wartości
a więc dla m=4 mamy:

4*1+6*3+4*2=30 lu jak kto woli:

\(\displaystyle{ {4\choose 1}*1 +{4\choose 2}*3+ {4\choose 3}*2=30}\)
dla n=5 będzie:

\(\displaystyle{ {5\choose 1}*1 +{5\choose 2}*3+ {5\choose 3}*2=55}\)

Oczywiście czwarty składnik i dalsze się zerują łatwo zauważyć ,że będzie się zgadzać ze wzorem
co nawet indukcyjnie dowiedzie...że będzie to równe:

\(\displaystyle{ 1^{2}+2^{2}+3^{2}+4^{2}+5^{2}+.....}\)

Teraz można kontynuować ze względu na n...

-- 27 grudnia 2009, 16:27 --

Jeśli ustalimy m=2 i będziemy zwiększać n dla n=2 jest ilość funkcji 5 , dla n=3

mamy taką tabelkę:

0 | {1} {2} {3} | {1,2} {1,3} {2,3} | {1,2,3}
1 | 1 1 1 | 1 1 1 | 1
1 | 1 1 1 | 1 1 1 | 2
1 | 2 1 1 | 2 2 1 | 2
1 | 1 2 1 | 2 1 2 | 2
1 | 1 1 2 | 1 2 2 | 2
1 | 1 1 1 | 2 1 1 | 2
1 | 1 1 1 | 1 2 1 | 2
1 | 1 1 1 | 1 1 2 | 2
2 | 2 2 2 | 2 2 2 | 2

I ilość funkcji wynosi 9 co zgadza się ze wzorem bo:

\(\displaystyle{ 1^{3} +2^{3}=9}\)

-- 27 grudnia 2009, 16:30 --

Troszkę pierwszy wiersz się przesunął w prawo

-- 27 grudnia 2009, 16:58 --

łatwo sprawdzić że dla m=2 i zwiększając n, ilość funkcji będzie się zwiększać rekurencyjnie w stosunku do poprzedniego n, mianowicie:

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

co też zgodne jest ze wzorem:

\(\displaystyle{ 1^{n}+2^{n}}\)-- 27 grudnia 2009, 17:01 --Oczywiście to nie żaden ścisły dowód tylko próba przybliżenia (obłaskawienia) treści zadania oraz
dalszego wyciągania wniosków