88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 9 - היסטוריית גרסאות

ארז שיינר ב־16:17, 11 במרץ 2015

2015-03-11T16:17:29Z

→ הגרסה הקודמת		גרסה מ־16:17, 11 במרץ 2015
שורה 1:		שורה 1:
	'''[[מתמטיקה בדידה - מערך תרגול\|חזרה למערכי התרגול]]'''		'''[[מתמטיקה בדידה - מערך תרגול\|חזרה למערכי התרגול]]'''

	~~[[מדיה:11BdidaCombBG.pdf\|קובץ דוגמאות והסברים בקומבינטוריקה מבן גוריון]]~~

	=מבוא לקומבינטוריקה=		=מבוא לקומבינטוריקה=

			[[מדיה:11BdidaCombBG.pdf\|קובץ דוגמאות והסברים בקומבינטוריקה מבן גוריון]]

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

אחיה בר-און: /* מספר האפשריות לבחור k עצמים מתוך n עצמים */

2013-08-09T08:29:44Z

מספר האפשריות לבחור k עצמים מתוך n עצמים

→ הגרסה הקודמת		גרסה מ־08:29, 9 באוגוסט 2013
שורה 22:		שורה 22:
	== מספר האפשריות לבחור k עצמים מתוך n עצמים==		== מספר האפשריות לבחור k עצמים מתוך n עצמים==
	השאלות שצריך לשאול הם- האם יש חשיבות לסדר (הבחירה) והאם מותר לבחור איבר פעמיים. לכן ישנם 4 מקרים אפשריים.		השאלות שצריך לשאול הם- האם יש חשיבות לסדר (הבחירה) והאם מותר לבחור איבר פעמיים. לכן ישנם 4 מקרים אפשריים.

			נשים לב שאם אסור חזרות אזי חייב להיות <math>k\leq n</math> (אחרת התשובה היא 0)

	{\| border="1" align="center" style="text-align:center;"		{\| border="1" align="center" style="text-align:center;"

אחיה בר-און: /* אין חשיבות לסדר ויש חזרות */

2013-08-09T08:27:51Z

אין חשיבות לסדר ויש חזרות

→ הגרסה הקודמת		גרסה מ־08:27, 9 באוגוסט 2013
שורה 135:		שורה 135:

	ג. נסמן <math>\|A\|=a</math>. מספרים היחסים על A הוא קבוצת החזקה של <math>A\times A</math> שזה <math>2^{\|A\times A\|}=2^{a^2}</math>. כעת, פונקציה חד ערכית מקבוצה בגודל k אל קבוצה בגודל n מכילה		ג. נסמן <math>\|A\|=a</math>. מספרים היחסים על A הוא קבוצת החזקה של <math>A\times A</math> שזה <math>2^{\|A\times A\|}=2^{a^2}</math>. כעת, פונקציה חד ערכית מקבוצה בגודל k אל קבוצה בגודל n מכילה
	<math>n\cdot (n-1) \cdots (n-k+1)=\frac{n!}{(n-k)!}</math> איברים.		<math>n\cdot (n-1) \cdots (n-k+1)=\frac{n!}{(n-k)!}</math> איברים.

	אבל, חייב להתקיים ש k<n אחרת לא תתכן פונקציה חח"ע (והנוסחא כמובן לא תהא הגיונית), במקרה שלנו <math>2^{a^2}>a</math> ולכן אין אף פונקציה חח"ע מקבוצת היחסים של A אל A.		אבל, חייב להתקיים ש k<n אחרת לא תתכן פונקציה חח"ע (והנוסחא כמובן לא תהא הגיונית), במקרה שלנו <math>2^{a^2}>a</math> ולכן אין אף פונקציה חח"ע מקבוצת היחסים של A אל A.

אחיה בר-און: /* אין חשיבות לסדר ויש חזרות */

2013-08-09T08:27:18Z

אין חשיבות לסדר ויש חזרות

→ הגרסה הקודמת		גרסה מ־08:27, 9 באוגוסט 2013
שורה 94:		שורה 94:
	כעת, יש לנו <math>n+k-1</math> מקומות שצריך למלא (k אחדות ו n-1 חוצצים) וצריך לבחור מתוכם את המקומות של החוצצים (ואז ממילא יקבעו מקומות של האחדות) ולכן יש		כעת, יש לנו <math>n+k-1</math> מקומות שצריך למלא (k אחדות ו n-1 חוצצים) וצריך לבחור מתוכם את המקומות של החוצצים (ואז ממילא יקבעו מקומות של האחדות) ולכן יש
	<math>{n+k-1\choose k}=\frac{(n+k-1)!}{k!(n-1)!}</math> אפשריות כאלו.		<math>{n+k-1\choose k}=\frac{(n+k-1)!}{k!(n-1)!}</math> אפשריות כאלו.
	אם כן, נספור את מספר האפשרויות לסדר את החוצצים. נשים בשורה את כל האחדות ואת כל החוצצים, סה"כ נקבל <math>n+k-1</math> איברים. מספר האפשרויות לסדר אותם הוא <math>(n+k-1)!</math>. כעת, צריך לחלק בחזרות המיותרות: סדר החוצצים אינו משנה, וכמו כן סדר האחדות אינו משנה. לכן סה"כ מספר האפשרויות הינו <math>{n+k-1\choose k}=\frac{(n+k-1)!}{k!(n-1)!}</math>

			'''מסקנה''' מספר הדרכים שיש לבחור k איברים מתוך קבוצה של n איברים כאשר מותר לי לבצע חזרות ולא משנה הסדר הוא <math>{n+k-1\choose k}</math>
	'''מסקנה''' מספר הדרכים שיש לבחור k איברים מתוך קבוצה של n איברים כאשר מותר לי לבצע חזרות ולא משנה ~~לי סדר האיברים~~ הוא <math>{n+k-1\choose k}</math>

	'''הוכחה'''		'''הוכחה'''

	נסמן את האיברים בקבוצה <math>a_1,...,a_n</math>. נסמן את מספר ~~הפעמים ש~~<math>~~a_n~~</math> ~~נבחר~~ ב-<math>~~x_n~~</math> (שלם אי שלילי). ~~כמובן שסכום~~ <math>x_n</math> ~~חייב להיות~~ k.		נסמן את האיברים בקבוצה <math>a_1,...,a_n</math>. נסמן את מספר החזרות של כל איבר <math>a_i</math> ב-<math>x_i</math> (שלם אי שלילי).
			כיוון שרוצים לבחור k איברים השאלה שקולה ל-כמה פתרונות שלמים אי שליליים יש למשוואה <math>x_1+...+x_n=k</math> שראינו שהתשובה היא <math>{n+k-1\choose k}</math>

	~~בדוגמא לעיל נסמן <math>\{0,1\}=\{a_1,a_2\}</math>. בחירת שני אחדות ואפס יחיד שקולה לפתרון המשוואה <math>x_1+x_2=2+1=3</math>, וכדומה.~~


שורה 136:		שורה 134:
	ב. ניתן לבחור שלושה מספרים זוגיים, או שני אי זוגיים וזוגי. <math>{50 \choose 3}+{50\choose 2}\cdot{50 \choose 1}</math>		ב. ניתן לבחור שלושה מספרים זוגיים, או שני אי זוגיים וזוגי. <math>{50 \choose 3}+{50\choose 2}\cdot{50 \choose 1}</math>

	ג. נסמן <math>\|A\|=a</math>. מספרים היחסים על A הוא קבוצת החזקה של <math>A\times A</math> שזה <math>2^{\|A\times A\|}=2^{a^2}</math>. כעת, פונקציה חד ערכית מקבוצה בגודל k אל קבוצה בגודל n מכילה <math>n\cdot (n-1) \cdots (n-k+1)=\frac{n!}{(n-k)!}</math> איברים.		ג. נסמן <math>\|A\|=a</math>. מספרים היחסים על A הוא קבוצת החזקה של <math>A\times A</math> שזה <math>2^{\|A\times A\|}=2^{a^2}</math>. כעת, פונקציה חד ערכית מקבוצה בגודל k אל קבוצה בגודל n מכילה
			<math>n\cdot (n-1) \cdots (n-k+1)=\frac{n!}{(n-k)!}</math> איברים.

	אבל, חייב להתקיים ש k<n אחרת לא תתכן פונקציה חח"ע (והנוסחא כמובן לא תהא הגיונית), במקרה שלנו <math>2^{a^2}>a</math> ולכן אין אף פונקציה חח"ע מקבוצת היחסים של A אל A.		אבל, חייב להתקיים ש k<n אחרת לא תתכן פונקציה חח"ע (והנוסחא כמובן לא תהא הגיונית), במקרה שלנו <math>2^{a^2}>a</math> ולכן אין אף פונקציה חח"ע מקבוצת היחסים של A אל A.

אחיה בר-און: /* מספר האפשריות לבחור k עצמים מתוך n עצמים */

2013-08-09T08:16:11Z

מספר האפשריות לבחור k עצמים מתוך n עצמים

→ הגרסה הקודמת		גרסה מ־08:16, 9 באוגוסט 2013
שורה 38:		שורה 38:
	\|}		\|}

			נתחיל לטפל בכל אחד מהמקרים:

			=== יש חשיבות לסדר ויש חזרות ===
			בהנתן n עצמים אזי בבחירה הראשונה ניתן יש n אפשרויות לבחור ולבחירה השניה יש n אפשריות לבחור (כי מותר חזרות), ... ,לבחירה ה-k יש n אפשרויות לבחור ולכן בסה"כ יש <math>n^k</math> אפשרויות.

			'''דוגמא''' כמה מספרים בינאריים יש עם 3 ספרות ?

			''' פתרון''' לספרה הראשונה יש 2 אפשרויות, לספרה השניה יש 2 אפשרויות ולספרה השלישית יש 2 אפשריות ולכן בסה"כ יש <math>2^3</math> וזה כל המספרים. (הבחירה היא הספרות 0,1 כאשר מותר חזרות ויש חשיבות לסדר)

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

			'''דוגמא''' כמה מספרים בעלי 3 ספרות שונות יש?

			''' פתרון''' נבחר מתוך הספרות 0-9 שלוש בחירות עם חשיבות לסדר ובלי חזרות ונקבל <math>\frac{10!}{(7)!}=10\cdot 9 \cdot 8</math> (לספרה הראשונה יש 10 אפשרויות, לספרה השניה יש רק 9 אפשרויות ולספרה האחרונה נשארו 8 אפשרויות)


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

	'''דוגמא.''' בכמה דרכים ניתן לבחור קבוצה של k חפצים מתוך קבוצה של n חפצים? (במילים אחרות, כמה תת קבוצות מעוצמת k יש לקבוצה מגודל n).		'''דוגמא.''' בכמה דרכים ניתן לבחור קבוצה של k חפצים מתוך קבוצה של n חפצים? (במילים אחרות, כמה תת קבוצות מעוצמת k יש לקבוצה מגודל n).

			'''פתרון.''' זה שקול לבחור k חפצים כאשר הסדר לא משנה ובלי חזרות ולכן יש <math> {n \choose k} </math> תתי קבוצות.

	'''פתרון.''' נמיר את הבעייה לבעייה אחרת. נספור את כמות האפשרויות לבחור k חפצים כאשר הסדר בינהם משנה, ולאחר מכן נחלק את הכמות שקיבלנו במספר האפשרויות לסדר את k החפצים (הלא הוא <math>k!</math>).		מסקנה: <math>\sum_{k=0}^n {n \choose k}=2^n</math>

	~~אם כך, אנו מעוניינים לדעת כמה אפשרויות יש לנו לבחור k חפצים מתוך~~ n חפצים כאשר הסדר שלהם משנה. נסדר את n החפצים בשורה וניקח את k הראשונים. כמה פעמים נקבל את אותה סדרת k חפצים? בדיוק כמספר הפעמים שאפשר לסדר את n-k החפצים הנותרים.		הוכחה: ניקח קבוצה X בת n איברים אזי שני האגפים שווים למספר הקבוצות של בקבוצת החזקה.

	~~אם כך, קיבלנו נוסחא~~ <math>{n \choose k} = ~~\frac~~{n~~!}{k!(~~n-k)!}</math>		'''תרגיל''' הוכח כי <math> {n \choose k}= {n \choose n-k}</math>

			'''פתרון''' לבחור קבוצה של k אברים שקול לבחור n-k אברים שאינם בקבוצה (כלומר לבחור תת קבוצה A זה כמו לבחור את המשלימה שלה)

			אתם מוזמנים גם לחשב ישירות.


			=== אין חשיבות לסדר ויש חזרות ===

	'''תרגיל.''' כמה פתרונות שלמים אי שליליים יש למשוואה <math>x_1+...+x_n=k</math>?		'''תרגיל.''' כמה פתרונות שלמים אי שליליים יש למשוואה <math>x_1+...+x_n=k</math>?

	'''פתרון.''' נחלק את המספר k לאחדות, ~~ונשים בין~~ האחדות n-1 חוצצים ~~שונים. המשתנה~~ ה-~~s הוא מספר האחדות שבין החוצץ ה~~-~~s לקודמו~~.		'''פתרון.''' נחלק את המספר <math>k=1+1+1\cdots+1</math> לאחדות, ונחלק את האחדות ל-n המשתנים האפשריים.
			נעשה זאת כך- נשים n-1 חוצצים בין n המשתנים ונחלק 1-ים לפי כמות ה-1-ים שכל משתנה מקבל.

	למשל נביט בפתרונות שונים למשוואה <math>x_1+x_2+x_3=2</math>:		למשל נביט בפתרונות שונים למשוואה <math>x_1+x_2+x_3=2</math>:
