Multiset - Multiset

Жылы математика, а мультисет (немесе сөмке, немесе mset) а тұжырымдамасының модификациясы болып табылады орнатылды бұл, жиынтықтан айырмашылығы, оның әрқайсысы үшін бірнеше даналарға мүмкіндік береді элементтер. Әр элемент үшін берілген даналардың оң санының саны деп аталады көптік бұл элементтің мультисистемадағы. Нәтижесінде тек элементтерден тұратын мультисеталардың шексіз саны бар $а$ және $б$ , бірақ олардың элементтерінің көптігі бойынша өзгереді:

Жинақ ${а, б}$ тек элементтерден тұрады $а$ және $б$ , әрқайсысының көбейтіндісі 1 болғанда ${а, б}$ мультисет ретінде көрінеді.
Мультисет ${а, а, б}$ , элемент $а$ көбейтіндісі 2, және $б$ еселікке ие 1.
Мультисет ${а, а, а, б, б, б}$ , $а$ және $б$ екеуінде де еселік бар 3.

Бұл нысандардың барлығы бірдей, дегенмен мультисисеталар ретінде қарастырылған кезде әр түрлі болады орнатылды, өйткені олардың барлығы бірдей элементтерден тұрады. Жиынтықтардағы сияқты, және керісінше кортеждер, мультисөлелерді дискриминациялау кезінде тәртіптің маңызы жоқ, сондықтан ${а, а, б}$ және ${а, б, а}$ бірдей мультисультті белгілеңіз. Жиындар мен мультисездерді ажырату үшін кейде төртбұрышты жақшаларды қамтитын белгі қолданылады: мультисет ${а, а, б}$ деп белгілеуге болады $[а, а, б]$ .^[1]

The түпкілікті мультисет оның барлық элементтерінің еселіктерін қосу арқылы құрылады. Мысалы, мультисистемада ${а, а, б, б, б, c}$ мүшелердің көптігі $а$ , $б$ , және $c$ сәйкесінше 2, 3 және 1 болып табылады, демек, бұл мультисететтің мәні 6-ға тең.

Николас Говерт де Брюйн сөзді ойлап тапты мультисет сәйкес, 1970 жылдары Дональд Кнут.^[2]^:694Алайда, мультисездер ұғымын қолдану сөздің ақша айналымынан бұрын пайда болды мультисет ғасырлар бойы. Кнуттың өзі мультисистемаларды алғашқы зерттеуді үнді математигіне жатқызады Бхаркарахария, ол шамамен 1150-ге жуық мультисеталардың ауыстырылуын сипаттады. Кнут сонымен бірге осы тұжырымдама үшін ұсынылған немесе пайдаланылған басқа атауларды, соның ішінде тізім, шоқ, сөмке, үйінді, үлгі, өлшенген жиынтық, коллекция, және люкс.^[2]^:694

Тарих

Уэйн Близард мультисисеттерді сандардың шығу тарихына дейін іздеп, «ежелгі уақытта бұл сан n жиынтығымен жиі ұсынылды n соққылар, сандық белгілер немесе бірліктер ».^[3] Заттардың осы және сол сияқтылар коллекциясы көпөлшемді болып табылады, өйткені соққылар, сандық белгілер немесе бірліктер ажыратылмайтын болып саналады. Бұл адамдар математиканың пайда болуынан бұрын да мультисистемаларды жанама түрде қолданғанын көрсетеді.

Бұл құрылымның практикалық қажеттіліктері әдебиеттерде әртүрлі атаулармен көрінетін мультисистемаларды бірнеше рет қайта ашуға мәжбүр етті.^[4]^:323 Мысалы, олар ерте жасанды интеллект тілдерінде маңызды болды, мысалы QA4, олар аталған жерде сөмкелер, Питер Дойчқа қатысты термин.^[5] Сондай-ақ, мультисет агрегат, үйінді, шоғыр, үлгі, өлшенген жиынтық, пайда болу жиыны және өрт сөндіру қондырғысы деп аталады (ақырғы элементтер жиынтығы).^[4]^:320^[6]

Мультисеталар ежелгі дәуірден бастап қолданылғанымен, олардың айқын зерттелуі кейінірек болды. Мультисет туралы алғашқы белгілі зерттеу үнді математигіне жатады Бхаркарахария шамамен 1150, ол мультисөлелердің ауыстырылуын сипаттады.^[2]^:694 Жұмысы Мариус Низолий (1498–1576) мультисиздер тұжырымдамасына тағы бір ерте сілтеме бар.^[7] Афанасий Кирхер бір элементті қайталауға болатын мультисеторлы ауыстырудың санын тапты.^[8] Жан Престет 1675 жылы мультисеталды ауыстырудың жалпы ережесін жариялады.^[9] Джон Уоллис бұл ережені 1685 жылы толығырақ түсіндірді.^[10]

Мультисеталар жұмысында айқын пайда болды Ричард Дедекинд.^[11]^:114^[12]

Басқа математиктер 20-ғасырда мультисисеттерді рәсімдеп, оларды нақты математикалық құрылым ретінде зерттей бастады. Мысалы, Уитни (1933) сипаттады жалпыланған жиынтықтар («жиындар» кімнің сипаттамалық функциялар кез келген бүтін санды қабылдай алады - оң, теріс немесе нөл).^[4]^:326^[13]^:405 Монро (1987) зерттеді санат Мул а анықтайтын мультисеталар және олардың морфизмдері мультисет элементтер арасындағы эквиваленттік қатынасы бар жиын ретінде «бірдей сұрыптау«және а морфизм құрметтейтін функция ретінде мультисеталар арасында сорттары. Ол сондай-ақ а көп санды: функция f (x) мультисететтен натурал сандарға дейін көптік элемент х мультисетінде. Монро мультисет және көпсандық ұғымдары көбінесе әр түрлі болады, дегенмен екеуі де пайдалы деп тұжырымдады.^[4]^:327–328^[14]

