الطريقة الاثني عشرية

قد تكون هذه المقالة تقنية للغاية بحيث يصعب على معظم القراء فهمها . يرجى المساعدة في تحسينها لجعلها مفهومة لغير المتخصصين ، دون إزالة التفاصيل التقنية. ( مارس 2019 ) ( تعرف على كيفية ومتى يمكنك إزالة هذه الرسالة )

في علم التوافقيات ، الطريقة الاثني عشرية هي تصنيف منهجي لـ 12 مشكلة عدية ذات صلة تتعلق بمجموعتين منتهيتين، والتي تتضمن المشاكل الكلاسيكية لحساب التباديل والتوليفات والمجموعات المتعددة وتقسيمات إما مجموعة أو عدد . تُنسب فكرة التصنيف إلى جيان كارلو روتا ، واقترح الاسم جويل سبنسر . ^[1]

ليكن N و X مجموعات منتهية . وليكن و هما عدد المجموعات. وبالتالي فإن N هي مجموعة بها n عنصر، و X هي مجموعة بها x عنصر. ${\displaystyle n=|N|}$${\displaystyle x=|X|}$

المشكلة العامة التي نأخذها في الاعتبار هي تعداد فئات التكافؤ للوظائف . ${\displaystyle f:N\to X}$

تخضع الوظائف لأحد القيود الثلاثة التالية:

• لا يوجد شرط: يمكن إرسال كل a في N بواسطة f إلى أي b في X ، ويمكن أن يحدث كل b عدة مرات.
• f هي قيمة حقنية : كل قيمة لـ a في N يجب أن تكون مميزة عن كل قيمة أخرى، وبالتالي فإن كل b في X قد تظهر مرة واحدة على الأكثر في صورة f .${\displaystyle f(a)}$
• f هي حالة شمولية : لكل b في X يجب أن يكون هناك على الأقل a واحد في N بحيث ، وبالتالي فإن كل b سوف يظهر مرة واحدة على الأقل في صورة f .${\displaystyle f(a)=b}$

(الشرط " f هو شرط محايد " هو خيار فقط عندما ؛ ولكن بعد ذلك يكون مكافئًا لكل من " f هو شرط محايد" و" f هو شرط محايد".) ${\displaystyle n=x}$

هناك أربع علاقات تكافؤ مختلفة يمكن تعريفها على مجموعة الدوال f من N إلى X :

• المساواة؛
• المساواة حتى تبديل N ؛​​
• المساواة حتى تبديل X ؛
• المساواة حتى تبديلات N و X.

يمكن إقران الشروط الثلاثة للوظائف وعلاقات التكافؤ الأربعة بـ 3 × 4 = 12 طريقة.

لا تنطوي المسائل الاثنتي عشرة الخاصة بحساب فئات التكافؤ للوظائف على نفس الصعوبات، ولا توجد طريقة منهجية واحدة لحلها. اثنتان من المسائل تافهتان (عدد فئات التكافؤ هو 0 أو 1)، وخمس مسائل لها إجابة من حيث صيغة الضرب n و x ، والمسائل الخمس المتبقية لها إجابة من حيث الدوال التوافقية ( أرقام ستيرلينج ودالة التقسيم لعدد معين من الأجزاء).

يتم دمج مشاكل العد الكلاسيكية في هذا الإعداد على النحو التالي.

• إن عد n من التبديلات (أي التبديلات الجزئية أو التسلسلات بدون تكرار) لـ X يعادل عد الدوال الحقنية N → X.
• إن عد n من التركيبات لـ X يعادل عد الدوال الحقنية N → X حتى التباديل لـ N.
• إن عد التباديل للمجموعة X يعادل عد الدوال الحقنية N → X عندما n = x ، ويعادل أيضًا عد الدوال الشاملة N → X عندما n = x .
• إن عد مجموعات متعددة من الحجم n (المعروفة أيضًا باسم n من التركيبات ذات التكرارات) من العناصر في X يعادل عد جميع الدوال N → X حتى تبديلات N.
• إن عد أقسام المجموعة N إلى مجموعات فرعية X يعادل عد جميع الدوال الشاملة N → X حتى تبديلات X.
• إن عد تركيبات العدد n إلى x أجزاء يعادل عد جميع الدوال الشاملة N → X حتى تبديلات N.

يمكن النظر إلى المشاكل المختلفة في الطريقة الاثني عشر من وجهات نظر مختلفة.

تقليديًا، تمت صياغة العديد من المشكلات في الطريقة الاثني عشرية من حيث وضع الكرات في الصناديق (أو بعض التصورات المماثلة) بدلاً من تعريف الوظائف. يمكن تحديد المجموعة N بمجموعة من الكرات، و X بمجموعة من الصناديق؛ تصف الوظيفة بعد ذلك طريقة لتوزيع الكرات في الصناديق، أي بوضع كل كرة في صندوق . تنسب الوظيفة صورة فريدة لكل قيمة في نطاقها؛ تنعكس هذه الخاصية من خلال الخاصية التي مفادها أن أي كرة يمكن أن تدخل صندوقًا واحدًا فقط (جنبًا إلى جنب مع المتطلب الذي ينص على عدم بقاء أي كرة خارج الصناديق)، في حين يمكن لأي صندوق استيعاب عدد عشوائي من الكرات. إن اشتراط أن تكون بالإضافة إلى كونها حقنية يعني منع وضع أكثر من كرة واحدة في أي صندوق واحد، بينما يعني اشتراط أن تكون شمولية الإصرار على أن يحتوي كل صندوق على كرة واحدة على الأقل. ${\displaystyle f:N\to X}$${\displaystyle f(a)}$${\displaystyle f}$${\displaystyle f}$

إن عد التباديل المعيارية لـ N أو X ينعكس من خلال وصف الكرات أو الصناديق على التوالي بأنها "غير قابلة للتمييز". هذه صياغة غير دقيقة، تهدف إلى الإشارة إلى أنه لا ينبغي عد التكوينات المختلفة بشكل منفصل إذا كان من الممكن تحويل إحداها إلى الأخرى عن طريق بعض التبادلات للكرات أو الصناديق. يتم إضفاء الطابع الرسمي على إمكانية التحويل هذه من خلال العمل بالتباديل.

