Факториал функциясы

Рекурсияның алғашқы мысалы ретінде факториал функциясын қалай есептеу керек екендігін қарастырайық. $n$n санының факториалы $n!$n, ! символымен белгіленеді. Бұл 1-ден $n$n-ге дейінгі бүтін сандардың көбейтіндісі болып табылады. Мысалы, $5!$5, ! = $1 \cdot 2 \cdot 3 \cdot 4 \cdot 5$1, dot, 2, dot, 3, dot, 4, dot, 5 немесе $5! = 120$5, !, equals, 120.

"Факториал функциясын қарастырудың қажеттілігі неде?" деген сұрақ туындауы мүмкін. Элементтерді орналастырудың немесе біріктірудің неше тәсілі бар екендігін есептегенде факториал өте пайдалы болып келеді. Мысалы, $n$n элементті неше түрлі әдіспен орналастыруға болады? Бізде бірінші элементті орналастырудың $n$n тәсілі бар. Осы $n$n тәсілдің әрқайсысы үшін бізде екінші элементті орналастырудың $n-1$n, minus, 1 тәсілі бар. Сонымен бізде алғашқы екі элементті орналастырудың $n\cdot (n-1)$n, dot, left parenthesis, n, minus, 1, right parenthesis тәсілі бар. Енді осы алғашқы екі тәсілдің әрқайсысы үшін үшінші элементті орналастырудың $n-2$n, minus, 2 тәсілі бар. Бұл бізге алғашқы үш элементті орналастырудың $n\cdot (n-1)\cdot (n-2)$n, dot, left parenthesis, n, minus, 1, right parenthesis, dot, left parenthesis, n, minus, 2, right parenthesis тәсілін береді. Осылай бізде 2 элемент қалғанға дейін, содан соң 1 элемент қалғанға дейін жалғастырамыз. Осылайша бізде $n$n элементті орналастырудың $n\cdot (n-1) \cdot (n-2) \cdots 2\cdot 1$n, dot, left parenthesis, n, minus, 1, right parenthesis, dot, left parenthesis, n, minus, 2, right parenthesis, \@cdots, 2, dot, 1 тәсілі бар. Бұл көбейтінді $n!$n, ! ($n$n факториал) болып табылады. Бірақ бұл көбейтінді 1-ден $n$n - ге дейін емес, керісінше $n$n - нен 1-ге дейінгі көбейтінді ретінде жазылады.

Факториал функциясының тағы бір қолданылуы - элементтер жиынтығынан белгілі бір элементтерді қанша жолмен таңдауға болатындығын есептеу. Мысалы, сіз сапарға шығайын деп жатырсыз және өзіңізбен бірге алатын футболкаларды таңдағыңыз келеді делік. Сізде $n$n футболка бар делік, бірақ олардың ішінен тек $k$k футболканы ғана салатын орын бар. $n$n футболкалар жиынтығынан $k$k оларды неше түрлі жолмен таңдауға болады? Жауап (оны біз мұнда дәлелдеуге тырыспаймыз) $n ! / (k!\cdot (n-k)!)$n, !, slash, left parenthesis, k, !, dot, left parenthesis, n, minus, k, right parenthesis, !, right parenthesis болып табылады. Осылайша факториал функциясының қаншалықты пайдалы бола алатындығын көре аламыз. Сіз алмастырулар мен терулер туралы осы жерден көбірек біле аласыз, бірақ факториал алгоритмін жүзеге асыру үшін оларды түсіну міндетті емес.

Факториал функциясы барлық оң бүтін сандар мен 0 үшін анықталады. 0! мәні қандай болуы керек? Бұл 1-ден үлкен немесе тең және 0-ден кіші немесе тең барлық бүтін сандардың көбейтіндісі болып табылады. Бірақ мұндай бүтін сандар жоқ. Демек, біз 0! мәнін көбейтуге қатысты бірлікке, яғни 1-ге тең етіп аламыз. (0! = 1 тағайындауы $n$n элементтен $k$k элементін таңдауға арналған формуламен жақсы үйлеседі. $n$n элементтен $k$k элементті таңдаудың қанша тәсілі бар екенін білгіміз келеді делік. Бұл оңай болып табылады, өйткені таңдаудың бір ғана жолы бар: барлық $n$n элементті таңдау. Сонымен жоғарыдағы формуланы қолдана отырып, біз $n!/(n! \cdot (n-n)!)$n, !, slash, left parenthesis, n, !, dot, left parenthesis, n, minus, n, right parenthesis, !, right parenthesis 1-ге тең болу керектігін білеміз. Бірақ $(n-n)!$left parenthesis, n, minus, n, right parenthesis, ! өрнегі 0!-ге тең болып табылады, сондықтан біз $n!/(n! \cdot 0!)$n, !, slash, left parenthesis, n, !, dot, 0, !, right parenthesis 1-ге тең болуы тиіс екендігін білеміз. Егер біз алымын да, бөлімін де $n!$n, !-ға қысқартсақ, $1!/ (0! )$1, !, slash, left parenthesis, 0, !, right parenthesis өрнегі 1-ге тең болуы керек екендігін көре аламыз. Ал ол расында 1-ге тең, себебі 0! = 1.

Енді біз $n!$n, ! туралы білеміз. Оның мәні $n = 0$n, equals, 0 болған кезде 1-ге тең, ал $n$n оң саң болғанда $1 \cdot 2 \cdots (n-1) \cdot n$1, dot, 2, \@cdots, left parenthesis, n, minus, 1, right parenthesis, dot, n көбейтіндісіне тең.

Бұл мазмұн ынтымақтастықтың нәтижесі Дартмут компьютерлік ғылымы профессорлар [Томас Кормен](http://www.cs.dartmouth.edu / ~thc/) және [Дэвин Бэлком](http://www.cs.dartmouth.edu / ~devin/), сонымен қатар Хан академиясының компьютерлік оқу бағдарламасы бойынша тобы. Мазмұн лицензияланған CC-BY-NC-SA.