Мысалдар

Қарапайым және табиғи мысалдардың бірі - бұл мультисет қарапайым санның факторлары $n$ . Мұнда элементтердің негізгі жиынтығы жай сандар жиыны болып табылады бөлгіштер туралы $n$ . Мысалы, нөмір 120 бар қарапайым факторизация

{ displaystyle 120 = 2 ^ {3} 3 ^ {1} 5 ^ {1}}

бұл мультисет береді ${2, 2, 2, 3, 5}$ .

Осыған байланысты мысал - алгебралық теңдеу шешімдерінің көп жиынтығы. A квадрат теңдеу, мысалы, екі шешім бар. Алайда, кейбір жағдайларда олардың саны бірдей. Осылайша, теңдеудің шешімдерінің көпжосары болуы мүмкін ${3, 5}$ , немесе болуы мүмкін ${4, 4}$ . Екінші жағдайда оның еселік шешімі бар. 2. Жалпы алғанда алгебраның негізгі теоремасы деп бекітеді күрделі а шешімдері көпмүшелік теңдеу дәрежесі $г.$ әрдайым кардиналдылықтың көпсалалығын құрайды $г.$ .

Жоғарыда айтылғандардың ерекше жағдайы болып табылады меншікті мәндер көбейтіндісі көбінесе олардың түбірлері ретінде олардың көптігі ретінде анықталатын матрицаның тән көпмүшелік. Сонымен, меншікті мәндер үшін тағы екі еселіктер табиғи түрде анықталады, олардың еселіктері-нің түбірі ретінде минималды көпмүшелік, және геометриялық еселік ретінде анықталады өлшем ядросының $A - λМен$ (қайда $λ$ матрицаның өзіндік мәні болып табылады $A$ ). Бұл үш еселік әр түрлі болуы мүмкін үш мәнді жеке меншікті анықтайды: Келіңіздер $A$ болуы а $n \times n$ матрица Иордания қалыпты формасы бір меншікті мәні бар. Оның көптігі $n$ , оның минималды көпмүшенің түбірі ретіндегі еселігі ең үлкен Джордан блогының өлшемі, ал геометриялық еселігі - Иордан блоктарының саны.

Анықтама

A мультисет формальды түрде 2- ретінде анықталуы мүмкінкортеж $(A, м)$ қайда $A$ болып табылады негізгі жиынтық оның ерекше элементтерінен пайда болған мультисет, және ${ displaystyle m қос нүкте A -дан mathbb {N} _ { geq 1}}$ Бұл функциясы бастап $A$ жиынтығына оң бүтін сандар, беру көптік, яғни элементтің пайда болу саны $а$ сан ретінде мультисет $м (а)$ .

Функцияны ұсыну $м$ оның көмегімен график, бұл жиынтығы жұптарға тапсырыс берді ${ displaystyle left { left (a, m сол (a right) right): a in A right },}$ мультисет жазуға мүмкіндік береді ${а, а, б}$ сияқты $({а, б}, {(а, 2), (б, 1)})$ және мультисет ${а, б}$ сияқты $({а, б}, {(а, 1), (б, 1)})$ . Алайда бұл белгілер жиі қолданылмайды және ықшам белгілер қолданылады.

Егер ${ displaystyle A = {a_ {1}, ldots, a_ {n} }}$ Бұл ақырлы жиынтық, мультисет $(A, м)$ ретінде ұсынылады

{ displaystyle left {a_ {1} ^ {m (a_ {1})}, ldots, a_ {n} ^ {m (a_ {n})} right }, quad}

кейде жеңілдетілген

{ displaystyle quad a_ {1} ^ {m (a_ {1})} cdots a_ {n} ^ {m (a_ {n})},}

мұнда 1-ге тең жоғарғы индекстер алынып тасталады. Мысалы, multiset {а, а, б} жазылуы мүмкін ${ displaystyle {a ^ {2}, b }}$ немесе ${ displaystyle a ^ {2} b.}$ Егер мультисет элементтері сандар болса, қарапайыммен шатасуы мүмкін арифметикалық амалдар, әдетте оларды контекстен шығаруға болады. Екінші жағынан, соңғы белгілер қарапайым факторизация оң бүтін сан - деп көрсетілгендей, ерекше анықталған мультисет арифметиканың негізгі теоремасы. Сондай-ақ, а мономиялық болып табылады анықталмайды.^{[қосымша түсініктеме қажет ]}

Мультисет кәдімгі жиынтыққа сәйкес келеді, егер әр элементтің еселігі бір болса (кейбір үлкен натурал санға қарағанда). Ан индекстелген отбасы, $(а мен) мен Мен$ , қайда $мен$ кейбір индекстерге сәйкес өзгереді Мен, мультисетені анықтауы мүмкін, кейде жазылған ${а мен}$ . Бұл көріністе мультисететтің негізгі жиынтығы сурет отбасы, және кез-келген элементтің көптігі $х$ - индекс мәндерінің саны $мен$ осындай ${ displaystyle a_ {i} = x}$ . Бұл мақалада еселіктер ақырлы болып саналады, яғни бірде-бір элемент отбасында шексіз көп кездеспейді: тіпті шексіз көпжоспарда да еселіктер ақырлы сандар болып табылады.

