עקרון הכפל

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

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

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

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

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

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

באינדוקציה מכלילים את עקרון הכפל למספר כלשהו של קבוצות. אם מספר האיברים בקבוצות ${\displaystyle \ A_{1},A_{2},\ldots ,A_{n}}$ הוא ${\displaystyle \ m_{1},m_{2},\ldots ,m_{n}}$ בהתאמה, אז מספר האיברים ב-${\displaystyle \ A_{1}\times A_{2}\times \ldots \times A_{n}}$ הוא ${\displaystyle \ \prod _{i=1}^{n}m_{i}}$. מקרה פרטי חשוב הוא כאשר הקבוצות במכפלה כולן זהות, אז מספר האיברים במכפלה הקרטזית הוא ${\displaystyle \ m^{n}}$. המשמעות הקומבינטורית היא שמספר הדרכים לסדר עם חזרות ${\displaystyle n}$ עצמים בשורה, כאשר הם נבחרים מתוך ${\displaystyle m}$ עצמים, היא ${\displaystyle \ m^{n}}$. תוצאה נוספת הנובעת מעקרון הכפל היא שמספר הדרכים לסדר ${\displaystyle n}$ עצמים בשורה בלי חזרות היא ${\displaystyle \ n!}$(ראו עצרת).

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

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

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

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

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

• עקרון הכפל, באתר MathWorld (באנגלית)