تركيبات

من ويكيبيديا، الموسوعة الحرة
(بالتحويل من توافقيات)
اذهب إلى: تصفح، ‏ ابحث

التركيبات أو التوافقيات (بالإنجليزية: Combinatorics) هي أحد فروع الرياضيات التي تدرس البُنى المتقطعة المنتهية والقابلة للعد. تتضمن التركيبات عدّ العناصر في المجموعات، مع تحديد ما إذا كانت تتوافق مع المعايير المطلوبة، وكذلك دراسة بناء وتحليل الكائنات التي تحقق هذه المعايير (كما في التصميم التوافقي ونظرية الماترويد)، يهتم هذا العلم أيضاً بإيجاد الكائنات الأكبر أو الأصغر أو الأفضل (فيما يعرف بالتوافقيات الحجمية والتوافقيات التحسينية). ودراسة الهيكل التركيبي الظاهر في محتوى جبري، أو تطبيق تقنيات الجبر لحل مسائل التركيبات (التركيبات الجبرية).

التاريخ[عدل]

An example of change ringing (with six bells), one of the earliest nontrivial results in Graph Theory

انظر أعداد شرودر.

مقاربات التوافقيات وفروعها[عدل]

التوافقيات التعدادية[عدل]

خمسة أشجار ثنائية على ثلاثة رؤوس, مثال على أعداد كاتالان.

انظر إلى عدد فيبوناتشي.

التوافقيات التحليلية[عدل]

نظرية التجزآت[عدل]

في نظرية الأعداد وفي التوافقيات، تجزئة عدد طبيعي هي طريقة لكتابة هذا العدد على شكل مجموع أعداد طبيعية. مجموعان يختلفان فقط في ترتيب حدودهما، يعتبران نفس المجموع. على سبيل المثال، يكتب 4 على شكل خمسة مجاميع مختلفة وهي:

4,     3 + 1,     2 + 2,     2 + 1 + 1,     1 + 1 + 1 + 1.

نظرية المخططات[عدل]

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

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

تعتبر المخططات كائنات أساسية في دراسة التوافقيات .

الهندسة المنتهية[عدل]

الهندسة المنتهية هي أي نظام هندسي رياضي يحوي عددا منتهيا (محددا) من النقاط. على سبيل المثال، الهندسة الإقليدية هي هندسة غير منتهية، حيث أن المستقيم الإقليدي يحتوي عددا لا نهائيا من النقاط. من الممكن للهندسة المنتهية أن تمتلك عددا منتهيا من الأبعاد.

نظرية الترتيب[عدل]

نظرية الترتيب هي فرع من الرياضيات يهتم بدراسة الأنواع المختلفة من العلاقات الثنائية التي تعطي انطباعا حسّياً عن فكرة ترتيبها موفرة بنية يمكن القول من خلالها متى يكون الشيء "أقل من" أو "يسبق" الآخر.

تدرس نظرية الترتيب مختلف أنواع العلاقات الثنائية بين العناصر الرياضية المختلفة التي ترمز ترتيب هذه العناصر.

مخطط هاس of the powerset of {x,y,z} ordered by inclusion.

التوافقيات الاحتمالية[عدل]

سَير مع تجنب النقط اللائي سِير عليهن من قبل في شبكة من النقط على شكل مربع.

مبادئ العد الأساسية[عدل]

مبدأ الضرب[عدل]

إذا كان لدينا مجموعتان مختلفتان وعدد الإمكانيات للاختيار من المجموعة الأولى هو N وعدد الإمكانيات للاختيار من المجموعة الثانية هو M، فإن عدد الإمكانيات للاختيار من المجموعة الأولى و المجموعة الثانية هو .

مثال: لدى منال 5 تنانير و 7 قمصان. في كل مرة تخرج فيها من البيت ترتدي قميصا وتنورة. كم إمكانية مختلفة توجد لمنال لاختيار قميص و تنورة؟. الإجابة: حسب قانون الضرب إمكانية مختلفة.

التجزيئات المرتبة وغير المرتبة[عدل]

التجزيئات المرتبة وغير المرتبة في حالة وجود تساوي لعدد عناصر المجموعات[عدل]

أولا: صيغة السؤال في حالة (غير المرتبة) تكون: بكم طريقة يمكن أن تقسم..... ​إلى​..... أو توزيع .... ​إلى​...... إي أن  : في هذه الحالة تكون المجموعات أو الفرق أو اللجان أو....ألخ غير موجودة مسبقا ونقوم نحن بإنشائها أثناء التقسيم.

