Gammel Putnam

Her kan brukere av forum utfordre hverandre med morsomme oppgaver og nøtter man ønsker å dele med andre. Dette er altså ikke et sted for desperate skrik om hjelp, de kan man poste i de andre forumene, men et sted for problemløsing på tvers av trinn og fag.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

La $P_n$ være mengden av delmengder av $\{1,2,...,n\}$. La $c(n,m)$ være antallet funksjoner $f:P_n\to \{1,2,...,m\}$ slik at $f(A\cap B)=\min \{f(A),f(B)\}$.

Vis at $$ c(n,m)=\sum_{j=1}^m j^n$$
mingjun
Cayley
Cayley
Innlegg: 91
Registrert: 18/11-2016 21:13
Sted: Det projektive planet

La $P'=\left\{S|S\in P_n,|S|=n-1\right\}$. Vi starter med observasjonen at $f$ er unikt bestemt av verdiene til $f(S), S\in P'$ samt $f\left(\left\{1,2,\dots,n\right\}\right)$. Det er fordi enhver mengde i $P_n$ med størrelse mindre enn $n$ kan uttrykkes som et unikt snitt mellom mengder i $P'$, og at $$f(S_1\cap S_2 \cap \dots \cap S_k)=\min\left(f(S_1),f(S_2 \cap \dots \cap S_k)\right)=\dots =\min\left(f(S_1),f(S_2),f(S_3),\dots,f(S_k)\right).$$ Man kan overbevise seg selv om at den genererte $f$ stemmer overens med definisjonene pga de gitte grunnene.

Nå trenger vi kun å telle antall gyldige verdier $f(S), S\in P'$ og $f\left(\left\{1,2,\dots,n\right\}\right)$. Den eneste måten et sett verdier ikke kan være gyldige på er hvis $f\left(\left\{1,2,\dots,n\right\}\right)<f(S), S\in P'$, ettersom snittet av de to mengdene er nøyaktig $S$ og vi får $f(S)=f(\left(\left\{1,2,\dots,n\right\}\cap S\right)=\min\left(f\left(\left\{1,2,\dots,n\right\}\right),f(S)\right)=f\left(\left\{1,2,\dots,n\right\}\right)<f(S)$. Dermed har vi at for hver verdi av $f\left(\left\{1,2,\dots,n\right\}\right)$, må $f(S)$ være ikke større enn nevnte verdi. Følgelig kan vi summere over alle mulige verdier av $j:=f\left(\left\{1,2,\dots,n\right\}\right)$ : $$c\left(n,m\right)=\sum_{j=1}^{m} j^n,$$ siden det er $n$ elementer i $P'$. $\blacksquare$
Svar