tellemetoder
Tellemetoder er en gren av kombinatorikk som handler om å bestemme hvor mange ulike objekter eller utfall som kan oppstå i et gitt problem uten å telle dem manuelt. De brukes ofte i sannsynlighet, statistikk, og i design av algoritmer der man ønsker å vite hvor mange muligheter som finnes.
De grunnleggende prinsippene er addisjonsprinsippet og multiplikasjonsprinsippet. Addisjonsprinsippet sier at hvis et problem kan løses på
Vanlige tellemetoder inkluderer:
- Permutasjoner: antall ordnede utvalg. Uten gjentakelser: P(n,k) = n!/(n-k)!. Med gjentakelser: n^k for sekvenser av lengde k
- Kombinasjoner: antall uordnede utvalg. Uten repetisjon: C(n,k) = n!/(k!(n-k)!). Med repetisjon: C(n+k-1, k).
- Stjerner og streker (stars and bars): fordelinger av r identiske objekter i n bokser, ofte uttrykt
- Inkludering-ekskludering: tellemetode som håndterer overlapp mellom grupper.
- Generating functions og rekursjon: mer avanserte teknikker for komplekse telleproblem.
Anvendelser inkluderer beregning av sannsynligheter, analyse av datamønstre, og løsning av problems som krever forståelse av