3

Разбиения множеств, циклы в подстановках

[25/100%]
Показать
LaTeX
Задача 1.186

Составить таблицу чисел SknS_k^n для n≤8n \leq 8, 1≤k≤n1 \leq k \leq n.

?
Примечание.
?

Выписать конкретно различные возможности для малых nn, для всех n≥3n \geq 3 воспользоваться задачей 187.

Задача 1.187

Очевидно,

S1n=Snn=1. S_1^n = S_n^n = 1 .

Показать, что

Skn+1=Sk−1n+kSkn. S_k^{n+1} = S_{k-1}^n + k S_k^n .
?
Задача 1.188

Показать, что

Skkzk+1+Skk+1zk+2+⋯+Sknzn+1+⋯=1z(z−1)(z−2)⋯(z−k). \frac{S_k^k}{z^{k+1}} + \frac{S_k^{k+1}}{z^{k+2}} + \cdots + \frac{S_k^n}{z^{n+1}} + \cdots = \frac{1}{z(z-1)(z-2) \cdots (z-k)} .
?
Задача 1.189

Показать, что при n≥1n \geq 1

Skn=1k![kn−(k1)(k−1)n+(k2)(k−2)n−⋯+(−1)k0n]. S_k^n = \frac{1}{k!} \left[ k^n - \binom {k}{1}(k-1)^n + \binom {k}{2}(k-2)^n - \cdots + (-1)^k 0^n \right] .
?
Задача 1.190

Показать, что

∑n=k∞Sknznn!=(ez−1)kk!. \sum _{n=k}^{\infty } \frac{S_k^n z^n}{n!} = \frac{(e^z-1)^k}{k!} .
?
Задача 1.191

Доказать тождество относительно xx

xn=S1nx+S2nx(x−1)+⋯+Snnx(x−1)⋯(x−n+1).[Задача 189; см. также III 221.] x^n = S_1^n x + S_2^n x(x-1) + \cdots + S_n^n x(x-1) \cdots (x-n+1) . \qquad \text{[Задача 189; см. также III 221.]}
?
Задача 1.192

Доказать тождество задачи 191 независимо от задачи 189 и вывести отсюда новое доказательство задачи 189.

?
Примечание.
?

Комбинаторным рассуждением.

Задача 1.193

Положим T0=1T_0=1. Тогда

T0+T1z1!+T2z22!+⋯+Tnznn!+⋯=eez−1. T_0 + \frac{T_1 z}{1!} + \frac{T_2 z^2}{2!} + \cdots + \frac{T_n z^n}{n!} + \cdots = e^{e^z-1} .
?
Задача 1.194

Показать, что

Tn+1=(n0)Tn+(n1)Tn−1+(n2)Tn−2+⋯+(nn)T0. T_{n+1} = \binom {n}{0} T_n + \binom {n}{1} T_{n-1} + \binom {n}{2} T_{n-2} + \cdots + \binom {n}{n} T_0 .
?
Примечание.
?

Комбинаторным рассуждением.

Задача 1.195

Воспользоваться задачей 194 для доказательства задачи 193 [см. также задачу 34].

?
Задача 1.196

Показать, что при n≥1n \geq 1

Tn=1e(1n1!+2n2!+3n3!+⋯ ). T_n = \frac{1}{e} \left( \frac{1^n}{1!} + \frac{2^n}{2!} + \frac{3^n}{3!} + \cdots \right) .
?
Задача 1.197

Составить таблицу чисел skns_k^n для n≤8n \leq 8, 1≤k≤n1 \leq k \leq n.

?
Примечание.
?

Выписать конкретно различные возможности для малых nn, для всех n≥3n \geq 3 воспользоваться задачей 198.

Задача 1.198

Очевидно,

s1n=(n−1)!,snn=1. s_1^n = (n-1)!, \qquad s_n^n = 1 .

Показать, что

skn+1=sk−1n+nskn. s_k^{n+1} = s_{k-1}^n + n s_k^n .
?
Задача 1.199

Показать, что

x(x+1)(x+2)⋯(x+n−1)=s1nx+s2nx2+⋯+snnxn x(x+1)(x+2) \cdots (x+n-1) = s_1^n x + s_2^n x^2 + \cdots + s_n^n x^n

или, что то же самое, что

x(x−1)(x−2)⋯(x−n+1)=(−1)n−1s1nx+⋯−sn−1nxn−1+snnxn. x(x-1)(x-2) \cdots (x-n+1) = (-1)^{n-1} s_1^n x + \cdots - s_{n-1}^n x^{n-1} + s_n^n x^n .
?
Задача 1.200

Показать, что

∑n=k∞sknznn!=1k!(log⁡11−z)k. \sum _{n=k}^{\infty } \frac{s_k^n z^n}{n!} = \frac{1}{k!} \left( \log \frac{1}{1-z} \right)^k .
?
Примечание.
?

Сравнить задачу 200 с задачей 190, задачу 199 с задачей 188 и еще раз задачу 199 с задачей 191. См. также [VII 54.2] и [VIII 247.1].

Задача 1.201

Составить таблицу чисел S~kn\widetilde{S}_k^n для n≤8n \leq 8, 1≤k≤n1 \leq k \leq n.

?
Примечание.
?

