Ivan Shishkin, Rye (1878)

Problems/Combinatorics

Démonstration de la formule du crible à l’aide des fonctions indicatrices

by T.W·
33
Difficulty scaleÉchelle de difficulté

This score reflects both the level of the required concepts and the difficulty of the solution.Ce score tient compte à la fois du niveau des notions nécessaires et de la difficulté de la résolution.

  1. 1–10First steps / middle schoolPremiers pas / collège
  2. 11–25Beginner / high schoolDébutant / lycée
  3. 26–50Intermediate / undergraduateIntermédiaire / licence
  4. 51–70Advanced / graduateAvancé / master
  5. 71–90Expert / specializedExpert / spécialisé
  6. 91–100Research levelNiveau recherche
These levels are approximate guides.Ces niveaux sont des repères approximatifs.
·
ReviewedReviewed by darktoaster
·
Français
FrançaisAdd translation

Showing the Français version because no English translation exists yet. Add that translation.

Soient AA et BB tels que A⊂BA \subset B. On appelle l'indicatrice de AA sur BB la fonction 1A:B⟶{0,1}\mathbb{1}_{A} : B \longrightarrow \{0,1\} telle que

∀x∈B,1A(x)={1si x∈A,0si x∉A.\forall x \in B,\quad \mathbb{1}_A(x)= \begin{cases} 1 & \text{si } x\in A,\\ 0 & \text{si } x\notin A. \end{cases}

  1. Soit EE un ensemble de cardinal fini et soient A1,...,AnA_{1}, ..., A_{n} tels que A1∪...∪An⊂EA_1 \cup ... \cup A_{n} \subset E. On prend comme ensemble de définition de 1Ai1_{A_{i}} l’ensemble EE pour tout i∈[ ⁣[1,n] ⁣]i \in [\![1,n]\!].

Montrer les propriétés suivantes :

i) ∀i∈⟦1,n⟧\forall i \in \llbracket 1,n\rrbracket, 1Ai=1−1Ai‾1_{A_{i}} = 1 - 1_{\overline{A_{i}}}

ii) ∀i,j∈⟦1,n⟧\forall i, j \in \llbracket 1,n\rrbracket, 1Ai∩Aj=1Ai×1Aj1_{A_{i}\cap A_{j}} = 1_{A_{i}} \times 1_{A_{j}}

iii) ∀k∈⟦1,n⟧\forall k \in \llbracket 1,n\rrbracket, 1A1‾∩...∩Ak‾=∏i=1k(1−1Ai)1_{\overline{A_1}\cap ... \cap \overline{A_k}} = \displaystyle \prod_{i=1}^{k}(1-1_{A_{i}})

iv) ∀i∈⟦1,n⟧,∑x∈E1Ai(x)=card(Ai)\forall i \in \llbracket 1,n\rrbracket, \displaystyle \sum_ {x \in E} 1_{A_{i}}(x) = \mathrm{card} (A_i)

  1. À l’aide des propriétés de la question 1, démontrer la formule :

∣⋃i=1nAi∣=∑k=1n(−1)k+1∑I⊆⟦1,n⟧,∣I∣=k∣⋂i∈IAi∣\left|\bigcup_{i=1}^{n}A_i\right|=\sum_{k=1}^{n}(-1)^{k+1}\displaystyle\sum_{\substack{I\subseteq\llbracket 1,n\rrbracket,|I|=k}}\left|\bigcap_{i\in I}A_i\right|.

I solved itMark it doneAdd to my listKeep it in your list
I like this problem1 like

Liked by

Show related problems0

No related problems yet.

Solutions

1
Reveal solutionsAre you sure? Give it a try first.

Solution by darktoaster

Discussions0 useful votes

Question 1 : Quelques propriétés de l’indicatrice

\newline

Propriété i)

\newline
Soit i∈[ ⁣[1,n] ⁣]i \in [\![1,n]\!], montrons que 1Ai=1−1Ai‾\mathbb{1}_{A_{i}} = 1 - \mathbb{1}_{\overline{ A_{i}}}
Soit x∈Ex \in E, montrons 1Ai(x)=1−1Ai‾(x)\mathbb{1}_{A_{i}}(x) = 1 - \mathbb{1}_{\overline{ A_{i}}}(x)

Si x∈Aix \in A_{i}, alors 1Ai(x)=1\mathbb{1}_{A_{i}} (x) = 1, de plus x∉Ai‾x \not\in \overline{A_{i}}, ainsi 1Ai‾(x)=0\mathbb{1}_{\overline{A_{i}}}(x) = 0
nous avons bien 1Ai(x)=1−1Ai‾(x)\mathbb{1}_{A_{i}}(x) = 1 - \mathbb{1}_{\overline{ A_{i}}}(x) , en effet 1=1−01 = 1 - 0

