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

[הרוצה להחכים]

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

נתונים המספרים מ- 1 עד 10.

בכמה דרכים אפשר לחלק את המספרים לשלוש קבוצות לא ריקות אם אין חשיבות לסדר הקבוצות?

בסעיף הקודם היתה שאלה דומה רק עם שתי קבוצות במקום שלוש, ושם הגעתי לתשובה 511.
מניח שבשלב ראשון צריך להוריד מ- 3 בחזקת 10 את מספר החלוקות שבהן כל המספרים בקבוצה אחת (ויש שלוש חלוקות כאלה) ואחרי זה את מספר החלוקות שבהן כל המספרים בשתי קבוצות בלבד והשלישית ריקה. ולכאורה לפי הסעיף הקודם זה צריך להיות 1533 אבל משהו כאן לא מסתדר לי. עזרה?

(שונא שאלות חישוביות וקורסים חישוביים! שונא!)

 

[עריסטו]

הכלה הדחה

כמובן קודם כל נחשב עם חשיבות לסדר הקבוצות ובסוף נחלק ב-6.
קח את כל החלוקות (3 בחזקת 10 כמו שכתבת)
חסר את מספר החלוקות בהן קבוצה א ריקה (1024), את מספר החלוקות בהן קבוצה ב ריקה (כנ"ל), ואת מספר החלוקות בהן קבוצה ג ריקה (כנ"ל)
הוסף את מספר החלוקות בהן א+ב ריקות (1), את מספר החלוקות בהן א+ג ריקות (1) ואת מספר החלוקות בהן ב+ג ריקות (1)
ולבסוף חסר את מספר החלוקות בהן א+ב+ג ריקות (0)
יצא לי 9330.

 

[הרוצה להחכים]

תודה! ועוד אחת

בכמה דרכים אפשר לסדר את המספרים (כאמור מ-1 עד 10) במעגל, אם אסור שיהיו במעגל שני מספרים זוגיים סמוכים ?

 

[אורי769]

הדרכה

נסה ראשית לפתור את זה עבור n=4 ועבור n=6. הפתרון עבור מקרים אלו הוא מספיק קטן שניתן למנות את האפשרויות "באופן ידני". בעיקר המקרה של n=6 אמור לתת לך אינטואיציה לפתרון עבור n=10.
בנוסף, הנה שאלה - נניח יש לך p ראשוני. בכמה אפשרויות ניתן לסדר את המספרים מ-1 עד p במעגל?

 

[הרוצה להחכים]

נסיון - 2880. זה נכון ?

&nbsp
יש 4! אפשרויות לסדר את 5 המספרים הזוגיים במעגל, וביניהם יש 5! אפשרויות לסדר את המספרים האי זוגיים. זה בסדר?

 

[אורי769]

נכון מאד

 

[הרוצה להחכים]

תודה! ועוד אחת

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

 

[אורי769]

דווקא התחלת טוב

תמיד טוב לחקור קצת באופן ידני מקרים קטנים כדי לקבל אינטואיציה. מה יצא לך עבור סולם בן 1,2,3,4,... שלבים?

 

[הרוצה להחכים]

1,2,3,5

 

[אורי769]

נכון

תמשיך עוד שניים. נסה לחשוב מה הדרך הידנית שבה אתה מחשב את הערך ה-n-י בסדה הזו

 

[AnarchistPhilosopher]

האם למדת על נוסחאות נסיגה?

 

[הרוצה להחכים]

לא, לא למדתי.

וגם אם כן הייתי מכיר, הייתי מעדיף פתרון קומבינטורי בסיסי.

 

[אורי769]

לצערי אין

כפי שציין האנרכיסט, הפתרון כאן הוא בעזרת נוסחת נסיגה. הנה הסבר:
נסמן ב-an את הפתרון עבור סולם בן n שלבים. קל לבדוק ש-
a1=1
a2=2
כעת השאלה היא מהו an. אז התשובה היא שצריך להסתכל על הצעד האחרון שביצעת. הוא יכול להיות צעד בודד או צעד כפול. אם ביצעת צעד בודד אז לפני הצעד האחרון היית בשלב n-1. לכן היו לך (a(n-1 אפשרויות להגיע לשם. אם הצעד האחרון היה צעד כפול אז לפני אותו הצעד היית בשלב n-2 והיו לך (a(n-2 אפשרויות להגיע לשם. לכן
(a = a(n-1)+a(n-2
זו סדרה המכונה גם סדרת פיבונצ'י. יש לה אגב גם נוסחא מפורשת, אבל לא ניתן להגיע אליה בכלים קומבינטוריים אלא בעזרת כלים אלגבריים.

 

[הרוצה להחכים]

מוזר

&nbsp
מה הקשר כאן סדרת פיבונאצ'י ? (בקורס בתורת המספרים היה לנו פרק שעסק בזה, דילגתי בזמנו על הנושא המשעמם הזה ואני לא מצטער, גם הציון שלי כלל לא מצטער על כך ).
&nbsp
השאלות האלה נועדו לתרגל קומבינטוריקה בסיסית. לא ברור.
&nbsp
תודה לכם

 

[אורי769]

גם עובדה זה פאקט

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

 

[AnarchistPhilosopher]

איך קבעת שזה נושא משעמם?

נוסחאות נסיגה יחד עם משוואות דיפרנציאליות הם שני נושאים עם הכי הרבה שימושים במדמ"ח ובהנדסה.
&nbsp
כמובן שזה אינדיבידואלי, אני מוצא שחינוך ופסיכולוגיה זה בלבולי מוח, אבל כל אחד ומה שהוא אוהב אני מניח.
&nbsp

 

[הרוצה להחכים]

פשוט קבעתי

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