چندمجموعه

بررسی اجمالی

تعداد دفعاتی که یک عنصر متعلق به‌چندمجموعه هاست تعدد که عضو است. تعداد کل عناصر در یک‌های چندمجموعه، شامل تکرار در عضویت، کاردینال چندمجموعه است. به عنوان مثال، در چندمجموعه {a, a, b, b, b, c} چندگانگی از اعضای a, b, و c به ترتیب ۲, ۳, و ۱ و کاردینال (اعداد اصلی) چندمجموعه ۶ است. برای تشخیص بین مجموعه و چندمجموعه، یک نماد شامل براکت است که گاهی اوقات استفاده می‌شود: چندمجموعه {۲٬۲,۳} می‌تواند به عنوان [2,2,3]. نشان داده شود. در چندمجموعه‌ها، همانند مجموعه‌ها و در مقابل به تاپل ترتیب اعضا اهمیتی ندارد. {a, a, b} و {a, b, a} برابر است.

تاریخچه

بلیزارد(۱۹۸۹) چندمجموعه را به مبداهایی از اعداد منسوب می‌کند؛ با این استدلال که «در دوران باستان، عدد n اغلب توسط جمعی از ضربه‌ها، علائم چوب خط، یا قسمت‌ها نشان داده می‌شد.» این‌ها و مجموعه‌ای از اشیاء مشابه، چندمجموعه‌هایی هستند؛ چنانچه ضربه‌ها، علائم چوب خط، یا قسمت‌ها غیرقابل تشخیص قلمداد می‌شدند (همانند مفهوم چند مجموعه‌ها). این نشان می‌دهد که مردم به‌طور ضمنی از چندمجموعه‌ها حتی قبل از ظهور ریاضیات استفاده می‌کردند.
این نشان می‌دهد که ضرورت در این ساختار همیشه مبرم بوده‌است که چندمجموعه چندین بار بازکشف شده‌اند و در ادبیات تحت نام‌های مختلف ظاهر شده‌است (بلیزارد ۱۹۹۱). به عنوان مثال، پترسون(۱۹۸۱) آن‌ها کیسه‌ها نامیده است که این جمله را به سرف، گوسلو، استرین و ولانسکی نسبت داده است. چندمجموعه‌ها هم چنین یک انبوهه، گروه، دسته، نمونه، مجموعهٔ وزنی، مجموعه وقایع و مجموعه آتشین (متناهی، با تکرار عنصر مجموعه) نامیده می‌شده‌است (بلیزارد ۱۹۹۱، سینگ ۲۰۰۷).
اگر چه به‌طور ضمنی چندمجموعه از دوران باستان مورد استفاده قرار گرفت، اکتشاف صریح و روشن خود را بسیار زودتر اتفاق افتاده است. اولین مطالعه شناخته شده از چندمجموعه به ریاضی‌دان هندی بهاسکارا آچاریا (حدود ۱۱۵۰)، که جایگشت از چندمجموعه‌ها را (کنوت، ۱۹۹۸) شرح داده شده، نسبت داد. آنجلیلی (۱۹۶۵) مرجعی اخیر دیگری منسوب به ایده چندمجموعه را در کار ماریوس نیزولوییس کشف کرد. مدت‌ها قبل، کیرچر(۱۶۵۰) تعداد جایگشت‌های چندمجموعه هنگامی که یک عنصر می‌تواند تکرار شود، کشف کرد. پرستت(۱۶۷۵) یک قاعده کلی برای جایگشت‌های چندمجموعه را بیان داشت. والیس (۱۶۸۵) این قانون را با جزئیات بیشتر توضیح می‌دهد.
در قالب صریح، چندمجموعه در کار '''ریچارد ددکیند''' ظهور یافت «چه هستند و اعداد چه هستند»(۱۸۸۸). با این حال، ریاضیدانان چندمجموعه را رسمی‌کردند و شروع به مطالعه آن‌ها به عنوان یک شی (ساختار) دقیق ریاضی تنها در قرن ۲۰ام کردند.

تعریف رسمی