هناك طريقة أخرى للتفكير في بعض الحالات من حيث العينة ، في الإحصاء . تخيل مجموعة من العناصر (أو الأشخاص) X ، اخترنا منها N. يتم وصف مخططين مختلفين عادةً، يُعرفان باسم " العينة مع الاستبدال " و " العينة بدون استبدال ". في الحالة الأولى (العينة مع الاستبدال)، بمجرد اختيار عنصر ما، نضعه مرة أخرى في المجموعة، حتى نتمكن من اختياره مرة أخرى. والنتيجة هي أن كل خيار مستقل عن جميع الخيارات الأخرى، ويشار إلى مجموعة العينات تقنيًا على أنها مستقلة وموزعة بشكل متطابق . ومع ذلك، في الحالة الأخيرة، بمجرد اختيار عنصر ما، نضعه جانبًا حتى لا نتمكن من اختياره مرة أخرى. وهذا يعني أن فعل اختيار عنصر ما له تأثير على جميع الخيارات التالية (لا يمكن رؤية العنصر المعين مرة أخرى)، وبالتالي فإن خياراتنا تعتمد على بعضها البعض.

إن التمييز الثاني بين مخططات أخذ العينات هو ما إذا كان الترتيب مهمًا. على سبيل المثال، إذا كان لدينا عشرة عناصر، اخترنا منها عنصرين، فإن الاختيار (4، 7) يختلف عن (7، 4) إذا كان الترتيب مهمًا؛ من ناحية أخرى، إذا لم يكن الترتيب مهمًا، فإن الاختيارين (4، 7) و(7، 4) متكافئان.

يتوافق الصفان والأعمدة الأوليان من الجدول أدناه مع أخذ العينات مع الاستبدال وبدونه، مع مراعاة الترتيب وبدونه. توجد حالات أخذ العينات مع الاستبدال في العمود المسمى "أي "، بينما توجد حالات أخذ العينات بدون استبدال في العمود المسمى "حقن ". توجد الحالات التي يكون فيها الترتيب مهمًا في الصف المسمى "متميز"، وتوجد الحالات التي لا يكون فيها الترتيب مهمًا في الصف المسمى " مدارات S _n ". يشير كل إدخال في الجدول إلى عدد مجموعات الاختيارات المختلفة الموجودة، في مخطط أخذ عينات معين. تتوافق ثلاثة من إدخالات الجدول هذه أيضًا مع توزيعات الاحتمالات . أخذ العينات مع الاستبدال حيث يكون الترتيب مهمًا يمكن مقارنته بوصف التوزيع المشترك لـ N متغير عشوائي منفصل ، كل منها بتوزيع فئوي X -fold . ومع ذلك، فإن أخذ العينات مع الاستبدال حيث لا يكون الترتيب مهمًا يمكن مقارنته بوصف توزيع متعدد الحدود واحد لـ N سحوبات من فئة X -fold، حيث يهم فقط العدد المرئي لكل فئة. إن أخذ العينات بدون استبدال حيث لا يهم الترتيب يمكن مقارنته بتوزيع هندسي متعدد المتغيرات واحد . أما أخذ العينات بدون استبدال حيث يهم الترتيب فلا يبدو أنه يتوافق مع توزيع الاحتمالات. ^[2] وفي جميع الحالات الحقنية (أخذ العينات بدون استبدال)، يكون عدد مجموعات الاختيارات صفرًا ما لم يكن N ≤ X. (تعني عبارة "قابلة للمقارنة" في الحالات المذكورة أعلاه أن كل عنصر من عناصر مساحة العينة للتوزيع المقابل يتوافق مع مجموعة منفصلة من الاختيارات، وبالتالي فإن الرقم الموجود في المربع المناسب يشير إلى حجم مساحة العينة للتوزيع المعطى). ${\displaystyle f}$${\displaystyle f}$

من منظور أخذ العينات، فإن العمود المسمى "Surjective " غريب إلى حد ما: في الأساس، نستمر في أخذ العينات مع الاستبدال حتى نختار كل عنصر مرة واحدة على الأقل. ثم نحسب عدد الخيارات التي قمنا بها، وإذا لم تكن مساوية لـ N ، نتخلص من المجموعة بأكملها ونكرر. هذا قابل للمقارنة بشكل غامض بمشكلة جامع القسائم ، حيث تتضمن العملية "جمع" (عن طريق أخذ العينات مع الاستبدال) مجموعة من X قسائم حتى تتم رؤية كل قسيمة مرة واحدة على الأقل. في جميع حالات Surjective ، يكون عدد مجموعات الخيارات صفرًا ما لم يكن N ≥ X.${\displaystyle f}$

يمكن النظر إلى الدالة من منظور X أو N. وهذا يؤدي إلى وجهات نظر مختلفة: ${\displaystyle f:N\to X}$

• تقوم الدالة بتسمية كل عنصر من N بعنصر من X.${\displaystyle f}$
• تختار الوظيفة عنصرًا من المجموعة X لكل عنصر من N ، بإجمالي n اختيارًا.${\displaystyle f}$
• تقوم الوظيفة بتجميع عناصر N معًا والتي يتم تعيينها إلى نفس عنصر X.${\displaystyle f}$

لا تصلح وجهات النظر هذه بالتساوي لجميع الحالات. فوجهتا نظر التسمية والاختيار غير متوافقتين جيدًا مع تبديل عناصر X ، لأن هذا يغير التسميات أو الاختيار؛ ومن ناحية أخرى، لا تقدم وجهة نظر التجميع معلومات كاملة عن التكوين ما لم يكن من الممكن تبديل عناصر X بحرية. وتكون وجهتا نظر التسمية والاختيار متكافئتين إلى حد ما عندما لا يتم تبديل N ، ولكن عندما يتم ذلك، تكون وجهة نظر الاختيار أكثر ملاءمة. ومن ثم يمكن النظر إلى الاختيار باعتباره اختيارًا غير مرتب: يتم إجراء اختيار واحد لمجموعة (متعددة) من n عنصر من X.

