|
==מונחים בקומבינטוריקה==
'''[[תמורה (מתמטיקה)|תמורה]]''' (פרמוטציה) - סידור כלשהו של n עצמים שונים בשורה. באופו פורמלי, תמורה זו בה[[פונקציה nהפיכה]] מקומותמקבוצה (ללאסופית חזרות)לעצמה.
מספר התמורות השונות של n עצמים הוא !n (קרי: n [[עצרת]],). פונקציה השווההמוגדרת למכפלתבצורה כל השלמים מ-1 ועד n זה בזהרקורסיבית: <math>n1! = \begin{cases} 1\cdot2\cdot3\cdot \cdot</math>ו-<math>n! \cdot (n,+1) &= (n\in\N \\ +1, & n=0 \end{cases})!</math> . למשל: <math>1\cdot 2\cdot 3\cdot 4=4!=24</math>){{ש}}יש. יותר מטריליון אפשרויות לסדר 15 עצמים שונים בשורה.
פונקצית העצרת גדלה בקצב מהיר מאוד. [[אי-שוויון הממוצעים]] ו[[אינטגרל]] פשוט אומר כי <math>(\frac{n+1}{2})^n \geq n! \geq (\frac{n}{1+ln(n)})^n</math>. [[נוסחת סטירלינג|נוסחת סטרלינג]] נותנת פונקציה פשוטה יותר להבנה שהיא קירוב אסימפטוטי של העצרת.
הסיבה לכך ש-<math>\ n!</math> הוא מספר האפשרויות לסדר <math>n</math> עצמים שונים בשורה היא פשוטה: בכמה מקומות ניתן לשים את העצם הראשון? <math>n</math> מקומות (כל המקומות פנויים). בכמה מקומות ניתן לשים את העצם השני? <math>n-1</math> מקומות, שכן מקום אחד כבר תפוס על ידי העצם הראשון. כך הלאה, עד לעצם האחרון, לו נשאר רק מקום אחד פנוי. בסך-הכל יש <math>n</math> אפשרויות לסידור העצם הראשון; על כל אפשרות כזו יש <math>n-1</math> אפשרויות לסידור העצם השני, וכן הלאה: <math>n\cdot (n-1)\cdot \cdot \cdot 3\cdot 2\cdot 1=n!</math>
'''חליפות''' - מספר האפשרויות לבחור k עצמים מתוך n עצמים שונים, עם חשיבות לסדר הבחירה.
| 