Помощ за задача по Дискретна математика

[Гост]

Здравейте колеги! Можете ли да ми дадете някакви насоки по тази задача, защото нямам никаква представа какво трябва да направя. Благодаря ви!

[Гост]

Тази също не я разбирам.

[Kre4etalo]

Първо разглеждаме при $k=2$. Искаме да проверим дали $(n!)^{(n-1)!}$ дели $(n!)!$. Частното на двете е така наречения мултиномен коефициент. Следната комбинаторна интерпретация показва, че това частно е цяло число. Представи си, че имаме $n!$ топки, подредени в редица, които са оцветени в $(n-1)!$ цвята, така че от всеки цвят има точно по $n$ топки - топките в еднакъв цвят считаме за неразличими. Сега въпросът е по колко различни начина можем да ги подредим в редица. Това са пермутации с повторения. Нагледен пример - разбъркванията на буквите в думата МАТЕМАТИКА не са $10!$, а са $10!/(2! 3! 2!)$, защото имаме 2-М, 3-А, 2-Т. Понеже са неразличими букви, например М-тата помежду си могат да се разбъркат по $3!$ начина, но няма да го забележим, затова делим на $3!$. Така и в нашата задача - в числител имаме $(n!)!$, а в знаменател слагаме $n!$ за $n$-те топки от цвят 1, след това $n!$ за $n$-те топки от цвят 2, и така нататък до $n!$ за $n$-те топки от цвят $(n-1)!$. Така в знаменател имаме $(n!)$ общо $(n-1)!$ пъти, значи $(n!)^{(n-1)!}$. Полученото частно е някакъв брой (разбърквания) - следователно цяло число.
Нататък задачата се довършва с индукция по $k$. Ще покажем прехода от $k=2$ към $k=3$. За $k=3$ искаме да докажем, че $(n!)^{(n-1)!(n!-1)!}$ дели $((n!)!)!$. Вече знаем (от $k=2$), че $(n!)^{(n-1)!}$ дели $(n!)!$, откъдето $(n!)^{(n-1)!(n!-1)!}$ дели $((n!)!)^{(n!-1)!}$. Така, ако успеем да докажем, че $((n!)!)^{(n!-1)!}$ дели $((n!)!)!$, ще сме готови. Но да забележим, че това е същото като при случая $k=2$, само че навсякъде вместо $n$ пише $n!$ (малко е странно, но да - твърдението при $k=2$ е в сила за всяко естествено число $n$. Тук това естествено число може да е n! - факториел от някакво число - отново естествено). Делимостта е налице. Нататък може да го разпишеш в общия случай - преход от $k$ към $k+1$.

Интересно ми е, колега, откъде са тези задачи? Подозирам, че е ФМИ-СУ. Ако може да кажеш и за коя специалност са.

[Гост]

Благодаря ти за доброто разяснение на задачата! Тя, както и 3-та, са за специалност Компютърни науки във ФМИ.

[Kre4etalo]

Мерси. За другата задача първо да го направим с рекурентно - защото е по-лесно. Нека $a_n$ е броят на тези хубави пермутации на числата от $1$ до $n$. Сега да видим как от една хубава пермутация за $n$ числа можем да получим хубава пермутация за числата до $n+1$. Трябва да вмъкнем някъде най-голямото число - $n+1$. Понеже нарастващите редици трябва да останат две, то трябва най-голямото число да го вмъкнем или в края на първата, или в края на втората (на последно място). Така от всяка хубава пермутация за $n$ числа можем да получим две хубави за $n+1$ числа. Има още една ситуация за получаване на хубава пермутация за $n$ числа - тогава идваме от нехубава пермутация за $n$ числа. Просто вземаме числата от $1$ до $n$ наредени в нарастващ ред (така че не образуват хубава пермутация за $n$ числа, защото всяко е по-малко от следващото) и вмъкваме някъде числото $n+1$. За да получим хубава пермутация можем да го вмъкнем навсякъде, с изключение на последното място - защото тогава отново бихме получили числата в нарастващ ред. Така още $n$ възможни нови хубави пермутации на числата до $n+1$. Може би е удачно да се разгледа и наобратно - вземаме хубава пермутация на числата до $n+1$, махаме числото $n+1$ и проверяваме, че винаги се получава точно един от двата случая - или хубава пермутация на числата до $n$, или числата до $n$ подредени в нарастващ ред.
Така получаваме рекурентното уравнение $a_{n+1}=2a_n+n$, с начално условие $a_2=1$ (или $a_1=0$). Решението е $a_n=2^n-n-1$.
Сега да се опитаме директно. Например нека първата нарастваща редица да е с дължина $k$ ($k\le n-1$ и $k\ge 1$). Тогава по колко начина може да се образува тя - избираме от $n$-те числа $k$ на брой по ${n\choose k}$ начина, и ги подреждаме в нарастваща редица по един единствен начин, т.е. общо ${n\choose k}$ начина. Останалите $n-k$ числа ги слагаме във втората редица също по единствен начин в нарастващ ред. Сега въпросът е, може ли така да се е случило, че получената пермутация да не е хубава. Така ще се окаже, че вместо две отделни нарастващи редици, имаме че цялата пермутация е в нарастващ ред. Тогава най-голямото число от първата е по-малко (а трябва да е по-голямо) от най-малкото във втората. Ако сме получили пермутация, която е изцяло растяща, то това трябва да е просто подредбата $1,2,3,\ldots, n$. Значи това се случва, точно когато първите $k$ числа, които сме избрали са числата $1,2,3,\ldots,k$. Така този случай (и само той) е неблагоприятен за нас. Това означава, че от ${n\choose k}$ начина да изберем първата нарастваща редица, един начин няма да ни доведе в крайна сметка до хубава пермутация. Сега просто събираме по $k$ - $$\sum_{k=1}^{n-1}{n\choose k}-1=2^n-2-(n-1)=2^n-n-1.$$
Може да видиш в OEIS за други интерпретации и информация (тази задача е четвъртия абзац в Comments).