Жеке элементтердің көптігі натурал сандардың орнына шексіз кардинал болуға мүмкіндік беру арқылы мультисет анықтамасын кеңейтуге болады, бірақ барлық қасиеттер бұл жалпылауға көшпейді.

Негізгі қасиеттері мен әрекеттері

Мультисет элементтері негізінен бекітілген жиынтықта алынады $U$ , кейде а деп аталады ғалам, бұл әдетте жиынтығы натурал сандар. Элементі $U$ берілген көпжоспарға жатпайтын, бұл көпжоспарда 0-ге еселік болады делінеді. Бұл мультисететтің еселік функциясын бастап функциясына дейін кеңейтеді $U$ жиынтыққа ${ displaystyle mathbb {N}}$ туралы теріс емес бүтін сандар. Бұл осы функциялар мен олардың элементтері бар мультисездер арасындағы сәйкестікті анықтайды $U$ .

Бұл кеңейтілген көбейту функциясы әдетте жай деп аталады көп функцияжәне элементтері бар әлем бекітілген кезде мультисиздерді анықтау үшін жеткілікті. Бұл еселік функция - жалпылау индикатор функциясы ішкі жиыны және кейбір қасиеттерін онымен бөліседі.

The қолдау мультисет ${ displaystyle A}$ ғаламда $U$ мультисистеманың негізгі жиынтығы болып табылады. Көптік функциясын қолдану ${ displaystyle m}$ , ретінде сипатталады

{ displaystyle operatorname {Supp} (A): = left {x in U mid m_ {A} (x)> 0 right }}

.

Мультисет ақырлы егер оның қолдауы шектеулі болса, немесе оның баламасы, егер оның түпнұсқалығы болса

{ displaystyle | A | = sum _ {x in operatorname {Supp} (A)} m_ {A} (x) = sum _ {x in U} m_ {A} (x)}

ақырлы. The бос мультисет бұл бос тірегі бар бірегей мультисет (негізгі жиынтық), демек 0 мәні бар.

Жиындардың кәдімгі операциялары ішкі жиындылар үшін индикатор функциясын қолдану сияқты көп функция функциясын қолдану арқылы мультисездерге таралуы мүмкін. Келесіде, $A$ және $B$ берілген ғаламдағы көп өлшемді болып табылады $U$ , еселік функцияларымен ${ displaystyle m_ {A}}$ және ${ displaystyle m_ {B}.}$

Қосылу: $A$ енгізілген $B$ , деп белгіленді $A \subseteq B$ , егер

{ displaystyle forall x in U, m_ {A} (x) leq m_ {B} (x).}

Қиылыс: The қиылысу (кейбір контексттерде деп аталады шексіз немесе ең үлкен ортақ бөлгіш) of $A$ және $B$ мультисет $C$ еселік функциясы бар

{ displaystyle m_ {C} (x) = min (m_ {A} (x), m_ {B} (x)) quad forall x in U})

Одақ: The одақ (кейбір контексттерде деп аталады максимум немесе ең төменгі ортақ еселік) of $A$ және $B$ мультисет $C$ еселік функциясы бар

{ displaystyle m_ {C} (x) = max (m_ {A} (x), m_ {B} (x)) quad forall x in U})

^{[дәйексөз қажет ]}

Қорытынды: мультисездердің қосындысын жалпылама ретінде қарастыруға болады бірлескен одақ жиындар, және анықталады

{ displaystyle m_ {C} (x) = m_ {A} (x) + m_ {B} (x) quad for all x in U.}

Қосынды а анықтайды коммутативті моноид берілген әлемдегі ақырлы мультисисеттердегі құрылым. Бұл моноид - а тегін коммутативті моноид, ғаламның негізі ретінде.

Екі мультисет бөлу егер олардың тіректері болса бөлінбеген жиынтықтар. Бұл олардың қиылысы бос мультисет немесе олардың қосындысы олардың қосылуына тең дегенге тең.

Ақырлы көпжақтылардың кіру-алып тастау қағидасы бар (жиындарға арналғанға ұқсас), бұл ақырлы көпжақтылардың ақырлы қосындысы екі жиынтықтың қосындысының айырымы екенін айтады: бірінші қосындыда тақ санының барлық мүмкін қиылыстарын қарастырамыз берілген мультисет, ал екінші қосындыда біз берілген мультисисстің жұп санының барлық мүмкін қиылыстарын қарастырамыз.^{[дәйексөз қажет ]}

Мультисездерді санау

Биекция 7 жиынтықтың 3 ішкі жиыны арасында (сол жақта)
және 5-жиынтықтан (оң жақта) элементтері бар 3-мультисет
Демек, бұл осыны көрсетеді

{ displaystyle textstyle {7 select 3} = left (! ! {5 3} ! ! right таңдаңыз)}

.

Кардиналдың мульти-жиынтығы $к$ , элементтермен бірге кардиналдың ақырғы жиынтығынан алынған $n$ , деп аталады мультисет коэффициенті немесе мультисет нөмірі. Бұл санды кейбір авторлар осылай жазады ${ displaystyle textstyle left (! ! {n k} ! ! right таңдаңыз)}$ , дегенге ұқсайтын жазба биномдық коэффициенттер; ол мысалы, (Стэнли, 1997 ж.) қолданылған және айтылуы мүмкін « $n$ көп түсті $к$ «ұқсау» $n$ таңдау $к$ « үшін ${ displaystyle { tbinom {n} {k}}}$ . Биномдық коэффициенттерден айырмашылығы, көпжақты коэффициенттер пайда болатын «көпжоспарлы теорема» жоқ және оларды өзара байланысты емес деп шатастыруға болмайды. көп мәнді коэффициенттер кездеседі көпнұсқалық теорема.

