چندمجموعه
چندمجموعه (یا خورجین) در ریاضیات تعمیمی از مفهوم مجموعه است که بر خلاف یک مجموعه،می تواند دارای چند عضو یکسان از هز عنصر باشد. multiplicity تعداد اعضایی است که از یک عنصر گرفته شده اند. برای مثال multiplicity عنصر b در formula_1 برابر 2 است.
به عنوان مثال، تعداد نامتناهی از چندمجموعه‌ها وجود دارد که حاوی عناصر "a" و "b" است، تنها با تعدد مختلف: این اشیاء وقتی به عنوان چندمجموعه به کار می‌روند همگی متفاوتند، اگرچه به خاطر اینکه از عناصر یکسانی تشکیل شده‌اند، بک مجموعه (سه تا چندمجموعه) محسوب می‌شوند. اما متقابلاً برخلاف دنباله‌ها و تاپل‌ها ترتیب تمایزی در چند مجموعه‌ها ایجاد نمی‌کند. یعنی:
formula_2
تعداد اعضای چند مجموعه نیز با جمع فراوانی عناصر برابر است:
formula_3
formula_4
formula_5
در دهه ۱۹۷۰، نیکلاس گاورت دبرویجن و دونالد کنوت به صورت جدا از هم کلمه چندمجموعه را بکار بردند. با این حال، مفهوم چندمجموعه‌ها (قبل از وجود کلمهٔ چندمجموعه) در قرن‌ها پیش نیز وجود داشته. کنوت اولین مطالعهٔ چندمجموعه‌ها را به ریاضی‌دان هندی بهسکارا چاریا منسوب کرده‌است که او جایگشت چند مجموعه‌ها را حدود ۱۱۵۰ بیان داشته‌است. نام‌های دیگری که برای چند مجموعه‌ها پیشنهاد یا استفاده شده عبارتند است از: "لیست، خوشه، کیسه، گروه، نمونه، مجموعهٔ وزنی، اجتماع و دنباله".
تعداد دفعاتی که یک عنصر متعلق به‌چندمجموعه هاست تعدد که عضو است. تعداد کل عناصر در یک‌های چندمجموعه، شامل تکرار در عضویت، کاردینال چندمجموعه است. به عنوان مثال، در چندمجموعه {"a", "a", "b", "b", "b", "c"} چندگانگی از اعضای "a", "b", و "c" به ترتیب ۲, ۳, و ۱ و کاردینال (اعداد اصلی) چندمجموعه ۶ است. برای تشخیص بین مجموعه و چندمجموعه، یک نماد شامل براکت است که گاهی اوقات استفاده می‌شود: چندمجموعه {۲٬۲٬۳} می‌تواند به عنوان [2,2,3]. نشان داده شود. در چندمجموعه‌ها، همانند مجموعه‌ها و در مقابل به تاپل ترتیب اعضا اهمیتی ندارد. {"a", "a", "b"} و {"a", "b", "a"} برابر است.
بلیزارد(۱۹۸۹) چندمجموعه را به مبداهایی از اعداد منسوب می‌کند؛ با این استدلال که «در دوران باستان، عدد n اغلب توسط جمعی از ضربه‌ها، علائم چوب خط، یا قسمت‌ها نشان داده می‌شد.» این‌ها و مجموعه‌ای از اشیاء مشابه، چندمجموعه‌هایی هستند؛ چنانچه ضربه‌ها، علائم چوب خط، یا قسمت‌ها غیرقابل تشخیص قلمداد می‌شدند (همانند مفهوم چند مجموعه‌ها). این نشان می‌دهد که مردم به‌طور ضمنی از چندمجموعه‌ها حتی قبل از ظهور ریاضیات استفاده می‌کردند.
این نشان می‌دهد که ضرورت در این ساختار همیشه مبرم بوده‌است که چندمجموعه چندین بار بازکشف شده‌اند و در ادبیات تحت نام‌های مختلف ظاهر شده‌است (بلیزارد ۱۹۹۱). به عنوان مثال، پترسون(۱۹۸۱) آن‌ها کیسه‌ها نامیده‌است که این جمله را به سرف، گوسلو، استرین و ولانسکی نسبت داده‌است. چندمجموعه‌ها هم چنین یک انبوهه، گروه، دسته، نمونه، مجموعهٔ وزنی، مجموعه وقایع و مجموعه آتشین (متناهی، با تکرار عنصر مجموعه) نامیده می‌شده‌است (بلیزارد ۱۹۹۱، سینگ ۲۰۰۷).
اگر چه به‌طور ضمنی چندمجموعه از دوران باستان مورد استفاده قرار گرفت، اکتشاف صریح و روشن خود را بسیار زودتر اتفاق افتاده‌است. اولین مطالعه شناخته شده از چندمجموعه به ریاضی‌دان هندی بهاسکارا آچاریا (حدود ۱۱۵۰)، که جایگشت از چندمجموعه‌ها را (کنوت، ۱۹۹۸) شرح داده شده، نسبت داد. آنجلیلی (۱۹۶۵) مرجعی اخیر دیگری منسوب به ایده چندمجموعه را در کار ماریوس نیزولوییس کشف کرد. مدت‌ها قبل، کیرچر(۱۶۵۰) تعداد جایگشت‌های چندمجموعه هنگامی که یک عنصر می‌تواند تکرار شود، کشف کرد. پرستت(۱۶۷۵) یک قاعده کلی برای جایگشت‌های چندمجموعه را بیان داشت. والیس (۱۶۸۵) این قانون را با جزئیات بیشتر توضیح می‌دهد.
در قالب صریح، چندمجموعه در کار ریچارد ددکیند ظهور یافت «چه هستند و اعداد چه هستند»(۱۸۸۸). با این حال، ریاضیدانان چندمجموعه را رسمی‌کردند و شروع به مطالعه آن‌ها به عنوان یک شی (ساختار) دقیق ریاضی تنها در قرن ۲۰ام کردند.
در تئوری مجموعه، های | ممکن است به‌طور رسمی به عنوان یک تاپل | که در آن برخی مجموعه است و یک تابع از به مجموعه‌ای از اعداد مثبت طبیعی است تعریف شده‌است. مجموعه است مجموعه‌ای از عناصر اساسی نامیده می‌شود. برای هر یک از در تعدد (که شده‌است، تعداد وقوع) از تعداد است. اگر یک جهان که در آن عناصر باید زندگی کنند مشخص شده باشد، تعریف می‌توان به تنها یک تابع تعدد از به مجموعه‌ای از اعداد طبیعی، به دست آمده با گسترش به با ارزش | برای هر عنصر در ساده. این تابع تعدد گسترده تابع تعدد نام زیر است. مجموعه‌ای از زوج مرتب: مانند هر تابع، تابع ممکن است به عنوان گراف آن تعریف شده‌است. با این تعاریف‌های | نوشته شده به عنوان به عنوان تعریف شده‌است، و به عنوان‌های | تعریف شده‌است.
مفهوم‌های | یک کلیت از مفهوم مجموعه است. های | مربوط به یک مجموعه معمولی اگر تعدد هر عنصر است (به عنوان برخی از عدد طبیعی بزرگتر مخالف). خانواده نمایه، جایی که در برخی از شاخص مجموعه‌ای است، ممکن است یک‌های | گاهی اوقات نوشته شده‌است، که در آن تعدد هر عنصر تعداد شاخص به طوری که تعریف می‌کنند. شرط برای این به امکان وجود دارد که هیچ عنصر بی‌نهایت چند بار در خانواده رخ می‌دهد: حتی در یک‌های | نامحدود، چندگانگی باید شماره محدود باشد.
ممکن است که به گسترش تعریف یک‌های | با اجازه دادن به چندگانگی از عناصر منحصر به فرد به کاردینال‌ها نامحدود به جای اعداد طبیعی. تمام خواص را حمل بیش از این تعمیم این حال، و این مقاله با استفاده از تعریف بالا، با چندگانگی محدود است.
های | کوچک محدود، | است، توسط یک لیست که در آن هر عنصر، |، هر چند بار رخ می‌دهد به عنوان تعدد نشان داده، |، نشان می‌دهد.
یکی از ساده‌ترین و طبیعی‌ترین نمونه‌های | از عوامل اول از | تعداد است. در اینجا مجموعه‌ای از عناصر اساسی مجموعه‌ای از مقسوم علیه‌های ان از | است. به عنوان مثال تعداد | دارای فاکتور نخست
می‌دهد که‌های |
یک مثال مربوط به راه حل‌های | یک معادله جبری است. معادله درجه دوم، به عنوان مثال، دو راه حل. با این حال، در برخی از موارد آن‌ها هر دو به همان تعداد است؛ بنابراین‌های | از راه حل‌های معادله می‌تواند |، یا آن را می‌تواند |. در مورد دوم دارای یک راه حل از تعدد |.
حالت خاصی از بالا مقادیر ویژه یک ماتریس هستند، اگر این به عنوان‌های | از ریشه‌های چند جمله‌ای مشخصه آن تعریف شده‌است. با این حال یک انتخاب در اینجا ساخته شده‌است: (معمول) تعریف مقادیر ویژه به چند جمله‌ای مشخصه به |مختلف اشاره‌ای نکرد، و دیگر فرصت را افزایش مفاهیم مختلف تعدد، و در نتیجه. |، که اغلب کوچکتر از تعدد خود را به عنوان ریشه چند جمله‌ای مشخصه (کثرت جبری) وقتی که آخر بزرگتر از | مجموعه‌ای است - تعدد هندسی از | به عنوان مقادیر ویژه یک ماتریس بعد از هسته است از مقادیر ویژه نیز مجموعه‌ای از ریشه‌های چند جمله‌ای حداقل آن، اما از آن ریشه‌های | لازم نیست همان یا به عنوان یکی از با استفاده از تعدد جبری، یا با استفاده از تعدد هندسی تعریف شده‌است.
گروه آبلی رایگان مبالغ رسمی (یعنی ترکیب خطی) از عناصر | با ضرایب عدد صحیح است. معادل، آن‌ها ممکن است به عنوان | محدود امضاء شده با عناصر برگرفته از |. دیده
همچنین نگاه کنید به: ستاره‌ها و میله‌های زندان (ترکیبیات)
تعداد |از کاردینالیتی |، با عناصر گرفته شده از یک مجموعه متناهی از کاردینالیتی |، | ضریب‌های | یا شماره‌های | نامیده می‌شود. این شماره است که توسط برخی از نویسندگان به عنوان، یک نماد است که به معنای شبیه است که از ضرایب فرعی-جزئی نوشته شده‌است؛ از آن است که به عنوان مثال در (استنلی، |) استفاده می‌شود، و می‌تواند تلفظ | شبیه به "| را انتخاب کنید" برای. بر خلاف برای ضرایب فرعی-جزئی، هیچ "قضیه‌های | " که در آن ضرایب‌های | که رخ می‌دهد وجود دارد، و آن‌ها باید با ضرایب چندگانه نامربوط که در قضیه چندگانه رخ می‌دهد اشتباه گرفت. ارزش ضرایب‌های | می‌توان به صراحت به عنوان داده
که در آن عبارت دوم است به عنوان یک ضریب دو جمله‌ای. نویسندگان بسیاری در واقع جلوگیری از نماد جداگانه و فقط ارسال ضرایب فرعی-جزئی. |. قیاس با ضرایب فرعی-جزئی می‌توان با نوشتن صورت کسر در عبارت بالا به عنوان یک قدرت در حال افزایش فاکتوریل تأکید - بنابراین، تعدادی از چنین | همان تعداد زیر مجموعه از کاردینالیتی | در مجموعه‌ای از کاردینالیتی | است.
برای مطابقت با بیان ضرایب فرعی-جزئی با استفاده از یک قدرت فاکتوریل در حال سقوط:
به عنوان مثال وجود دارد | | از کاردینالیتی | با عناصر گرفته شده از مجموعه | از کاردینالیتی | | باشد، |، یعنی: |، |، |، |. و نیز وجود دارد | زیر مجموعه از کاردینالیتی | در مجموعه | از کاردینالیتی |، یعنی: |، |، |، |
یکی از راه‌های ساده برای اثبات برابری ضریب‌های | و ضرایب فرعی-جزئی داده شده در بالا، شامل نمایندگی | در راه زیر است. اول، در نظر نماد برای | که نشان دهنده | عنوان، | | در این فرم:
این یک‌های | از کاردینالیتی | ساخته شده از عناصر مجموعه‌ای از کاردینالیتی |. تعدادی از شخصیت‌های از جمله هر دو نقطه و خطوط عمودی استفاده می‌شود در این نماد | تعداد خطوط عمودی است | تعداد | از کاردینالیتی | است پس از آن تعدادی از راه‌های به ترتیب | خطوط عمودی در میان | حرف، و در نتیجه تعداد زیر مجموعه‌های کاردینالیتی | در مجموعه‌ای از کاردینالیتی | معادل، آن را به تعدادی از راه‌های به ترتیب | نقطه در میان | است | شخصیت است، که تعداد زیر مجموعه از کاردینالیتی | از مجموعه‌ای از کاردینالیتی | این است.
در نتیجه ارزش ضریب‌های |و معادلات آن است:
ممکن است یک ضریب دو جمله‌ای تعمیم تعریف
که در آن | نیاز نیست که یک عدد صحیح نامنفی، اما ممکن است منفی یا غیر صحیح، یا یک عدد مختلط غیر واقعی است. تعداد | از کاردینالیتی | در مجموعه‌ای از کاردینالیتی | اگر | سپس مقدار این ضریب | است، زیرا محصول خالی است. پس از آن است.
رابطه بازگشتی برای ضرایب‌های | ممکن است به عنوان داده
با
عود بالا ممکن است به شرح زیر است تفسیر شده‌است. اجازه دهید | را تنظیم شود منبع آن است. همواره وجود دارد دقیقاً یک (خالی)های | اندازه |، و اگر | هیچ | بزرگتر، می‌دهد که شرایط اولیه وجود دارد.
در حال حاضر، در مورد که در آن |. های | از کاردینالیتی | با عناصر از | ممکن است یا ممکن است هر نمونه از عنصر | نهایی را شامل نمی‌شود در نظر بگیرید. اگر آن را به نظر می‌رسد، پس از آن با از بین بردن | یک بار، یکی با کاردینالیتی‌های | از سمت چپ | از عناصر از |، و هر جمله‌های | می‌تواند به وجود می‌آیند، می‌دهد که در مجموع
امکانات.
مجموعه | ممکن است توسط یک اصطلاحی | نشان داده شود. مجموعه‌ای از زیر مجموعه‌های |، توسط دو جمله‌ای | نشان داده شود.
مجموعه | ممکن است توسط | دارای فقط یک جمله •نشان داده شود. مجموعه‌ای از زیر مجموعه‌های |، توسط چند جمله‌ای به نمایندگی
به همین دلیل است که ضریب دو جمله‌ای شمارش تعداد | ترکیبی از | مجموعه.
که توسط قضیه دو جمل‌های برابر
بنابراین تعداد | نمونه با | بازدیدها است.
در توزیع بازدیدها ببینید توزیع فوقهندسی و آمار استنباطی برای بیشتر است.
مجموعه نامتناهی از | متناهی از عناصر گرفته شده از مجموعه |: ممکن است با سری توانی رسمی نمایندگی
راه حل‌های رسمی، را حس می‌کند به عنوان یک مجموعه‌ای از |، اما نتیجه متوسط، | معنی به عنوان مجموعه‌ای از | را ندارد.
مجموعه نامتناهی از |متناهی از عناصر گرفته شده از مجموعه | است. مورد | ویژه:های | بی‌نهایت از | متناهی از عناصر گرفته شده از |های | است. حالت کلی:های | بی‌نهایت از | متناهی از عناصر گرفته شده از |های | است. این توضیح می‌دهد که چرا «| مجموعه منفی است». ضرایب فرعی-جزئی منفی تعداد | از عناصر از یک | مجموعه.
یک عدد صحیح غیر منفی، | می‌تواند توسط | دارای فقط یک جمله بیان کرد. های | متناهی از اعداد صحیح غیر منفی، می‌گویند |، می‌تواند به همین ترتیب توسط یک چند جمله‌ای | نشان داده |، می‌گویند |
آن را راحت به در نظر گرفتن تابع مولد | گرم | ورود | است، می‌گویند گرم | ورود |
کاردینالیتی ازهای | به عنوان مثال | است |، می‌گویند | مشتق گرم گرم | است | • همکاران، می‌گویند | مقدار متوسط ازهای | است، می‌گویند |. واریانس‌های | است | اعداد | نامیده می‌شوند |.
مجموعه‌ای نامتناهی از اعداد صحیح غیر منفی | توسط سری‌های توانی رسمی نمایندگی | مقدار متوسط و انحراف استاندارد تعریف نشده‌است. با این حال آن را به یک تابع | تولید، گرم |. مشتق شده از این تابع | مولد | است |های | متناهی از اعداد واقعی، | هوش مصنوعی، توسط تابع مولد | نمایندگی
این نمایندگی منحصر به فرد است: | مختلف توابع تولید | متفاوت است. تابع پارتیشن (مکانیک آماری) در مورد که در آن اعداد را در سؤال سطوح انرژی یک سیستم فیزیکی را ببینید.
تابع | مولد یک از اعدادهای | واقعی داشتن میانگین | انحراف | و استاندارد است: گرم | ورود |، و مشتق است که به سادگی: |
تابع | تولید مجموعه، |، متشکل از یک عدد حقیقی تنها، | است • و مشتق تعداد خود را است: |. بنابراین، مفهوم مشتق تابع مولد | یک‌های | از اعداد حقیقی یک کلیت از مفهوم عدد حقیقی است.
تابع | مولد یک‌های | ثابت، | از عناصر | همه به همان تعداد واقعی | برابر، گرم | ورود | است • |، و مشتق تعداد خود را است: |، صرف نظر از |.
تابع | مولدهای | از مبالغ از عناصر دو | از اعداد مجموع دو تابع | تولید است:
متأسفانه فرمول کلی برای محاسبه تابع مولد | از یک محصول وجود دارد
اما حالت خاصی از یک بار ثابت‌های | از اعداد است: های | هوش مصنوعی است‌های | همان | نمی| |هوش مصنوعی | | به عنوان مثال، | در حالی که |
توزیع نرمال استاندارد است مانند یک حد | بزرگ از اعداد.
این محدودیت معنی ندارد به عنوان یک‌های | از اعداد، اما مشتق از توابع مولد | از | در سؤال را حس می‌کند، و از حد است که به خوبی تعریف شده‌است.
همچنین متغیر تصادفی را مشاهده کنید
چندمجموعه‌ها کاربردهای فراوانی به ویژه در علوم کامپیوتر دارند. همچنین چندمجموعه‌ها ساختمان اصلی ترکیبیات هستند. یک نمونه از کاربرد چندمجموعه‌ها در پایگاه‌داده‌های رابطه‌ای می‌باشد. به‌طور خاص هر جدول پایگاه‌داده (به شرط عدم وجود کلید اصلی) می‌تواند چندین رکورد مشابه داشته باشد. همچنین زبان SQL برمبنای چندمجموعه‌ها عمل می‌کند، به عنوان نمونه اگر خروجی یک دستور SELECT چند رکورد مشابه باشد، همه آنها چاپ می‌شوند؛ یعنی اگر خروجی اسم دانشجویان باشد و در آن چند اسم «سارا» باشد، همهٔ آنها چاپ می‌شود. در صورتی که اگر SQL بر روی مجموعه (و نه چندمجموعه) عمل می‌کرد، بایستی اسمهای مشابه حذف می‌شدند، چنانچه در جبر رابطه‌ای (Relational Algebra) نیز چنین است. برای نمونه، برای خروجی اسم دانشجویان فقط یک اسم «سارا» چاپ می‌شد. یک کاربرد دیگر در مدل‌سازی گرافهای چندگانه است که بین دو راس ممکن است چند یال وجود داشته باشد. در این صورت آنچه یالها را بیان می‌کند یک چندمجموعه است در حالی که برای گرافهای ساده که یال چندگانه ندارند، یک مجموعه یالها را تعریف می‌کند.
تعمیمات متفاوت چندمجموعه‌ها معرفی، مطالعه و استفاده شده‌اند تا مسئله‌های مختلف را حل کنند. یاگر (۱۹۶۸) چندمجموعه‌های گنگ را تحت نام کیف‌های گنگ معرفی کرد. گریزمالا-بروس (۱۹۸۷) ایدهٔ چندمجموعهٔ ناصاف را که از چندرابطه‌ها استفاده می‌کند، داد. بلیزارد (۱۹۸۹) چندمجموعه‌ها را به چندمجموعه‌های مقدار حقیقی، تعمیم داد. چندمجموعه‌ها که در آن ضرب یک جزء می‌تواند یک عدد حقیقی نا منفی باشد. بلیزلرد (۱۹۹۰) هم چنین چندمجموعه‌هایی با ضرب منفی را بیان کرد. لوب (۱۹۹۲) مجموعه‌های پیوندی را به عنوان تعمیم چندمجموعه معرفی کرد که در آن ضرب هر جزء هر عدد صحیح است. میاماتو (۲۰۰۱) چندمجموعه‌ها را بیش تر تعمیم داد. او چندمجموعه‌هایی که در آن ضرب یک جزء هر تابع پله‌ای عدد حقیقی است. الخزاله (۱۹۹۰ – ۱۹۹۲ – ۲۰۰۴ – ۲۰۱۱) چندمجموعه‌ها و تمام تعمیمات آن را با ایدهٔ مجموعهٔ نامدار متحد کرد که تمام تعمیمات مجموعه را دربردارد.