שורה 63:		שורה 92:


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


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

	~~דבר ראשון נסביר את התרגיל. נגיד אנו רוצים לבחור 3 מספרים בינאריים כאשר לא חשוב לנו הסדר. אז אפשר לבחור~~ 1 ~~אחד ושני אפסים, או שלושה אפסים, או שתי אחדות ואפס יחיד או שלושה אחדות.~~

	'''~~פתרון.~~'''		'''הוכחה'''

	~~נשים לב שזה תרגיל שקול לתרגיל הקודם. נקרא לאיברים~~ בקבוצה <math>a_1,...,a_n</math>. נסמן את מספר הפעמים ש<math>a_n</math> נבחר ב-<math>x_n</math> (שלם אי שלילי). כמובן שסכום <math>x_n</math> חייב להיות k.		נסמן את האיברים בקבוצה <math>a_1,...,a_n</math>. נסמן את מספר הפעמים ש<math>a_n</math> נבחר ב-<math>x_n</math> (שלם אי שלילי). כמובן שסכום <math>x_n</math> חייב להיות k.

	בדוגמא לעיל נסמן <math>\{0,1\}=\{a_1,a_2\}</math>. בחירת שני אחדות ואפס יחיד שקולה לפתרון המשוואה <math>x_1+x_2=2+1=3</math>, וכדומה.		בדוגמא לעיל נסמן <math>\{0,1\}=\{a_1,a_2\}</math>. בחירת שני אחדות ואפס יחיד שקולה לפתרון המשוואה <math>x_1+x_2=2+1=3</math>, וכדומה.

