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

אנחנו יודעים איך סידור חוזר, או סידור מלא, כל הארגונים המסודרים שנוכל ליצור איתם 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] רפאל ברלנדי / שוטרסטוק

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

מָקוֹר: בית ספר ברזיל - https://brasilescola.uol.com.br/matematica/arranjo-com-repeticao.htm