در تئوری مجموعه،‌های | ممکن است به‌طور رسمی به عنوان یک تاپل | که در آن برخی مجموعه است و یک تابع از به مجموعه‌ای از اعداد مثبت طبیعی است تعریف شده‌است. مجموعه است مجموعه‌ای از عناصر اساسی نامیده می‌شود. برای هر یک از در تعدد (که شده‌است، تعداد وقوع) از تعداد است. اگر یک جهان که در آن عناصر باید زندگی کنند مشخص شده باشد، تعریف می‌توان به تنها یک تابع تعدد از به مجموعه‌ای از اعداد طبیعی، به دست آمده با گسترش به با ارزش | برای هر عنصر در ساده. این تابع تعدد گسترده تابع تعدد نام زیر است. مجموعه‌ای از زوج مرتب: مانند هر تابع، تابع ممکن است به عنوان گراف آن تعریف شده‌است. با این تعاریف‌های | نوشته شده به عنوان به عنوان تعریف شده‌است، و به عنوان‌های | تعریف شده‌است.
مفهوم‌های | یک کلیت از مفهوم مجموعه است.‌های | مربوط به یک مجموعه معمولی اگر تعدد هر عنصر است (به عنوان برخی از عدد طبیعی بزرگتر مخالف). خانواده نمایه، جایی که در برخی از شاخص مجموعه‌ای است، ممکن است یک‌های | گاهی اوقات نوشته شده‌است، که در آن تعدد هر عنصر تعداد شاخص به طوری که تعریف می‌کنند. شرط برای این به امکان وجود دارد که هیچ عنصر بی‌نهایت چند بار در خانواده رخ می‌دهد: حتی در یک‌های | نامحدود، چندگانگی باید شماره محدود باشد.
ممکن است که به گسترش تعریف یک‌های | با اجازه دادن به چندگانگی از عناصر منحصر به فرد به کاردینال‌ها نامحدود به جای اعداد طبیعی. تمام خواص را حمل بیش از این تعمیم این حال، و این مقاله با استفاده از تعریف بالا، با چندگانگی محدود است.

مثال‌ها

یکی از ساده‌ترین و طبیعی‌ترین نمونه‌های | از عوامل اول از | تعداد است. در اینجا مجموعه‌ای از عناصر اساسی مجموعه‌ای از مقسوم علیه‌های ان از | است. به عنوان مثال تعداد | دارای فاکتور نخست
می‌دهد که‌های |
یک مثال مربوط به راه حل‌های | یک معادله جبری است. معادله درجه دوم، به عنوان مثال، دو راه حل. با این حال، در برخی از موارد آن‌ها هر دو به همان تعداد است؛ بنابراین‌های | از راه حل‌های معادله می‌تواند |، یا آن را می‌تواند |. در مورد دوم دارای یک راه حل از تعدد |.
حالت خاصی از بالا مقادیر ویژه یک ماتریس هستند، اگر این به عنوان‌های | از ریشه‌های چند جمله‌ای مشخصه آن تعریف شده‌است. با این حال یک انتخاب در اینجا ساخته شده‌است: (معمول) تعریف مقادیر ویژه به چند جمله‌ای مشخصه به |مختلف اشاره‌ای نکرد، و دیگر فرصت را افزایش مفاهیم مختلف تعدد، و در نتیجه. |، که اغلب کوچکتر از تعدد خود را به عنوان ریشه چند جمله‌ای مشخصه (کثرت جبری) وقتی که آخر بزرگتر از | مجموعه‌ای است - تعدد هندسی از | به عنوان مقادیر ویژه یک ماتریس بعد از هسته است از مقادیر ویژه نیز مجموعه‌ای از ریشه‌های چند جمله‌ای حداقل آن، اما از آن ریشه‌های | لازم نیست همان یا به عنوان یکی از با استفاده از تعدد جبری، یا با استفاده از تعدد هندسی تعریف شده‌است.

جابجایی رایگان چندمجموعه

| جابجایی آزاد در یک مجموعه | (جسم آزاد را ببینید) را می‌توان به عنوان مجموعه‌ای از | محدود با عناصر برگرفته از |، با عملیات | بودن جمع‌های | و خالی به عنوان عنصرهای | هویت. چنین | نیز به عنوان (محدود) مبالغ رسمی از عناصر | با ضرایب طبیعی شناخته شده‌است.| جابجایی آزاد زیر مجموعه‌ای از | جابجایی آزاد است که شامل تمام | با عناصر برگرفته از | به جزهای | خالی است.
گروه آبلی رایگان مبالغ رسمی (یعنی ترکیب خطی) از عناصر | با ضرایب عدد صحیح است. معادل، آن‌ها ممکن است به عنوان | محدود امضاء شده با عناصر برگرفته از |. دیده

