مزيج

في الرياضيات ، التوافيق هي اختيار عناصر من مجموعة ذات عناصر مميزة، بحيث لا يهم ترتيب الاختيار (على عكس التباديل ). على سبيل المثال، إذا أُعطيت ثلاث فواكه، ولتكن تفاحة وبرتقالة وإجاصة، فهناك ثلاث توافيق ثنائية يمكن اختيارها من هذه المجموعة: تفاحة وإجاصة؛ تفاحة وبرتقالة؛ أو إجاصة وبرتقالة. بتعبير أدق، التوافيق من الرتبة k لمجموعة S هي مجموعة جزئية من k عنصرًا مميزًا من S. لذا، يكون توافيقان متطابقين إذا وفقط إذا كان لكل منهما نفس العناصر. (لا يهم ترتيب العناصر في كل مجموعة). إذا كانت المجموعة تحتوي على n عنصرًا، فإن عدد التوافيق من الرتبة k ، ويرمز له بـ${\displaystyle C(n,k)}$أو${\displaystyle C_{k}^{n}}$، يساوي معامل ذات الحدين :

$${\displaystyle {\binom {n}{k}}={\frac {n(n-1)\dotsb (n-k+1)}{k(k-1)\dotsb 1}},}$$

والتي يمكن التعبير عنها بإيجاز باستخدام ترميز المضروب كما يلي

$${\displaystyle {\binom {n}{k}}={\frac {n!}{k!(nk)!}}}$$

حينما${\displaystyle n\geq k\geq 0}$يمكن اشتقاق هذه الصيغة من حقيقة أن كل تركيبة من k مجموعة من S مكونة من n عنصرًا لها${\displaystyle k!}$التباديل إذن${\displaystyle P_{k}^{n}=C_{k}^{n}\times k!}$أو${\displaystyle C_{k}^{n}=P_{k}^{n}/k!}$[ ^{1 ]} غالبًا ما يُرمز إلى مجموعة جميع التوليفات من الرتبة k لمجموعة S بالرمز التالي ^:${\displaystyle \textstyle {\binom {S}{k}}}$.

التوليفة هي اختيار n عنصرًا، يتم اختيار k منها في كل مرة دون تكرار . وللإشارة إلى التوليفات التي يُسمح فيها بالتكرار، تُستخدم غالبًا المصطلحات : توليفة k مع التكرار، أو مجموعة k متعددة ، ^{[ 2 ]} أو اختيار k ، ^{[ 3 ] [ 4 ]} . إذا كان من الممكن، في المثال السابق، الحصول على اثنين من أي نوع واحد من الفاكهة، فسيكون هناك 3 اختيارات ثنائية إضافية: واحدة تحتوي على تفاحتين، وواحدة تحتوي على برتقالتين، وواحدة تحتوي على إجاصتين.

على الرغم من أن مجموعة الفواكه الثلاث كانت صغيرة بما يكفي لكتابة قائمة كاملة بالتوليفات، إلا أن هذا يصبح غير عملي مع ازدياد حجم المجموعة. على سبيل المثال، يمكن وصف يد البوكر بأنها توليفة من 5 أوراق ( k  =  5) من مجموعة أوراق لعب مكونة من 52 ورقة ( n  =  52). جميع أوراق اليد الخمس مختلفة، ولا يهم ترتيبها. يوجد 2,598,960 توليفة من هذا النوع، واحتمالية سحب أي يد عشوائيًا هي  1  /  2,598,960.

يُشار غالبًا في كتب التوافقية الأساسية إلى عدد التوليفات من الرتبة k من مجموعة معينة S مكونة من n عنصرًا بالرمز k.${\displaystyle C(n,k)}$أو عن طريق صيغة مختلفة مثل${\displaystyle C_{k}^{n}}$، ${\displaystyle {}_{n}C_{k}}$،${\displaystyle {}^{n}C_{k}}$،${\displaystyle C_{n,k}}$أو حتى${\displaystyle C_{n}^{k}}$[ ^{5 ] ومع ذلك ،} يظهر نفس الرقم في العديد من السياقات الرياضية الأخرى، حيث يُرمز إليه بـ${\displaystyle {\tbinom {n}{k}}}$(غالباً ما تُقرأ " ن يختار ك ")؛ ومن الجدير بالذكر أنها تظهر كمعامل في صيغة ذات الحدين ، ومن هنا جاء اسمها معامل ذات الحدين. يمكن تعريف${\displaystyle {\tbinom {n}{k}}}$لجميع الأعداد الطبيعية k في آن واحد بالعلاقة

