עקרון הכפל

עקרון הכפל הוא עקרון יסודי בקומבינטוריקה המופיע בצורות שונות בתחומים רבים במתמטיקה.

העקרון קובע כי אם יש קבוצה אחת בת $n$ עצמים וקבוצה שנייה בת $m$ עצמים, אז מספר העצמים בקבוצה המורכבת מכל הזוגות האפשריים של עצם אחד מן הקבוצה הראשונה ועצם שני מן הקבוצה השנייה שווה למכפלה $n\times m$ .

קומבינטוריקה

בניסוח פורמלי עקרון הכפל קובע כי אם בקבוצה סופית $A$ יש $n$ איברים ובקבוצה סופית $B$ יש $m$ איברים, אז במכפלה הקרטזית $A\times B$ יש $n\cdot m$ איברים. ניתן להוכיח את עקרון הכפל באינדוקציה בהסתמך על הגדרת הכפל במערכת פאנו ועל עקרון החיבור (הקובע כי מספר האיברים באיחוד של שתי קבוצות זרות שווה לסכום מספר האיברים בכל אחת).

לדוגמה קלף משחק סטנדרטי (שאינו ג'וקר) מוגדר על ידי צורה מבין הצורות ♠, ♣, ♥, ♦ ומספר מבין המספרים 1-13. לכן מספר הקלפים בחפיסה (ללא ג'וקרים) הוא מספר הצורות כפול מספר המספרים: 4×13=52.

באינדוקציה מכלילים את עקרון הכפל למספר כלשהו של קבוצות. אם מספר האיברים בקבוצות $A_{1},\ldots ,A_{n}$ הוא $m_{1},\ldots ,m_{n}$ בהתאמה, אז מספר האיברים במכפלה $A_{1}\times \cdots \times A_{n}$ הוא $\prod _{i=1}^{n}m_{i}$ .

מקרה פרטי חשוב הוא כאשר הקבוצות במכפלה כולן זהות, אז מספר האיברים במכפלה הקרטזית הוא $m^{n}$ . המשמעות הקומבינטורית היא שמספר הדרכים לסדר $n$ עצמים בשורה, כאשר הם נבחרים מתוך $m$ עצמים ומתירים חזרות על אותו עצם, היא $m^{n}$ . תוצאה נוספת הנובעת מעקרון הכפל היא שמספר הדרכים לסדר $n$ עצמים בשורה בלי חזרות היא $n!$ (ראו עצרת).

תורת הקבוצות

ערך מורחב – עוצמה (מתמטיקה)#אריתמטיקה של עוצמות

בתורת הקבוצות משתמשים בעקרון הכפל כדי להגדיר פעולת כפל בין עוצמות. עוצמות סופיות הן מספרים טבעיים ולכן המכפלה שלהן תואמת את עקרון הכפל. לכן טבעי להכליל את עקרון הכפל כך שיגדיר גם מכפלה בין עוצמות אינסופיות: $|A|\cdot |B|:=|A\times B|$ . הגדרה זו אינה תלויה בבחירת נציגים.

בהכללה, המכפלה של קבוצה כלשהי של עוצמות מוגדרת לפי: $\prod _{i\in I}|A_{i}|:=\left|\prod _{i\in I}A_{i}\right|$

שטח מלבן

ניתן לחלק מלבן שהאורך והרוחב שלו הם מספרים טבעיים למספר טבעי של ריבועי יחידה. לפי עקרון הכפל מספר הריבועים שווה למכפלת אורך המלבן ברוחבו. אם מוסכם ששטחו של ריבוע יחידה הוא 1, ניתן להגדיר כי שטחו של מלבן כזה שווה למכפלת אורכו ברוחבו. באמצעות חשבון אינפיניטסימלי ניתן להכליל את התוצאה לכל מספר ממשי ולקבל כי שטחו של מלבן כלשהו שווה שמכפלת האורך ברוחב. באמצעות אינטגרל לבג הדבר מאפשר להגדיר את שטחה של צורה דו-ממדית (או באופן כללי את המידה של צורה $n$-ממדית) בהסתמך על הגדרת שטחו של ריבוע היחידה ומידת לבג בלבד.

ראו גם

• תלות (הסתברות)