נוסחת ההיפוך של מביוס
קפיצה לניווט
קפיצה לחיפוש
בקומבינטוריקה, נוסחת ההיפוך של מביוס משמשת, בהינתן פונקציה $ F $ שניתנת לתיאור בתור סכום מסוים על ערכי פונקציה אחרת $ f $, לתאר בצורה ישירה את הפונקציה $ f $ באמצעות סכום של $ F $.
הגרסה הקלאסית
הגרסה ה"קלאסית" של הנוסחה היא כדלהלן: בהינתן שתי פונקציות אריתמטיות $ f,F $, אם מתקיים $ F(n)=\sum _{d\mid n}f(d) $ לכל $ n\geq 1 $, אז ניתן להפוך את הנוסחה ולקבל $ f(n)=\sum _{d\mid n}F(n/d)\mu (d) $, כאשר $ \mu $ היא פונקציית מביוס.
אם מסמנים ב-$ \mathbf {1} $ את הפונקציה הקבועה שמקיימת $ \mathbf {1} (n)=1 $ לכל $ n $, ומשתמשים בסימון של קונבולוציית דיריכלה, נוסחת מביוס אומרת שבהינתן $ F=f*\mathbf {1} $, אז $ f=F*\mu $. כלומר $ \mathbf {1} $ ו-$ \mu $ הם איברים הופכיים ביחס לקונבולוציית דיריכלה.
קישורים חיצוניים
- גדי אלכסנדרוביץ', נוסחת ההיפוך של מביוס, באתר "לא מדויק", 7 בינואר 2012
- נוסחת ההיפוך של מביוס, באתר MathWorld (באנגלית)
נוסחת ההיפוך של מביוס30143159Q1072771