$${\displaystyle (1+X)^{n}=\sum _{k\geq 0}{\binom {n}{k}}X^{k},}$$

ويتضح من ذلك أن

$${\displaystyle {\binom {n}{0}}={\binom {n}{n}}=1,}$$

والمزيد

$${\displaystyle {\binom {n}{k}}=0}$$

ل${\displaystyle k>n}$.

لإثبات أن هذه المعاملات تحسب k من التوليفات من S ، يمكن للمرء أولاً أن ينظر في مجموعة من n متغيرات مميزة X _s مصنفة بواسطة العناصر s من S ، وتوسيع الناتج على جميع عناصر S : 

$${\displaystyle \prod _{s\in S}(1+X_{s});}$$

تحتوي على 2 ^{^n} حدًا مميزًا تُقابل جميع المجموعات الجزئية من S ، حيث تُعطي كل مجموعة جزئية حاصل ضرب المتغيرات المقابلة لها X^ _s . الآن، بمساواة جميع قيم X _^s بالمتغير غير المُسمى X ، بحيث يصبح حاصل الضرب (1 + X ^ ⁿ⁾ ، يصبح الحد الخاص بكل توليفة k من S هو X^ ^k ، وبالتالي فإن معامل هذا الأس في النتيجة يساوي عدد هذه التوليفات k .

يمكن حساب معاملات ذات الحدين بشكل صريح بطرق مختلفة. وللحصول على جميعها للتوسعات حتى (1 + X ) ^ⁿ ، يمكن استخدام علاقة التكرار (بالإضافة إلى الحالات الأساسية المذكورة سابقًا).

$${\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},}$$

لـ 0 < k < n ، وهو ما يتبع من (1 + X ) ⁿ = (1 + X ) ^{n − 1} (1 + X ) ؛ وهذا يؤدي إلى إنشاء مثلث باسكال .

لتحديد معامل ذي الحدين الفردي، من العملي أكثر استخدام الصيغة التالية:

$${\displaystyle {\binom {n}{k}}={\frac {n(n-1)(n-2)\cdots (n-k+1)}{k!}}.}$$

يعطي البسط عدد التباديل k لـ n ، أي تسلسلات من k عناصر مميزة من S ، بينما يعطي المقام عدد هذه التباديل k التي تعطي نفس التركيبة k عند تجاهل الترتيب.

عندما تتجاوز قيمة k قيمة n /2، فإن الصيغة أعلاه تحتوي على عوامل مشتركة بين البسط والمقام، وبحذفها نحصل على العلاقة

$${\displaystyle {\binom {n}{k}}={\binom {n}{nk}},}$$

لـ 0 ≤ k ≤ n . هذا يعبر عن تناظر واضح من صيغة ذات الحدين، ويمكن فهمه أيضًا من حيث التوافيق k عن طريق أخذ مكمل هذا التوافيق، وهو توافيق ( n − k ) .

وأخيراً، هناك صيغة تُظهر هذا التناظر بشكل مباشر، وتتميز بسهولة تذكرها:

$${\displaystyle {\binom {n}{k}}={\frac {n!}{k!(nk)!}},}$$

حيث يرمز n ! إلى مضروب n . ويتم الحصول عليه من الصيغة السابقة بضرب المقام والبسط في ( n − k ) !، لذا فهو بالتأكيد أقل كفاءة حسابية من تلك الصيغة.

يمكن فهم الصيغة الأخيرة مباشرةً بالنظر إلى عدد n من التباديل لجميع عناصر المجموعة S. يُعطي كل تبديل من هذه التباديل k تركيبةً باختيار أول k عنصر منها. توجد العديد من الاختيارات المكررة: أي تبديل مُدمج لأول k عنصر فيما بينها، ولآخر ( n - k ) عنصر فيما بينها، يُنتج نفس التركيبة؛ وهذا يُفسر القسمة في الصيغة.  

انطلاقاً من الصيغ المذكورة أعلاه، يمكن استنتاج العلاقات بين الأعداد المتجاورة في مثلث باسكال في جميع الاتجاهات الثلاثة:

