עקרון ההכלה וההפרדה, ואז הכללה והפחדה

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

פונקציות יוצרות – והפעם ברצינות

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

משפט רמזי

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

כל כך קשה לבחור…

אני ממשיך את סדרת הפוסטים שלי על קומבינטוריקה ברמה תיכונית, והפעם אני רוצה לנקוט בגישה "מתמטית" לדברים שכבר גילינו. המתמטיקאי תמיד מנסה לבחון מחדש את ההנחות שלו ולהקל על הדרישות בכדי להכליל את התוצאות שלו, וזה גם מה שאני רוצה לעשות. הנוסחה המרכזית שגילינו עד כה הייתה כי $latex \frac{n!}{k!\left(n-k\right)!}$, שאותו סימנו בקיצור $latex {n …

משולש פסקל

אחד הדברים היפים במתמטיקה הוא האופן שבו אובייקטים שנראים תמימים בהתחלה מתגלים כבעלי תכונות רבות ומעניינות. במבט ראשון, קשה לחשוב שאוסף הפתרונות של משוואה מוזרה כמו $latex y^{2}=x^{3}+ax+b$ יתגלה כבעל מבנה עשיר ומעניין מאין כמוהו, אך אוספי פתרונות שכאלו (שמכונים "עקומים אליפטיים") הם אובייקט שנחקר בצורה אינטנסיבית במתמטיקה המודרנית, והתפרסמו בפרט בגלל הקשר שלהם לפתרון …

הבינום של ניוטון

הפוסט הקודם שלי עסק במבוא לקומבינטוריקה, ברמה שבתקווה גם תלמידי תיכון יוכלו להבין. אני רוצה להמשיך כעת באותה הרוח ולהציג תוצאה קומבינטורית פשוטה אך יפה, שכבר בשלב זה ניתן להבין, באמצעות הכלים שהצגתי בפוסט הקודם – הבינום של ניוטון. בשלב כלשהו בתיכון נלמדת הנוסחה הפשוטה הבאה: $latex \left(a+b\right)^{2}=a^{2}+2ab+b^{2}$. למה? ככה. לפעמים גם נלמדת נוסחה יותר …

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

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