5.2 Комбинаторика перестановок

модуль 5.2 шаг 4

Дать комбинаторную интерпретацию рекуррентного соотношения для чисел Стирлинга первого рода

\[c(n+1,k)=n\cdot{c(n,k)}+c(n,k-1), \quad \quad \quad k = 1,2,...,n+1, \quad \quad \quad n=0,1,2...\] \[c(0,0)=1, \quad \quad \quad c(n,0)=0 \quad \quad \forall{n=1,2,...,} \quad \quad c(n,k)=0 \quad \forall{k>n}\]

Решение и ответ

1747906079163

модуль 5.2 шаг 6

Представить многочлен

\[x^4-8x^3+21x^2-6x+3\]

в виде многочлена от убывающих факториальных степеней \((x)_k\). Пример: многочлен \(x^2-1\) в факториальном базисе \((x)_k\) записывается так:

\[(x)_2+(x)_1-1\]

Пример ввода данного результата в Степик:

x_2+x_1-1

Иными словами, при вводе ответа считается, что \(x_k \equiv (x)_k\) .

Решение

https://abakbot.ru/online-16/372-fac-polynom

Ответ

8*x_1+4*x_2-2*x_3+x_4+3

модуль 5.2 шаг 7

Переписать многочлен

\[3(x)_4-(x)_3-2(x)_2-3(x)_1-5,\]

записанный в факториальном базисе, в виде обычного многочлена четвертой степени, то есть переписать его в степенном базисе.

Пример: многочлен \((x)_2+(x)_1-1\), записанный в факториальном базисе, в обычном степенном базисе имеет вид

\[x^2-1.\]

Пример ввода ответа в Степик: <pre>x^2-1</pre>

Ответ

3*x^4-19*x^3+34*x^2-21*x-5

модуль 5.2 шаг 9

Еще одним обобщением задачи о беспорядках является задача о поиске количества \(D(n,k)\) перестановок, в которых ровно \(k\) элементов остаются на своих местах, а \((n−k)\) элементов меняют свое положение. Доказать, что

\[D(n,k)=\binom{n}{k}\cdot{D_{n-k}}=\frac{n!}{k!}\sum_{i=0}^{n-k}\frac{(-1)^i}{i!}.\]

Построить производящую функцию \(D(z,t)\) для этих чисел.

Решение и ответ

1747906079163

модуль 5.2 шаг 10

Перестановка \(\sigma\) называется инволюцией, если квадрат этой перестановки есть тождественная перестановка \(id\):

\[\sigma\cdot\sigma=id.\]

Записать экспоненциальную производящую функцию \(H(z)\), описывающую количество таких перестановок.

Ответ

e^(z+z^2/2)

модуль 5.2 шаг 12

Записать из комбинаторных соображений цикловой индекс \(\tilde{Z}(x_1,x_2,x_3,x_4)\) в виде многочлена, зависящего от \(x_1,x_2,x_3,x_4\). Пример ввода в Степик циклового индекса \(\tilde{Z}(x_1,x_2,x_3)\):

x_1^3+3*x_1*x_2+2*x_3

Ответ

x_1^4+6*x_1^2*x_2+8*x_1*x_3+3*x_2^2+6*x_4