$${\displaystyle {\binom {n}{k}}={\begin{cases}\displaystyle {\binom {n}{k-1}}{\frac {n-k+1}{k}}&\quad {\text{إذا كان }}k>0\\\displaystyle {\binom {n-1}{k}}{\frac {n}{nk}}&\quad {\text{إذا كان }}k<n\\\displaystyle {\binom {n-1}{k-1}}{\frac {n}{k}}&\quad {\text{إذا كان }}n,k>0\end{cases}}.}$$

بالإضافة إلى الحالات الأساسية${\displaystyle {\tbinom {n}{0}}=1={\tbinom {n}{n}}}$، تسمح هذه بالحساب المتتالي لجميع أعداد التوليفات من نفس المجموعة (صف في مثلث باسكال)، والتوليفات k من مجموعات ذات أحجام متزايدة، والتوليفات ذات مكمل بحجم ثابت n − k .

تُعرَّف المجموعة الجزئية المتعددة من الرتبة k، أو المجموعة الجزئية المتعددة من الرتبة k، أو المجموعة الجزئية المتعددة من الرتبة k من مجموعة S من الرتبة n، بأنها مجموعة من k عنصرًا ، ليست بالضرورة عناصر متميزة ، من S ، حيث لا يُؤخذ الترتيب في الاعتبار : تُعرِّف سلسلتان نفس المجموعة الجزئية المتعددة إذا أمكن الحصول على إحداهما من الأخرى عن طريق تبديل الحدود. بعبارة أخرى، هي عينة من k عنصرًا من مجموعة من n عنصرًا تسمح بالتكرارات (أي مع الإحلال) ولكن تتجاهل الترتيبات المختلفة (مثل {2,1,2} = {1,2,2}). إذا ربطنا فهرسًا بكل عنصر من S واعتبرنا عناصر S أنواعًا من الكائنات، فيمكننا حينها أن${\displaystyle x_{i}}$لنرمز إلى عدد العناصر من النوع i في مجموعة جزئية متعددة. عدد المجموعات الجزئية المتعددة ذات الحجم k هو عدد الحلول الصحيحة غير السالبة (وبالتالي السماح بالصفر) للمعادلة الديوفانتية : ^{[ 9 ]}

$${\displaystyle x_{1}+x_{2}+\ldots +x_{n}=k.}$$

إذا كانت المجموعة S تحتوي على n عنصرًا، فإن عدد المجموعات الجزئية المتعددة من الرتبة k يُرمز له بـ

$${\displaystyle \left(\!\!{\binom {n}{k}}\!\!\right),}$$

رمز مشابه لمعامل ذي الحدين الذي يحسب المجموعات الجزئية من الرتبة k . يمكن أيضًا التعبير عن هذا الرمز، n multichoose k ، ^{[ 10 ] بدلالة معاملات ذي الحدين:}

$${\displaystyle \left(\!\!{\binom {n}{k}}\!\!\right)={\binom {n+k-1}{k}}.}$$

يمكن إثبات هذه العلاقة بسهولة باستخدام تمثيل يُعرف باسم النجوم والخطوط . ^{[ 11 ]}

كما هو الحال مع معاملات ذات الحدين، توجد عدة علاقات بين هذه التعبيرات متعددة الخيارات. على سبيل المثال، بالنسبة لـ${\displaystyle n\geq 1,k\geq 0}$،

$${\displaystyle \left(\!\!{\binom {n}{k}}\!\!\right)=\left(\!\!{\binom {k+1}{n-1}}\!\!\right).}$$ تنتج هذه الهوية من تبديل النجوم والخطوط في التمثيل أعلاه. ^{[ 13 ]}

مثال على عد المجموعات الفرعية المتعددة

على سبيل المثال، إذا كان لديك أربعة أنواع من الدونات ( ن  =  4) في قائمة طعام للاختيار من بينها، وتريد ثلاثة أنواع ( ك  =  3)، فيمكن حساب عدد طرق اختيار الدونات مع التكرار على النحو التالي:

$${\displaystyle \left(\!\!{\binom {4}{3}}\!\!\right)={\binom {4+3-1}{3}}={\binom {6}{3}}={\frac {6\times 5\times 4}{3\times 2\times 1}}=20.}$$