عند النظر إلى N على أنها تسمية لعناصرها ، يمكن اعتبار الأخير مرتبًا في تسلسل، والتسميات من X يتم تعيينها على التوالي لها. يعني الشرط الذي يكون حقنًا أنه لا يمكن استخدام أي تسمية مرة ثانية؛ والنتيجة هي تسلسل من التسميات بدون تكرار . في غياب مثل هذا الشرط، يتم استخدام المصطلح "تسلسلات مع التكرار"، مما يعني أنه يمكن استخدام التسميات أكثر من مرة (على الرغم من أن التسلسلات التي تكون بدون تكرار مسموح بها أيضًا). ${\displaystyle f}$${\displaystyle f}$

عند عرض عناصر X كاختيار غير مرتب ، ينطبق نفس النوع من التمييز. إذا كان يجب أن يكون حقنيًا، فيجب أن يتضمن الاختيار n عناصر مميزة من X ، لذا فهو مجموعة فرعية من X بحجم n ، وتسمى أيضًا تركيبة n . بدون هذا المتطلب، قد يحدث نفس عنصر X عدة مرات في الاختيار، والنتيجة هي مجموعة متعددة من عناصر X بحجم n ، وتسمى أيضًا تركيبة متعددة n أو تركيبة n مع التكرار. ${\displaystyle f}$${\displaystyle f}$

إن الشرط الذي يتطلب أن يكون العنصر شموليًا، من وجهة نظر تسمية عناصر N ، يعني أنه يجب استخدام كل تسمية مرة واحدة على الأقل؛ ومن وجهة نظر الاختيار من X ، فهذا يعني أنه يجب تضمين كل عنصر من X في الاختيار مرة واحدة على الأقل. إن التسمية باستخدام الشمولية تعادل تجميع عناصر N متبوعًا بتسمية كل مجموعة بعنصر من X ، وبالتالي يكون وصفها رياضيًا أكثر تعقيدًا إلى حد ما. ${\displaystyle f}$

عند النظر إلى الأمر باعتباره مجموعة من عناصر N (وهو ما يفترض أن يتم تحديده تحت ترتيبات X )، فإن اشتراط أن يكون العدد مطلقًا يعني أن عدد المجموعات يجب أن يكون بالضبط x . وبدون هذا الشرط، لا يمكن أن يكون عدد المجموعات أكثر من x . ويعني شرط أن يكون العدد مطلقًا أن كل عنصر من عناصر N يجب أن يكون مجموعة في حد ذاته، وهو ما يترك مجموعة واحدة صالحة على الأكثر وبالتالي يعطي مشكلة عد غير مثيرة للاهتمام إلى حد ما .${\displaystyle f}$${\displaystyle f}$${\displaystyle f}$

عندما يتم تحديد إضافة إلى ذلك تحت ترتيبات N ، فإن هذا يعادل نسيان المجموعات نفسها مع الاحتفاظ بأحجامها فقط. علاوة على ذلك، لا تأتي هذه الأحجام بأي ترتيب محدد، في حين قد يحدث نفس الحجم أكثر من مرة؛ قد يختار المرء ترتيبها في قائمة متناقصة بشكل ضعيف من الأرقام، يكون مجموعها هو الرقم n . وهذا يعطي المفهوم التوافقي لتقسيم الرقم n ، إلى أجزاء x بالضبط (للمجموع الكلي ) أو x على الأكثر (للأجزاء التعسفية ). ${\displaystyle f}$${\displaystyle f}$

يتم تلخيص الصيغ الخاصة بالحالات المختلفة للطريقة الاثني عشرية في الجدول التالي؛ ويرتبط كل مدخل في الجدول بقسم فرعي أدناه يشرح الصيغة.

الكائنات التركيبية الإثني عشر وصيغ تعدادها

${\displaystyle f}$-فصل	أي${\displaystyle f}$	حقنة${\displaystyle f}$	صفة${\displaystyle f}$
مميزة ف	تسلسل n في X x n {\displaystyle x^{n}}	تبديل n لـ X x n _ {\displaystyle x^{\underline {n}}}	تكوين N مع X مجموعات فرعية x ! { n x } {\displaystyle x!\left\{{n \atop x}\right\}}
يدور S n حول f ∘ S n	مجموعة فرعية متعددة من X ( x + n − 1 n ) {\displaystyle {\binom {x+n-1}{n}}}	مجموعة فرعية من x ( x n ) {\displaystyle {\binom {x}{n}}}	تكوين n مع x حدود ( n − 1 n − x ) {\displaystyle {\binom {n-1}{nx}}}
S x يدور حول S x ∘ f	تقسيم N إلى ≤ x مجموعات فرعية ∑ k = 0 x { n k } {\displaystyle \sum _{k=0}^{x}\left\{{n \atop k}\right\}}	تقسيم N إلى ≤ x عناصر [ n ≤ x ] {\displaystyle [n\leq x]}	تقسيم N إلى مجموعات فرعية x { n x } {\displaystyle \left\{{n \atop x}\right\}}
S n × S x يدور حول S x ∘ f ∘ S n	تقسيم n إلى ≤ x أجزاء p x ( n + x ) {\displaystyle p_{x}(n+x)}	تقسيم n إلى ≤ x أجزاء 1 [ n ≤ x ] {\displaystyle [n\leq x]}	تقسيم n إلى x أجزاء p x ( n ) {\displaystyle p_{x}(n)}

الرموز الخاصة المستخدمة هي:

• القوة العاملية المتساقطة ${\textstyle x^{\underline {n}}={\frac {x!}{(xn)!}}=x(x-1)(x-2)\cdots (x-n+1)}$
• القوة العاملية الصاعدة ${\textstyle x^{\overline {n}}={\frac {(x+n-1)!}{(x-1)!}}=x(x+1)(x+2)\cdots (x+n-1)}$
• العامل​ ${\textstyle n!=n^{\underline {n}}=n(n-1)(n-2)\cdots 1}$
• عدد ستيرلينج من النوع الثاني ، والذي يشير إلى عدد الطرق لتقسيم مجموعة من n عنصر إلى k مجموعات فرعية غير فارغة${\textstyle \left\{{n \atop k}\right\}}$
• معامل ثنائي الحدين ${\textstyle {\binom {n}{k}}={\frac {n^{\underline {k}}}{k!}}}$
• قوس إيفرسون [ ] الذي يشفر قيمة الحقيقة على أنها 0 أو 1
• عدد أقسام n إلى k جزء​​${\textstyle p_{k}(n)}$

