כמה שאלות בקומבינטוריקה (ספירה בסיסית)

[csstud]

עברתי על התרגולים הרלבנטיים והבנתי אותם, ובכל זאת אני מתקשה עם החומר. אני מקווה שתשובות לשאלות שלי (מהש"ב) יעזרו לי להבין את זה יותר טוב.

1. בקורס יש 2N סטודנטים ו5N סטודנטיות. המתרגל האחראי דורש שיגישו תרגילי בית בשביעיות, כאשר בכל שביעיה יש 2 סטודנטים ו5 סטודנטיות. חשבו כמה אפשרויות יש לשדך את השביעיות, בהנחה שהסדר בין השביעיות אינו חשוב, וכך גם הסדר בתוך השביעיות.
חשבתי על לקחת את כל הפרמוטציות האפשריות של 7N סטודנטים משני סוגים (5N בנות ו2N בנים) - שזה (7N)! לחלק ל(5N)!(2N)! ואז לבטל את הסדר בין הזוגות ע"י חלוקה בN!, ואת הסדר בתוך השביעיות ע"י חלוקה ב7! בחזקת N. אבל נראה לי שאני מפספס משהו. יכול להיות שהחלוקה ב(5N)!(2N)! מיותרת?

2. כמה סדרות שונות באורך 1 או יותר ניתן להרכיב מהמספרים 1, 2, ..., N כך שבכל סדרה כל המספרים שונים זה מזה?
זה נראה לי שקול למספר הוקטורים הבינאריים עם לפחות מופע אחד של הספרה 1 (שזה כל הוקטורים הבינאריים מלבד וקטור האפס - סה"כ N^2 - 1) כפול N! ליצירת סדר. אבל כשהשוויתי לתוצאה שמתקבלת אם פותרים עם סכימה יצא לי משהו אחר. איפה אני טועה?

3. בכמה דרכים שונות ניתן לסדר M + N רקדנים בשני מעגלים - מעגל בגודל M בו רוקדים "הורה כרוב" ומעגל בגודל N בו רוקדים "הורה תרד"?
מה שעשיתי זה לבחור M רקדנים למעגל הראשון, כלומר M + N מעל M אפשרויות, ולכפול באפשרויות לסדר את שני המעגלים: M - 1 כפול N - 1. זה נכון?

4. רוצים לצבוע קוביות, כל פאה בצבע שונה. מהו מספר האפשרויות לצבוע קוביה ב6 צבעים שונים? (כל הפאות זהות)
אין לי מושג איך לגשת לזה. אגב, 6! זה אם הפאות שונות?

5. עבור השאלה: "מה מספר הוקטורים הבינאריים באורך N שבהם לפחות M אפסים?" ענה סטודנט את התשובה: "בוחרים M מקומות עבור האפסים, ואז בשאר המקומות ניתן לשים 0 או 1. לכן התשובה היא (N מעל M), כפול: שתיים בגובה (N - M)". מצא את השגיאה בתשובת הסטודנט.
לא מצאתי. זה בדיוק מה שיצא לי 

[incog]

טוב:

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


2) אתה צודק בגישתך (זה פתרון מאוד אלגנטי), רק צריך להוריד את ה"כפול N!" , אין צורך להכניס סדר כמו שאמרת יש פונקציה חח"ע למספר הוקטורים הבינאריים פחות הווקטור שכולו אפסים


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


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

[csstud]

קודם כל תודה רבה על התגובה 



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


(על 1 אני צריך עוד לחשוב)

[incog]

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

4) טוב אז כמו שאמרת אם זה היה ממוספר אז זה 6!, עכשיו מכיוון שזה לא ממוספר אזי הכפילות שתקבל היא ממספר הסיבובים של הקוביה.
עכשיו מספר הסיבובים של הקוביה הוא 4*4=16 תחשוב על זה בצורה הזו:
תניח קוביה על ראשית הצירים, אז יש לך 4 דרכים לסובב את הפאות סביב ציר ה-Y ו-4 דרכים לסובב סביב ציר ה-Z.