From c49b969659d8761442a560f8feda436bfb7b01e8 Mon Sep 17 00:00:00 2001 From: Anhgelus Morhtuuzh Date: Thu, 27 Mar 2025 17:24:15 +0100 Subject: Ajout des cours du 10 au 27 mars --- semestre 2/maths/4- combinatoire/cours.pdf | Bin 0 -> 276010 bytes semestre 2/maths/4- combinatoire/cours.tex | 255 +++++++++++++++++++++++++++++ 2 files changed, 255 insertions(+) create mode 100644 semestre 2/maths/4- combinatoire/cours.pdf create mode 100644 semestre 2/maths/4- combinatoire/cours.tex (limited to 'semestre 2/maths/4- combinatoire') 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 Binary files /dev/null and b/semestre 2/maths/4- combinatoire/cours.pdf differ 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} -- cgit v1.2.3