אחיה בר-און: /* מספר האפשריות לבחור k עצמים מתוך n עצמים */

2013-08-09T07:36:23Z

מספר האפשריות לבחור k עצמים מתוך n עצמים

→ הגרסה הקודמת		גרסה מ־07:36, 9 באוגוסט 2013
שורה 33:		שורה 33:
	\|-		\|-
	\|'''אין חשיבות לסדר'''		\|'''אין חשיבות לסדר'''
	\|<math>\;\;\;\{n \choose k} = \frac{n!}{k!(n-k)!} \;\;\;</math>		\|<math>\;\;\;{n \choose k} = \frac{n!}{k!(n-k)!} \;\;\;</math>
	\|<math>\;\;\;{n+k-1\choose k}\;\;\;</math>		\|<math>\;\;\;{n+k-1\choose k}\;\;\;</math>
	\|-		\|-

אחיה בר-און: /* מבוא לקומבינטוריקה */

2013-08-09T07:34:04Z

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

@@ שורה 13: / שורה 13: @@
 '''פתרון.''' למעשה בעייה זו שקולה לבעיית חלוקת 10 אנשים לשתי קבוצות שונות בלבד, מכיוון שיש רק דרך אחת למיין את האנשים לפי הסדר של התור המקורי בכל תת קבוצה. נלמד בהמשך כיצד לפתור בעייה פשוטה זו.
 '''דוגמא.''' בכמה דרכים אפשר לסדר n אנשים בתור?
 '''פתרון.''' כל אחד יכול להיות ראשון בתור לכן כבר יש n אפשרויות. כעת, נניח ואיציק ראשון בתור, נותר לסדר n-1 אנשים אחריו בתור. נניח באינדוקציה שמספר האפשרויות לסדר n-1 אנשים בתור הוא <math>(n-1)!</math> ונקבל שמספר האפשרויות שלנו הוא <math>n\cdot (n-1)! = n!</math>.