فمثلا : (1) بكم طريقة يمكن توزيع (تقسيم) 9 طلاب ​إلى​ 3 فرق رياضية تحوي كل منها 3طلاب ؟ الحل: 9!/( 3! 3! 3! *3! ) =280 حل آخر 1*ق(8، 2) *1* ق(5، 2)* 1 * ق(2، 2) =280 لاحظ أن كلمة تقسيم (توزيع) ...إلى .... تعني أن هذه الفرق لم تكن موجودة من قبل ولم تسمى (تميز) بعد . ولكن إذا قال : تقسيم (توزيع)....على فرق .... فإن هذه الفرق قد أنشأت وميزت بمحتواها أو أسمائها وما علينا إلا التوزيع عليها ولم نعد بحاجة إلى القسمة على مضروب الثلاثة أي عدد الطرق في هذه الحالة يصبح 9!/( 3! 3! 3! ) = 1680


(2) بكم طريقة يمكن تقسيم 18 طالبا ​إلى​ 3 مجموعات بحيث تحوي كل مجموعة 6 طلاب ؟ الحل : 18!/(6! 6! 6!*3! ) = 2858856

لاحظ أن المجموعات لم تنشأ بعد ونحن من قمنا بإنشائها.


(3) كم عدد الطرق المختلفة التي يمكن بها تقسيم( 14) فردا ​إلى​ 6 مجموعات بحيث مجموعتان منها تحوي كل منها (3) أفراد وبقية المجموعات تحوي كل منها فردين ؟ الحل: 14!/(3!3!2!2!2!2!2!4!) = 25225200


(4 أ) كم عدد الطرق المختلفة لتقسيم (10)لمبات إضاءة مختلفة القدرة ​إلى​ قسمين بحيث يحوي كل قسم 5 لمبات ؟ الحل: 10!/( 5! 5!* 2! )= 126


(4 ب) كم عدد الطرق المختلفة لتوزيع (10)لمبات إضاءة مختلفة القدرة ​على​ كرتونين لهما نفس الشكل والحجم (متماثلين) بحيث يحوي كل كرتون 5 لمبات ؟ الحل:

10!/( 5! 5!*2!) = 126 لاحظ في السؤال 4أ ، 4ب بالرغم أن الصياغة تبدو مختلفة إلا أن إضافة عبارة لهما نفس الشكل والحجم( في 4ب) بعد كرتونين جعلتهما غير متمايزين


(5)كم عدد الطرق التي يمكن بها توزيع كمبيوترين بنفس المواصفات على 4طلاب بحيث يأخذ كل طالبين كمبيوتر ؟ الحل: هنا نلاحظ أن صيغة السؤال تكافئ تقسيم 4 طلاب إلى مجموعتين كل مجموعة تحوي طالبين. ويكون الحل 4!/( 2!2! *2!) = 3 لأن الكمبيوترين متماثلين سيكون توزيعهم بطريقة واحدة على المجموعتين. ولو كان الكمبيوتران مختلفين لرتبناهما ب 2! ويكون الحل في المتمايزين 4!/( 2!2! ) =6


ثانيا: في حالة التجزيئات المرتبة تكون صيغة السؤال كمايلي: بكم طريقة يمكن

توزيع...... ​على​...أو

تقسيم ...*بين*(على)...... أي أن المجموعات أو اللجان أو الفرق أو....ألخ قد شكلت مسبقا أي أنها موجودة من قبل أن نبدأ التوزيع أو التقسيم ويتم التوزيع عليها أو التقسيم بينها.

 فمثلا : 

1 ) كم عدد طرق توزيع(تقسيم) 9 لعب مختلفة ​على​ 3 أطفال بحيث يحصل كل طفل منهم على 3 لعب ؟ الحل: 9!/( 3! 3! 3! ) = 1680 حل اخر ق(9 ، 3) * ق(6 ، 3. ) * ق(3 ، 3 ) = 1680

------------

2) كم عدد طرق توزيع 12 لاعبا في نادي رياضي ​على​ ثلاث قاعات تدريب بالتساوي ؟ الحل: 12!/( 4! 4! 4! ) = 34650 حل اخر ق( 12، 4)* ق(8، 4)*ق(4،4 ) = 34650 لاحظ ان القاعات متمايزة بطبيعتها لأنها أشياء مادية موجودة مسبقا والأصل في الأشياء الاختلاف مالم يذكر غير ذلك.


