چندمجموعه

چندمجموعه (یا خورجین) در ریاضیات تعمیمی از مفهوم مجموعه است که بر خلاف یک مجموعه،می تواند دارای چند عضو یکسان از هر عنصر باشد. multiplicity تعداد اعضایی است که از یک عنصر گرفته شده اند. برای مثال multiplicity عنصر b در $\{a,a,a,a,b,b,c\}$ برابر 2 است.

به عنوان مثال، تعداد نامتناهی از چندمجموعه‌ها وجود دارد که حاوی عناصر a و b است، تنها با تعدد مختلف:

مجموعه منحصر به فرد {a, b} تنها حاوی عناصر a و b، هر یک با داشتن تعدد ۱
در چندمجموعه‌های {a, a, b}، دارای تعدد ۲ عدد a و ۱ عدد b است
در چندمجموعه‌های {a, a, a, b, b, b}, aو b هر دو دارای تعداد ۳ عدد هستند

این اشیاء وقتی به عنوان چندمجموعه به کار می‌روند همگی متفاوتند، اگرچه به خاطر اینکه از عناصر یکسانی تشکیل شده‌اند، بک مجموعه (سه تا چندمجموعه) محسوب می‌شوند. اما متقابلاً برخلاف دنباله‌ها و تاپل‌ها ترتیب تمایزی در چند مجموعه‌ها ایجاد نمی‌کند.^[۱] یعنی:

$\{a,a,b\}=\{a,b,a\}$

تعداد اعضای چند مجموعه نیز با جمع فراوانی عناصر برابر است:

$A=\{a,a,a,a,t,t,t,k\},B=\{a,a,d,d\}$

$|A|=8$

$|B|=4$

در دهه ۱۹۷۰، نیکلاس گاورت دبرویجن و دونالد کنوت به صورت جدا از هم کلمه چندمجموعه را بکار بردند.^[۲] با این حال، مفهوم چندمجموعه‌ها (قبل از وجود کلمهٔ چندمجموعه) در قرن‌ها پیش نیز وجود داشته. کنوت اولین مطالعهٔ چندمجموعه‌ها را به ریاضی‌دان هندی بهسکارا چاریا منسوب کرده‌است که او جایگشت چند مجموعه‌ها را حدود ۱۱۵۰ بیان داشته‌است. نام‌های دیگری که برای چند مجموعه‌ها پیشنهاد یا استفاده شده عبارتند است از: لیست، خوشه، کیسه، گروه، نمونه، مجموعهٔ وزنی، اجتماع و دنباله.^[۲]

بررسی اجمالی

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

تاریخچه

بلیزارد(۱۹۸۹) چندمجموعه را به مبداهایی از اعداد منسوب می‌کند؛ با این استدلال که «در دوران باستان، عدد n اغلب توسط جمعی از ضربه‌ها، علائم چوب خط، یا قسمت‌ها نشان داده می‌شد.» این‌ها و مجموعه‌ای از اشیاء مشابه، چندمجموعه‌هایی هستند؛ چنانچه ضربه‌ها، علائم چوب خط، یا قسمت‌ها غیرقابل تشخیص قلمداد می‌شدند (همانند مفهوم چند مجموعه‌ها). این نشان می‌دهد که مردم به‌طور ضمنی از چندمجموعه‌ها حتی قبل از ظهور ریاضیات استفاده می‌کردند.

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

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

در قالب صریح، چندمجموعه در کار '''ریچارد ددکیند''' ظهور یافت «چه هستند و اعداد چه هستند»(۱۸۸۸). با این حال، ریاضیدانان چندمجموعه را رسمی‌کردند و شروع به مطالعه آن‌ها به عنوان یک شی (ساختار) دقیق ریاضی تنها در قرن ۲۰ام کردند.

تعریف رسمی

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

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

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

تابع تعدد

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

های | کوچک محدود، | است، توسط یک لیست که در آن هر عنصر، |، هر چند بار رخ می‌دهد به عنوان تعدد نشان داده، |، نشان می‌دهد.

مثال‌ها

یکی از ساده‌ترین و طبیعی‌ترین نمونه‌های | از عوامل اول از | تعداد است. در اینجا مجموعه‌ای از عناصر اساسی مجموعه‌ای از مقسوم علیه‌های ان از | است. به عنوان مثال تعداد | دارای فاکتور نخست

می‌دهد که‌های |

یک مثال مربوط به راه حل‌های | یک معادله جبری است. معادله درجه دوم، به عنوان مثال، دو راه حل. با این حال، در برخی از موارد آن‌ها هر دو به همان تعداد است؛ بنابراین‌های | از راه حل‌های معادله می‌تواند |، یا آن را می‌تواند |. در مورد دوم دارای یک راه حل از تعدد |.

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

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

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

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

همچنین نگاه کنید به: ستاره‌ها و میله‌های زندان (ترکیبیات)

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

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

برای مطابقت با بیان ضرایب فرعی-جزئی با استفاده از یک قدرت فاکتوریل در حال سقوط:

در نتیجه ارزش ضریب‌های |و معادلات آن است:

ممکن است یک ضریب دو جمله‌ای تعمیم تعریف

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

رابطه بازگشتی برای ضرایب‌های | ممکن است به عنوان داده

با

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

