נוסחת ההיפוך של מביוס

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

בקומבינטוריקה, נוסחת ההיפוך של מביוס משמשת, בהינתן פונקציה $ 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 $ הם איברים הופכיים ביחס לקונבולוציית דיריכלה.

קישורים חיצוניים

ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום למכלול ולהרחיב אותו.
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

נוסחת ההיפוך של מביוס30143159Q1072771