Көп өлшемді коэффициенттердің мәнін нақты түрде беруге болады

{ displaystyle left (! ! {n k} ! ! right) = {n + k-1 k} = { frac {(n + k-1) таңдаңыз!} {k ! , (n-1)!}} = {n (n + 1) (n + 2) cdots (n + k-1) k үстінен!},}

мұндағы екінші өрнек биномдық коэффициент түрінде; көптеген авторлар нақты белгілерден қашады және биномдық коэффициенттерді жазады. Сонымен, мұндай мультисеттер саны кардиналдың ішкі жиындарының санымен бірдей $к$ кардинал жиынтығында $n + к - 1$ . Биномдық коэффициенттермен ұқсастықты нуматорды жоғарыдағы өрнекте а түрінде жазу арқылы баса айтуға болады факторлық күштің жоғарылауы

{ displaystyle left (! ! {n k} ! ! right таңдаңыз) = {n ^ { overline {k}} over k!},}

төмендейтін факторлық қуатты пайдаланып биномдық коэффициенттің өрнегін сәйкестендіру үшін:

{ displaystyle {n таңдаңыз k} = {n ^ { астын сызыңыз {k}} үстінен k!}.}

Мысалы, жиынтықтан алынған элементтері бар 3 кардиналдың 4 мультисистемасы бар ${1, 2}$ кардинал 2 ( $n = 2$ , $к = 3$ ), атап айтқанда ${1, 1, 1}$ , ${1, 1, 2}$ , ${1, 2, 2}$ , ${2, 2, 2}$ . 4 бар ішкі жиындар жиынтықтағы кардинал 3 ${1, 2, 3, 4}$ кардинал 4 ( $n + к - 1$ ), атап айтқанда ${1, 2, 3}$ , ${1, 2, 4}$ , ${1, 3, 4}$ , ${2, 3, 4}$ .

Жоғары жиіліктегі коэффициенттер мен биномдық коэффициенттердің теңдігін дәлелдеудің бір қарапайым әдісі мультисөлелерді келесі жолмен бейнелеуді қамтиды. Алдымен, бейнелейтін мультисистемаларға арналған белгілерді қарастырыңыз ${а, а, а, а, а, а, б, б, c, c, c, г., г., г., г., г., г., г.}$ (6 $а$ s, 2 $б$ с, 3 $c$ с, 7 $г.$ s) осы нысанда:

• • • • • • | • • | • • • | • • • • • • •

Бұл кардиналдың мультисеті $к$ = 18 кардинал жиынтығының элементтерінен жасалған $n$ = 4. Осы нотада қолданылатын нүктелер мен тік сызықтарды қосатын символдар саны 18 + 4 - 1. Тік сызықтар саны 4 - 1. Мульти-жиынтықтың саны 18-ді білдіретін болса, оны орналастырудың тәсілдерінің саны болады. 18 + 4 - 1 символдарының арасындағы 4 - 1 тік сызықтар, және, осылайша, 18 + 4 - 1 кардинал жиынтығындағы 4 - 1 кардиналдың ішкі жиынтықтарының саны. Эквивалентті түрде, бұл 18 нүктені орналастыру тәсілдерінің саны 18 + 4 - 1 символдарының арасында, бұл 18 + 4 - 1 кардинал жиынтығының кардиналдың ішкі жиынтықтарының саны.

{ displaystyle {4 + 18-1 таңдау 4-1} = {4 + 18-1 таңдау 18} = 1330,}

мультисет коэффициентінің мәні және оның эквиваленттері:

{ displaystyle left (! ! {4 18} таңдау ! ! оң) = {21 таңдау 18} = { frac {21!} {18! , 3!}} = {21 таңдау 3} = сол жақта (! ! {19 таңдау 3} ! ! оң),}

{ displaystyle = { frac {{ color {red} { mathfrak {4 cdot 5 cdot 6 cdot 7 cdot 8 cdot 9 cdot 10 cdot 11 cdot 12 cdot 13 cdot 14 cdot 15 cdot 16 cdot 17 cdot 18}}}} cdot mathbf {19 cdot 20 cdot 21}} { mathbf {1 cdot 2 cdot 3} cdot { color {red} { mathfrak {4 cdot 5 cdot 6 cdot 7 cdot 8 cdot 9 cdot 10 cdot 11 cdot 12 cdot 13 cdot 14 cdot 15 cdot 16 cdot 17 cdot 18}}}}}} ,}

{ displaystyle = { frac {1 cdot 2 cdot 3 cdot 4 cdot 5 cdots 16 cdot 17 cdot 18 ; mathbf { cdot ; 19 cdot 20 cdot 21}} { , 1 cdot 2 cdot 3 cdot 4 cdot 5 cdots 16 cdot 17 cdot 18 , times , mathbf {1 cdot 2 cdot 3 quad}}}},}

{ displaystyle = { frac {19 cdot 20 cdot 21} {1 cdot 2 cdot 3}}.}

Жалпыланған биномдық коэффициентті анықтауға болады

{ displaystyle {n k} = {n (n-1) (n-2) cdots (n-k + 1) k дан артық таңдаңыз!}}