شمارش چندمجموعه‌ها

همچنین نگاه کنید به: ستاره‌ها و میله‌های زندان (ترکیبیات)
تعداد |از کاردینالیتی |، با عناصر گرفته شده از یک مجموعه متناهی از کاردینالیتی |، | ضریب‌های | یا شماره‌های | نامیده می‌شود. این شماره است که توسط برخی از نویسندگان به عنوان، یک نماد است که به معنای شبیه است که از ضرایب فرعی-جزیی نوشته شده‌است؛ از آن است که به عنوان مثال در (استنلی، |) استفاده می‌شود، و می‌تواند تلفظ | شبیه به "| را انتخاب کنید" برای. بر خلاف برای ضرایب فرعی-جزیی، هیچ "قضیه‌های | " که در آن ضرایب‌های | که رخ می‌دهد وجود دارد، و آن‌ها باید با ضرایب چندگانه نامربوط که در قضیه چندگانه رخ می‌دهد اشتباه گرفت. ارزش ضرایب‌های | می‌توان به صراحت به عنوان داده
که در آن عبارت دوم است به عنوان یک ضریب دو جمله‌ای. نویسندگان بسیاری در واقع جلوگیری از نماد جداگانه و فقط ارسال ضرایب فرعی-جزیی. |. قیاس با ضرایب فرعی-جزیی می‌توان با نوشتن صورت کسر در عبارت بالا به عنوان یک قدرت در حال افزایش فاکتوریل تأکید - بنابراین، تعدادی از چنین | همان تعداد زیر مجموعه از کاردینالیتی | در مجموعه‌ای از کاردینالیتی | است.
برای مطابقت با بیان ضرایب فرعی-جزیی با استفاده از یک قدرت فاکتوریل در حال سقوط:
به عنوان مثال وجود دارد | | از کاردینالیتی | با عناصر گرفته شده از مجموعه | از کاردینالیتی | | باشد، |، یعنی: |، |، |، |. و نیز وجود دارد | زیر مجموعه از کاردینالیتی | در مجموعه | از کاردینالیتی |، یعنی: |، |، |، |
یکی از راه‌های ساده برای اثبات برابری ضریب‌های | و ضرایب فرعی-جزیی داده شده در بالا، شامل نمایندگی | در راه زیر است. اول، در نظر نماد برای | که نشان دهنده | عنوان، | | در این فرم:
این یک‌های | از کاردینالیتی | ساخته شده از عناصر مجموعه‌ای از کاردینالیتی |. تعدادی از شخصیت‌های از جمله هر دو نقطه و خطوط عمودی استفاده می‌شود در این نماد | تعداد خطوط عمودی است | تعداد | از کاردینالیتی | است پس از آن تعدادی از راه‌های به ترتیب | خطوط عمودی در میان | حرف، و در نتیجه تعداد زیر مجموعه‌های کاردینالیتی | در مجموعه‌ای از کاردینالیتی | معادل، آن را به تعدادی از راه‌های به ترتیب | نقطه در میان | است | شخصیت است، که تعداد زیر مجموعه از کاردینالیتی | از مجموعه‌ای از کاردینالیتی | این است.
در نتیجه ارزش ضریب‌های |و معادلات آن است:
ممکن است یک ضریب دو جمله‌ای تعمیم تعریف
که در آن | نیاز نیست که یک عدد صحیح نامنفی، اما ممکن است منفی یا غیر صحیح، یا یک عدد مختلط غیر واقعی است. تعداد | از کاردینالیتی | در مجموعه‌ای از کاردینالیتی | اگر | سپس مقدار این ضریب | است، زیرا محصول خالی است. پس از آن است.

رابطه بازگشتی

رابطه بازگشتی برای ضرایب‌های | ممکن است به عنوان داده
با
عود بالا ممکن است به شرح زیر است تفسیر شده‌است. اجازه دهید | را تنظیم شود منبع آن است. همواره وجود دارد دقیقاً یک (خالی)های | اندازه |، و اگر | هیچ | بزرگتر، می‌دهد که شرایط اولیه وجود دارد.
در حال حاضر، در مورد که در آن |.‌های | از کاردینالیتی | با عناصر از | ممکن است یا ممکن است هر نمونه از عنصر | نهایی را شامل نمی‌شود در نظر بگیرید. اگر آن را به نظر می‌رسد، پس از آن با از بین بردن | یک بار، یکی با کاردینالیتی‌های | از سمت چپ | از عناصر از |، و هر جمله‌های | می‌تواند به وجود می‌آیند، می‌دهد که در مجموع
امکانات.
|، که وجود دارد اگر | به نظر نمی‌رسد، پس از آن‌های | اصلی ما به‌های | از کاردینالیتی | با عناصر از برابر است با

