📚 مقدمة في العد
مسائل العد تظهر في كل مكان في الرياضيات وعلوم الحاسب. لازم نعدّ النتائج الناجحة للتجارب، ونحدد احتمالات الأحداث المتقطعة، ونحلل تعقيد الخوارزميات. هذا الدليل يغطي التقنيات الأساسية اللي تحتاجها عشان تجاوب على هالأسئلة.
- تحديد الاحتمالات في الأحداث المتقطعة.
- تحليل التعقيد الزمني للخوارزميات.
- حل مشاكل كلمات المرور والأمن.
- فهم الهياكل التوافقية (combinatorial structures).
🔢 أساسيات نظرية المجموعات
تعريفات أساسية
- المجموعة: مجموعة غير مرتبة من العناصر المتميزة (الأعضاء).
- المجموعة الفارغة: مجموعة ما فيها عناصر.
- الأصل |A|: عدد العناصر في مجموعة منتهية A.
- الاتحاد (A ∪ B): مجموعة كل العناصر اللي في A أو B.
- التقاطع (A ∩ B): مجموعة كل العناصر اللي في A و B معًا.
🎯 قواعد العد الأربعة الأساسية
١. قاعدة المجموع (قاعدة "أو")
إذا كان في مهمة أولى تقدّر تسويها بـ n₁ طريقة ومهمة ثانية بـ n₂ طريقة، و تسوي وحدة منهم فقط (مو الاثنين)، إذن عدد الطرق تسوي أي مهمة = n₁ + n₂.
|A ∪ B| = |A| + |B|
المسألة: في معرض سيارات، في ٣ سيارات ألمانية في صالة و ٢ سيارات يابانية في صالة ثانية. كم خيار عندك تشتري سيارة؟
تقدّر تشتري إما سيارة ألمانية أو يابانية (مو الاثنين).
عدد الخيارات = ٣ + ٢ = ٥ خيارات
المسألة: في لغة برمجة، تسمية العبارات (statement labels) لازم تكون حرف واحد أو رقم عشري واحد. كم تسمية ممكنة؟
الحروف (A-Z): ٢٦ خيار
الأرقام (0-9): ١٠ خيارات
المجموع = ٢٦ + ١٠ = ٣٦ تسمية ممكنة
٢. قاعدة الضرب (قاعدة "و")
إذا كان الإجراء ينقسم لمهمتين، المهمة الأولى تقدّر تسويها بـ n₁ طريقة والمهمة الثانية بـ n₂ طريقة (بعد ما خلصت المهمة الأولى)، إذن عدد طرق تنفيذ الإجراء كامل = n₁ × n₂.
|A × B| = |A| × |B|
المسألة: تبي تسافر من دولة A إلى دولة C مرورًا بدولة B. في ٣ طرق من A إلى B و ٢ طرق من B إلى C. كم طريقة توصل من A إلى C؟
لازم تمشي من A إلى B و بعدين من B إلى C.
عدد الطرق = ٣ × ٢ = ٦ طرق
المسألة: أرقام الجوال في الرياض ٧ أرقام وأول رقم يبدأ بـ ٤ أو ٢. كم خط جوال ممكن؟
الحالة ١: التكرار مسموح
الخانة الأولى: ٢ خيارات (٤ أو ٢)
الخانات ٢-٧: ١٠ خيارات لكل خانة (٠-٩)
المجموع = ٢ × ١٠⁶ = ٢,٠٠٠,٠٠٠ خط
الحالة ٢: ممنوع التكرار
الخانة الأولى: ٢ خيارات
الخانة الثانية: ٩ خيارات (ما نكرر الرقم الأول)
الخانة الثالثة: ٨ خيارات
وهكذا...
المجموع = ٢ × ٩ × ٨ × ٧ × ٦ × ٥ × ٤ = ١٢٠,٩٦٠ خط
٣. قاعدة الطرح (مبدأ الشمول والتضمين)
إذا كانت المهمة تقدّر تسويها بـ n₁ طريقة أو بـ n₂ طريقة، العدد الكلي للطرق = n₁ + n₂ ناقص عدد الطرق المشتركة بينهم.
|A ∪ B| = |A| + |B| - |A ∩ B|
المسألة: شركة استقبلت ٣٥٠ طلب توظيف. ٢٢٠ طالب تخصصهم علوم حاسب، ١٤٧ طالب تخصصهم إدارة أعمال، و ٥١ طالب عندهم التخصصين معًا. كم طالب ما تخصصه ولا واحد منهم؟
ليكن A₁ = مجموعة طلاب الحاسب = ٢٢٠
ليكن A₂ = مجموعة طلاب الإدارة = ١٤٧
A₁ ∩ A₂ = اللي عندهم التخصصين = ٥١
|A₁ ∪ A₂| = |A₁| + |A₂| - |A₁ ∩ A₂|
|A₁ ∪ A₂| = ٢٢٠ + ١٤٧ - ٥١ = ٣١٦
اللي ما تخصصوا بواحد منهم = ٣٥٠ - ٣١٦ = ٣٤ طالب
٤. قاعدة القسمة
إذا كان في n طريقة لتنجز مهمة، وكل نتيجة ممكن تتكرر بـ d طريقة مختلفة، إذن عدد النتائج المميزة = n/d.
المسألة: كم طريقة نقدّر نجلس n شخص حول طاولة دائرية؟
في خط مستقيم: n! ترتيب.
حول دائرة: كل ترتيب له n دوران (مختلفين بنفس الترتيب الدائري).
الترتيبات الدائرية المميزة = n!/n = (n-1)!
🤔 دليل الاختيار: متى تستخدم أي قاعدة؟
| الموقف | القاعدة اللي تستخدمها | كلمات مفتاحية |
|---|---|---|
| المهام بدائل (تسوي وحدة بس) | قاعدة المجموع | أو، إمَّا... وإمَّا، واحد من |
| المهام متسلسلة (تسوي واحدة ورا الثانية) | قاعدة الضرب | و، بعدين، ثم |
| المجموعات متداخلة (فيهم عناصر مشتركة) | قاعدة الطرح | على الأقل واحد، بعضهم، تداخل |
| عدة طرق تعطيك نفس النتيجة | قاعدة القسمة | مميز، فريد، مختلف |
🔄 التباديل
وش هو التبديل؟
التبديل هو ترتيب للأشياء. الترتيب يهم!
عدد تباديل r من الأشياء المختارة من n شيء مميز نرمز له P(n,r).
P(n,r) = n!/(n-r)!
حالة خاصة: P(n,n) = n!
(نرتب كل n شيء في كل n خانة)
P(n,r) = n × (n-1) × (n-2) × ... × (n-r+1)
- الخانة الأولى: n خيارات
- الخانة الثانية: n-1 خيار
- الخانة رقم r: n-r+1 خيار
المسألة: كم طريقة تقدّر تختار ٣ طيور من ٨ طيور إذا كان الترتيب يهم؟
n = 8, r = 3
P(8,3) = 8!/(8-3)! = 8!/5!
= 8 × 7 × 6 × 5!/5!
= 8 × 7 × 6
= ٣٣٦ طريقة
المسألة: في ٨ متسابقين. فيه ميداليات ذهب، فضة، برونز. كم طريقة مختلفة تقدّر توزع الميداليات؟
هذا تبديل لأن الترتيب يهم (الذهب مو مثل الفضة مو مثل البرونز).
P(8,3) = 8!/(8-3)! = 8 × 7 × 6 = ٣٣٦ طريقة
🎲 التوافيق
وش هو التوافيق؟
التوفيقة هي اختيار غير مرتب للأشياء. الترتيب ما يهم!
عدد توافيق r من الأشياء المختارة من n شيء نرمز له C(n,r) أو (n choose r) أو ⁿCᵣ.
C(n,r) = n! / (r!(n-r)!)
العلاقة مع التباديل:
C(n,r) = P(n,r) / r!
(نقسم على r! لأن الترتيب ما يهم)
كل توفيقة فيها r عنصر تقدّر ترتب بـ r! طريقة مختلفة. بما إن الترتيب ما يهم، نضرب بعدد التكرارات الزايدة.
المسألة: كم طريقة تقدّر تختار ٢ كتاب من ١٠ كتب؟
n = 10, r = 2
C(10,2) = 10!/(2!(10-2)!)
= 10!/(2! × 8!)
= (10 × 9 × 8!)/(2 × 1 × 8!)
= (10 × 9)/2
= ٤٥ طريقة
المسألة: نبي نكوّن فريق من ٥ لاعبين من ١٠ أعضاء الفريق. كم فريق مختلف تقدّر تسوي؟
الترتيب ما يهم (الفريق عبارة عن مجموعة أشخاص).
C(10,5) = 10!/(5!(10-5)!)
= 10!/(5! × 5!)
= (10 × 9 × 8 × 7 × 6)/(5 × 4 × 3 × 2 × 1)
= ٢٥٢ فريق مختلف
⚖️ الفرق بين التباديل والتوافيق
| الوجه | التبديل | التوفيقة |
|---|---|---|
| الترتيب | يهم | ما يهم |
| الصيغة | P(n,r) = n!/(n-r)! | C(n,r) = n!/(r!(n-r)!) |
| مثال | (a,b) و (b,a) يعتبرون مختلفين | {a,b} و {b,a} يعتبرون نفس الشيء |
| كلمات مفتاحية | رتب، ترتيب، تسلسل | اختار، اختر، مجموعة |
| الناتج | دائمًا أكبر | دائمًا أصغر |
P(3,2) = 3!/(3-2)! = 6
التوافيق: {ab, ac, bc} = ٣ اختيارات
C(3,2) = 3!/(2!×1!) = 3
📐 نظرية ذات الحدين (Binomial Theorem)
وش هي ذات الحدين؟
ذات الحدين هي كثيرة حدود مكونة من حدين، مثل (x + y).
(x + y)ⁿ = Σ(k=0 to n) C(n,k) × xⁿ⁻ᵏ × yᵏ
بشكل مفكوك:
(x + y)ⁿ = C(n,0)xⁿ + C(n,1)xⁿ⁻¹y + C(n,2)xⁿ⁻²y² + ... + C(n,n)yⁿ
(x + y)⁴ = C(4,0)x⁴ + C(4,1)x³y + C(4,2)x²y² + C(4,3)xy³ + C(4,4)y⁴
= 1x⁴ + 4x³y + 6x²y² + 4xy³ + 1y⁴
= x⁴ + 4x³y + 6x²y² + 4xy³ + y⁴
المسألة: وش هو معامل x¹²y¹³ في مفكوك (2x - 3y)²⁵؟
أول شيء، نكتب (2x + (-3y))²⁵
عشان نحصل على x¹²y¹٣، نختار j = 13 في نظرية ذات الحدين:
المعامل = C(25,13) × (2)¹² × (-3)¹³
= [25!/(13!×12!)] × 2¹² × (-3)¹³
= -[25!/(13!×12!)] × 2¹² × 3¹³
🔺 مثلث باسكال
متطابقة باسكال
معاملات ذات الحدين تقدّر ترتب على شكل مثلث يُسمّى مثلث باسكال.
C(n+1, k) = C(n, k-1) + C(n, k)
كل عنصر = مجموع العنصرين اللي فوقه.
مثلث باسكال
- الصف رقم n فيه معاملات مفكوك (x + y)ⁿ.
- العنصر في موقع k بالصف n هو C(n,k).
- كل صف متماثل (symmetric).
- كل عنصر يساوي مجموع العنصرين اللي فوقه.
- مجموع أرقام الصف n يساوي 2ⁿ.
📋 مرجع سريع
كل الصيغ بنظرة واحدة
• قاعدة المجموع: |A ∪ B| = |A| + |B| (إذا A و B منفصلتين)
• قاعدة الضرب: |A × B| = |A| × |B|
• قاعدة الطرح: |A ∪ B| = |A| + |B| - |A ∩ B|
التباديل:
• P(n,r) = n!/(n-r)!
• P(n,n) = n!
التوافيق:
• C(n,r) = n!/(r!(n-r)!)
• C(n,r) = C(n, n-r)
• C(n,0) = C(n,n) = 1
نظرية ذات الحدين:
• (x + y)ⁿ = Σ C(n,k) × xⁿ⁻ᵏ × yᵏ
المضروب (Factorial):
• n! = n × (n-1) × (n-2) × ... × 3 × 2 × 1
• 0! = 1
إستراتيجية حل المسائل
- حدد: وش اللي تبي تعدّه؟
- قرر: الترتيب يهم ولا لا؟
- أيوة → استخدم التباديل
- لا → استخدم التوافيق
- تأكد: المهام متسلسلة ولا بدائل؟
- متسلسلة → استخدم قاعدة الضرب
- بدائل → استخدم قاعدة المجموع
- طبّق: الصيغة المناسبة
- تحقق: هل الإجابة منطقية؟
💪 مسائل تدريبية
لوحة السيارة مكونة من ٣ حروف يليها ٣ أرقام. كم لوحة ممكنة؟
الحروف: ٢٦ خيار لكل خانة (٣ خانات) = ٢٦³
الأرقام: ١٠ خيارات لكل خانة (٣ خانات) = ١٠³
المجموع = ٢٦³ × ١٠³ = ١٧,٥٧٦,٠٠٠ لوحة
من مجموعة ١٢ شخص، كم طريقة تقدّر تختار لجنة من ٥ أشخاص؟
الترتيب ما يهم، نستخدم التوافيق:
C(12,5) = 12!/(5!×7!) = ٧٩٢ طريقة
كلمة المرور لازم تكون ٨ خانات، كل خانة حرف إنجليزي صغير. كم كلمة مرور ممكنة إذا التكرار مسموح؟
كل خانة: ٢٦ خيار
المجموع = ٢٦⁸ = ٢٠٨,٨٢٧,٠٦٤,٥٧٦ كلمة مرور