онда $n$ теріс емес бүтін сан болуы қажет емес, бірақ теріс немесе бүтін емес, нақты емес болуы мүмкін күрделі сан. (Егер $к$ = 0, онда бұл коэффициенттің мәні 1 болады, өйткені ол бос өнім.) Сонда кардиналдың мульти-жиынтық саны $к$ кардинал жиынтығында $n$ болып табылады

{ displaystyle left (! ! {n k} ! ! right) = (- 1) ^ {k} {- n k} таңдаңыз.}

Қайталану қатынасы

A қайталану қатынасы мультисет коэффициенттері ретінде берілуі мүмкін

{ displaystyle left (! ! {n k} ! ! right) = = left (! ! {n k-1} ! ! right) + left ( ! ! {n-1 k} ! ! right) quad { mbox {for}} n, k> 0} таңдаңыз

бірге

{ displaystyle left (! ! {n select 0} ! ! right) = 1, quad n in mathbb {N}, quad { mbox {and}} quad left (! ! {0 k} ! ! Right таңдаңыз) = 0, quad k> 0.}

Жоғарыда келтірілген қайталануды келесідей түсіндіруге болады $[n]$ := ${ displaystyle {1, cdots, n }}$ дереккөздер жиынтығы болыңыз. Әрдайым 0 өлшемді дәл бір (бос) мультисет бар, егер болса $n$ = 0 үлкен шарттар жоқ, бұл бастапқы шарттарды береді.

Енді істі қарастырыңыз $n, к$ > 0. Маңыздылық $к$ элементтерімен $[n]$ соңғы элементтің кез-келген данасын қамтуы мүмкін немесе болмауы мүмкін $n$ . Егер ол пайда болса, жою арқылы $n$ бірде кардиналды мультисет қалады $к$ - бастап 1 элементтер $[n]$ , және әрбір осындай мультисет пайда болуы мүмкін, бұл жалпы соманы береді

{ displaystyle left (! ! {n k-1} таңдаңыз ! ! right)}

мүмкіндіктер.

Егер $n$ пайда болмайды, сонда біздің түпнұсқа мультисет кардиналдың мультисетіне тең болады $к$ элементтерімен $[n - 1]$ , оның ішінде

{ displaystyle left (! ! {n-1 k} ! ! right таңдаңыз).}

Осылайша,

{ displaystyle left (! ! {n k} ! ! right) = = left (! ! {n k-1} ! ! right) + left ( ! ! {n-1 k} ! ! дұрысын таңдаңыз).}

Сериялар жасалуда

The генерациялық функция көпмөлшерлі коэффициенттер өте қарапайым

{ displaystyle sum _ {d = 0} ^ { infty} left (! ! {n d} ! ! right таңдаңыз) t ^ {d} = { frac {1} {( 1-t) ^ {n}}}.}

Мультисездер мономиалдармен бір-бірден сәйкес келетіндіктен, ${ displaystyle left (! ! {n d} ! ! right таңдаңыз)}$ сонымен қатар мономиалды заттар дәрежесі $г.$ жылы $n$ анықталмайды. Сонымен, жоғарыда аталған сериялар да болып табылады Гильберт сериясы туралы көпмүшелік сақина ${ displaystyle k [x_ {1}, ldots, x_ {n}].}$

Қалай ${ displaystyle left (! ! {n d} ! ! right таңдаңыз)}$ in көпмүшесі болып табылады $n$ , ол кез келген үшін анықталады күрделі мәні $n$ .

Жалпылау және теріс биномдық қатарға қосылу

Мультипликативті формула мультисет коэффициенттерінің анықтамасын ауыстыру арқылы кеңейтуге мүмкіндік береді n ерікті санмен α (теріс, нақты, күрделі):

{ displaystyle left (! ! { alpha select k} ! ! right) = { frac { alpha ^ { overline {k}}} {k!}} = { frac { alpha ( альфа +1) ( альфа +2) cdots ( альфа + k-1)} {k (k-1) (k-2) cdots 1}} quad { text {for} } k in mathbb {N} { text {және ерікті}} альфа.}

Осы анықтаманың көмегімен теріс биномдық формуланы қорытуға болады (айнымалылардың бірі 1-ге тең), бұл шақыруды негіздейді ${ displaystyle left (! ! { alpha k} ! ! right таңдаңыз)}$ теріс биномдық коэффициенттер:

{ displaystyle (1-X) ^ {- alpha} = sum _ {k = 0} ^ { infty} left (! ! { alpha k} ! ! right) select X ^ {k}.}

Бұл Тейлор сериясы формула барлық күрделі сандар үшін жарамды α және X бірге |X| <1. Сондай-ақ, оны жеке тұлға ретінде түсіндіруге болады ресми қуат сериялары жылы X, мұнда ол нақты коэффициенті 1-ге тең қатарлардың ерікті дәрежелерінің анықтамасы бола алады; мәселе осы анықтамамен күткен барлық сәйкестілікке сәйкес келеді дәрежелеу, атап айтқанда

{ displaystyle (1-X) ^ {- alpha} (1-X) ^ {- beta} = (1-X) ^ {- ( alpha + beta)} quad { text {and} } quad ((1-X) ^ {- альфа}) ^ {- бета} = (1-X) ^ {- (- альфа бета)}}

,

және осы сияқты формулалармен көпсатылы коэффициенттердің сәйкестігін дәлелдеуге болады.

Егер α оң емес бүтін сан n, содан кейін барлық шарттар к > −n нөлге тең, ал шексіз қатар ақырлы қосындыға айналады. Алайда, басқа мәндері үшін αнатурал сандар мен рационал сандарды қосқанда, қатар шексіз.

Қолданбалар

