סידור עם חזרה: מה זה, נוסחה, דוגמאות

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

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

קרא גם: עקרון יסוד של ספירה - מושג עיקרי של ניתוח קומבינטורי

מה זה סידור עם חזרה?

יש סידור עם חזרה בייצור לוחות רכב. [1]

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

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

ניתנה סט עם לא אנו מכירים כסידור עם חזרה את כל הקבוצות שנוכל ליצור איתן k אלמנטים של זה מַעֲרֶכֶת, שבו ניתן לחזור על אלמנט יותר מפעם אחת. על לוחיות רישוי לרכב, למשל, זהו מספר הלוחיות האפשריות שנוכל ליצור תוך לקיחה בחשבון שיש להם שלוש אותיות וארבע ספרות וכי ניתן לחזור על האותיות והמספרים.

כדי לחשב את מספר הסדרים החוזרים האפשריים, אנו משתמשים בנוסחה פשוטה מאוד.

אל תפסיק עכשיו... יש עוד אחרי הפרסום;)

נוסחת סידור עם חזרה

כדי למצוא את סכום ההסדר המלא של לא אלמנטים מובחנים שנלקחו מ k ב

אה, במצב נתון המאפשר חזרה על אלמנט, אנו משתמשים בנוסחה הבאה:

אוויר_לא,_k = לא^k

AR → סידור עם חזרה
לא → מספר האלמנטים בערכה
k → מספר האלמנטים שייבחרו

ראה גם: שילוב פשוט - ספר את כל קבוצות המשנה של קבוצה נתונה

כיצד לחשב את מספר ההסדר החוזר

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

דוגמה 1:

סיסמה של בנק כוללת חמש ספרות המורכבות אך ורק ממספרים, מה מספר הסיסמאות האפשריות?

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

אוויר_10,5 = 10⁵ = 10.000

אז יש 10,000 אפשרויות סיסמה.

דוגמה 2:

בידיעה כי לוחיות רישוי לרכב מורכבות משלוש אותיות וארבע מספרים, כמה לוחיות רישוי ניתן ליצור?

האלף בית שלנו מורכב מ -26 אותיות, ויש 10 מספרים אפשריים, אז בואו נחלק לשני מערכים שלמים ונמצא את מספר המערכים האפשריים עבור האותיות והמספרים.

אוויר_26,3 = 26³ = 17.576
אוויר₁₀,₄ = 10⁴ = 10.000

לפיכך, סך ההסדרים האפשריים הוא:

17.576 · 10.000 = 1.757.600.000

ההבדל בין סידור פשוט לסידור חוזר

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

הנוסחה לסידור הפשוט שונה מזו שאנו משתמשים בה לסידור החוזר.

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

דוגמא:

פאולו רוצה לשים על המדף שלושה מתוך עשרה ספרי הלימוד שלו, כולם שונים זה מזה, כמה דרכים הוא יכול לארגן את הספרים האלה?

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

למידע נוסף על צורת קיבוץ אחרת זו המשמשת לניתוח קומבינטורי, קרא את הטקסט: הסידור פשוט.

תרגילים נפתרו:

שאלה 1 - (אויב) בנק ביקש מלקוחותיו ליצור סיסמה אישית בת שש ספרות, המורכבת רק ממספרים 0 עד 9, כדי לגשת לחשבון הצ'ק באמצעות האינטרנט. עם זאת, מומחה במערכות אבטחה אלקטרוניות המליץ ​​להנהלת הבנק לרשום מחדש את משתמשיו, בבקשה כל אחת מהן, יצירת סיסמא חדשה עם שש ספרות, המאפשרת כעת שימוש ב -26 אותיות האלף-בית, מלבד הספרות מ -0 עד 9. במערכת חדשה זו, כל אות גדולה נחשבה מובחנת מגרסתה הקטנה. בנוסף, השימוש בסוגים אחרים של דמויות היה אסור.

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

פתרון הבעיה

חלופה א

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

אוויר_10,6 = 10⁶

הסיסמה החדשה יכולה להכיל 10 ספרות וגם אותיות גדולות (26 אותיות) ו- אותיות קטנות (26 אותיות), כך שהסיסמא כוללת לכל ספרה 10 + 26 + 26 = 62 אפשרויות. מכיוון שיש שש ספרות, נחשב את הסדר עם חזרה של 62 אלמנטים שצולמו כל שש.

אוויר_62,6 = 62⁶

ה סיבה של המספר החדש של אפשרויות הסיסמה בהשוואה לזו הישנה שווה ל -62⁶/10⁶.

שאלה 2 - (Enem 2017) חברה תקים את אתר האינטרנט שלה ומקווה למשוך קהל של כמיליון לקוחות. כדי לגשת לדף זה תצטרך סיסמה עם פורמט שתוגדר על ידי החברה. ישנן חמש אפשרויות פורמט המוצעות על ידי המתכנת, המתוארות בטבלה, כאשר "L" ו- "D" מייצגות, בהתאמה, אות גדולה וספרה.

ניתן לחזור על אותיות האלף-בית, בין 26 האפשריות, כמו גם הספרות, בין 10 האפשריות בכל אחת מהאפשרויות.

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

פתרון הבעיה

חלופה ה

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

אני → LDDDDD

26 ·10⁵ גדול משני מיליון, כך שהוא אינו מספק את בקשת החברה.

II → DDDDDD

10⁶ שווה למיליון, כך שהוא אינו מספק את בקשת החברה.

III → LLDDDD

26² · 10⁴ גדול משני מיליון, כך שהוא אינו מספק את בקשת החברה.

IV → DDDDD

10⁵ זה פחות ממיליון, כך שהוא לא מספק את בקשת החברה.

V → LLLDD

26³ · 10² הוא בין מיליון לשני מיליון, כך שתבנית סיסמא זו היא אידיאלית.

אשראי תדמיתי

[1] רפאל ברלנדי / שוטרסטוק

מאת ראול רודריגס דה אוליביירה
מורה למתמטיקה