Podsilnie i nieporządki

https://xpil.eu/z4l 📋

Każdy, kto choćby otarł się o matematykę na poziomie szkoły średniej wie, że wykrzyknik jest matematycznym symbolem silni.

Cóż to takiego - silnia?

Proste jak konstrukcja silni: najpierw przyjmujemy, że silnia z zera i z jedynki wynosi jeden, a następnie dla każdej kolejnej liczby naturalnej przyjmujemy, że silnia z tej liczby to iloczyn tej liczby przez silnię liczby ją poprzedzającej.

Skomplikowane?

To może prościej: silnia z dowolnej liczby naturalnej n to iloczyn wszystkich liczb naturalnych mniejszych lub równych n:

n! = 1 * 2 * 3 * 4 * ... * n

Odświeżywszy tę szkolną definicję pokażę teraz coś, czego w szkołach raczej nie uczą. Otóż silnię można obliczyć w jeszcze jeden sposób:

n! = (n - 1) * ((n - 1)! + (n - 2)!)

Czyli tak: dla zera i jedynki przyjmujemy n!=1, a dla całej reszty n! to iloczyn liczby poprzedzającej n oraz sumy silni dwóch liczb poprzedzających n.

Dla trójki mamy:

3! = 2 * (2! + 1!)

Dla szóstki:

6! = 5 * (5! + 4!)

Taki sposób wyliczania silni jest na pierwszy rzut oka może nieco dziwny, jednak po bliższym przyjrzeniu się nie ma tu niczego nadzwyczajnego. W przykładzie z 6! w nawiasie mamy 5!+4!, przy czym 5! to nic innego jak 5*4!. Jeżeli do 5*4! dodamy 4!, otrzymamy 6*4!. Mnożąc to przez piątkę (tę przed nawiasem) dostajemy: 6! = 4!*5*6 czyli wszystko się zgadza.

No dobra. Silnie są na dłuższą metę nudne.

A gdyby tak dać silnię dwulatkowi, co zrobi?

Na pewno spróbuje najpierw oderwać wykrzyknik od n, bo dwulatki (i nie tylko) uwielbiają rozbijać wszystko na mniejsze kawałki, żeby sprawdzić co jest w środku i jak to działa.

A więc zamiast n! mamy teraz samo n oraz leżący obok wykrzyknik.

Co dalej?

Spróbujemy je skleić do kupy, ale odwrotnie:

!n

Uzyskaliśmy w ten sposób symbol  p o d s i l n i  czyli takiej jakby silni, ale trochę na odwrót.

O ssso chodzzzzi?

Najpierw pokażę definicję formalną:

!0 = 1
!1 = 0
!n = (n - 1) * (!(n - 1) + !(n - 2))

Wygląda znajomo?

Zgadza się! Silnia i podsilnia są liczone w analogiczny sposób. Podsilnia z zera to jeden, podsilnia z jedynki to zero (!), natomiast podsilnia z czegokolwiek większego od jedynki to iloczyn liczby poprzedniej przez sumę dwóch poprzednich podsilni.

Jedyna istotna różnica jest taka, że 1! = 1 ale !1 = 0.

Oczywiście możemy też zapomnieć o "tradycyjnej" definicji - jeżeli błędnie założymy (wzorem zwykłej silni), że !n = n * !(n-1), dostaniemy w wyniku same zera. A więc zapominamy o mnożeniu i przyjmujemy powyższą definicję: !n = (n - 1) * (!(n - 1) + !(n - 2))

Efekt?

Oto kilka pierwszych podsilni, dla n kolejno 1, 2, 3, 4, ... 17:

!0 = 1
!1 = 0
!2 = 1
!3 = 2
!4 = 9
!5 = 44
!6 = 265
!7 = 1854
!8 = 14833
!9 = 133496
!10 = 1334961
!11 = 14684570
!12 = 176214841
!13 = 2290792932
!14 = 32071101049
!15 = 481066515734
!16 = 7697064251745
!17 = 130850092279664

Pozostaje teraz zadać sobie jeszcze jedno istotne pytanie:

A po co?

Po jaką cholerę męczyć się z jakimiś dodatkowymi, wymyślonymi pseudo-silniami skoro mamy już normalną, zwykłą silnię? Nie można po prostu ustawić tego cholernego wykrzyknika po prawej stronie i zapomnieć o całej sprawie?

Niby można, ale wtedy byłoby nudno... Poza tym podsilnia ma - wbrew pierwszemu wrażeniu - jedno bardzo konkretne zastosowanie: liczy nieporządki.

Proszę się nie stresować, nie będziemy teraz liczyć nieporządków w szafie ani w zlewozmywaku. Nieporządek w sensie matematycznym to takie ułożenie elementów zbioru X, w którym żaden z elementów nie znajduje się na swojej oryginalnej pozycji.

Que??

Spróbujmy prościej:

Mamy trzech uczniów: Adrian, Bartek i Czarek.

Rysujemy na boisku trzy kwadraty, oznaczamy je literami A, B i C.

Pytanie: na ile sposobów można ustawić Adriana, Bartka i Czarka w tych kwadratach, żeby żaden z nich nie stał w kwadracie z literą, na jaką zaczyna się jego imię?

Innymi słowy, na ile sposobów można uporządkować listę [A, B, C] tak, żeby A nigdy nie było pierwsze, B drugie a C - trzecie?

Spróbujmy:

[B, C, A] [C, A, B]

i to wszystko. Inaczej się nie da. Czyli dla trzech elementów mamy dwa nieuporządkowania. !3 = 2

Sprawdźmy dla czterech elementów:

[B, A, D, C] [B, C, D, A] [B, D, A, C] [C, A, D, B] [C, D, A, B] [C, D, B, A] [D, A, B, C] [D, C, A, B] [D, C, B, A]

Jak widać, jest dokładnie dziewięć takich nieuporządkowań. !4 = 9

A po co takie cyrki, spytacie uparcie?

A no na przykład żeby rozwiązać następującą zagadkę:

Nauczyciel zrobił w czteroosobowej grupie kartkówkę. Zebrał kartki, wymieszał je i rozdał uczniom w losowej kolejności, żeby sprawdzili sobie nawzajem wyniki. Jaka jest szansa, że żaden z uczniów nie dostał swojego własnego sprawdzianu?

Wynik: !4/4! czyli 9/24, czyli trzy ósme. Ciut ponad jedną trzecią.

Podsilnia ma jeszcze jedną interesującą (zieeeew) cechę: jeżeli będziemy brać silnie z kolejnych liczb naturalnych, a następnie dzielić je przez podsilnie z tych liczb, będziemy się zbliżać do wartości e, czyli podstawy logarytmu naturalnego. Po wykonaniu nieskończonej ilości dzieleń dojdziemy do e.

Granica jest dość szybko zbieżna, rzućmy okiem co na ten temat mówi Wolfram Alpha:

Jak widać różnica między faktyczną wartością e a wartością wyliczoną za pomocą podsilni wynosi mniej niż 5 undecylionowych części jedności. Bardzo niewiele. Prawdopodobnie wystarczająco dokładnie, żeby policzyć trajektorię pojazdu wokół całego Wszechświata, z dokładnością do stałej Plancka.

Czy coś.

https://xpil.eu/z4l 📋