هذا ملخص سريع لما تعنيه الحالات المختلفة. يتم وصف الحالات بالتفصيل أدناه.

فكر في مجموعة من العناصر المرقمة X (مرقمة من 1 إلى x )، والتي نختار منها n ، مما ينتج عنه قائمة مرتبة من العناصر: على سبيل المثال، إذا كان هناك عناصر نختار منها ، فقد تكون النتيجة هي القائمة (5، 2، 10). ثم نحسب عدد القوائم المختلفة الموجودة، وأحيانًا نقوم أولاً بتحويل القوائم بطرق تقلل من عدد الاحتمالات المتميزة. ${\displaystyle x=10}$${\displaystyle n=3}$

ثم تعني الأعمدة:

أي ف

بعد أن نختار عنصرًا ما، نضعه في مكانه، حتى نتمكن من اختياره مرة أخرى.

حقنة ف

بعد أن نختار عنصرًا، نضعه جانبًا، لذا لا يمكننا اختياره مرة أخرى؛ وبالتالي سننتهي بـ n عنصرًا مميزًا. وبالتالي، لا يمكن اختيار أي قوائم على الإطلاق، ما لم يكن ،.${\displaystyle n\leq x}$

ضمير المخاطب f

بعد أن نختار عنصرًا ما، نعيده إلى مكانه، حتى نتمكن من اختياره مرة أخرى — ولكن في النهاية، يتعين علينا أن ننتهي باختيار كل عنصر مرة واحدة على الأقل. وبالتالي، لا يمكن اختيار أي قوائم على الإطلاق، ما لم يكن ذلك صحيحًا.${\displaystyle n\geq x}$

والصفوف تعني:

متميز

اترك القوائم بمفردها؛ احسبها بشكل مباشر.

مدارات S _n

قبل العد، قم بفرز القوائم حسب رقم العنصر للعناصر المختارة، بحيث لا يهم الترتيب، على سبيل المثال، (5، 2، 10)، (10، 2، 5)، (2، 10، 5) → (2، 5، 10).

مدارات S _x

قبل العد، قم بإعادة ترقيم العناصر التي تمت رؤيتها بحيث يكون العنصر الأول الذي تمت رؤيته يحمل الرقم 1، والثاني 2، وهكذا. قد تتكرر الأرقام إذا تمت رؤية العنصر أكثر من مرة، على سبيل المثال، (3، 5، 3)، (5، 2، 5)، (4، 9، 4) → (1، 2، 1) بينما (3، 3، 5)، (5، 5، 3)، (2، 2، 9) → (1، 1، 2).

مدارات S _n × S _x

يتم احتساب القائمتين على أنهما متماثلتان إذا كان من الممكن إعادة ترتيبهما وإعادة تسميتهما كما هو موضح أعلاه وإنتاج نفس النتيجة. على سبيل المثال، يتم احتساب (3، 5، 3) و(2، 9، 9) على أنهما متماثلتان لأنه يمكن إعادة ترتيبهما على أنهما (3، 3، 5) و(9، 9، 2) ثم يؤدي إعادة التسمية إلى إنتاج نفس القائمة (1، 1، 2).

الرسم البياني أدناه مشابه للرسم البياني أعلاه، ولكن بدلاً من عرض الصيغ، فإنه يعطي فهمًا بديهيًا لمعناها باستخدام مثال الكرات والصناديق المألوف. تمثل الصفوف تميز الكرات والصناديق. تمثل الأعمدة ما إذا كان يُسمح بحزم متعددة (أكثر من كرة في صندوق واحد) أو صناديق فارغة. تُظهر الخلايا في الرسم البياني السؤال الذي تتم الإجابة عليه عن طريق حل الصيغة الواردة في الرسم البياني للصيغة أعلاه.

جدول الكائنات التركيبية الاثني عشر - مخطط بديهي باستخدام الكرات والصناديق

	أي ف (لا توجد قواعد بشأن التنسيب)	حقنة ف (لا يسمح بالحزم المتعددة)	ضمير المخاطب f (لا يسمح بوضع الصناديق الفارغة)
f (الكرات والصناديق المحددة)	تسلسل n في X كم عدد الطرق التي يمكنك بها وضع الكرات المحددة بـ n في الصناديق المحددة بـ x، دون وجود قواعد أخرى فيما يتعلق بالوضع؟	تبديل n في X كم عدد الطرق التي يمكنك بها وضع الكرات المحددة بـ n في الصناديق المحددة بـ x، مع عدم السماح بوضع مجموعات متعددة من الكرات؟	تكوين N مع مجموعات فرعية x كم عدد الطرق التي يمكنك بها وضع الكرات المحددة بـ n في الصناديق المحددة بـ x، مع عدم السماح بأي صناديق فارغة؟
f ∘ S n (كرات عادية، مربعات مميزة)	مجموعة فرعية متعددة من X كم عدد الطرق التي يمكنك بها وضع n كرة عادية في صناديق تحمل علامة X، دون وجود قواعد أخرى بشأن وضع الكرات؟	مجموعة فرعية من X كم عدد الطرق التي يمكنك بها وضع n كرة عادية في صناديق تحمل علامة X، مع عدم السماح بوضع مجموعات متعددة منها؟	تكوين n مع x من الحدود كم عدد الطرق التي يمكنك بها وضع n كرة عادية في صناديق تحمل علامة X، مع عدم السماح بأي صناديق فارغة؟
S x ∘ f (كرات مميزة، صناديق عادية)	تقسيم N إلى مجموعات فرعية ≤ x كم عدد الطرق التي يمكنك بها وضع n كرة محددة في x صندوق عادي، دون وجود قواعد أخرى بشأن وضع الكرات؟	تقسيم N إلى عناصر ≤ x كم عدد الطرق التي يمكنك بها وضع الكرات المحددة بـ n في x صناديق عادية، مع عدم السماح بوضع مجموعات متعددة منها؟	تقسيم N إلى مجموعات فرعية x كم عدد الطرق التي يمكنك بها وضع n كرة محددة في x صناديق عادية، مع عدم السماح بأي صناديق فارغة؟
S x ∘ f ∘ S n (كرات وصناديق عادية)	تقسيم n إلى ≤ x أجزاء كم عدد الطرق التي يمكنك بها وضع n كرة عادية في x صندوق عادي، دون وجود قواعد أخرى بشأن وضع الكرات؟	تقسيم n إلى ≤ x أجزاء 1 كم عدد الطرق التي يمكنك بها وضع n كرة عادية في x صندوق عادي، مع عدم السماح بوضع عبوات متعددة؟	تقسيم n إلى x أجزاء كم عدد الطرق التي يمكنك بها وضع n كرة عادية في x صندوق عادي، مع عدم السماح بأي صندوق فارغ؟

