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.

Gammel Putnam

Innlegg Gustav » 03/07-2019 22:48

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$$
Beware of the Ratmen during the full moon for they grow stronger as the moon gets fuller
Gustav offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 4276
Registrert: 12/12-2008 12:44

Re: Gammel Putnam

Innlegg mingjun » 29/07-2019 16:34

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$
mingjun offline
Cayley
Cayley
Innlegg: 91
Registrert: 18/11-2016 21:13
Bosted: Det projektive planet

Hvem er i forumet

Brukere som leser i dette forumet: Ingen registrerte brukere og 5 gjester