Multisets-те әртүрлі қосымшалар бар.^[6] Олар негізгі болып табылады комбинаторика.^[15]^[16]^[17]^[18] Multisets теориясының маңызды құралына айналды реляциялық мәліметтер базасы, бұл синонимді жиі қолданады сөмке.^[19]^[20]^[21] Мысалы, деректер қоры жүйелеріндегі қатынастарды жүзеге асыру үшін мультисеталар жиі қолданылады. Атап айтқанда, кесте (бастапқы кілтсіз) мультисет ретінде жұмыс істейді, өйткені онда бірнеше бірдей жазбалар болуы мүмкін. Сол сияқты, SQL мультисездерде жұмыс істейді және бірдей жазбаларды қайтарады. Мысалы, «Студенттің атын таңдауды» қарастырыңыз. Студенттік кестеде «сара» деген бірнеше жазбалар болған жағдайда, олардың барлығы көрсетілген. Бұл дегеніміз, SQL нәтижелерінің жиынтығы мультисет болып табылады. Егер бұл жиынтық болса, нәтижелер жиынтығында қайталанатын жазбалар жойылды. Multiset-тің тағы бір қолданылуы модельдеуде мультиграфтар. Мультиграфтарда кез-келген екі төбенің арасында бірнеше шеттер болуы мүмкін. Осылайша, жиектерді көрсететін нысан жиын емес, мультисет болып табылады.

Сонымен қатар басқа қосымшалар бар. Мысалы, Ричард Радо жиындардың отбасыларының қасиеттерін зерттейтін құрылғы ретінде мультисеталарды қолданды. Ол былай деп жазды: «Жиын ұғымы оның бірде-бір мүшесінің бірнеше рет пайда болуының есебін жүргізбейді, бірақ көбіне дәл осындай ақпарат түрі маңызды. Біз тек f көпмүшесінің түбірлерінің жиынтығы туралы ойлауымыз керек. (х) немесе сызықтық оператордың спектрі. «^[4]^:328–329

Жалпылау

Мәселелерді шешуде мультисездердің әртүрлі жалпыламалары енгізілді, зерттелді және қолданылды.

Нақты бағаланатын мультисет (онда элементтің еселігі кез келген нақты сан болуы мүмкін)^[22]^[23]