Si x∈Aix \in A_{i}, alors 1Ai(x)=0\mathbb{1}_{A_{i}} (x) = 0, de plus x∈Ai‾x \in \overline{A_{i}}, ainsi 1Ai‾(x)=1\mathbb{1}_{\overline{A_{i}}}(x) = 1
nous avons également 1Ai(x)=1−1Ai‾(x)\mathbb{1}_{A_{i}}(x) = 1 - \mathbb{1}_{\overline{ A_{i}}}(x) , en effet 0=1−10 = 1 - 1
\newline

Propriété ii)

\newline
Soient i,j∈[ ⁣[1,n] ⁣]i,j \in [\![1,n]\!], montrons que 1Ai∩Aj=1Ai⋅1Aj\mathbb{1}_{A_{i} \cap A_{j}} = \mathbb{1}_{ A_{i}} \cdot \mathbb{1}_{A_{j}}
Soit x∈Ex \in E, montrons 1Ai∩Aj(x)=1Ai(x)⋅1Aj(x)\mathbb{1}_{A_{i} \cap A_{j}}(x) = \mathbb{1}_{ A_{i}} (x) \cdot \mathbb{1}_{A_{j}}(x)

Si x∈Ai∩Ajx \in A_{i}\cap A_{j}, alors 1Ai∩Aj(x)=1\mathbb{1}_{A_{i}\cap A_{j}} (x) = 1, de plus x∈Aix \in A_{i} et x∈Ajx \in A_{j}, ainsi 1Ai(x)=1\mathbb{1}_{A_{i}}(x) = 1 et 1Aj(x)=1\mathbb{1}_{A_{j}}(x) = 1
nous avons bien 1Ai∩Aj(x)=1Ai(x)⋅1Aj(x)\mathbb{1}_{A_{i} \cap A_{j}}(x) = \mathbb{1}_{ A_{i}} (x) \cdot \mathbb{1}_{A_{j}}(x) , en effet 1=1⋅11 = 1 \cdot 1

Si x∉Ai∩Ajx \not\in A_{i}\cap A_{j}, alors 1Ai∩Aj(x)=0\mathbb{1}_{A_{i}\cap A_{j}} (x) = 0, de plus x∉Aix \not\in A_{i} ou x∉Ajx \not\in A_{j} , ainsi 1Ai(x)=0\mathbb{1}_{A_{i}}(x) = 0 ou 1Aj(x)=0\mathbb{1}_{A_{j}}(x) = 0
nous avons également 1Ai∩Aj(x)=1Ai(x)⋅1Aj(x)\mathbb{1}_{A_{i} \cap A_{j}}(x) = \mathbb{1}_{ A_{i}} (x) \cdot \mathbb{1}_{A_{j}}(x) via la règle du produit nul

\newline

Propriété iii)

\newline
On généralise la propriété ii) par récurrence et on utilise la propriété i)
\newline

Propriété iv)

\newline
∀i∈[ ⁣[1,n] ⁣],∑x∈E1Ai(x)=∑x∈Ai1=card(Ai)\forall i \in [\![1,n]\!], \sum\limits_{x \in E} \mathbb{1}_{A_{i}}(x) = \sum\limits_{x \in A_{i}} 1 = \mathrm{card}(A_{i})
On enlève les éléments de EE n’étant pas dans AiA_{i} puis on compte 11 par 11 les éléments de AiA_{i}
\newline

Question 2 : Démonstration de la formule du crible