(3) كم عدد الطرق التي يمكن بها توزيع 3 نماذج اختبارات مختلفة ​على​ 12 طالبا بحيث يأخذ كل أربعة طلاب نفس النموذج ؟ الحل في هذا السؤال العملية مركبة فيها توزيع.. على ..وهذا يعني أنها مرتبة وفيها تقسيم الطلاب ...إلى...وهذا يعني غير مرتبة ولكن لن يحدث هذا التوزيع إلا بعد تقسيم الطلاب لذلك أولا سنقسم الطلاب إلى ثلاث مجموعات ولأن المجموعات نحن من سننشئها فسنعتبرها غير متمايزة وعدد الطرق لذلك هو 12!/( 4! 4! 4!*3!) ثانيا: نقوم بعملية توزيع النماذج ولأن التوزيع الآن أصبح لمجموعات موجودة فتعتبر متمايزة (لأنها متمايزة على الأقل بأعضائها) ويكون عدد طرق ذلك 3!/1! 1! 1! وبالتالي يكون حل الفقرة هو 12!/(4! 4! 4! 3! ) * 3!/ (1! 1!1!) = (4! 4! 4!)/12! حل أخر نعتبر النماذج هم أسماء المجموعات ونوزع الطلاب عليهم ولأن المجموعات متمايزة يكون 12!/( 4! 4! 4! ) =34650 حل ثالث نختار أربعة طلاب للنموذج الأول ب ق (12، 4) طريقة ثم للثاني ب ق (8، 4) ثم للثالث ب ق (4، 4) وحسب مبدأ العد يكون ق (12، 4)*ق(8، 4) *ق(4، 4)

=12!/( 4! 4! 4! ) 34650


(4) كم عدد طرق توزيع 4 مدرسين رياضيات بين(على) مجموعتين : مجموعة تفاضل و مجموعة تكامل بحيث تحوي كل مجموعةمدرسين اثنين؟

الحل: 4!/(2! 2! ) =6

لاحظ أن المجموعتين متمايزتان بأسمائها وأيضا حرف الجر على أو ظرف المكان (بين) يدل على وجود المجموعات مسبقا وحتى لو كان حرف الجر في هذا السؤال إلى والذي يدل على عدم وجود المجموعات مسبقا إلا أننا سنعتبرها متمايزة لأننا سننشئها ونسميها فتصبح متمايزة .


(5) كم عددطرق توزيع 4كرات مختلفة الألوان ​على​ طفلين بحيث يأخذ كل طفل كرتين ؟ الحل 4!/( 2! 2! ) =6


هذه فقط بعض الامثلة للتوضيح


ملاحظة هامة : صيغ الأسئلة ليست وحيدة كما تلاحظ في الأمثلة السابقة بمعنى قد توجد صيغ مكافئة أخرى لأي سؤال. وأيضا توجد حالات نضطر فيها لاستخدام كلمة( توزيع )بدلا عن كلمة( تقسيم) أوالعكس وهناك حالات يجوز فيها الصيغتين .

ولكن مايهم وما يجب الحرص عليه عند كتابة السؤال هو حرف الجر إلى أو على(بين)

فالحرف ​إلى​ :

يستخدم للمجهول أي أن المجموعات لم تشكل بعد وبالتالي فلا يوجد تمييز بينها.

بينما الحرف ​على​أو الظرف ​بين​ : تستخدم للمعلوم أي أن المجموعات قد وجدت من قبل ، وبالتالي يوجد تمييز بينها مالم توجد إضافة للسؤال تدل على التماثل أو التطابق أو عدم التمييز. كما لاحظنا في الأمثلة السابقة. عزيزي القارئ نختم بهذا المثال فكرتنا : بكم طرق عديدة ل(10) طلاب يمكن أن يقسموا الى ثنائيات ؟ الحل: هنا لدينا كل ثنائي (مجموعه) لديها شخصان والخاصية النوعية لهذه الثنائيات هي نفس الشيئ (بمعنى اخر ليس هناك مايميز واحده عن الاخرى) حيث هنا ليس لهذه الثنائيات أي غرض ( او وظيفة او مهام ) او اسماء لاي من هذه الثنائيات الجواب : 10!/ [( 2!)^5*5! ] لاحظ هنا كلمة into

  مما يعني ان  الأزواج (المجموعات) قيد الانشاء ولم تنشأ مسبقا ولم يحدد لها مهام و لم تسمى ولهذا يجب القسمة على مضروب عددها لانها تقسيمات غير مرتبة

مع خالص تحياتنا أ/ طارق الثوامي أ/ احمد الدبعي أ/ سيمور العبسي

مراجع[عدل]

وصلات خارجية[عدل]