Multisæt

Et multisæt er en modifikation af konceptet for et sæt , der tillader inklusion af det samme element i en samling flere gange. Antallet af elementer i et multisæt, under hensyntagen til gentagne elementer, kaldes dets størrelse eller styrke .

Ideen om et multisæt er implicit blevet brugt siden antikken ( Knuth citerer eksemplet med Bhaskara II fra det 12. århundrede, som studerede permutationer af multisæt), men introduktionen af konceptet og fikseringen af udtrykket tilskrives de Bruijn (1970'erne) [1] . Anvendes hovedsageligt i applikationer ( datalogi , kunstig intelligens , beslutningsteori ), når det anvendes på teorien om Petrinets, kaldes et multisæt et sæt [2] . Forskellige applikationer bruger forskellig notation.

Formelt defineres et multisæt på et sæt som et ordnet par , hvor er en funktion , der tildeler hvert element i mængden et naturligt tal , kaldet multipliciteten af dette element. $EN$ $(Er)$ $m \colon A \to \mathbb{N}$ $EN$

Et af de enkleste eksempler er multisættet af primfaktorer for et heltal. Så for eksempel har nedbrydningen af tallet 120 i primfaktorer formen: , så dets multisæt af primtalsdivisorer er . $120=2^{3}3^{1}5^{1}$ $\{2, 2, 2, 3, 5\}$

Et andet eksempel er multisæt af rødder i en algebraisk ligning . For eksempel har ligningen rødder . $x^3 - 5x^2 + 8x - 4 = 0$ $\{1, 2, 2\}$

Antallet af forskellige kardinalitetsmultisæt bestående af elementer valgt fra kardinalitetssættet kan beregnes ud fra følgende formel som en binomial koefficient : $k$ $n$

{n+k-1 \vælg k}

Noter

↑ Donald Knuth . The Art of Computer Programming, bind 2. De resulterende algoritmer = The Art of Computer Programming, vol.2. Seminumeriske algoritmer. - 3. udg. - M. : Williams, 2007. - S. 832. - ISBN 0-201-89684-2 .
↑ James Peterson. Oversigt over kitteori // Petri Net Theory and The Modeling of Systems. - M .: Mir , 1984. - S. 231-235. — 264 s. - 8400 eksemplarer.

Litteratur

A. B. Petrovsky. Mellemrum af sæt og multisæt . - M. : Redaktionel URSS, 2003. - S. 248. - ISBN 5-7262-0633-9 .