نماد چند جمله‌ای

مجموعه | ممکن است توسط یک اصطلاحی | نشان داده شود. مجموعه‌ای از زیر مجموعه‌های |، توسط دو جمله‌ای | نشان داده شود.
مجموعه | ممکن است توسط | دارای فقط یک جمله •نشان داده شود. مجموعه‌ای از زیر مجموعه‌های |، توسط چند جمله‌ای به نمایندگی
|های | ممکن است توسط یک اصطلاحی | نشان داده شود.‌های | از | توسط چند جمله‌ای به نمایندگی
|های | از | از |های | است.
به همین دلیل است که ضریب دو جمله‌ای شمارش تعداد | ترکیبی از | مجموعه.
|های | حاوی عناصر | که بازدید هستند، یک جامعه آماری نامیده می‌شود، و | است یک نمونه آماری نامیده می‌شود. مجموعه‌ای از نمونه است.
|
که توسط قضیه دو جمل‌های برابر
بنابراین تعداد | نمونه با | بازدیدها است.
در توزیع بازدیدها ببینید توزیع فوقهندسی و آمار استنباطی برای بیشتر است.
مجموعه نامتناهی از | متناهی از عناصر گرفته شده از مجموعه |:
|
ممکن است با سری توانی رسمی نمایندگی
| است.
راه حل‌های رسمی،
|
را حس می‌کند به عنوان یک مجموعه‌ای از |، اما نتیجه متوسط، | معنی به عنوان مجموعه‌ای از | را ندارد.
مجموعه نامتناهی از |متناهی از عناصر گرفته شده از مجموعه | است.
|
مورد | ویژه:های | بی‌نهایت از | متناهی از عناصر گرفته شده از |های | است.
|
حالت کلی:های | بی‌نهایت از | متناهی از عناصر گرفته شده از |های | است.
|
این توضیح می‌دهد که چرا «| مجموعه منفی است». ضرایب فرعی-جزیی منفی تعداد | از عناصر از یک | مجموعه.

تابع مولد چندمجموعه

یک عدد صحیح غیر منفی، | می‌تواند توسط | دارای فقط یک جمله بیان کرد.‌های | متناهی از اعداد صحیح غیر منفی، می‌گویند |، می‌تواند به همین ترتیب توسط یک چند جمله‌ای | نشان داده |، می‌گویند |
آن را راحت به در نظر گرفتن تابع مولد | گرم | ورود | است، می‌گویند گرم | ورود |
کاردینالیتی ازهای | به عنوان مثال | است |، می‌گویند |
مشتق گرم گرم | است | • همکاران، می‌گویند |
مقدار متوسط ازهای | است، می‌گویند |.
واریانس‌های | است |
اعداد | نامیده می‌شوند |.
مجموعه‌ای نامتناهی از اعداد صحیح غیر منفی | توسط سری‌های توانی رسمی نمایندگی | مقدار متوسط و انحراف استاندارد تعریف نشده‌است. با این حال آن را به یک تابع | تولید، گرم |. مشتق شده از این تابع | مولد | است |های | متناهی از اعداد واقعی، | هوش مصنوعی، توسط تابع مولد | نمایندگی
این نمایندگی منحصر به فرد است: | مختلف توابع تولید | متفاوت است. تابع پارتیشن (مکانیک آماری) در مورد که در آن اعداد را در سؤال سطوح انرژی یک سیستم فیزیکی را ببینید.
تابع | مولد یک از اعدادهای | واقعی داشتن میانگین | انحراف | و استاندارد است: گرم | ورود |، و مشتق است که به سادگی: |
تابع | تولید مجموعه، |، متشکل از یک عدد حقیقی تنها، | است • و مشتق تعداد خود را است: |. بنابراین، مفهوم مشتق تابع مولد | یک‌های | از اعداد حقیقی یک کلیت از مفهوم عدد حقیقی است.
تابع | مولد یک‌های | ثابت، | از عناصر | همه به همان تعداد واقعی | برابر، گرم | ورود | است • |، و مشتق تعداد خود را است: |، صرف نظر از |.
تابع | مولدهای | از مبالغ از عناصر دو | از اعداد مجموع دو تابع | تولید است:
متأسفانه فرمول کلی برای محاسبه تابع مولد | از یک محصول وجود دارد
اما حالت خاصی از یک بار ثابت‌های | از اعداد است:
های | هوش مصنوعی است‌های | همان | نمی‌| |هوش مصنوعی | | به عنوان مثال، | در حالی که |
توزیع نرمال استاندارد است مانند یک حد | بزرگ از اعداد.
این محدودیت معنی ندارد به عنوان یک‌های | از اعداد، اما مشتق از توابع مولد | از | در سؤال را حس می‌کند، و از حد است که به خوبی تعریف شده‌است.
| ثابت مدت | ورود | ناپدید شده توسط تمایز. شرایط | در حد ناپدید می‌شوند؛ بنابراین برای توزیع نرمال استاندارد، داشتن میانگین و انحراف استاندارد، مشتق تابع تولید است که به سادگی گرم | برای توزیع نرمال داشتن میانگین | و انحراف استاندارد | مشتق تابع مولد | است.
همچنین متغیر تصادفی را مشاهده کنید

