چندمجموعه

چندمجموعه () این مقاله در مورد یکی از مفاهیم ریاضی برای ساختمان داده علوم کامپیوتر است، (نوع داده انتزاعی) چندمجموعه را ببینید.
در ریاضیات چندمجموعه (یا کیسه) تعمیمی از مفهوم مجموعه است که بر خلاف یک مجموعه، چند نمونهیکسان می‌تواند از اعضای چندمجموعه را تشکیل دهد. تعدد یک عنصر تعداد مورد آن عضو در یک چندمجموعه خاص است.
به عنوان مثال، تعداد نامتناهی از چندمجموعه‌ها وجود دارد که حاوی عناصر a و b است، تنها با تعدد مختلف:
مجموعه منحصر به فرد {a, b تنها حاوی عناصر a و b، هر یک با داشتن تعدد ۱
در چندمجموعه‌های {a, a, b، دارای تعدد | و | است تعدد |
در چندمجموعه‌های {a, a, a, b, b, b, aو b هر دو دارای تعدد ۳
در دهه ۱۹۷۰، نیکلاس گاورت دبرویجن، همانند دونالد کنوت، کلمه چندمجموعه را بیان کرد.
با این حال، استفاده از چندمجموعه‌ها قبل از (وجود) کلمه چندمجموعه نیز در قرن‌ها پیش شده است. کنوت اولین مطالعه چندمجموعه‌ها را به ریاضی‌دان هندی بهسکارا چاریا منسوب کرده است که او جایگشت چند مجموعه‌ها را حدود ۱۱۵۰ بیان داشته است. کنوت همچنین نام‌های دیگر که مطرح شد یا مورد استفاده چندمجموعه‌ها قرارگرفته را لیست کرده است، از جمله لیست، خوشه، کیسه، گروه، نمونه، مجموعه وزنی، اجتماع و دنباله.
بررسی اجمالی
تعداد دفعاتی که یک عنصر متعلق به‌چندمجموعه هاست تعدد که عضو است. تعداد کل عناصر در یک‌های چندمجموعه، شامل تکرار در عضویت، کاردینال چندمجموعه است. به عنوان مثال، در چندمجموعه {a, a, b, b, b, c چندگانگی از اعضای a, b, و c به ترتیب ۲, ۳, و ۱ و کاردینال (اعداد اصلی) چندمجموعه ۶ می‌باشد. برای تشخیص بین مجموعه و چندمجموعه، یک نماد شامل براکت است که گاهی اوقات استفاده می‌شود: چندمجموعه {۲،۲,۳ می‌تواند به عنوان 2,2,3. نشان داده شود. در چندمجموعه‌ها، همانند مجموعه‌ها و در مقابل به تاپل ترتیب اعضا اهمیتی ندارد. {a, a, b و {a, b, a برابر است.
تاریخچه
بلیزارد(۱۹۸۹) چندمجموعه را به مبداهایی از اعداد منسوب می‌کند؛ با این استدلال که «در دوران باستان، عدد n اغلب توسط جمعی از ضربه‌ها، علائم چوب خط، یا قسمت‌ها نشان داده می‌شد.» این‌ها و مجموعه‌ای از اشیاء مشابه، چندمجموعه‌هایی هستند؛ چنانچه ضربه‌ها، علائم چوب خط، یا قسمت‌ها غیرقابل تشخیص قلمداد می‌شدند (همانند مفهوم چند مجموعه‌ها). این نشان می‌دهد که مردم به طور ضمنی از چندمجموعه‌ها حتی قبل از ظهور ریاضیات استفاده می‌کردند.
این نشان می‌دهد که ضرورت در این ساختار همیشه مبرم بوده است که چندمجموعه چندین بار بازکشف شده‌اند و در ادبیات تحت نام‌های مختلف ظاهر شده است (بلیزارد ۱۹۹۱). به عنوان مثال، پترسون(۱۹۸۱) آنها کیسه‌ها نامیده است که این جمله را به سرف، گوسلو، استرین و ولانسکی نسبت داده است. چندمجموعه‌ها هم چنین یک انبوهه، گروه، دسته، نمونه، مجموعه وزنی، مجموعه وقایع و مجموعه آتشین (متناهی، با تکرار عنصر مجموعه) نامیده می‌شده است (بلیزارد ۱۹۹۱، سینگ ۲۰۰۷).
اگر چه به طور ضمنی چندمجموعه از دوران باستان مورد استفاده قرار گرفت، اکتشاف صریح و روشن خود را بسیار زودتر اتفاق افتاده است. اولین مطالعه شناخته شده از چندمجموعه به ریاضی‌دان هندی بهاسکارا آچاریا (حدود ۱۱۵۰)، که جایگشت از چندمجموعه‌ها را (کنوت، ۱۹۹۸) شرح داده شده، نسبت داد. آنجلیلی (۱۹۶۵) مرجعی اخیر دیگری منسوب به ایده چندمجموعه را در کار ماریوس نیزولوییس کشف کرد. مدت‌ها قبل، کیرچر(۱۶۵۰) تعداد جایگشت‌های چندمجموعه هنگامی که یک عنصر می‌تواند تکرار شود، کشف کرد. پرستت(۱۶۷۵) یک قاعده کلی برای جایگشت‌های چندمجموعه را بیان داشت. والیس (۱۶۸۵) این قانون را با جزئیات بیشتر توضیح می‌دهد.
در قالب صریح، چندمجموعه در کار ریچارد ددکیند ظهور یافت «چه هستند و اعداد چه هستند»(۱۸۸۸). با این حال، ریاضیدانان چندمجموعه را رسمی کردند و شروع به مطالعه آنها به عنوان یک شی (ساختار) دقیق ریاضی تنها در قرن ۲۰ام کردند.
تعریف رسمی
در تئوری مجموعه،‌های | ممکن است به طور رسمی به عنوان یک تاپل | که در آن برخی مجموعه است و یک تابع از به مجموعه‌ای از اعداد مثبت طبیعی است تعریف شده است. مجموعه است مجموعه‌ای از عناصر اساسی نامیده می‌شود. برای هر یک از در تعدد (که شده است، تعداد وقوع) از تعداد است. اگر یک جهان که در آن عناصر باید زندگی کنند مشخص شده باشد، تعریف می‌توان به تنها یک تابع تعدد از به مجموعه‌ای از اعداد طبیعی، به دست آمده با گسترش به با ارزش | برای هر عنصر در ساده. این تابع تعدد گسترده تابع تعدد نام زیر است. مجموعه‌ای از زوج مرتب: مانند هر تابع، تابع ممکن است به عنوان گراف آن تعریف شده است. با این تعاریف‌های | نوشته شده به عنوان به عنوان تعریف شده است، و به عنوان‌های | تعریف شده است.
مفهوم‌های | یک کلیت از مفهوم مجموعه است.‌های | مربوط به یک مجموعه معمولی اگر تعدد هر عنصر است (به عنوان برخی از عدد طبیعی بزرگتر مخالف). خانواده نمایه، جایی که در برخی از شاخص مجموعه‌ای است، ممکن است یک‌های | گاهی اوقات نوشته شده است، که در آن تعدد هر عنصر تعداد شاخص به طوری که تعریف می‌کنند. شرط برای این به امکان وجود دارد که هیچ عنصر بی‌نهایت چند بار در خانواده رخ می‌دهد: حتی در یک‌های | نامحدود، چندگانگی باید شماره محدود باشد.
ممکن است که به گسترش تعریف یک‌های | با اجازه دادن به چندگانگی از عناصر منحصر به فرد به کاردینالها نامحدود به جای اعداد طبیعی. تمام خواص را حمل بیش از این تعمیم این حال، و این مقاله با استفاده از تعریف بالا، با چندگانگی محدود است.
تابع تعدد
عملکرد نشانگر مجموعه‌ای از مجموعه‌ای طبیعی است به تابع تعدد برای | تعمیم داده شود. عملکرد نشانگر مجموعه‌ای از یک زیر مجموعه از مجموعه | تابع است
تعریف شده توسط
عملکرد نشانگر مجموعه‌ای از تقاطع مجموعه تابع حداقل از توابع شاخص است
عملکرد نشانگر مجموعه‌ای از اتحاد مجموعه تابع حداکثر از توابع شاخص است
عملکرد نشانگر مجموعه‌ای از زیر مجموعه‌های کوچکتر از یا برابر است که از سوپرست است
عملکرد نشانگر مجموعه‌ای از ضرب دکارتی محصول از توابع شاخص از عوامل دکارتی است
کاردینالیتی یک (محدود) مجموعه‌ای از مجموع ارزش تابع شاخص است
در حال حاضر مفهوم عملکرد نشانگر مجموعه‌ای تعمیم با آزاد محدودیت که مقادیر | و | و اجازه می‌دهد تنها مقادیر | | | و غیره. تابع به دست آمده است که به نام یک تابع تعدد و مانند یک تابع‌های | تعریف می‌کند. مفاهیم تقاطع، اتحادیه، زیر مجموعه، ضرب دکارتی و کاردینالیتی | توسط فرمول بالا تعریف شده است.
تابع تعدد مبلغ‌های | مجموع توابع تعدد است
تابع تعدد تفاوت‌های | تفریق صفر کوتاه از توابع تعدد است
ضرب عددی از یک‌های | توسط تعدادی | طبیعی ممکن است به عنوان تعریف می‌شود:
های | کوچک محدود، | است، توسط یک لیست که در آن هر عنصر، |، هر چند بار رخ می‌دهد به عنوان تعدد نشان داده، |، نشان می‌دهد.
مثال‌ها
یکی از ساده‌ترین و طبیعی‌ترین نمونه‌های | از عوامل اول از | تعداد است. در اینجا مجموعه‌ای از عناصر اساسی مجموعه‌ای از مقسوم علیههای ان از | می‌باشد. به عنوان مثال تعداد | دارای فاکتور نخست
می‌دهد که‌های |
یک مثال مربوط به راه حل‌های | یک معادله جبری است. معادله درجه دوم، به عنوان مثال، دو راه حل. با این حال، در برخی از موارد آنها هر دو به همان تعداد می‌باشد؛ بنابراین‌های | از راه حل‌های معادله می‌تواند |، یا آن را می‌تواند |. در مورد دوم دارای یک راه حل از تعدد |.
حالت خاصی از بالا مقادیر ویژه یک ماتریس هستند، اگر این به عنوان‌های | از ریشه‌های چند جمله‌ای مشخصه آن تعریف شده است. با این حال یک انتخاب در اینجا ساخته شده است: (معمول) تعریف مقادیر ویژه به چند جمله‌ای مشخصه به |مختلف اشاره‌ای نکرد، و دیگر فرصت را افزایش مفاهیم مختلف تعدد، و در نتیجه. |، که اغلب کوچکتر از تعدد خود را به عنوان ریشه چند جمله‌ای مشخصه (کثرت جبری) وقتی که آخر بزرگتر از | مجموعه‌ای است - تعدد هندسی از | به عنوان مقادیر ویژه یک ماتریس بعد از هسته است از مقادیر ویژه نیز مجموعه‌ای از ریشه‌های چند جمله‌ای حداقل آن، اما از آن ریشه‌های | لازم نیست همان یا به عنوان یکی از با استفاده از تعدد جبری، یا با استفاده از تعدد هندسی تعریف شده است.
جابجایی رایگان چندمجموعه
خالی است.
گروه آبلی رایگان مبالغ رسمی (یعنی ترکیب خطی) از عناصر | با ضرایب عدد صحیح می‌باشد. معادل، آنها ممکن است به عنوان | محدود امضاء شده با عناصر برگرفته از |. دیده
شمارش چندمجموعه‌ها
همچنین نگاه کنید به: ستاره‌ها و میله‌های زندان (ترکیبیات)
تعداد |از کاردینالیتی |، با عناصر گرفته شده از یک مجموعه متناهی از کاردینالیتی |، | ضریب‌های | یا شماره‌های | نامیده می‌شود. این شماره است که توسط برخی از نویسندگان به عنوان، یک نماد است که به معنای شبیه است که از ضرایب فرعی-جزیی نوشته شده است؛ از آن است که به عنوان مثال در (استنلی، |) استفاده می‌شود، و می‌تواند تلفظ | شبیه به "| را انتخاب کنید" برای. بر خلاف برای ضرایب فرعی-جزیی، هیچ "قضیه‌های | " که در آن ضرایب‌های | که رخ می‌دهد وجود دارد، و آنها باید با ضرایب چندگانه نامربوط که در قضیه چندگانه رخ می‌دهد اشتباه گرفت. ارزش ضرایب‌های | می‌توان به صراحت به عنوان داده
که در آن عبارت دوم است به عنوان یک ضریب دو جمله‌ای. نویسندگان بسیاری در واقع جلوگیری از نماد جداگانه و فقط ارسال ضرایب فرعی-جزیی. |. قیاس با ضرایب فرعی-جزیی می‌توان با نوشتن صورت کسر در عبارت بالا به عنوان یک قدرت در حال افزایش فاکتوریل تاکید - بنابراین، تعدادی از چنین | همان تعداد زیر مجموعه از کاردینالیتی | در مجموعه‌ای از کاردینالیتی | است
برای مطابقت با بیان ضرایب فرعی-جزیی با استفاده از یک قدرت فاکتوریل در حال سقوط:
به عنوان مثال وجود دارد | | از کاردینالیتی | با عناصر گرفته شده از مجموعه | از کاردینالیتی | | باشد، |، یعنی: |، |، |، |. و نیز وجود دارد | زیر مجموعه از کاردینالیتی | در مجموعه | از کاردینالیتی |، یعنی: |، |، |، |
یکی از راه‌های ساده برای اثبات برابری ضریب‌های | و ضرایب فرعی-جزیی داده شده در بالا، شامل نمایندگی | در راه زیر است. اول، در نظر نماد برای | که نشان دهنده | عنوان، | | در این فرم:
این یک‌های | از کاردینالیتی | ساخته شده از عناصر مجموعه‌ای از کاردینالیتی |. تعدادی از شخصیت‌های از جمله هر دو نقطه و خطوط عمودی استفاده می‌شود در این نماد | تعداد خطوط عمودی است | تعداد | از کاردینالیتی | است پس از آن تعدادی از راه‌های به ترتیب | خطوط عمودی در میان | حرف، و در نتیجه تعداد زیر مجموعه‌های کاردینالیتی | در مجموعه‌ای از کاردینالیتی | معادل، آن را به تعدادی از راه‌های به ترتیب | نقطه در میان | است | شخصیت است، که تعداد زیر مجموعه از کاردینالیتی | از مجموعه‌ای از کاردینالیتی | این است
در نتیجه ارزش ضریب‌های |و معادلات آن است:
ممکن است یک ضریب دو جمله‌ای تعمیم تعریف
که در آن | نیاز نیست که یک عدد صحیح نامنفی، اما ممکن است منفی یا غیر صحیح، یا یک عدد مختلط غیر واقعی است. تعداد | از کاردینالیتی | در مجموعه‌ای از کاردینالیتی | اگر | سپس مقدار این ضریب | است، زیرا محصول خالی است. پس از آن است
رابطه بازگشتی
رابطه بازگشتی برای ضرایب‌های | ممکن است به عنوان داده
با
عود بالا ممکن است به شرح زیر است تفسیر شده است. اجازه دهید | را تنظیم شود منبع آن است. همواره وجود دارد دقیقا یک (خالی)های | اندازه |، و اگر | هیچ | بزرگتر، می‌دهد که شرایط اولیه وجود دارد.
در حال حاضر، در مورد که در آن |.‌های | از کاردینالیتی | با عناصر از | ممکن است یا ممکن است هر نمونه از عنصر | نهایی را شامل نمی‌شود در نظر بگیرید. اگر آن را به نظر می‌رسد، پس از آن با از بین بردن | یک بار، یکی با کاردینالیتی‌های | از سمت چپ | از عناصر از |، و هر جمله‌های | می‌تواند بوجود می‌آیند، می‌دهد که در مجموع
امکانات.
با عناصر از برابر است با
نماد چند جمله‌ای
مجموعه | ممکن است توسط یک اصطلاحی | نشان داده شود. مجموعه‌ای از زیر مجموعه‌های |، توسط دو جمله‌ای | نشان داده شود.
مجموعه | ممکن است توسط | دارای فقط یک جمله •نشان داده شود. مجموعه‌ای از زیر مجموعه‌های |، توسط چند جمله‌ای به نمایندگی
توسط چند جمله‌ای به نمایندگی
است
به همین دلیل است که ضریب دو جمله‌ای شمارش تعداد | ترکیبی از | مجموعه.
است یک نمونه آماری نامیده می‌شود. مجموعه‌ای از نمونه است
که توسط قضیه دو جملهای برابر
بنابراین تعداد | نمونه با | بازدیدها است
در توزیع بازدیدها ببینید توزیع فوقهندسی و آمار استنباطی برای بیشتر است.
مجموعه نامتناهی از | متناهی از عناصر گرفته شده از مجموعه |:
ممکن است با سری توانی رسمی نمایندگی
است.
راه حل‌های رسمی،
را حس می‌کند به عنوان یک مجموعه‌ای از |، اما نتیجه متوسط، | معنی به عنوان مجموعه‌ای از | را ندارد.
مجموعه نامتناهی از |متناهی از عناصر گرفته شده از مجموعه | است
مورد | ویژه:های | بی‌نهایت از | متناهی از عناصر گرفته شده از |های | است
حالت کلی:های | بی‌نهایت از | متناهی از عناصر گرفته شده از |های | است
این توضیح می‌دهد که چرا «| مجموعه منفی است». ضرایب فرعی-جزیی منفی تعداد | از عناصر از یک | مجموعه.
تابع مولد چندمجموعه
یک عدد صحیح غیر منفی، | می‌تواند توسط | دارای فقط یک جمله بیان کرد.‌های | متناهی از اعداد صحیح غیر منفی، می‌گویند |، می‌تواند به همین ترتیب توسط یک چند جمله‌ای | نشان داده |، می‌گویند |
آن را راحت به در نظر گرفتن تابع مولد | گرم | ورود | است، می‌گویند گرم | ورود |
کاردینالیتی ازهای | به عنوان مثال | است |، می‌گویند |
مشتق گرم گرم | است | • همکاران، می‌گویند |
مقدار متوسط ازهای | است، می‌گویند |.
واریانس‌های | است |
اعداد | نامیده می‌شوند |.
مجموعه‌ای نامتناهی از اعداد صحیح غیر منفی | توسط سریهای توانی رسمی نمایندگی | مقدار متوسط و انحراف استاندارد تعریف نشده است. با این حال آن را به یک تابع | تولید، گرم |. مشتق شده از این تابع | مولد | است |های | متناهی از اعداد واقعی، | هوش مصنوعی، توسط تابع مولد | نمایندگی
این نمایندگی منحصر به فرد است: | مختلف توابع تولید | متفاوت است. تابع پارتیشن (مکانیک آماری) در مورد که در آن اعداد را در سوال سطوح انرژی یک سیستم فیزیکی را ببینید.
تابع | مولد یک از اعدادهای | واقعی داشتن میانگین | انحراف | و استاندارد است: گرم | ورود |، و مشتق است که به سادگی: |
تابع | تولید مجموعه، |، متشکل از یک عدد حقیقی تنها، | است • و مشتق تعداد خود را است: |. بنابراین، مفهوم مشتق تابع مولد | یک‌های | از اعداد حقیقی یک کلیت از مفهوم عدد حقیقی است.
تابع | مولد یک‌های | ثابت، | از عناصر | همه به همان تعداد واقعی | برابر، گرم | ورود | است • |، و مشتق تعداد خود را است: |، صرف نظر از |.
تابع | مولدهای | از مبالغ از عناصر دو | از اعداد مجموع دو تابع | تولید است:
متاسفانه فرمول کلی برای محاسبه تابع مولد | از یک محصول وجود دارد
اما حالت خاصی از یک بار ثابت‌های | از اعداد است:
های | هوش مصنوعی است‌های | همان | نمی‌| |هوش مصنوعی | | به عنوان مثال، | در حالی که |
توزیع نرمال استاندارد است مانند یک حد | بزرگ از اعداد.
این محدودیت معنی ندارد به عنوان یک‌های | از اعداد، اما مشتق از توابع مولد | از | در سوال را حس می‌کند، و از حد است که به خوبی تعریف شده است.
است.
همچنین متغیر تصادفی را مشاهده کنید
کاربردها
چندمجموعه‌ها کاربردهای فراوانی دارند. آن‌ها ساختمان اصلی ترکیبات هستند؛ زیرا در تحقیق سختگیری آن، ترکیبات مدرن برای مجموعه‌ها ارتقاء نیافتند بلکه برای چندمجموعه‌ها (آینر، ۱۹۷۹، اندسون ۱۹۸۷، استندلی ۱۹۹۹) انجام شد. چندمجموعه‌ها آزار مهمی در پایگاه داده‌ها به شمار می‌روند. (لیبکین و وانگ ۱۹۹۴، ۱۹۹۵، گرامباچ و مایلو ۱۹۹۶). برای مثال، چند مجموعه‌ها برای کامل کردن رابطه‌ها در پایگاه داده‌ها به کار می‌روند. چند مجموعه‌ها نقش مهمی را در علوم کامپیوتر ایفا می‌کنند (کنون ۱۹۹۷، ۱۹۹۸)
کاربردهای دیگری نیز وجود دارد. برای مثال رادو(۱۹۷۵) از چند مجموعه‌ها به عنوان دستگاهی برای بررسی ویژگی خانواده مجموعه‌ها استفاده کرد. او نوشت: «مفهوم یک مجموعه حسابی ضرب حصول هر یک از اعضای آن نیست؛ و حتی آن فقط این نوع از اطلاعات است که مستمرا مهم است. کافیست که فقط به مجموعه ریشه‌ها ی چندجمله‌ای (f(x یا طیف عملگر خطی فکر کنیم.»
تعمیمات
تعمیمات متفاوت چندمجموعه‌ها معرفی، مطالعه و استفاده شده‌اند تا مسئله‌های مختلف را حل کنند.
یاگر (۱۹۶۸) چندمجموعه‌های گنگ را تحت نام کیف‌های گنگ معرفی کرد.
گریزمالا-بروس (۱۹۸۷) ایده چندمجموعه ناصاف را که از چندرابطه‌ها استفاده می‌کند، داد.
بلیزارد (۱۹۸۹) چندمجموعه‌ها را به چندمجموعه‌های مقدار حقیقی، تعمیم داد. چندمجموعه‌ها که در آن ضرب یک جزء می‌تواند یک عدد حقیقی نا منفی باشد. بلیزلرد (۱۹۹۰) هم چنین چندمجموعه‌هایی با ضرب منفی را بیان کرد.
لوب (۱۹۹۲) مجموعه‌های پیوندی را به عنوان تعمیم چندمجموعه معرفی کرد که در آن ضرب هر جزء هر عدد صحیح می‌باشد.
میاماتو (۲۰۰۱) چندمجموعه‌ها را بیش‌تر تعمیم داد. او چندمجموعه‌هایی که درآن ضرب یک جزء هر تابع پله‌ای عدد حقیقی می‌باشد.
الخزاله (۱۹۹۰ – ۱۹۹۲ – ۲۰۰۴ – ۲۰۱۱) چندمجموعه‌ها و تمام تعمیمات آن را با ایده مجموعه نامدار متحد کرد که تمام تعمیمات مجموعه را در بردارد.