مجموعه | ممکن است توسط یک اصطلاحی | نشان داده شود. مجموعه‌ای از زیر مجموعه‌های |، توسط دو جمله‌ای | نشان داده شود.

مجموعه | ممکن است توسط | دارای فقط یک جمله •نشان داده شود. مجموعه‌ای از زیر مجموعه‌های |، توسط چند جمله‌ای به نمایندگی

|های | از | از |های | است.

به همین دلیل است که ضریب دو جمله‌ای شمارش تعداد | ترکیبی از | مجموعه.

|های | حاوی عناصر | که بازدید هستند، یک جامعه آماری نامیده می‌شود، و | است یک نمونه آماری نامیده می‌شود. مجموعه‌ای از نمونه است.

| که توسط قضیه دو جمل‌های برابر

بنابراین تعداد | نمونه با | بازدیدها است.

در توزیع بازدیدها ببینید توزیع فوقهندسی و آمار استنباطی برای بیشتر است.

مجموعه نامتناهی از | متناهی از عناصر گرفته شده از مجموعه |:

| ممکن است با سری توانی رسمی نمایندگی

| است. راه حل‌های رسمی،

| را حس می‌کند به عنوان یک مجموعه‌ای از |، اما نتیجه متوسط، | معنی به عنوان مجموعه‌ای از | را ندارد.

مجموعه نامتناهی از |متناهی از عناصر گرفته شده از مجموعه | است.

| این توضیح می‌دهد که چرا «| مجموعه منفی است». ضرایب فرعی-جزئی منفی تعداد | از عناصر از یک | مجموعه.

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

این نمایندگی منحصر به فرد است: | مختلف توابع تولید | متفاوت است. تابع پارتیشن (مکانیک آماری) در مورد که در آن اعداد را در سؤال سطوح انرژی یک سیستم فیزیکی را ببینید.

تابع | مولدهای | از مبالغ از عناصر دو | از اعداد مجموع دو تابع | تولید است:

متأسفانه فرمول کلی برای محاسبه تابع مولد | از یک محصول وجود دارد

توزیع نرمال استاندارد است مانند یک حد | بزرگ از اعداد.

این محدودیت معنی ندارد به عنوان یک‌های | از اعداد، اما مشتق از توابع مولد | از | در سؤال را حس می‌کند، و از حد است که به خوبی تعریف شده‌است.

همچنین متغیر تصادفی را مشاهده کنید

کاربردها

چندمجموعه‌ها کاربردهای فراوانی به ویژه در علوم کامپیوتر دارند. همچنین چندمجموعه‌ها ساختمان اصلی ترکیبیات هستند. یک نمونه از کاربرد چندمجموعه‌ها در پایگاه‌داده‌های رابطه‌ای می‌باشد. به‌طور خاص هر جدول پایگاه‌داده (به شرط عدم وجود کلید اصلی) می‌تواند چندین رکورد مشابه داشته باشد. همچنین زبان SQL برمبنای چندمجموعه‌ها عمل می‌کند، به عنوان نمونه اگر خروجی یک دستور SELECT چند رکورد مشابه باشد، همه آنها چاپ می‌شوند؛ یعنی اگر خروجی اسم دانشجویان باشد و در آن چند اسم «سارا» باشد، همهٔ آنها چاپ می‌شود. در صورتی که اگر SQL بر روی مجموعه (و نه چندمجموعه) عمل می‌کرد، بایستی اسمهای مشابه حذف می‌شدند، چنانچه در جبر رابطه‌ای (Relational Algebra) نیز چنین است. برای نمونه، برای خروجی اسم دانشجویان فقط یک اسم «سارا» چاپ می‌شد. یک کاربرد دیگر در مدل‌سازی گرافهای چندگانه است که بین دو راس ممکن است چند یال وجود داشته باشد. در این صورت آنچه یالها را بیان می‌کند یک چندمجموعه است در حالی که برای گرافهای ساده که یال چندگانه ندارند، یک مجموعه یالها را تعریف می‌کند.

تعمیمات

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

منابع

↑ Discrete mathematics. Hein, James L. شابک ۰-۷۶۳۷-۲۲۱۰-۳.
↑ ^۲٫۰ ^۲٫۱ Knuth, Donald E. (1998). Seminumerical Algorithms. هنر برنامه‌نویسی رایانه. Vol. 2 (3rd ed.). ادیسون-وزلی. p. 694. ISBN 0-201-89684-2.
↑ Hein, James L. (2003). Discrete mathematics. Jones & Bartlett Publishers. pp. 29–30. ISBN 0-7637-2210-3.

مشارکت‌کنندگان ویکی‌پدیا. «Multiset». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۴ ژوئن ۲۰۱۵.

[1] Discrete mathematics. Hein, James L. شابک ۰-۷۶۳۷-۲۲۱۰-۳.

[Knuth_1988-2] ۲٫۰ ^۲٫۱ Knuth, Donald E. (1998). Seminumerical Algorithms. هنر برنامه‌نویسی رایانه. Vol. 2 (3rd ed.). ادیسون-وزلی. p. 694. ISBN 0-201-89684-2.

[3] Hein, James L. (2003). Discrete mathematics. Jones & Bartlett Publishers. pp. 29–30. ISBN 0-7637-2210-3.

[۱]

[۲]

[۳]