کاربردها

چندمجموعه‌ها کاربردهای فراوانی دارند. آن‌ها ساختمان اصلی ترکیبات هستند؛ زیرا در تحقیق سختگیری آن، ترکیبات مدرن برای مجموعه‌ها ارتقاء نیافتند بلکه برای چندمجموعه‌ها (آینر، ۱۹۷۹، اندسون ۱۹۸۷، استندلی ۱۹۹۹) انجام شد. چندمجموعه‌ها آزار مهمی در پایگاه داده‌ها به‌شمار می‌روند. (لیبکین و وانگ ۱۹۹۴، ۱۹۹۵، گرامباچ و مایلو ۱۹۹۶). برای مثال، چند مجموعه‌ها برای کامل کردن رابطه‌ها در پایگاه داده‌ها به کار می‌روند. چند مجموعه‌ها نقش مهمی را در علوم کامپیوتر ایفا می‌کنند (کنون ۱۹۹۷، ۱۹۹۸)
کاربردهای دیگری نیز وجود دارد. برای مثال رادو(۱۹۷۵) از چند مجموعه‌ها به عنوان دستگاهی برای بررسی ویژگی خانواده مجموعه‌ها استفاده کرد. او نوشت: «مفهوم یک مجموعه حسابی ضرب حصول هر یک از اعضای آن نیست؛ و حتی آن فقط این نوع از اطلاعات است که مستمراً مهم است. کافیست که فقط به مجموعه ریشه‌ها ی چندجمله‌ای (f(x یا طیف عملگر خطی فکر کنیم.»

تعمیمات

تعمیمات متفاوت چندمجموعه‌ها معرفی، مطالعه و استفاده شده‌اند تا مسئله‌های مختلف را حل کنند.
یاگر (۱۹۶۸) چندمجموعه‌های گنگ را تحت نام کیف‌های گنگ معرفی کرد.
گریزمالا-بروس (۱۹۸۷) ایدهٔ چندمجموعهٔ ناصاف را که از چندرابطه‌ها استفاده می‌کند، داد.
بلیزارد (۱۹۸۹) چندمجموعه‌ها را به چندمجموعه‌های مقدار حقیقی، تعمیم داد. چندمجموعه‌ها که در آن ضرب یک جزء می‌تواند یک عدد حقیقی نا منفی باشد. بلیزلرد (۱۹۹۰) هم چنین چندمجموعه‌هایی با ضرب منفی را بیان کرد.
لوب (۱۹۹۲) مجموعه‌های پیوندی را به عنوان تعمیم چندمجموعه معرفی کرد که در آن ضرب هر جزء هر عدد صحیح است.
میاماتو (۲۰۰۱) چندمجموعه‌ها را بیش تر تعمیم داد. او چندمجموعه‌هایی که در آن ضرب یک جزء هر تابع پله‌ای عدد حقیقی است.
الخزاله (۱۹۹۰ – ۱۹۹۲ – ۲۰۰۴ – ۲۰۱۱) چندمجموعه‌ها و تمام تعمیمات آن را با ایدهٔ مجموعهٔ نامدار متحد کرد که تمام تعمیمات مجموعه را در بردارد.