يتم ترتيب الحالات أدناه بطريقة يتم بها تجميع الحالات التي ترتبط بها الحجج المستخدمة في العد، وهو ليس الترتيب الموجود في الجدول الموضح.

هذه الحالة تعادل حساب تسلسلات من n عنصر من X بدون قيود: يتم تحديد الدالة f  : N → X من خلال n صورة لعناصر N ، والتي يمكن اختيار كل منها بشكل مستقل بين عناصر x . وهذا يعطي إجمالي x ⁿ احتمالات.

مثال:

${\displaystyle X=\{a,b,c\},N=\{1,2\}{\text{, ثم }}}$

${\displaystyle \left\vert \{(أ، أ)،(أ، ب)،(أ، ج)،(ب، أ)،(ب، ب)،(ب، ج)،(ج، أ)،(ج، ب)،(ج، ج)\}\right\vert =3^{2}=9}$

هذه الحالة تعادل عد تسلسلات من n عنصر مميز من X ، وتسمى أيضًا n تبديلات من X ، أو تسلسلات بدون تكرارات ؛ مرة أخرى يتكون هذا التسلسل من n صورة لعناصر N. تختلف هذه الحالة عن حالة التسلسلات غير المقيدة في أن هناك خيارًا أقل للعنصر الثاني، واثنين أقل للعنصر الثالث، وهكذا. لذلك بدلاً من قوة عادية لـ x ، تُعطى القيمة بقوة عاملية متساقطة لـ x ، حيث يكون كل عامل متتالي أقل بمقدار واحد من العامل السابق. الصيغة هي

${\displaystyle x^{\underline {n}}=x(x-1)\cdots (x-n+1).}$

لاحظ أنه إذا كان n > x فإننا نحصل على عامل صفر، لذلك في هذه الحالة لا توجد وظائف حقن N → X على الإطلاق؛ وهذا مجرد إعادة صياغة لمبدأ الحمامة .

مثال:

${\displaystyle X=\{a,b,c,d\},N=\{1,2\}{\text{, then }}}$

${\displaystyle \left\vert \{(a,b),(a,c),(a,d),(b,a),(b,c),(b,d),(c,a),(c,b),(c,d),(d,a),(d,b),(d,c)\}\right\vert =4^{\underline {2}}=4\times 3=12}$

هذه الحالة تعادل حساب مجموعات فرعية تحتوي على n عنصر من X ، وتسمى أيضًا n- تركيبات من X : بين تسلسلات n عنصر مميز من X ، يتم تحديد العناصر التي تختلف فقط في ترتيب حدودها من خلال تبديلات N. نظرًا لأن هذه المجموعات في جميع الحالات تجمع معًا n ! تسلسلات مختلفة تمامًا ، يمكننا قسمة عدد هذه التسلسلات على n ! للحصول على عدد n- تركيبات من X. يُعرف هذا الرقم باسم المعامل الثنائي ، والذي يُعطى بالتالي بواسطة ${\displaystyle {\tbinom {x}{n}}}$

${\displaystyle {\binom {x}{n}}={\frac {x^{\underline {n}}}{n!}}={\frac {x(x-1)\cdots (x-n+2)(x-n+1)}{n(n-1)\cdots 2\cdot 1}}.}$

مثال:

${\displaystyle X=\{a,b,c,d\},N=\{1,2\}{\text{, then }}}$

${\displaystyle \left\vert \{\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\}\}\right\vert ={\frac {4^{\underline {2}}}{2!}}={\frac {4\times 3}{2}}=6}$

هذه الحالة تعادل عد مجموعات متعددة تحتوي على n عنصر من X (وتسمى أيضًا n - مجموعات متعددة ). والسبب هو أنه بالنسبة لكل عنصر من X يتم تحديد عدد عناصر N التي يتم تعيينها إليه بواسطة f ، بينما يمكن دائمًا تحويل دالتين تعطيان نفس "التعددات" لكل عنصر من X إلى أخرى عن طريق تبديل N. الصيغة التي تحسب جميع الدوال N → X ليست مفيدة هنا، لأن عددها المجمعة معًا عن طريق تبديلات N يختلف من دالة إلى أخرى. بدلاً من ذلك، كما هو موضح تحت التوليفات ، يمكن رؤية عدد n - مجموعات متعددة من مجموعة تحتوي على x عناصر على أنه نفس عدد n - مجموعات من مجموعة تحتوي على x + n - 1 عنصر. هذا يقلل المشكلة إلى مشكلة أخرى بطريقة اثني عشر ضعفًا، ويعطي النتيجة

${\displaystyle {\binom {x+n-1}{n}}={\frac {(x+n-1)(x+n-2)\cdots (x+1)x}{n(n-1)\cdots 2\cdot 1}}={\frac {x^{\overline {n}}}{n!}}.}$

مثال:

${\displaystyle X=\{a,b,c\},N=\{1,2\}{\text{, then }}}$