עדיאל ב־14:30, 21 באוגוסט 2012

2012-08-21T14:30:31Z

→ הגרסה הקודמת		גרסה מ־14:30, 21 באוגוסט 2012
שורה 79:		שורה 79:

	א. ניתן לבחור כל מספר מ1 עד 100. כעת, המספר המתאים לו צריך להיות מאותה זוגיות על מנת שהסכום יהיה זוגי. לכן בבחירה הראשונה היו לנו 100 אפשרויות ובשנייה 49. כעת, סדר הזוג לא משנה לכן נחלק ב2. סה"כ התוצאה היא <math>50\cdot 49</math>. זה בדיוק שווה לסעיף 1, שכן		א. ניתן לבחור כל מספר מ1 עד 100. כעת, המספר המתאים לו צריך להיות מאותה זוגיות על מנת שהסכום יהיה זוגי. לכן בבחירה הראשונה היו לנו 100 אפשרויות ובשנייה 49. כעת, סדר הזוג לא משנה לכן נחלק ב2. סה"כ התוצאה היא <math>50\cdot 49</math>. זה בדיוק שווה לסעיף 1, שכן
	<math>{50 \choose 2}+{50 \choose 2}+2{50 \choose 2} = 2\frac{50!}{2!48!}=2\frac{50\cdot 49}{2}</math>		<math>{50 \choose 2}+{50 \choose 2}=2{50 \choose 2} = 2\frac{50!}{2!48!}=2\frac{50\cdot 49}{2}</math>