يمكن التحقق من هذه النتيجة بسرد جميع المجموعات الجزئية الثلاثية للمجموعة S = {1,2,3,4}. يظهر ذلك في الجدول التالي. ^{[ 14 ]} يسرد العمود الثاني قطع الدونات التي اخترتها فعليًا، بينما يُظهر العمود الثالث الحلول الصحيحة غير السالبة.${\displaystyle [x_{1},x_{2},x_{3},x_{4}]}$من المعادلة${\displaystyle x_{1}+x_{2}+x_{3}+x_{4}=3}$ويُظهر العمود الأخير تمثيل الحلول باستخدام النجوم والخطوط. ^{[ 15 ]}

لا.	3-مجموعة متعددة	حل المعادلة	النجوم والخطوط
1	{1,1,1}	[3,0,0,0]	${\displaystyle \bigstar \bigstar \bigstar |||}$
2	{1,1,2}	[2,1,0,0]	${\displaystyle \bigstar \bigstar |\bigstar ||}$
3	{1,1,3}	[2,0,1,0]	${\displaystyle \bigstar \bigstar ||\bigstar |}$
4	{1,1,4}	[2,0,0,1]	${\displaystyle \bigstar \bigstar |||\bigstar }$
5	{1,2,2}	[1,2,0,0]	${\displaystyle \bigstar |\bigstar \bigstar ||}$
6	{1,2,3}	[1,1,1,0]	${\displaystyle \bigstar |\bigstar |\bigstar |}$
7	{1,2,4}	[1,1,0,1]	${\displaystyle \bigstar |\bigstar ||\bigstar }$
8	{1,3,3}	[1,0,2,0]	${\displaystyle \bigstar ||\bigstar \bigstar |}$
9	{1,3,4}	[1,0,1,1]	${\displaystyle \bigstar ||\bigstar |\bigstar }$
10	{1,4,4}	[1,0,0,2]	${\displaystyle \bigstar |||\bigstar \bigstar }$
11	{2,2,2}	[0,3,0,0]	${\displaystyle |\bigstar \bigstar \bigstar ||}$
12	{2,2,3}	[0,2,1,0]	${\displaystyle |\bigstar \bigstar |\bigstar |}$
13	{2,2,4}	[0,2,0,1]	${\displaystyle |\bigstar \bigstar ||\bigstar }$
14	{2,3,3}	[0,1,2,0]	${\displaystyle |\bigstar |\bigstar \bigstar |}$
15	{2، 3، 4}	[0,1,1,1]	${\displaystyle |\bigstar |\bigstar |\bigstar }$
16	{2,4,4}	[0,1,0,2]	${\displaystyle |\bigstar ||\bigstar \bigstar }$
17	{3,3,3}	[0,0,3,0]	${\displaystyle ||\bigstar \bigstar \bigstar |}$
18	{3,3,4}	[0,0,2,1]	${\displaystyle ||\bigstar \bigstar |\bigstar }$
19	{3,4,4}	[0,0,1,2]	${\displaystyle ||\bigstar |\bigstar \bigstar }$
20	{4,4,4}	[0,0,0,3]	${\displaystyle |||\bigstar \bigstar \bigstar }$

عدد التوافيق الممكنة من الرتبة k لجميع قيم k هو عدد المجموعات الجزئية لمجموعة مكونة من n عنصرًا. وهناك عدة طرق لإثبات أن هذا العدد يساوي 2^ ⁿ . من حيث التوافيق،${\textstyle \sum _{0\leq {k}\leq {n}}{\binom {n}{k}}=2^{n}}$وهو مجموع الصف النوني (بدءًا من 0) لمعاملات ذات الحدين في مثلث باسكال . تُعدّ هذه التوليفات (المجموعات الجزئية) بواسطة الأرقام العشرية من مجموعة الأعداد الأساسية 2 بدءًا من 0 إلى 2^ ⁿ  -  1، حيث يمثل كل رقم عنصرًا من مجموعة n .

إذا تم إعطاء 3 بطاقات مرقمة من 1 إلى 3، فهناك 8 مجموعات فرعية مميزة ، بما في ذلك المجموعة الفارغة :

$${\displaystyle |\{\{\};\{1\};\{2\};\{1,2\};\{3\};\{1,3\};\{2,3\};\{1,2,3\}\}|=2^{3}=8}$$

تمثيل هذه المجموعات الفرعية (بنفس الترتيب) كأرقام أساسها 2:

• 0 – 000
• 1 – 001
• 2 – 010
• 3 – 011
• 4 – 100
• 5 – 101
• 6 – 110
• 7 – 111

