Дискретно математическо консултиране (usfaq)
Въпрос № 183013: Здравейте! Моля за помощ по следния въпрос: 1. Всички пермутации от 7 числа (1; 2; 3; 4; 5; 6; 7) са подредени в лексикографски ред. Каква е пермутацията на 6153742? 4. Изградете най-голямото съвпадение за двустранна графика. Въпрос № 183013:
Здравейте! Моля за помощ със следния въпрос:
1. Всички пермутации от 7 числа (1; 2; 3; 4; 5; 6; 7) са подредени в лексикографски ред. Каква е пермутацията на акаунта 6153742 ?
4. Постройте най-голямото съвпадение за двустранната графика G. Първата част се състои от върхове, втората част се състои от върхове. Ръбовете са определени от следния списък: .
Нека разгледаме първата задача. Когато подреждате пермутации в лексикографски ред, първата е пермутация 1234567, последната е пермутация 7654321.
1) Преди пермутацията 6153742 има пермутации, започващи с числата 1, 2, 3, 4, 5. Броят им е 5 * 6! = 3600. Броят на пермутацията, която разглеждаме, е не по-малък от 3600 + 1 = 3601.
2) Помислете за пермутацията 153742. Числото 1 е първото възможно, така че броят на пермутацията не се променя.
3) Помислете за пермутацията 53742. Пред нея има пермутации, започващи с числата 2, 3, 4 (числото 1 вече е използвано). Техният брой е 3 * 4! = 72. Като се вземат предвид обсъдените по-горе пермутации, броят на дадената пермутация е не по-малък от 3601 + 72 = 3673.
4) Помислете за пермутация 3742. Преди нея има пермутации, започващи с числото 2 (числото 1 вече е използвано). Техният брой е 1 * 3! = 6. Като се вземат предвид обсъдените по-горе пермутации, броят на дадената пермутация е не по-малък от 3673 + 6 = 3679.
5) Помислете за пермутация 742. Преди нея има пермутации, започващи с числа 2, 4 (числа 1, 3, 5, 6 вече са използвани). Техният брой е 2 * 2! = 8. Предвид обсъжданите по-горе пермутации, броят на дадената пермутация е не по-малък от 3679 + 8 = 3687.
6) Помислете за пермутацията 42. Преди нея има пермутации, започващи с числото 2. Техният брой е 1 * 1! = 1. Като се вземат предвид обсъдените по-горе пермутации, броят на дадената пермутация е не по-малък от 3687 + 1 = 3688.