База ответов ИНТУИТ

Комбинаторные алгоритмы для программистов

<<- Назад к вопросам

Обозначим число перестановок последовательности α1,...,αn-1,αn через Pn. Какая формула подсчета перестановок верна?

(Отметьте один правильный вариант ответа.)
Варианты ответа
число различных мест, которые может занять элемент αn, равно n, и поэтому из каждой перестановки элементов α1,...,αn-1 получается n перестановок элементов α1,...,αn-1,αn. Но это означает, что перестановок из n элементов в n раз больше, чем перестановок из n-1 элементов. Тем самым установлено рекуррентное соотношение, последовательно выводим, что Pn=nPn-1=n(n-1)Pn-2=n(n-1)...2P1. Но P1=1, так как из одного элемента можно сделать одну перестановку. Поэтому Pn=n(n-1)...2·1=n! Таким образом мы получили формулу Pn=n!/4
число различных мест, которые может занять элемент αn, равно n, и поэтому из каждой перестановки элементов α1,...,αn-1 получается n перестановок элементов α1,...,αn-1,αn. Но это означает, что перестановок из n элементов в n раз больше, чем перестановок из n-1 элементов. Тем самым установлено рекуррентное соотношение, последовательно выводим, что Pn=nPn-1=n(n-1)Pn-2=n(n-1)...2P1. Но P1=1, так как из одного элемента можно сделать одну перестановку. Поэтому Pn=n(n-1)...2·1=n! Таким образом мы получили формулу Pn=n!/3
число различных мест, которые может занять элемент αn, равно n, и поэтому из каждой перестановки элементов α1,...,αn-1 получается n перестановок элементов α1,...,αn-1,αn. Но это означает, что перестановок из n элементов в n раз больше, чем перестановок из n-1 элементов. Тем самым установлено рекуррентное соотношение, последовательно выводим, что Pn=nPn-1=n(n-1)Pn-2=n(n-1)...2P1. Но P1=1, так как из одного элемента можно сделать одну перестановку. Поэтому Pn=n(n-1)...2·1=n! Таким образом мы получили формулу Pn=n!/2
число различных мест, которые может занять элемент αn, равно n, и поэтому из каждой перестановки элементов α1,...,αn-1 получается n перестановок элементов α1,...,αn-1,αn. Но это означает, что перестановок из n элементов в n раз больше, чем перестановок из n-1 элементов. Тем самым установлено рекуррентное соотношение, последовательно выводим, что Pn=nPn-1=n(n-1)Pn-2=n(n-1)...2P1. Но P1=1, так как из одного элемента можно сделать одну перестановку. Поэтому Pn=n(n-1)...2·1=n! Таким образом мы получили формулу Pn=n!(Верный ответ)
Похожие вопросы
Имеется pq+r разных предметов, где 0≤r<p. Они делятся между p людьми возможно ровнее (все получают либо q, либо q+1 предметов). Сколько существует способов такого раздела?
Ряд c0+c1x+...+cnxn+... при достаточно малых значениях x сходится к f(x)/ϕ(x). От чего зависит размер области сходимости?
Может ли корень иметь сыновей меньше m в сбалансированном сильно ветвящемся дереве порядка m?
Что называется производящей функцией для последовательности a0,a1,a2,...,?
Что называется формальным рядом для последовательности a0,a1,a2,...,?
Какую функцию называют производящей для последовательности чисел a0,a1,...,an?
Если последовательность вершин v0,v1,...,vp определяет путь в G(V,E) графе, то как определяется его длина?
Что называется потомком определенной вершины в дереве <V,T>, где Т⊆E?
Какая последовательность удовлетворяет равенству an+2+2an+1-8an=2n
Какая функция является производящей функцией для чисел Сnk,k=0,1,...,?