Tælleprocedurer

Tælleprocedurer er metoder til at bestemme antallet af elementer i en mængde eller antallet af måder et givent problem kan udføres. De anvendes i diskret matematik, kombinatorik og datalogi til at tælle objekter, udlede sandsynligheder og analysere algoritmers kompleksitet. Hovedideen er at udnytte strukturer og regler, der gør tælling muligt uden at liste alle løsninger.

De grundlæggende principper om tælling omfatter additivt princip og multiplikativt princip. Det additive princip siger, at hvis to muligheder er gensidigt udelukkende, er det samlede antal muligheder summen af de enkelte muligheder. Det multiplikative princip siger, at hvis en proces består af uafhængige trin og hvert trin har et antal muligheder, så er det samlede antal muligheder produktet af mulighederne i hvert trin.

Vigtige teknikker inkluderer partitionering af problemet i mindre dele, brug af rekursioner og rekursionsrelationer, samt anvendelse af binomialkoefficienter og kombinationer. Genererende funktioner og inklusions-eksklusions-princippet er centrale værktøjer. Specifikke tælleprocedurer som stjerner og stænger hjælper f.eks. med at tælle ikke-negative løsninger til ligninger, og tælling af subsets ved hjælp af binomialkoefficienter giver antallet af mulige udvalg.

I praksis kan tælling ske ved direkte bevis, rekonstruktion af konstruktioner, ved dynamisk programmering eller ved probabilistiske metoder som Monte Carlo-sampling til approksimativ tælling.

Eksempler: Antallet af underudvalg af en mængde med n elementer er 2^n; antallet af måder at vælge k elementer ud af n er binomialkoefficienten C(n,k); antallet af monotone lattice-stier fra (0,0) til (a,b) er antal positioner for skridt, hvilket også beregnes som C(a+b,a). Tælleprocedurer er grundlæggende i statistik, algoritmeanalyse og kombinationsforskning.