3

Принцип включения-исключения

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

Пусть дано NN любых объектов. Пусть NαN_{\alpha } — число тех из них, которые обладают некоторым свойством α\alpha, NβN_{\beta } — число тех, которые обладают свойством β,…,Nϰ\beta , \ldots , N_{\varkappa }, соотв. NλN_{\lambda }, — число тех, которые обладают свойством ϰ\varkappa, соотв. λ\lambda. Аналогично пусть NαβN_{\alpha \beta }, Nαγ,…,Nαβγ,…,Nαβγ…ϰλN_{\alpha \gamma }, \ldots , N_{\alpha \beta \gamma }, \ldots , N_{\alpha \beta \gamma \ldots \varkappa \lambda } обозначают число тех из этих объектов, которые одновременно обладают свойствами α\alpha и β\beta, соотв. α\alpha и γ,…\gamma , \ldots, соотв. α,β\alpha , \beta и γ,…\gamma , \ldots, соотв. α,β,γ,…,ϰ\alpha , \beta , \gamma , \ldots , \varkappa и λ\lambda. Тогда число объектов, которые не обладают ни одним из свойств α,β,γ,…,ϰ,λ\alpha , \beta , \gamma , \ldots , \varkappa , \lambda, равно

N−Nα−Nβ−Nγ−…−Nϰ−Nλ++Nαβ+Nαγ+…+Nϰλ−−Nαβγ−…+…………±Nαβγ…ϰλ. \begin{aligned} & N-N_{\alpha }-N_{\beta }-N_{\gamma }-\ldots -N_{\varkappa }-N_{\lambda }+ \\ & +N_{\alpha \beta }+N_{\alpha \gamma }+\ldots +N_{\varkappa \lambda }- \\ & -N_{\alpha \beta \gamma }-\ldots + \\ & \ldots \ldots \ldots \ldots \\ & \pm N_{\alpha \beta \gamma \ldots \varkappa \lambda } . \end{aligned}
?
Примечание.
?

J. J. Sylvester, C. R., т. 96, стр. 463, 1883.

Задача 8.21.1

Что представляет собой характеристическая функция

?
(1)

дополнения множества AA,

(2)

пересечения множеств AA и BB,

(3)

объединения множеств AA и BB?

Задача 8.21.2

Дать другое доказательство задачи 21.

?
Задача 8.22

Пусть дано nn объектов (n>1n>1) и пусть свойством α\alpha обладают все кроме первого, свойством β\beta — все кроме второго, , свойством λ\lambda — все кроме последнего, nn-го объекта. Что дает 21 в этом случае?

?
Задача 8.22.1

Доказать задачу I 189 комбинаторным рассуждением (ср. задачу 21 выше и задачу I 192).

?
Задача 8.22.2

Доказать задачу I 208 комбинаторным рассуждением.

?
Задача 8.22.3

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

S~kn=Skn−(n1)Sk−1n−1+(n2)Sk−2n−2−⋯+(−1)nSk−n0. \widetilde{S}_k^n = S_k^n - \binom {n}{1}S_{k-1}^{n-1} + \binom {n}{2}S_{k-2}^{n-2} - \cdots + (-1)^n S_{k-n}^0 .
?
Примечание.
?

Определения см. I, гл. 4, § 3; если условие 1≤k≤n1 \leq k \leq n не выполнено, то SknS_k^n следует считать равным 0.

Задача 8.23

Сколько из n!n! членов в разложении определителя nn-го порядка обращается в нуль, если положить все элементы главной диагонали равными нулю?

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

В другой формулировке, как «jeu de rencontre», у Montmort и A. de Moivre. См. Euler, Opera omnia, серия 1, т. 7, стр. 11, Leipzig und Berlin, B. G. Teubner, 1923.

Задача 8.24

Пусть a,b,c,…,k,la, b, c, \ldots , k, l — взаимно простые целые положительные числа. Сколько из чисел 1,2,3,…,n1,2,3, \ldots , n не делится ни на одно из этих чисел a,b,c,…,k,la, b, c, \ldots , k, l?

?
Задача 8.25

Пусть p,q,r,…p, q, r, \ldots будут различные простые множители числа nn. Число чисел, меньших nn и взаимно простых с ним, равно

n(1−1p)(1−1q)(1−1r)… n\left(1-\frac{1}{p}\right)\left(1-\frac{1}{q}\right)\left(1-\frac{1}{r}\right) \ldots
?
Примечание.
?

Euler.

Задача 8.26