On commence par utiliser les différentes propriétés de l’indicatrice démontrées précédemment et les lois de de Morgan pour récrire notre cardinal :
\newline
∣⋃i=1nAi∣\left| \bigcup\limits_{i = 1}^{n} A_{i}\right| =∑x∈E1⋃i=1nAi(x)= \sum\limits_{x\in E} \mathbb{1}_{\bigcup\limits_{i = 1}^{n} A_{i}}(x) =∑x∈E1−1⋃i=1nAi‾(x)= \sum\limits_{x\in E} 1 - \mathbb{1}_{\overline{\bigcup\limits_{i = 1}^{n} A_{i}}}(x) =∑x∈E1−1⋂i=1nAi‾(x)= \sum\limits_{x\in E} 1 - \mathbb{1}_{\bigcap\limits_{i = 1}^{n} \overline{A_{i}}}(x) =∑x∈E1−∏i=1n1Ai‾(x)= \sum\limits_{x\in E} 1 - \prod\limits_{i = 1}^{n}\mathbb{1}_{ \overline{A_{i}}}(x) =∑x∈E1−∏i=1n(1−1Ai(x))= \sum\limits_{x\in E} 1 - \prod\limits_{i = 1}^{n} ( 1 - \mathbb{1}_{ A_{i}}(x))
\newline
Ensuite, passage délicat, on va développer le produit :
∣⋃i=1nAi∣\left| \bigcup\limits_{i = 1}^{n} A_{i}\right|=∑x∈E1−∑k=0n∑I⊂[[1,n]]∣I∣=k∏i∈I(−1Ai(x))= \sum\limits_{x \in E} 1 - \sum\limits_{k=0}^{n} \sum\limits_{ \scriptsize{ \begin{matrix} I \subset [\![1,n]\!] \\ |I| = k \end{matrix}} } \prod\limits_{i \in I} (-\mathbb{1}_{A_{i}}(x))

  • Lorsque l’on développe, soit on prend 00 indicatrice, soit 11, ..., soit nn, d’où la somme ∑k=0n\sum\limits_{k = 0}^{n}
  • Ensuite, en fixant le nombre d’indicatrices sélectionnées, par exemple k=1k=1, les termes sont −1A1-\mathbb{1}_{A_{1}}, ..., −1An-\mathbb{1}_{A_{n}} . Pour k=2k=2 : (−1A1)⋅(−1A2)(-\mathbb{1}_{A_{1}} ) \cdot (-\mathbb{1}_{A_{2}}) , ..., (−1A1)⋅(−1An)(-\mathbb{1}_{A_{1}} ) \cdot (-\mathbb{1}_{A_{n}}) ,..., d’où ∑I⊂[[1,n]]∣I∣=k∏i∈I\sum\limits_{ \scriptsize{ \begin{matrix} I \subset [\![1,n]\!] \\ |I| = k \end{matrix}} } \prod\limits_{i \in I}
    \newline
    On peut réaranger l’expression
    ∣⋃i=1nAi∣\left| \bigcup\limits_{i = 1}^{n} A_{i}\right|
    =∑x∈E1−∑k=0n∑I⊂[[1,n]]∣I∣=k(−1)k∏i∈I1Ai(x)= \sum\limits_{x \in E} 1 - \sum\limits_{k=0}^{n} \sum\limits_{ \scriptsize{ \begin{matrix} I \subset [\![1,n]\!] \\ |I| = k \end{matrix}} } (-1)^{k}\prod\limits_{i \in I} \mathbb{1}_{A_{i}}(x)
    =∑x∈E1−∑k=0n∑I⊂[[1,n]]∣I∣=k(−1)k1⋂i∈IAi(x)= \sum\limits_{x \in E} 1 - \sum\limits_{k=0}^{n} \sum\limits_{ \scriptsize{ \begin{matrix} I \subset [\![1,n]\!] \\ |I| = k \end{matrix}} } (-1)^{k} \mathbb{1}_{\bigcap\limits_{i \in I} A_{i}}(x)
    =∑x∈E1+∑k=0n(−1)k+1∑I⊂[[1,n]]∣I∣=k1⋂i∈IAi(x)= \sum\limits_{x \in E} 1 + \sum\limits_{k=0}^{n} (-1)^{k+1} \sum\limits_{ \scriptsize{ \begin{matrix} I \subset [\![1,n]\!] \\ |I| = k \end{matrix}} } \mathbb{1}_{\bigcap\limits_{i \in I} A_{i}}(x)
    =∑x∈E∑k=1n(−1)k+1∑I⊂[[1,n]]∣I∣=k1⋂i∈IAi(x)= \sum\limits_{x \in E} \sum\limits_{k=1}^{n} (-1)^{k+1} \sum\limits_{ \scriptsize{ \begin{matrix} I \subset [\![1,n]\!] \\ |I| = k \end{matrix}} } \mathbb{1}_{\bigcap\limits_{i \in I} A_{i}}(x)
    \newline
    On conclut :
    ∣⋃i=1nAi∣\left| \bigcup\limits_{i = 1}^{n} A_{i}\right|=∑k=1n(−1)k+1∑I⊂[[1,n]]∣I∣=k∣⋂i∈IAi∣= \sum\limits_{k=1}^{n} (-1)^{k+1} \sum\limits_{ \scriptsize{ \begin{matrix} I \subset [\![1,n]\!] \\ |I| = k \end{matrix}} } \left| \bigcap\limits_{i \in I} A_{i}\right|
Report

For an unclear, ambiguous, or possibly incorrect statement, please use the Discussion tab on the right. Report content that needs moderator intervention, such as dangerous, clearly non-mathematical, or plagiarized content.