${\displaystyle \left\vert \{\{a,a\},\{a,b\},\{a,c\},\{b,b\},\{b,c\},\{c,c\}\}\right\vert ={\frac {3^{\overline {2}}}{2!}}={\frac {4\times 3}{2}}=6}$

هذه الحالة تعادل عد مجموعات متعددة تحتوي على n عنصر من X ، حيث يحدث كل عنصر من X مرة واحدة على الأقل. وهذا يعادل أيضًا عد تركيبات n مع x (مصطلحات غير صفرية) ، من خلال سرد مضاعفات عناصر x بالترتيب. المراسلات بين الدوال والمجموعات المتعددة هي نفسها كما في الحالة السابقة، ويعني شرط التبعية أن جميع المضاعفات تكون على الأقل واحدة. من خلال تقليل جميع المضاعفات بمقدار 1، يتم تقليل هذا إلى الحالة السابقة؛ نظرًا لأن التغيير يقلل من قيمة n بمقدار x ، تكون النتيجة

${\displaystyle {\binom {n-1}{n-x}}.}$

لاحظ أنه عندما تكون n < x لا توجد دوال شمولية N → X على الإطلاق (نوع من مبدأ "الخانة الفارغة")؛ يؤخذ هذا في الاعتبار في الصيغة، وفقًا للاتفاقية التي تنص على أن معاملات ثنائية الحد تكون دائمًا 0 إذا كان المؤشر الأدنى سلبيًا. يتم أيضًا إعطاء نفس القيمة بواسطة التعبير

${\displaystyle {\binom {n-1}{x-1}},}$

باستثناء الحالة القصوى n = x = 0 ، حيث يعطي التعبير السابق بشكل صحيح ، بينما يعطي التعبير الأخير بشكل غير صحيح . ${\displaystyle {\tbinom {-1}{0}}=1}$${\displaystyle {\tbinom {-1}{-1}}=0}$

يشير شكل النتيجة إلى البحث عن طريقة لربط فئة من الدوال الشاملة N → X مباشرة بمجموعة فرعية من عناصر n − x المختارة من إجمالي n − 1 ، ويمكن القيام بذلك على النحو التالي. اختر أولاً ترتيبًا إجماليًا للمجموعتين N و X ، ولاحظ أنه من خلال تطبيق تبديل مناسب لـ N ، يمكن تحويل كل دالة شاملة N → X إلى دالة فريدة متزايدة بشكل ضعيف (وبالطبع لا تزال شاملة). إذا ربط المرء عناصر N بالترتيب بمقدار n − 1 قوس في رسم بياني خطي ، فعند اختيار أي مجموعة فرعية من n − x قوس وإزالة الباقي، يحصل المرء على رسم بياني به مكونات متصلة x ، ومن خلال إرسالها إلى العناصر المتعاقبة لـ X ، يحصل المرء على دالة شاملة متزايدة بشكل ضعيف N → X ؛ كما أن أحجام المكونات المتصلة تعطي تركيبة من n إلى x أجزاء. هذه الحجة هي في الأساس الحجة المذكورة في النجوم والأشرطة ، إلا أنه هناك يتم الاختيار التكميلي لـ x − 1 "فصل".

مثال:

${\displaystyle X=\{a,b\},N=\{1,2,3\}{\text{, then }}}$

${\displaystyle \left\vert \{\{a,a,b\},\{a,b,b\}\}\right\vert ={\binom {3-1}{3-2}}={\binom {2}{1}}={\frac {2!}{1!\times (2-1)!}}=2}$

في هذه الحالة، نعتبر تسلسلات من n عنصرًا مميزًا من X ، ولكننا نحدد العناصر التي تم الحصول عليها من بعضها البعض من خلال تطبيق تبديل X على كل عنصر . من السهل أن نرى أنه يمكن دائمًا تحديد تسلسلين مختلفين من هذا القبيل: يجب أن يطابق التبديل الحد i من التسلسل الأول مع الحد i من التسلسل الثاني، ونظرًا لعدم حدوث أي قيمة مرتين في أي من التسلسلين، فإن هذه المتطلبات لا تتعارض مع بعضها البعض؛ يبقى أن نطابق العناصر التي لا تحدث في التسلسل الأول بشكل ثنائي مع تلك التي لا تحدث في التسلسل الثاني بطريقة تعسفية. الحقيقة الوحيدة التي تجعل النتيجة تعتمد على n و x على الإطلاق هي أن وجود أي من هذه التسلسلات في البداية يتطلب n ≤ x ، وفقًا لمبدأ الحمامة. وبالتالي، يتم التعبير عن الرقم على أنه ، باستخدام قوس إيفرسون . ${\displaystyle [n\leq x]}$

يتم تقليص هذه الحالة إلى الحالة السابقة: بما أن جميع تسلسلات العناصر المميزة n من X يمكن بالفعل تحويلها إلى بعضها البعض عن طريق تطبيق تبديل X على كل من مصطلحاتها، فإن السماح بإعادة ترتيب المصطلحات لا يعطي أي تعريفات جديدة؛ يبقى العدد كما هو . ${\displaystyle [n\leq x]}$

هذه الحالة تعادل حساب أقسام N إلى مجموعات فرعية x (غير فارغة) ، أو حساب علاقات التكافؤ على N مع فئات x بالضبط . في الواقع، بالنسبة لأي دالة شاملة f  : N → X ، فإن علاقة وجود نفس الصورة تحت f هي علاقة تكافؤ، ولا تتغير عند تطبيق تبديل X لاحقًا؛ على العكس من ذلك، يمكن للمرء تحويل علاقة التكافؤ هذه إلى دالة شاملة عن طريق تعيين عناصر X بطريقة ما لفئات تكافؤ x . عدد هذه الأقسام أو علاقات التكافؤ هو بحكم التعريف رقم ستيرلينج من النوع الثاني S ( n ، x )، مكتوب أيضًا . يمكن وصف قيمته باستخدام علاقة تكرار أو باستخدام وظائف توليد ، ولكن على عكس المعاملات ذات الحدين لا توجد صيغة مغلقة لهذه الأرقام لا تتضمن مجموعًا . ${\displaystyle \textstyle \{{n \atop x}\}}$