ארז שיינר: /* טבלת סיכום לנוסחאות בסיסיות ידועות */

2012-08-15T07:47:23Z

טבלת סיכום לנוסחאות בסיסיות ידועות

→ הגרסה הקודמת		גרסה מ־07:47, 15 באוגוסט 2012
שורה 111:		שורה 111:
	\|מספר האפשרויות לבחור k איברים מתוך n איברים '''(ללא משמעות לסדר, עם חזרות)'''		\|מספר האפשרויות לבחור k איברים מתוך n איברים '''(ללא משמעות לסדר, עם חזרות)'''
	\|<math>{n+k-1\choose k}=\frac{(n+k-1)!}{k!(n-1)!}</math>		\|<math>{n+k-1\choose k}=\frac{(n+k-1)!}{k!(n-1)!}</math>
	\|-
	~~\|מספר הפונקציות החח"ע בין קבוצות סופיות A ו-B (כאשר <math>\|A\|\leq \|B\|</math>)~~
	~~\|<math>\frac{\|B\|!}{(\|B\|-\|A\|)!}</math>~~
	\|-		\|-
	\|}		\|}

ארז שיינר ב־02:10, 23 ביולי 2012

2012-07-23T02:10:49Z

→ הגרסה הקודמת		גרסה מ־02:10, 23 ביולי 2012
שורה 1:		שורה 1:
	'''[[88-~~195 בדידה לתיכוניסטים תשעא/~~מערך ~~שיעור~~\|חזרה למערכי התרגול]]'''		'''[[מתמטיקה בדידה - מערך תרגול\|חזרה למערכי התרגול]]'''

	[[מדיה:11BdidaCombBG.pdf\|קובץ דוגמאות והסברים בקומבינטוריקה מבן גוריון]]		[[מדיה:11BdidaCombBG.pdf\|קובץ דוגמאות והסברים בקומבינטוריקה מבן גוריון]]