Бұл өте қарапайым болып көрінеді, өйткені бұлыңғыр жиындар мен көпөлшемдерге арналған көптеген анықтамалар өте ұқсас және оларды сипаттамалық функцияның мәндер диапазонын ([0, 1] немесе ℕ) ауыстыру арқылы нақты бағаланатын мультисөлелер үшін қабылдауға болады.₀ = {0, 1, 2, 3, ...} сәйкесінше) ℝ₀⁺ = [0, ∞ [. Алайда, а-ны қолданатын жалпыланған түсініксіз жиынтықтар үшін бұл тәсілді оңай кеңейту мүмкін емес посет немесе тор қарапайым мүшелік дәрежесінің орнына. Бұлыңғыр мультисеталарға арналған бірнеше басқа тәсілдер әзірленді, оларда мұндай шектеулер жоқ.

Бұлыңғыр мультисеталар^[24]
Дөрекі мультисет^[25]
Гибридтік жиынтықтар^[26]
Көпмүшелік, олардың еселігі кез келген нақты бағаланатын қадам функциясы болып табылады^[27]
Жұмсақ мультисет^[28]
Жұмсақ бұлыңғыр мультисездер^[29]
Атаулы жиындар (жиындардың барлық жалпыламаларын біріздендіру)^[30]^[31]^[32]^[33]

Сондай-ақ қараңыз

Жиілік (статистика) көптік аналогы ретінде
Квази-жиынтықтар
Жиынтық теориясы
Көп өлшемді бөлімдер

Әдебиеттер тізімі

^ Хейн, Джеймс Л. (2003). Дискретті математика. Джонс және Бартлетт баспагерлері. бет.29 –30. ISBN 0-7637-2210-3.
^ ^а ^б ^c Кнут, Дональд Э. (1998). Жартылай алгоритмдер. Компьютерлік бағдарламалау өнері. 2 (3-ші басылым). Аддисон Уэсли. ISBN 0-201-89684-2.
^ Blizard, Wayne D (1989). «Мультисет теориясы». Нотр-Дам журналы формальды логика журналы. 30 (1): 36–66. дои:10.1305 / ndjfl / 1093634995.
^ ^а ^б ^c ^г. ^e Близард, Уэйн Д. (1991). «Мультисет теориясының дамуы». Қазіргі заманғы логика. 1 (4): 319–352.
^ Рулифсон, Дж. Ф .; Дерксон, Дж. А .; Уолдингер, Дж. Дж. (Қараша 1972). QA4: Интуитивті пайымдауға арналған процедуралық есеп (Техникалық есеп). Халықаралық ҒЗИ. 73.
^ ^а ^б Сингх, Д .; Ибраһим, А.М .; Йоханна, Т .; Сингх, Дж. Н. (2007). «Мультисеталардың қосымшаларына шолу». Novi Sad Journal of Mathematics. 37 (2): 73–92.
^ Анжелелли, И. (1965). «Лейбництің Низолийдің« көп өлшемділік »түсінігін дұрыс түсінбеуі'". Нотр-Дам журналы формальды логика журналы (6): 319–322.
^ Кирхер, Афанасий (1650). Musurgia Universalis. Рим: Corbelletti.
^ Престет, Жан (1675). Elemens des Mathematiques. Париж: Андре Пралард.
^ Уоллис, Джон (1685). Алгебраның трактаты. Лондон: Джон Плейфорд.
^ Дедекинд, Ричард (1888). Zahlen қайтыс болды ма?. Брауншвейг: Vieweg.
^ Syropoulos, Apostolos (2001). «Мультисет математикасы». Калуде, С.С .; т.б. (ред.). Multiset өңдеу: математикалық, информатика және молекулалық есептеу нүктелері. Шпрингер-Верлаг. 347–358 беттер.
^ Уитни, Х. (1933). «Сипаттамалық функциялар және логика алгебрасы». Математика жылнамалары. 34: 405–414. дои:10.2307/1968168.
^ Monro, G. P. (1987). «Мультисет тұжырымдамасы». Mathematische Logik und Grundlagen der Mathematik. 33: 171–178. дои:10.1002 / malq.19870330212.
^ Айгер, М. (1979). Комбинаторлық теория. Нью-Йорк / Берлин: Springer Verlag.
^ Андерсон, И. (1987). Соңғы жиынтықтардың комбинаторикасы. Оксфорд: Clarendon Press.
^ Стэнли, Ричард П. (1997). Санақ комбинаторикасы. 1. Кембридж университетінің баспасы. ISBN 0-521-55309-1.
^ Стэнли, Ричард П. (1999). Санақ комбинаторикасы. 2. Кембридж университетінің баспасы. ISBN 0-521-56069-1.
^ Грумбах, С .; Milo, T (1996). «Қаптарға арналған тартылатын алгебраларға». Компьютерлік және жүйелік ғылымдар журналы. 52 (3): 570–588. дои:10.1006 / jcss.1996.0042.
^ Либкин, Л .; Вонг, Л. (1994). «Сөмкелерге арналған сұраныс тілдерінің кейбір қасиеттері». Деректер базасын бағдарламалау тілдері бойынша семинар материалдары. Springer Verlag. 97–114 бб.
^ Либкин, Л .; Вонг, Л. (1995). «Сөмкелері бар мәліметтер базасында толық емес ақпаратты ұсыну және сұрау туралы». Ақпаратты өңдеу хаттары. 56 (4): 209–214. дои:10.1016/0020-0190(95)00154-5.
^ Близард, Уэйн Д. (1989). «Нақты бағаланған мультисездер және бұлыңғыр жиынтықтар». Бұлыңғыр жиынтықтар мен жүйелер. 33: 77–97. дои:10.1016/0165-0114(89)90218-2.
^ Близард, Уэйн Д. (1990). «Теріс мүшелік». Нотр-Дам журналы формальды логика журналы. 31 (1): 346–368.
^ Ягер, Р.Р (1986). «Сөмкелер теориясы туралы». Халықаралық жалпы жүйелер журналы. 13: 23–37. дои:10.1080/03081078608934952.
^ Грзимала-Буссе, Дж. (1987). «Дөрекі мультисисеттерге негізделген мысалдардан сабақ алу». Интеллектуалды жүйелер әдістемесі бойынша 2-ші халықаралық симпозиум материалдары. Шарлотта, Солтүстік Каролина. 325-332 бб.
^ Loeb, D. (1992). «Элементтердің теріс сандары бар жиынтықтар». Математикадағы жетістіктер. 91: 64–74. дои:10.1016/0001-8708(92)90011-9.
^ Миямото, С. (2001). «Бұлыңғыр мултисеттер және оларды қорыту». Multiset өңдеу. 2235: 225–235.
^ Алхазалех, С .; Саллех, А.Р .; Хасан, Н. (2011). «Жұмсақ мультисет теориясы». Қолданбалы математика ғылымдары. 5 (72): 3561–3573.
^ Алхазалех, С .; Salleh, A. R. (2012). «Fuzzy Soft Multiset теориясы». Реферат және қолданбалы талдау.
^ Бургин, Марк (1990). «Математиканың негізі ретінде аталған жиындар теориясы». Математикалық теориялардағы құрылымдар. Сан-Себастьян. 417-420 бб.
^ Бургин, Марк (1992). «Кибернетикадағы мультисет тұжырымдамасы туралы». Кибернетика және жүйелік талдау. 3: 165–167.
^ Burgin, Mark (2004). «Математиканың бірыңғай негіздері». arXiv:математика / 0403186.
^ Burgin, Mark (2011). Аталған жиындар теориясы. Математиканың зерттеулері. Nova Science Pub Inc. ISBN 978-1-61122-788-8.

[1] Хейн, Джеймс Л. (2003). Дискретті математика. Джонс және Бартлетт баспагерлері. бет.29 –30. ISBN 0-7637-2210-3.

[Knuth1998-2] а ^б ^c Кнут, Дональд Э. (1998). Жартылай алгоритмдер. Компьютерлік бағдарламалау өнері. 2 (3-ші басылым). Аддисон Уэсли. ISBN 0-201-89684-2.

[Blizard1989-3] Blizard, Wayne D (1989). «Мультисет теориясы». Нотр-Дам журналы формальды логика журналы. 30 (1): 36–66. дои:10.1305 / ndjfl / 1093634995.

[Blizard1991-4] а ^б ^c ^г. ^e Близард, Уэйн Д. (1991). «Мультисет теориясының дамуы». Қазіргі заманғы логика. 1 (4): 319–352.

[Rulifson1972-5] Рулифсон, Дж. Ф .; Дерксон, Дж. А .; Уолдингер, Дж. Дж. (Қараша 1972). QA4: Интуитивті пайымдауға арналған процедуралық есеп (Техникалық есеп). Халықаралық ҒЗИ. 73.

[Singh2007-6] а ^б Сингх, Д .; Ибраһим, А.М .; Йоханна, Т .; Сингх, Дж. Н. (2007). «Мультисеталардың қосымшаларына шолу». Novi Sad Journal of Mathematics. 37 (2): 73–92.

[Angelelli1965-7] Анжелелли, И. (1965). «Лейбництің Низолийдің« көп өлшемділік »түсінігін дұрыс түсінбеуі'". Нотр-Дам журналы формальды логика журналы (6): 319–322.

[8] Кирхер, Афанасий (1650). Musurgia Universalis. Рим: Corbelletti.

[9] Престет, Жан (1675). Elemens des Mathematiques. Париж: Андре Пралард.

[10] Уоллис, Джон (1685). Алгебраның трактаты. Лондон: Джон Плейфорд.

[11] Дедекинд, Ричард (1888). Zahlen қайтыс болды ма?. Брауншвейг: Vieweg.

[12] Syropoulos, Apostolos (2001). «Мультисет математикасы». Калуде, С.С .; т.б. (ред.). Multiset өңдеу: математикалық, информатика және молекулалық есептеу нүктелері. Шпрингер-Верлаг. 347–358 беттер.

[Whitney-13] Уитни, Х. (1933). «Сипаттамалық функциялар және логика алгебрасы». Математика жылнамалары. 34: 405–414. дои:10.2307/1968168.

[14] Monro, G. P. (1987). «Мультисет тұжырымдамасы». Mathematische Logik und Grundlagen der Mathematik. 33: 171–178. дои:10.1002 / malq.19870330212.

[Aigner1979-15] Айгер, М. (1979). Комбинаторлық теория. Нью-Йорк / Берлин: Springer Verlag.

[Anderson1987-16] Андерсон, И. (1987). Соңғы жиынтықтардың комбинаторикасы. Оксфорд: Clarendon Press.

[Stanley1997-17] Стэнли, Ричард П. (1997). Санақ комбинаторикасы. 1. Кембридж университетінің баспасы. ISBN 0-521-55309-1.

[Stanley1999-18] Стэнли, Ричард П. (1999). Санақ комбинаторикасы. 2. Кембридж университетінің баспасы. ISBN 0-521-56069-1.

[GrumbachMilo1996-19] Грумбах, С .; Milo, T (1996). «Қаптарға арналған тартылатын алгебраларға». Компьютерлік және жүйелік ғылымдар журналы. 52 (3): 570–588. дои:10.1006 / jcss.1996.0042.

[LibkinWong1994-20] Либкин, Л .; Вонг, Л. (1994). «Сөмкелерге арналған сұраныс тілдерінің кейбір қасиеттері». Деректер базасын бағдарламалау тілдері бойынша семинар материалдары. Springer Verlag. 97–114 бб.

[LibkingWong1995-21] Либкин, Л .; Вонг, Л. (1995). «Сөмкелері бар мәліметтер базасында толық емес ақпаратты ұсыну және сұрау туралы». Ақпаратты өңдеу хаттары. 56 (4): 209–214. дои:10.1016/0020-0190(95)00154-5.

[22] Близард, Уэйн Д. (1989). «Нақты бағаланған мультисездер және бұлыңғыр жиынтықтар». Бұлыңғыр жиынтықтар мен жүйелер. 33: 77–97. дои:10.1016/0165-0114(89)90218-2.

[Blizard1990-23] Близард, Уэйн Д. (1990). «Теріс мүшелік». Нотр-Дам журналы формальды логика журналы. 31 (1): 346–368.

[Yager1986-24] Ягер, Р.Р (1986). «Сөмкелер теориясы туралы». Халықаралық жалпы жүйелер журналы. 13: 23–37. дои:10.1080/03081078608934952.

[Grzymala-Busse1987-25] Грзимала-Буссе, Дж. (1987). «Дөрекі мультисисеттерге негізделген мысалдардан сабақ алу». Интеллектуалды жүйелер әдістемесі бойынша 2-ші халықаралық симпозиум материалдары. Шарлотта, Солтүстік Каролина. 325-332 бб.

[Loeb1992-26] Loeb, D. (1992). «Элементтердің теріс сандары бар жиынтықтар». Математикадағы жетістіктер. 91: 64–74. дои:10.1016/0001-8708(92)90011-9.

[Miyamoto2001-27] Миямото, С. (2001). «Бұлыңғыр мултисеттер және оларды қорыту». Multiset өңдеу. 2235: 225–235.

[Alkhazaleh2011-28] Алхазалех, С .; Саллех, А.Р .; Хасан, Н. (2011). «Жұмсақ мультисет теориясы». Қолданбалы математика ғылымдары. 5 (72): 3561–3573.

[Alkhazaleh2012-29] Алхазалех, С .; Salleh, A. R. (2012). «Fuzzy Soft Multiset теориясы». Реферат және қолданбалы талдау.

[30] Бургин, Марк (1990). «Математиканың негізі ретінде аталған жиындар теориясы». Математикалық теориялардағы құрылымдар. Сан-Себастьян. 417-420 бб.

[31] Бургин, Марк (1992). «Кибернетикадағы мультисет тұжырымдамасы туралы». Кибернетика және жүйелік талдау. 3: 165–167.

[32] Burgin, Mark (2004). «Математиканың бірыңғай негіздері». arXiv:математика / 0403186.

[33] Burgin, Mark (2011). Аталған жиындар теориясы. Математиканың зерттеулері. Nova Science Pub Inc. ISBN 978-1-61122-788-8.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]