Выписать конкретно различные возможности для малых nn, для всех n≥4n \geq 4 воспользоваться задачей 202.

Задача 1.202

Очевидно,

S~1n=1 при n≥2,S~kn=0 при n<2k. \widetilde{S}_1^n = 1 \text{ при } n \geq 2, \qquad \widetilde{S}_k^n = 0 \text{ при } n<2k .

Показать, что

S~kn+1=nS~k−1n−1+kS~kn. \widetilde{S}_k^{n+1} = n \widetilde{S}_{k-1}^{n-1} + k \widetilde{S}_k^n .
?
Задача 1.203

Показать, что

S~2n=2n−1−n−1,S~n2n=1⋅3⋅5⋯(2n−1). \widetilde{S}_2^n = 2^{n-1}-n-1, \qquad \widetilde{S}_n^{2n} = 1 \cdot 3 \cdot 5 \cdots (2n-1) .
?
Задача 1.204

Возвращаясь к SknS_k^n, показать, что

Sn−1n=(n2),Sn−2n=(n3)3n−54,Sn−3n=(n4)(n−2)(n−3)2 S_{n-1}^n = \binom {n}{2}, \qquad S_{n-2}^n = \binom {n}{3} \frac{3n-5}{4}, \qquad S_{n-3}^n = \binom {n}{4} \frac{(n-2)(n-3)}{2}

и что вообще Sn−anS_{n-a}^n есть полином от nn степени 2a2a, делящийся на n(n−1)(n−2)⋯(n−a)n(n-1)(n-2) \cdots (n-a); разумеется, a≥1a \geq 1.

?
Задача 1.205

Положим T~0=1\widetilde{T}_0=1,

T~n=S~1n+S~2n+⋯+S~nn \widetilde{T}_n = \widetilde{S}_1^n + \widetilde{S}_2^n + \cdots + \widetilde{S}_n^n

при n≥1n \geq 1. Вычислить TnT_n и T~n\widetilde{T}_n для n≤8n \leq 8.

?
Задача 1.206
T~n+1=(n1)T~n−1+(n2)T~n−2+⋯+(nn−1)T~1+(nn)T~0. \widetilde{T}_{n+1} = \binom {n}{1} \widetilde{T}_{n-1} + \binom {n}{2} \widetilde{T}_{n-2} + \cdots + \binom {n}{n-1} \widetilde{T}_1 + \binom {n}{n} \widetilde{T}_0 .
?
Задача 1.207
T~0+T~1z1!+T~2z22!+⋯+T~nznn!+⋯=eez−1−z. \widetilde{T}_0 + \frac{\widetilde{T}_1 z}{1!} + \frac{\widetilde{T}_2 z^2}{2!} + \cdots + \frac{\widetilde{T}_n z^n}{n!} + \cdots = e^{e^z-1-z} .
?
Задача 1.208
T~n=(n0)Tn−(n1)Tn−1+(n2)Tn−2−⋯+(−1)n(nn)T0. \widetilde{T}_n = \binom {n}{0} T_n - \binom {n}{1} T_{n-1} + \binom {n}{2} T_{n-2} - \cdots + (-1)^n \binom {n}{n} T_0 .
?
Примечание.
?

T~n=ΔnT0\widetilde{T}_n = \Delta^n T_0, если пользоваться обозначениями исчисления конечных разностей, см. введение к [III 220].

Задача 1.209

Если функция F(t)F(t) имеет nn-ю производную, то

(ddx)nF(ex)=S1nF′(ex)ex+S2nF′′(ex)e2x+⋯+SnnF(n)(ex)enx. \left( \frac{d}{dx} \right)^n F(e^x) = S_1^n F'(e^x) e^x + S_2^n F''(e^x) e^{2x} + \cdots + S_n^n F^{(n)}(e^x) e^{nx} .
?
Задача 1.210

Вывести тождества относительно переменных zz и ww:

∑n=0∞∑k≤n(nk)wkznn!=ez(w+1),(1) \sum _{n=0}^{\infty } \sum _{k \leq n} \binom {n}{k} \frac{w^k z^n}{n!} = e^{z(w+1)} , \tag {1} ∑n=0∞∑k≤nSknwkznn!=e(ez−1)w,(2) \sum _{n=0}^{\infty } \sum _{k \leq n} S_k^n \frac{w^k z^n}{n!} = e^{(e^z-1)w} , \tag {2} ∑n=0∞∑k≤nsknwkznn!=(1−z)−w(3) \sum _{n=0}^{\infty } \sum _{k \leq n} s_k^n \frac{w^k z^n}{n!} = (1-z)^{-w} \tag {3}

либо на основании предыдущего [задачи 10, 190, 200], либо независимо от предыдущего.

?
Примечание.
?

С другой стороны, мы могли бы рассматривать (1), (2) и (3) как определения соответственно (nk)\binom {n}{k}, SknS_k^n и skns_k^n и затем принять их за основу и отправную точку для установления предложений, в особенности комбинаторных предложений, обсуждавшихся в заканчивающемся здесь параграфе. Дополнительный материал по предмету, рассмотренному в этом параграфе, см. [V 62.1], [VII 54.2], [VIII 22.1, 22.2, 22.3, 58.3, 247.1], а также задачи 191.1, 191.2 настоящего отдела.