Пусть дано NN произвольных объектов, могущих, как в 21, обладать свойствами α,β,γ,…,ϰ,λ\alpha , \beta , \gamma , \ldots , \varkappa , \lambda. Пусть каждому отдельному объекту приписано некоторое числовое значение. Обозначим через WαW_{\alpha } сумму числовых значений тех объектов, которые обладают свойством α\alpha, через WβW_{\beta } сумму числовых значений объектов со свойством β\beta и т. д. Аналогично будем обозначать через Wαβ,Wαγ,…,Wαβγ,…,Wαβγ…ϰλW_{\alpha \beta }, W_{\alpha \gamma }, \ldots , W_{\alpha \beta \gamma }, \ldots , W_{\alpha \beta \gamma \ldots \varkappa \lambda } сумму числовых значений тех объектов, которые одновременно обладают свойствами α\alpha и β\beta, соотв. α\alpha и γ,…\gamma , \ldots, соотв. α,β\alpha , \beta и γ,…\gamma , \ldots, соотв. α,β,γ,…,ϰ\alpha , \beta , \gamma , \ldots , \varkappa и λ\lambda. Пусть, наконец, WW — сумма числовых значений всех объектов. Тогда сумма числовых значений объектов, не обладающих ни одним из свойств α,β,γ,…,ϰ,λ\alpha , \beta , \gamma , \ldots , \varkappa , \lambda, будет равна

W−Wα−Wβ−Wγ−…−Wϰ−Wλ++Wαβ+Wαγ+…+Wϰλ−−Wαβγ−…+…………±Wαβγ…ϰλ. \begin{aligned} & W-W_{\alpha }-W_{\beta }-W_{\gamma }-\ldots -W_{\varkappa }-W_{\lambda }+ \\ & +W_{\alpha \beta }+W_{\alpha \gamma }+\ldots +W_{\varkappa \lambda }- \\ & -W_{\alpha \beta \gamma }-\ldots + \\ & \ldots \ldots \ldots \ldots \\ & \pm W_{\alpha \beta \gamma \ldots \varkappa \lambda } . \end{aligned}
?
Задача 8.27

Пусть r1,r2,…,rφ(n)r_{1}, r_{2}, \ldots , r_{\varphi (n)} — взаимно простые с nn числа, меньшие, чем nn (n>1n>1). Показать, что

r12+r22+…+rφ(n)2=φ(n)3(n2+(−1)ν2pqr…), r_{1}^{2}+r_{2}^{2}+\ldots +r_{\varphi (n)}^{2}=\frac{\varphi (n)}{3}\left(n^{2}+\frac{(-1)^{\nu }}{2} p q r \ldots \right),

где p,q,r,…p, q, r, \ldots — различные простые множители nn, а ν\nu — их число.

?
Задача 8.27.1

Число N0N_0, искомое в 21, удовлетворяет соотношениям

≤N \leq N ≥N−Nα−Nβ−Nγ−⋯−Nκ−Nλ \geq N - N_\alpha - N_\beta - N_\gamma - \cdots - N_\kappa - N_\lambda ≤N−Nα−Nβ−Nγ−⋯−Nκ−Nλ+Nαβ+Nαγ+⋯+Nκλ. \leq N - N_\alpha - N_\beta - N_\gamma - \cdots - N_\kappa - N_\lambda + N_{\alpha \beta } + N_{\alpha \gamma } + \cdots + N_{\kappa \lambda } . ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots
?
Примечание.
?

Короче говоря, в несколько расширенном смысле этого термина (см. введение к задачам I 140 и I 144), выражение, приведенное в 21, «обвертывает» N0N_0.

Задача 8.27.2

Пусть ll — число свойств, рассматриваемых в 21. Положим

S0=N,S1=Nα+Nβ+Nγ+⋯+Nκ+Nλ,S2=Nαβ+Nαγ+⋯+Nκλ,…,Sl=Nαβγ…κλ, S_0=N, \qquad S_1=N_\alpha +N_\beta +N_\gamma +\cdots +N_\kappa +N_\lambda , \qquad S_2=N_{\alpha \beta }+N_{\alpha \gamma }+\cdots +N_{\kappa \lambda }, \qquad \ldots , \qquad S_l=N_{\alpha \beta \gamma \ldots \kappa \lambda } ,

и пусть sks_k обозначает число тех объектов, которые обладают в точности kk из рассматриваемых ll свойств, 0≤k≤l0 \leq k \leq l. Легко видеть (обнаружить связь с биномиальными коэффициентами), что

S0=s0+s1+s2+s3+⋯+sl, S_0=s_0+s_1+s_2+s_3+\cdots +s_l , S1=s0+s1+2s2+3s3+⋯+lsl, S_1=\phantom{s_0+{}}s_1+2s_2+3s_3+\cdots +ls_l , S2=s0+s1+s2+3s3+⋯+(l2)sl, S_2=\phantom{s_0+s_1+{}}s_2+3s_3+\cdots +\binom {l}{2}s_l , S3=s0+s1+s2+s3+⋯+(l3)sl, S_3=\phantom{s_0+s_1+s_2+{}}s_3+\cdots +\binom {l}{3}s_l , ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots Sl=s0+s1+s2+s3+⋯+sl. S_l=\phantom{s_0+s_1+s_2+s_3+\cdots +{}}s_l .
?