2 files changed, 255 insertions, 0 deletions
diff --git a/semestre 2/maths/4- combinatoire/cours.pdf b/semestre 2/maths/4- combinatoire/cours.pdf
new file mode 100644
index 0000000..1506655
--- /dev/null
+++ b/semestre 2/maths/4- combinatoire/cours.pdf
diff --git a/semestre 2/maths/4- combinatoire/cours.tex b/semestre 2/maths/4- combinatoire/cours.tex
new file mode 100644
index 0000000..4dff382
--- /dev/null
+++ b/semestre 2/maths/4- combinatoire/cours.tex
@@ -0,0 +1,255 @@
+%%=====================================================================================
+%%
+%%       Filename:  cours.tex
+%%
+%%    Description:  
+%%
+%%        Version:  1.0
+%%        Created:  03/06/2024
+%%       Revision:  none
+%%
+%%         Author:  YOUR NAME (), 
+%%   Organization:  
+%%      Copyright:  Copyright (c) 2024, YOUR NAME
+%%
+%%          Notes:  
+%%
+%%=====================================================================================
+\documentclass[a4paper, titlepage]{article}
+
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+\usepackage{textcomp}
+\usepackage[french]{babel}
+\usepackage{amsmath, amssymb}
+\usepackage{amsthm}
+\usepackage[svgnames]{xcolor}
+\usepackage{thmtools}
+\usepackage{lipsum}
+\usepackage{framed}
+\usepackage{parskip}
+\usepackage{titlesec}
+\usepackage{newtxtext}
+
+% \renewcommand{\familydefault}{\sfdefault}
+
+% figure support
+\usepackage{import}
+\usepackage{xifthen}
+\pdfminorversion=7
+\usepackage{pdfpages}
+\usepackage{transparent}
+\newcommand{\incfig}[1]{%
+	\def\svgwidth{\columnwidth}
+	\import{./figures/}{#1.pdf_tex}
+}
+
+\pdfsuppresswarningpagegroup=1
+
+\colorlet{defn-color}{DarkBlue}
+\colorlet{props-color}{Blue}
+\colorlet{warn-color}{Red}
+\colorlet{exemple-color}{Green}
+\colorlet{corol-color}{Orange}
+\newenvironment{defn-leftbar}{%
+  \def\FrameCommand{{\color{defn-color}\vrule width 3pt} \hspace{10pt}}%
+  \MakeFramed {\advance\hsize-\width \FrameRestore}}%
+ {\endMakeFramed}
+\newenvironment{warn-leftbar}{%
+  \def\FrameCommand{{\color{warn-color}\vrule width 3pt} \hspace{10pt}}%
+  \MakeFramed {\advance\hsize-\width \FrameRestore}}%
+ {\endMakeFramed}
+\newenvironment{exemple-leftbar}{%
+  \def\FrameCommand{{\color{exemple-color}\vrule width 3pt} \hspace{10pt}}%
+  \MakeFramed {\advance\hsize-\width \FrameRestore}}%
+ {\endMakeFramed}
+\newenvironment{props-leftbar}{%
+  \def\FrameCommand{{\color{props-color}\vrule width 3pt} \hspace{10pt}}%
+  \MakeFramed {\advance\hsize-\width \FrameRestore}}%
+ {\endMakeFramed}
+\newenvironment{corol-leftbar}{%
+  \def\FrameCommand{{\color{corol-color}\vrule width 3pt} \hspace{10pt}}%
+  \MakeFramed {\advance\hsize-\width \FrameRestore}}%
+ {\endMakeFramed}
+
+\def \freespace {1em}
+\declaretheoremstyle[headfont=\sffamily\bfseries,%
+ notefont=\sffamily\bfseries,%
+ notebraces={}{},%
+ headpunct=,%
+% bodyfont=\sffamily,%
+ headformat=\color{defn-color}Définition~\NUMBER\hfill\NOTE\smallskip\linebreak,%
+ preheadhook=\vspace{\freespace}\begin{defn-leftbar},%
+ postfoothook=\end{defn-leftbar},%
+]{better-defn}
+\declaretheoremstyle[headfont=\sffamily\bfseries,%
+ notefont=\sffamily\bfseries,%
+ notebraces={}{},%
+ headpunct=,%
+% bodyfont=\sffamily,%
+ headformat=\color{warn-color}Attention\hfill\NOTE\smallskip\linebreak,%
+ preheadhook=\vspace{\freespace}\begin{warn-leftbar},%
+ postfoothook=\end{warn-leftbar},%
+]{better-warn}
+\declaretheoremstyle[headfont=\sffamily\bfseries,%
+ notefont=\sffamily\bfseries,%
+notebraces={}{},%
+headpunct=,%
+% bodyfont=\sffamily,%
+ headformat=\color{exemple-color}Exemple~\NUMBER\hfill\NOTE\smallskip\linebreak,%
+ preheadhook=\vspace{\freespace}\begin{exemple-leftbar},%
+ postfoothook=\end{exemple-leftbar},%
+]{better-exemple}
+\declaretheoremstyle[headfont=\sffamily\bfseries,%
+ notefont=\sffamily\bfseries,%
+ notebraces={}{},%
+ headpunct=,%
+% bodyfont=\sffamily,%
+ headformat=\color{props-color}Proposition~\NUMBER\hfill\NOTE\smallskip\linebreak,%
+ preheadhook=\vspace{\freespace}\begin{props-leftbar},%
+ postfoothook=\end{props-leftbar},%
+]{better-props}
+\declaretheoremstyle[headfont=\sffamily\bfseries,%
+ notefont=\sffamily\bfseries,%
+ notebraces={}{},%
+ headpunct=,%
+% bodyfont=\sffamily,%
+ headformat=\color{props-color}Théorème~\NUMBER\hfill\NOTE\smallskip\linebreak,%
+ preheadhook=\vspace{\freespace}\begin{props-leftbar},%
+ postfoothook=\end{props-leftbar},%
+]{better-thm}
+\declaretheoremstyle[headfont=\sffamily\bfseries,%
+ notefont=\sffamily\bfseries,%
+ notebraces={}{},%
+ headpunct=,%
+% bodyfont=\sffamily,%
+ headformat=\color{corol-color}Corollaire~\NUMBER\hfill\NOTE\smallskip\linebreak,%
+ preheadhook=\vspace{\freespace}\begin{corol-leftbar},%
+ postfoothook=\end{corol-leftbar},%
+]{better-corol}
+
+\declaretheorem[style=better-defn]{defn}
+\declaretheorem[style=better-warn]{warn}
+\declaretheorem[style=better-exemple]{exemple}
+\declaretheorem[style=better-corol]{corol}
+\declaretheorem[style=better-props, numberwithin=defn]{props}
+\declaretheorem[style=better-thm, sibling=props]{thm}
+\newtheorem*{lemme}{Lemme}%[subsection]
+%\newtheorem{props}{Propriétés}[defn]
+
+\newenvironment{system}%
+{\left\lbrace\begin{align}}%
+{\end{align}\right.}
+
+\newenvironment{AQT}{{\fontfamily{qbk}\selectfont AQT}}
+
+\usepackage{LobsterTwo}
+\titleformat{\section}{\newpage\LobsterTwo \huge\bfseries}{\thesection.}{1em}{}
+\titleformat{\subsection}{\vspace{2em}\LobsterTwo \Large\bfseries}{\thesubsection.}{1em}{}
+\titleformat{\subsubsection}{\vspace{1em}\LobsterTwo \large\bfseries}{\thesubsubsection.}{1em}{}
+
+\newenvironment{lititle}%
+{\vspace{7mm}\LobsterTwo \large}%
+{\\}
+
+\renewenvironment{proof}{$\square$ \footnotesize\textit{Démonstration.}}{\begin{flushright}$\blacksquare$\end{flushright}}
+
+\title{Combinatoire}
+\author{William Hergès\thanks{Sorbonne Université - Faculté des Sciences, Faculté des Lettres}}
+
+\begin{document}
+	\maketitle
+	\tableofcontents
+	\newpage
+	\section{Notation}
+	Dans cette section, on parle de théorie des ensembles.
+
+	On notera toujours $E$ l'ensemble ambient. Soit $A$ un sous-ensemble de $E$. On le note~: $A\subseteq E$ (ou $A\subset E$, mais on l'aime moins celle-là). On note l'inclusion stricte $A\subsetneq E$.
+	\begin{defn}
+		$A\cup B$ est défini comme~:
+		$$ x\in A\cup B\quad\implies\quad x\in A\quad\lor\quad x\in B $$
+		On a :
+		$$ A\cup B = \{x\in E\quad|\quad x\in A\lor x\in B\} $$
+	\end{defn}
+	\begin{defn}
+		$A\cap B$ est défini comme~:
+		$$ x\in A\cap B\quad\implies\quad x\in A\quad\land\quad x\in B $$
+		On a :
+		$$ A\cup B = \{x\in E\quad|\quad x\in A\land x\in B\} $$
+	\end{defn}
+	\begin{defn}
+		$A\backslash B$ est défini comme~:
+		$$ x\in A\backslash B\quad\implies\quad x\in A\quad\land\quad x\not\in B$$
+		On a~:
+		$$ A\backslash B = \{x\in E\quad|\quad x\in A\land x\not\in B\} $$
+	\end{defn}
+	\begin{defn}
+		$E\backslash A$ est le complémentaire de $A$ et est défini comme~:
+		$$ \forall x\in E\backslash A\quad\implies\quad x\in E\quad\land\quad x\not\in A $$
+		On a~:
+		$$ E\backslash A=\{x\in E\quad|\quad x\not\in A\} $$
+	\end{defn}
+	\begin{defn}
+		Si $E$ est un ensemble fini, on a que $\mathrm{card}(E)$ ou $|E|$ est le nombre d'éléments de $E$.
+	\end{defn}
+	\begin{props}
+		On a :
+		$$ \mathrm{card}(A\cup B) = \mathrm{card}(A) + \mathrm{card}(B) - \mathrm{card}(A\cap B) $$
+	\end{props}
+	\begin{defn}
+		Le produit cartésien est noté $\times$ et est :
+		$$ A\times B = \{(x,y)\quad|\quad x\in A,y\in B\} $$
+	\end{defn}
+	\begin{props}
+		On a~:
+		$$ \mathrm{card}(A\times B) = \mathrm{card}(A)\times\mathrm{card}(B) $$
+	\end{props}
+	\section{Combinaisons}
+	Soit $\Omega=\{1,2,\ldots,n\}$, un ensemble de $n$ éléments.
+
+	\begin{defn}
+		Une combinaison de $k$ éléments parmis les éléments de $\Omega$ est un sous-ensemble $A\subseteq\Omega$ tel que $\mathrm{card}(A) = k$.
+	\end{defn}
+	\begin{props}
+		Le nombre de combinaisons de $k$ éléments parmis les éléments de $\Omega$ est~:
+		$$ \frac{\mathrm{card}(\Omega)!}{k!(\mathrm{card}(\Omega)-k)!} = \frac{n!}{k!(n-k)!} $$
+		pour $n = \mathrm{card}(\Omega)$, i.e.
+		$$ \binom{\mathrm{card}(\Omega)}{k} = \binom nk $$
+		ce qui est un cœfficient binomial.
+	\end{props}
+	On peut aussi écrire le cœfficient binomial $\mathcal{C}^k_n = \binom nk$. $\mathcal{C}$ signifie \textit{combinaison}~! Ici, l'\textit{ordre ne compte pas}.
+
+	Il existe aussi $\mathcal{A}^k_n = \frac{n!}{(n-k)!}$, ce qui est le nombre de choix possible où l'\textit{ordre compte}. $\mathcal{A}$ pour \textit{arrangement}~!
+
+	\begin{exemple}
+		Une personne qui veut aller à un endroit doit forcément faire une combinaison parmis $\{D,D,D,B,B\}$. (Ceci représente tous les chemins les plus rapides pour y aller~: on doit forcément prendre 3 fois droite et deux fois gauche.) Donc, il y a $\binom 52 = 10$ possibilités~: il suffit de choisir quand on descend (donc 2 possibilités) pour avoir tous les cas possibles~! (On aurait aussi pu choisir quand on va à droite, mais les calculs sont plus méchants.)
+	\end{exemple}
+
+	\begin{props}
+		On a~:
+		$$ \mathcal{C}^k_n = \mathcal{C}^{k-1}_{n-1} + \mathcal{C}^k_{n-1} $$
+		i.e.
+		$$ \binom nk = \binom{k-1}{n-1}+\binom k{n-1} $$
+	\end{props}
+
+	Maintenant, voici un énoncé très pratique~: le \textit{binôme de Newton}. Le prof l'a démontré en cours, mais j'avais la flemme d'écrire la démo. Voir la démonstration de l'année dernière.
+
+	\begin{thm}[Binôme de Newton]
+		On a~:
+		$$ (x+y)^n = \sum_{k=0}^{n} \binom nk x^ky^{n-k} $$
+	\end{thm}
+
+	\begin{corol}
+		On a cette magnifique relation pas très utile~:
+		$$ \sum^n_{k=0}\binom nk = 2^n $$	
+	\end{corol}
+	\begin{proof}
+		D'après le binôme de Newton, on a~:
+		$$ (1+1)^n = \sum_{k=0}^{n} \binom nk 1^k1^{n-k} $$
+		i.e.
+		$$ 2^n = \sum_{k=0}^{n} \binom nk $$
+	\end{proof}
+	\begin{exemple}
+	Dans un groupe de 20 personnes, il y a $2^{20}$ sous-groupes possibles. Il y a $20$ tailles de sous-groupes possibles~: de 1 à 20. Le nombre de sous-groupe contenant personne est $\binom{20}0$, celui contenant une personne est $\binom{20}1$, \ldots, celui contenant 20 personnes est $\binom{20}{20}$. Ainsi, le nombre de sous-groupe est la somme de tout cela et le résultat est donné par la formule juste au dessus.
+	\end{exemple}
+\end{document}