لكل دالة شمولية f  : N → X ، فإن مدارها تحت تبديلات X يحتوي على x ! عناصر، لأن التركيب (على اليسار) مع تبديلين مميزين لـ X لا يعطي أبدًا نفس الدالة على N (يجب أن تختلف التبديلات عند بعض عناصر X ، والتي يمكن كتابتها دائمًا كما هي لبعض i ∈ N ، وستختلف التركيبات عند i ). ويترتب على ذلك أن الرقم لهذه الحالة هو x ! مضروبًا في الرقم للحالة السابقة، أي${\displaystyle f(i)}$${\displaystyle \textstyle x!\{{n \atop x}\}.}$

مثال:

${\displaystyle X=\{a,b\},N=\{1,2,3\}{\text{, then }}}$

${\displaystyle \left\vert \{(a,a,b),(a,b,a),(a,b,b),(b,a,a),(b,a,b),(b,b,a)\}\right\vert =2!\left\{{3 \atop 2}\right\}=2\times 3=6}$

هذه الحالة تشبه الحالة المقابلة للوظائف الشاملة، ولكن بعض عناصر x قد لا تتوافق مع أي فئة تكافؤ على الإطلاق (نظرًا لأننا نأخذ في الاعتبار وظائف تصل إلى تبديل X ، فلا يهم العناصر المعنية، فقط كم عددها). ونتيجة لذلك، نحسب علاقات التكافؤ على N مع x فئات على الأكثر ، ويتم الحصول على النتيجة من الحالة المذكورة عن طريق الجمع على القيم حتى x ، مما يعطي . في حالة x ≥ n ، لا يفرض حجم x أي قيد على الإطلاق، ونحسب جميع علاقات التكافؤ على مجموعة من n عنصر (كل أقسام هذه المجموعة على قدم المساواة)؛ وبالتالي يعطي تعبيرًا عن رقم بيل B _n . ${\displaystyle \textstyle \sum _{k=0}^{x}\{{n \atop k}\}}$${\displaystyle \textstyle \sum _{k=0}^{n}\{{n \atop k}\}}$

هذه الحالة تعادل عد أقسام العدد n إلى x أجزاء غير صفرية . وبالمقارنة بحالة عد الدوال الفوقية حتى تبديلات X فقط ( )، لا يتم الاحتفاظ إلا بأحجام فئات التكافؤ التي تقسم الدالة N إليها (بما في ذلك مضاعفة كل حجم)، حيث يمكن تحويل علاقتي تكافؤ إلى بعضهما البعض عن طريق تبديل N إذا وفقط إذا تطابقت أحجام فئاتهما. وهذا هو بالضبط ما يميز مفهوم تقسيم n عن مفهوم تقسيم N ، وبالتالي نحصل بحكم التعريف على عدد p _x ( n ) من أقسام n إلى x أجزاء غير صفرية. ${\displaystyle \textstyle \{{n \atop x}\}}$

هذه الحالة تعادل حساب أقسام العدد n إلى ≤ x أجزاء . الارتباط هو نفسه كما في الحالة السابقة، إلا أن بعض أجزاء القسم قد تساوي 0 الآن. (على وجه التحديد، فهي تتوافق مع عناصر X ليست في صورة الدالة.) يمكن تمديد كل قسم من n إلى x أجزاء غير صفرية على الأكثر إلى مثل هذا القسم عن طريق إضافة العدد المطلوب من الأصفار، وهذا يأخذ في الاعتبار جميع الاحتمالات مرة واحدة بالضبط، وبالتالي فإن النتيجة تعطى بواسطة . بإضافة 1 إلى كل جزء من أجزاء x ، نحصل على قسم من n + x إلى x أجزاء غير صفرية، وهذا التطابق هو ثنائي التقابل؛ وبالتالي يمكن تبسيط التعبير المعطى عن طريق كتابته على النحو التالي . ${\displaystyle \textstyle \sum _{k=0}^{x}p_{k}(n)}$${\displaystyle p_{x}(n+x)}$

تعطي الصيغ أعلاه القيم الصحيحة لجميع المجموعات المحدودة N و X. في بعض الحالات، توجد صيغ بديلة متكافئة تقريبًا، ولكنها لا تعطي النتيجة الصحيحة في بعض الحالات المتطرفة، مثل عندما تكون N أو X فارغة. تنطبق الاعتبارات التالية على مثل هذه الحالات.

• لكل مجموعة X يوجد دالة واحدة فقط من المجموعة الفارغة إلى X (لا توجد قيم لهذه الدالة لتحديدها)، والتي تكون دائمًا حقنية، ولكنها لا تكون شاملة أبدًا إلا إذا كانت X (أيضًا) فارغة.
• بالنسبة لكل مجموعة غير فارغة N لا توجد دوال من N إلى المجموعة الفارغة (هناك قيمة واحدة على الأقل للدالة يجب تحديدها، ولكن لا يمكن تحديدها).
• عندما يكون n > x لا توجد دوال حقنية N → X ، وإذا كان n < x لا توجد دوال شاملة N → X.
• التعبيرات المستخدمة في الصيغ لها قيم خاصة

${\displaystyle 0^{0}=0^{\underline {0}}=0!={\binom {0}{0}}={\binom {-1}{0}}=\left\{{0 \atop 0}\right\}=p_{0}(0)=1}$

(الأولى والثالثة هي حالات لمنتج فارغ ، ويتم تحديد القيمة عن طريق التمديد التقليدي لمعاملات ثنائية الحدين إلى قيم عشوائية للمؤشر العلوي)، بينما ${\displaystyle {\tbinom {-1}{0}}={\tfrac {(-1)^{\underline {0}}}{0!}}=1}$

${\displaystyle \left\{{n \atop x}\right\}=p_{x}(n)=0\quad {\hbox{whenever either }}n>0=x{\hbox{ or }}0\leq n<x.}$

