csstud

תודה :smile: בהרצאה הראו שתי דרכים: 1. פתרון רקורסיבי: הכדור הראשון יכול להיות לבד בתא או ביחד עם עוד כדורים. כשהוא לבד בתא אז אתה מחלק n-1 כדורים ל-k-1 תאים. כשהוא לא לבד אתה מוציא אותו (זמנית), מחלק n-1 כדורים ל-k תאים, ואז מחזיר אותו (יש k אפשרויות להחזרתו, כי התאים היו זהים כשהוא הוצא). סה"כ: S(n,k) = S(n-1,k-1) + S(n-1,k)*k. 2. פתרו קודם את הבעיה עבור תאים שונים, וחילקו ב-!k כדי לבטל את הסדר.

אני רוצה להבין אם הפתרון שלי נכון, ואם לא - למה. חלוקה של n כדורים שונים ל-k תאים זהים, כאשר אף תא אינו ריק. הפתרון שלי: אם אף תא אינו ריק, בכל תא יש לפחות כדור אחד. נשים כדור בכל תא - יש (n מעל k) אפשרויות לעשות את זה כי אחרי שבחרתי את k הכדורים שיחולקו מתוך כל ה-n, יש רק אפשרות אחת לחלק מתוכם כדור אחד לכל תא (כי התאים זהים). אחרי שעשיתי את זה, התאים כבר לא זהים ונשארתי עם n-k כדורים שונים לחלק ל-k תאים שונים, הפעם בלי אילוצים נוספים. לזה יש k בחזקת (n-k) אפשרויות. סה"כ: (n מעל k) * (k בחזקת n-k). לדעתי אני מפספס משהו כי פתרון אחר לשאלה שהופיע בהרצאה, נותן לי תוצאה מספרית שונה עבור ערכים מסויימים של n ו-k. אשמח לקבל הסברים.

אתה מועיל כמו תמיד. תודה :)

http://i.imgur.com/WtFrujY.jpg?1 נתחיל כרגע מסעיף ב' - אני רוצה לוודא שמה שעשיתי נכון: אם מוצאים הומומורפיזם (מעכשיו ייכתב בקיצור - הומ') מG לחבורה אחרת כלשהי כך שהגרעין של אותו הומ' הוא N, והתמונה שלו היא R עם הפעולה +, אז אפשר להשתמש במשפט ההומ' הראשון וזו הוכחה לטענה (אני צודק בזה?). זה הדבר שהכי חשוב לי לוודא. אבל גם לגבי שאר ההוכחה (כתוב בספוילר) אני לא בטוח, ואם מישהו רוצה לעזור לי גם לגבי זה אני כמובן אשמח מאד.

אוקיי, הבנתי עכשיו. תודה!

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

אה, הבנתי :thumbsup:

אוי, לא חשבתי על להעלות בחזקת k. תודה! אגב, סתם מסקרנות - מהמשוואה שהזכרתי כאן: לא ניתן להסיק את מה שאמרתי (ש-a^m שווה ל-e של G) ? כי אם כן, זה בעצם אומר (בצירוף להוכחה שלך) ש-k שווה ל-m (כי שניהם מחלקים זה את זה).

קודם כל, כרגיל - תודה רבה. באמת השתמשתי במשפט הזה (מותר לנו בקורס להשתמש בו בלי להוכיח), אבל הוא הביא אותי למסקנה ההפוכה. לגבי מה שכתבת, עכשיו אני באמת מבולבל. את זה לא הוכחתי, זה הנתון. גם זה, הנתון כבר אומר שהסדר של aN ב-G/N הוא בדיוק m. בעצם מה שחסר לי זה על איזה חבורה ואיזה איבר אני מיישם את המשפט שהזכרת. *אם a בחזקת m שווה לאיבר היחידה ב-G (זה נכון?), אז אפשר להגיד ש-k מחלק את m, אבל זה ההיפך ממה שהתבקשתי להוכיח...

G חבורה, N תת חבורה נורמלית בG. a איבר בG מסדר k. נסמן ב-m את הסדר של האיבר aN בחבורת המנה G/N. צ"ל: k מתחלק ב-m. הכיוון שלי: aN בחזקת m, זה בעצם (a בחזקת m) כפול N, ומכיוון ש-m זה הסדר אז הביטוי הזה שווה לאיבר היחידה של חבורת המנה, כלומר ל-N. כלומר, קיבלתי משוואה: N = N *י(a^m) מכאן נראה לי מתבקש לטעון ש-a בחזקת m שווה לאיבר היחידה ב-G אבל אני לא בטוח למה... וגם אם כן, זה יוכיח ש-m מתחלק ב-k, לא ש-k מתחלק ב-m. יכול להיות שהתבלבלו בשאלה?

אוי נכון.. תודה!

תודה לשניכם :) snorlax - לא הבנתי למה מספר הקשתות גדול או שווה לm-n+1 8-[

יהי G גרף פשוט לא מכוון עם n צמתים ו- m קשתות. צ"ל שאם m גדול מ (n בריבוע חלקי 4) אז בגרף G יש משולש (כלומר 3 צמתים שכולם מחוברים בקשתות זה לזה) רמז: להניח בעזרת אינדוקציה שהטענה נכונה לכל גרף G' עם פחות מ- n צמתים, ולהסתכל על שני צמתים כלשהם. אין לי מושג איך לפתור את זה.. אני מניח שהרעיון זה להחסיר מגרף עם n צמתים מספר מסויים של קשתות וצמתים, ולהראות שקיבלנו גרף שבו מספר הקשתות גדול ממספר הצמתים בריבוע חלקי 4, ואז יש בו משולש ולכן גם בגרף שלפני ההחסרה. או שאני לא בכיוון?

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

קודם כל תודה רבה על המאמץ. לא הבנתי איך איחוד של קבוצה כלשהי עם A_i יכול לתת לי קבוצה ספיקה, הרי קבוצת כל הפסוקים היא לא ספיקה.