קומבינטוריקה – הבדלי גרסאות

 

==מונחים בקומבינטוריקה==

'''[[תמורה (מתמטיקה)|תמורה]]''' (פרמוטציה) - סידור כלשהו של עצמים שונים בשורה. באופן פורמלי, תמורה היא [[פונקציה הפיכה]] מקבוצה סופית לעצמה.

 

פונקציית העצרת גדלה בקצב מהיר מאוד. [[אי-שוויון הממוצעים]] ו[[אינטגרל]] פשוט אומר כי <math>\left(\frac{n+1} {2}\right)^n \geq n! \geq \left(\frac{n}{1+\ln(n)}\right)^n</math>. [[נוסחת סטירלינג|נוסחת סטרלינג]] נותנת פונקציה פשוטה יותר להבנה שהיא קירוב אסימפטוטי של העצרת.

 

'''חליפות''' - מספר האפשרויות לבחור k עצמים מתוך n עצמים שונים, עם חשיבות לסדר הבחירה.

 

 

למשל, מספר הדרכים לכתוב מילה בת 5 אותיות. יש לבחור 5 אותיות מתוך 22, אך אפשר לבחור שוב ושוב באותה אות. הנוסחה היא <big><math>n^k</math></big>.

 

'''צירופים''' - מספר האפשרויות לבחור k עצמים מתוך n עצמים שונים בלי חזרות, כאשר אין חשיבות לסדר הבחירה. בחיי היום-יום בעיות של צירופים הן שכיחות למדי. הנוסחה היא <math>{n \choose k}</math>(קרי n על k או k מתוך n), או <math>nCk</math>, כלומר <math>{n! \over k!(n-k)!}</math>.

 

'''[[פונקציית החלוקה (תורת המספרים)|חלוקות]]''' - מספר הדרכים לבחור k עצמים מתוך n עצמים (ייתכן ש-k גדול מ-n), עם חזרות ובלי חשיבות לסדר.

ניתן לראות זאת כבעיה <math>x_1+x_2+x_3+\cdot \cdot \cdot +x_n=k</math>. מה מספר הדרכים להכניס מספרים שלמים אי שליליים ב-N משתנים, כך שחיבורם יתן תוצאה k? כדי לפתור בעיה זו, אפשר לדמיין שטיחת k כדורים בשורה והנחת מחיצות ב-n-1 מהמקומות שביניהם. ממילא יווצרו n תאים הבאים זה אחר זה, בעלי גדלים משתנים, לפי מיקום המחיצות, שהמספר הכולל של כדורים בהם הוא k (שימו לב לאפשרות שתא אינו מכיל כדורים כלל).

כלומר, מונחת לפנינו שורה ובה מקום ל-n-1 מחיצות ול-k כדורים, ויש לבחור היכן למקם את המחיצות. זו בעיית צירופים, והפתרון לה הוא <math>{k+n-1 \choose k}</math> כלומר k+n-1 על k. עוד דוגמה לחלוקות היא יצירת רצף בן k צורות כאשר הצורות נבחרות מ-n אפשרויות שונות.

 

עם בעיות קומבינטוריקה מורכבות יותר מתמודד [[משפט פוליה]], העושה שימוש ב[[פונקציית אוילר]]. השאלה שעליה עונה משפט [[ג'ורג' פוליה|פוליה]] היא: "כיצד ניתן להכין מחרוזת בת n חרוזים מתוך מלאי חרוזים לא מוגבל ב-k צבעים שונים".