على وجه الخصوص في حالة عد المجموعات المتعددة مع n عنصر مأخوذة من X ، فإن التعبير المعطى يعادل في معظم الحالات ، ولكن التعبير الأخير سيعطي 0 للحالة n = x = 0 (وفقًا للاتفاقية المعتادة التي تنص على أن المعاملات الثنائية ذات الفهرس السفلي السالب تكون دائمًا 0). وبالمثل، بالنسبة لحالة عد تركيبات n مع x أجزاء غير صفرية، فإن التعبير المعطى يعادل تقريبًا التعبير المعطى بواسطة وسيطة النجوم والأشرطة ، ولكن الأخير يعطي قيمًا غير صحيحة لـ n = 0 وجميع قيم  x . بالنسبة للحالات التي تتضمن فيها النتيجة جمعًا، أي تلك الخاصة بعدّ أقسام N إلى x مجموعات فرعية غير فارغة على الأكثر أو أقسام n إلى x أجزاء غير صفرية على الأكثر، يتم اعتبار مؤشر الجمع ليبدأ من 0؛ على الرغم من أن المصطلح المقابل يكون صفرًا كلما n > 0 ، فهو المصطلح الوحيد غير الصفري عندما n = 0 ، وستكون النتيجة خاطئة في تلك الحالات إذا تم اعتبار الجمع ليبدأ من 1. ${\displaystyle {\tbinom {n+x-1}{n}}}$${\displaystyle {\tbinom {n+x-1}{x-1}}}$${\displaystyle {\tbinom {n-1}{n-x}}}$${\displaystyle {\tbinom {n-1}{x-1}}}$

يمكننا التعميم بشكل أكبر من خلال السماح لمجموعات أخرى من التباديل بالعمل على N و X. إذا كانت G عبارة عن مجموعة من التباديل لـ N ، وكانت H عبارة عن مجموعة من التباديل لـ X ، فإننا نحسب فئات التكافؤ للدوال . تُعتبر الدالتان f و F متكافئتين إذا، وفقط إذا، كانتا موجودتين بحيث . يؤدي هذا الامتداد إلى مفاهيم مثل التباديل الدورية والثنائية السطوح ، بالإضافة إلى التقسيمات الدورية والثنائية السطوح للأرقام والمجموعات. ${\displaystyle f\colon N\rightarrow X}$${\displaystyle g\in G,h\in H}$${\displaystyle F=h\circ f\circ g}$

وقد طور كينيث ب. بوجارت تعميمًا آخر يُسمى الطريقة العشرينية في كتابه "التركيبات من خلال الاكتشاف الموجه". وفي مشكلة توزيع الأشياء على الصناديق، قد تكون الأشياء والصناديق متطابقة أو مختلفة. وقد حدد بوجارت عشرين حالة. ^[3] وقد بنى روبرت أ. بروكتور الطريقة الثلاثينية. ^[4]

الطريقة العشرينية؛ نماذج لتوزيع n كائن بين x متلقين

رقم	أشياء	حالة التوزيع	المستلمون
			متميز	تطابق
1	متميز	لا يوجد قيود	تسلسل n في X x n {\displaystyle x^{n}}	تقسيم N إلى مجموعات فرعية ≤ x ${\displaystyle \sum _{i=0}^{x}\left\{{n \atop i}\right\}}$
2		على الأكثر واحد لكل منهما	تبديل n لـ X x n _ {\displaystyle x^{\underline {n}}}	{ 1 إذا كان n ≤ x 0 وإلا {\displaystyle {\begin{cases}1&{\text{if }}n\leq x\\0&{\text{otherwise}}\end{cases}}}
3		على الأقل واحد لكل منهما	تكوين N مع x مجموعات فرعية x ! { n x } {\displaystyle x!\left\{{n \atop x}\right\}}	تقسيم N إلى مجموعات فرعية x { n x } {\displaystyle \left\{{n \atop x}\right\}}
4		واحد بالضبط لكل منهما	n ! = x ! {\displaystyle n!=x!} تبديلات	${\displaystyle {\begin{cases}1&{\text{if }}n=x\\0&{\text{otherwise}}\end{cases}}}$
5	متميز، منظم	لا يوجد قيود	( n + x − 1 ) n _ {\displaystyle (n+x-1)^{\underline {n}}} الدوال المرتبة	∑ i = 1 x L ( n , i ) {\displaystyle \sum _{i=1}^{x}L(n,i)} تبديلات مكسورة ( أجزاء) أين رقم لاه${\displaystyle \leq x}$ ${\displaystyle L(n,i)}$
6		على الأقل واحد لكل منهما	( n ) x _ ( n − 1 ) n − x _ {\displaystyle (n)^{\underline {x}}(n-1)^{\underline {nx}}} مرتبة على الدوال	L ( n , x ) = ( n x ) ( n − 1 ) n − x _ {\displaystyle L(n,x)=\left({n \atop x}\right)(n-1)^{\underline {nx}}} تبديلات مكسورة ( أجزاء x ) أين رقم لاه؟${\displaystyle L(n,x)}$
7	تطابق	لا يوجد قيود	مجموعة فرعية متعددة من X ( x + n − 1 n ) {\displaystyle \left({x+n-1 \atop n}\right)}	∑ i = 1 x p i ( n ) {\displaystyle \sum _{i=1}^{x}p_{i}(n)} أقسام عددية ( أجزاء) ${\displaystyle \leq x}$
8		على الأكثر واحد لكل منهما	مجموعة فرعية من x ( x n ) {\displaystyle \left({x \atop n}\right)}	${\displaystyle {\begin{cases}1&{\text{if }}n\leq x\\0&{\text{otherwise}}\end{cases}}}$
9		على الأقل واحد لكل منهما	( n − 1 x − 1 ) {\displaystyle \left({n-1 \atop x-1}\right)} تركيبات ( x أجزاء)	تقسيم n إلى x أجزاء p x ( n ) {\displaystyle p_{x}(n)}
10		واحد بالضبط لكل منهما	{ 1 إذا كان n = x 0 وإلا {\displaystyle {\begin{cases}1&{\text{if }}n=x\\0&{\text{otherwise}}\end{cases}}}	${\displaystyle {\begin{cases}1&{\text{if }}n=x\\0&{\text{otherwise}}\end{cases}}}$

• النجوم والأشرطة (التركيبات)