توجد خوارزميات متنوعة لاختيار توليفة عشوائية من مجموعة أو قائمة معينة. يُعدّ أخذ العينات بالرفض بطيئًا للغاية مع أحجام العينات الكبيرة. إحدى طرق اختيار توليفة k بكفاءة من مجموعة بحجم n هي التكرار عبر كل عنصر من عناصر المجموعة، وفي كل خطوة يتم اختيار ذلك العنصر باحتمالية متغيرة ديناميكيًا.${\textstyle {\frac {k-\#{\text{samples chosen}}}{n-\#{\text{samples visited}}}}}$(انظر أخذ عينات الخزان ). وهناك طريقة أخرى وهي اختيار عدد صحيح غير سالب عشوائي أقل من${\displaystyle \textstyle {\binom {n}{k}}}$وتحويلها إلى مجموعة باستخدام نظام الأعداد التوافقية .

يمكن أيضًا اعتبار التوليفة بمثابة اختيار مجموعتين من العناصر: تلك التي توضع في الصندوق المُختار، وتلك التي توضع في الصندوق غير المُختار. ويمكن تعميم ذلك على أي عدد من الصناديق مع مراعاة أن كل عنصر يجب أن يوضع في صندوق واحد فقط. ويُعطى عدد طرق وضع العناصر في الصناديق بواسطة معامل متعدد الحدود.

$${\displaystyle {\binom {n}{k_{1},k_{2},\ldots ,k_{m}}}={\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}},}$$

حيث n هو عدد العناصر، و m هو عدد الصناديق، و${\displaystyle k_{i}}$يمثل عدد العناصر التي توضع في الصندوق i .

إحدى طرق فهم سبب صحة هذه المعادلة هي ترقيم الأشياء بشكل عشوائي من 1 إلى n ووضع الأشياء مع الأرقام${\displaystyle 1,2,\ldots ,k_{1}}$ضع الأشياء ذات الأرقام في الصندوق الأول بالترتيب${\displaystyle k_{1}+1,k_{1}+2,\ldots ,k_{1}+k_{2}}$في الصندوق الثاني بالترتيب، وهكذا. هناك${\displaystyle n!}$تختلف الترقيمات، لكن العديد منها متكافئ، لأن المهم هو مجموعة العناصر الموجودة في الصندوق، وليس ترتيبها فيه. كل تبديل مُركّب لمحتويات كل صندوق يُنتج طريقة مكافئة لوضع العناصر في الصناديق. ونتيجة لذلك، تتكون كل فئة تكافؤ من${\displaystyle k_{1}!\,k_{2}!\cdots k_{m}!}$ترقيم مميز، وعدد فئات التكافؤ هو${\displaystyle \textstyle {\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}}}$.

معامل ذي الحدين هو الحالة الخاصة التي يتم فيها وضع k عنصر في الصندوق المختار، والباقي${\displaystyle n-k}$يتم وضع العناصر في صندوق العناصر غير المختارة:

$${\displaystyle {\binom {n}{k}}={\binom {n}{k,n-k}}={\frac {n!}{k!(n-k)!}}.}$$

• بنيامين، آرثر ت .؛ كوين، جينيفر ج. (2003)، براهين ذات قيمة حقيقية: فن البرهان التوافقي ، سلسلة دولسياني للعروض الرياضية 27، الجمعية الرياضية الأمريكية، ISBN 978-0-88385-333-7
• بروالدي، ريتشارد أ. (2010)، مقدمة في التوافقية (  الطبعة الخامسة)، بيرسون برنتيس هول، رقم ISBN 978-0-13-602040-0
• إروين كريزيج ، الرياضيات الهندسية المتقدمة ، جون وايلي وأولاده، 1999.
• مازور، ديفيد ر. (2010)، التوافقية: جولة إرشادية ، الجمعية الرياضية الأمريكية، ISBN 978-0-88385-762-5
• رايزر، هربرت جون (1963)، الرياضيات التوافقية ، سلسلة كاروس للرياضيات 14، الجمعية الرياضية الأمريكية
• أوسبنسكي، جيمس (1937)، مقدمة في الاحتمالات الرياضية ، ماكجرو هيل

• العديد من أنواع مسائل التباديل والتوافيق الرياضية الشائعة، مع حلول مفصلة
• الصيغة المجهولة للتوليفات عندما يمكن تكرار الخيارات ولا يهم الترتيب
• مسألة رمي النرد بمجموع معين: تطبيق التوافيق مع التكرار على رمي عدة نرد