Double comptage
Concept history
A revision trail for this concept page.
Revision 7820
10/26/2026, 11:53:39 AM · SalixBabylonica
Concept reviewed
statusUsableReviewed
Revision 7807
10/26/2026, 10:07:39 AM · Sequoia
Updated title and text
titleDouble-comptageDouble comptage
Compare with revision 78042 changed lines
1
##### Définition intuitive2
3
Un double-comptage est une manière de trouver de jolies relations en combinatoire, simplement par le fait de comprendre un problème sous deux angles différents, et donc de dénombrer un ensemble de deux façons différentes.3
Un double comptage est une manière de trouver de jolies relations en combinatoire, simplement par le fait de comprendre un problème sous deux angles différents, et donc de dénombrer un ensemble de deux façons différentes.4
5
##### Définition formelle6
7
Pour rédiger un double comptage, on peut simplement comprendre un ensemble de deux manières différentes.8
Une autre méthode répandue est de partir d'un couple d'éléments $(x,A)$ qui vérifie une certaine propriété $\mathcal{P}$. Ensuite on se demande combien peut-on choisir de $x$, puis combien de $A$ existent tels que $(x,A)$ vérifie $\mathcal{P}$. On raisonne aussi dans l'autre sens : on compte le nombre de $A$ possibles puis le nombre de $x$ qui vérifient que $(x,A)$ satisfait $\mathcal{P}$.9
10
##### Exemple de rédaction11
12
Considérons l'ensemble des couples $(x,A)$ où $x$ est un entier compris entre $1$ et $n$ et $A$ est une [[sous-ensemble|partie]] de $[\![1,n]\!]$ contenant $k$ éléments, dont $x$, et essayer de voir cet ensemble de deux manières différentes. 13
14
* D'un côté, on peut ainsi fixer $A$, il y a ainsi $\displaystyle\binom{n}{k}$ telles parties, où $\displaystyle \binom{n}{k}$ est le [[coefficient-binomial|coefficient binomial]] "$k$ parmi $n$" du [[triangle-de-pascal|triangle de Pascal]]. Puis $A$ possède $k$ éléments donc on a $k$ possibilités pour $x$ tel que $(x,A)$ vérifie notre condition. Cela nous donne donc $\displaystyle k\binom{n}{k}$ d'un côté.15
16
* De l'autre côté, on peut fixer $x$, il y a donc $n$ possibilités. Puis, pour construire $A$, on a déjà $x$, il nous reste plus qu'à prendre $k-1$ éléments de $[\![1,n]\!] \backslash \{x\}$ (ensemble à $n-1$ éléments), il y a alors $\displaystyle\binom{n-1}{k-1}$ telles parties. Cela nous donne donc $\displaystyle n\binom{n-1}{k-1}$.17
18
19
Finalement on trouve la relation 20
$$21
\displaystyle k\binom{n}{k}=\displaystyle n\binom{n-1}{k-1}22
$$23
en égalisant nos deux comptages !24
25
Bien sûr, on pourrait se dire que cette relation se déduit d'un simple calcul. Ceci dit, la combinatoire a surtout pour but de mieux comprendre le sens des objets, et ainsi cela permet de généraliser plus facilement qu'en trouvant des méthodes calculatoires qui marcheront uniquement pour chaque cas isolé.Revision 7804
10/26/2026, 9:04:40 AM · Ancient Tree
Updated text
Compare with revision 78032 changed lines
1
##### Définition intuitive2
3
Un double-comptage est une manière de trouver de jolies relations en combinatoire, simplement par le fait de comprendre un problème sous deux angles différents, et donc de dénombrer un ensemble de deux façons différentes.4
5
##### Définition formelle6
7
Pour rédiger un double comptage, on peut simplement comprendre un ensemble de deux manières différentes.8
Une autre méthode répandue est de partir d'un couple d'éléments $(x,A)$ qui vérifie une certaine propriété $\mathcal{P}$. Ensuite on se demande combien peut-on choisir de $x$, puis combien de $A$ existent tels que $(x,A)$ vérifie $\mathcal{P}$. On raisonne aussi dans l'autre sens: on compte le nombre de $A$ possibles puis le nombre de $x$ qui vérifient que $(x,A)$ satisfait $\mathcal{P}$.8
Une autre méthode répandue est de partir d'un couple d'éléments $(x,A)$ qui vérifie une certaine propriété $\mathcal{P}$. Ensuite on se demande combien peut-on choisir de $x$, puis combien de $A$ existent tels que $(x,A)$ vérifie $\mathcal{P}$. On raisonne aussi dans l'autre sens : on compte le nombre de $A$ possibles puis le nombre de $x$ qui vérifient que $(x,A)$ satisfait $\mathcal{P}$.9
10
##### Exemple de rédaction11
12
Considérons l'ensemble des couples $(x,A)$ où $x$ est un entier compris entre $1$ et $n$ et $A$ est une [[sous-ensemble|partie]] de $[\![1,n]\!]$ contenant $k$ éléments, dont $x$, et essayer de voir cet ensemble de deux manières différentes. 13
14
* D'un côté, on peut ainsi fixer $A$, il y a ainsi $\displaystyle\binom{n}{k}$ telles parties, où $\displaystyle \binom{n}{k}$ est le [[coefficient-binomial|coefficient binomial]] "$k$ parmi $n$" du [[triangle-de-pascal|triangle de Pascal]]. Puis $A$ possède $k$ éléments donc on a $k$ possibilités pour $x$ tel que $(x,A)$ vérifie notre condition. Cela nous donne donc $\displaystyle k\binom{n}{k}$ d'un côté.15
16
* De l'autre côté, on peut fixer $x$, il y a donc $n$ possibilités. Puis, pour construire $A$, on a déjà $x$, il nous reste plus qu'à prendre $k-1$ éléments de $[\![1,n]\!] \backslash \{x\}$ (ensemble à $n-1$ éléments), il y a alors $\displaystyle\binom{n-1}{k-1}$ telles parties. Cela nous donne donc $\displaystyle n\binom{n-1}{k-1}$.17
18
19
Finalement on trouve la relation 20
$$21
\displaystyle k\binom{n}{k}=\displaystyle n\binom{n-1}{k-1}22
$$23
en égalisant nos deux comptages !24
25
Bien sûr, on pourrait se dire que cette relation se déduit d'un simple calcul. Ceci dit, la combinatoire a surtout pour but de mieux comprendre le sens des objets, et ainsi cela permet de généraliser plus facilement qu'en trouvant des méthodes calculatoires qui marcheront uniquement pour chaque cas isolé.Revision 7803
10/26/2026, 9:04:04 AM · Ancient Tree
Concept marked usable
statusStubUsable
Revision 7802
10/26/2026, 8:55:05 AM · Sequoia
Updated text
Compare with revision 78012 changed lines
1
##### Définition intuitive2
3
Un double-comptage est une manière de trouver de jolies relations en combinatoire, simplement par le fait de comprendre un problème sous deux angles différents, et donc de dénombrer un ensemble de deux façons différentes.4
5
##### Définition formelle6
7
Pour rédiger un double comptage, on peut simplement comprendre un ensemble de deux manières différentes.8
Une autre méthode répandue est de partir d'un couple d'éléments $(x,A)$ qui vérifie une certaine propriété $\mathcal{P}$. Ensuite on se demande combien peut-on choisir de $x$, puis combien de $A$ existent tels que $(x,A)$ vérifie $\mathcal{P}$. On raisonne aussi dans l'autre sens: on compte le nombre de $A$ possibles puis le nombre de $x$ qui vérifient que $(x,A)$ satisfait $\mathcal{P}$.9
10
##### Exemple de rédaction11
12
Considérons l'ensemble des couples $(x,A)$ où $x$ est un entier compris entre $1$ et $n$ et $A$ est une [[sous-ensemble|partie]] de $[\![1,n]\!]$ contenant $k$ éléments, dont $x$, et essayer de voir cet ensemble de deux manières différentes. 13
14
* D'un côté, on peut ainsi fixer $A$, il y a ainsi $\displaystyle\binom{n}{k}$ telles parties. Puis $A$ possède $k$ éléments donc on a $k$ possibilités pour $x$ tel que $(x,A)$ vérifie notre condition. Cela nous donne donc $\displaystyle k\binom{n}{k}$ d'un côté.14
* D'un côté, on peut ainsi fixer $A$, il y a ainsi $\displaystyle\binom{n}{k}$ telles parties, où $\displaystyle \binom{n}{k}$ est le [[coefficient-binomial|coefficient binomial]] "$k$ parmi $n$" du [[triangle-de-pascal|triangle de Pascal]]. Puis $A$ possède $k$ éléments donc on a $k$ possibilités pour $x$ tel que $(x,A)$ vérifie notre condition. Cela nous donne donc $\displaystyle k\binom{n}{k}$ d'un côté.15
16
* De l'autre côté, on peut fixer $x$, il y a donc $n$ possibilités. Puis, pour construire $A$, on a déjà $x$, il nous reste plus qu'à prendre $k-1$ éléments de $[\![1,n]\!] \backslash \{x\}$ (ensemble à $n-1$ éléments), il y a alors $\displaystyle\binom{n-1}{k-1}$ telles parties. Cela nous donne donc $\displaystyle n\binom{n-1}{k-1}$.17
18
19
Finalement on trouve la relation 20
$$21
\displaystyle k\binom{n}{k}=\displaystyle n\binom{n-1}{k-1}22
$$23
en égalisant nos deux comptages !24
25
Bien sûr, on pourrait se dire que cette relation se déduit d'un simple calcul. Ceci dit, la combinatoire a surtout pour but de mieux comprendre le sens des objets, et ainsi cela permet de généraliser plus facilement qu'en trouvant des méthodes calculatoires qui marcheront uniquement pour chaque cas isolé.Revision 7801
10/26/2026, 8:53:38 AM · Sequoia
Updated text
Compare with revision 77994 changed lines
1
##### Définition intuitive2
3
Un double-comptage est une manière de trouver de jolies relations en combinatoire, simplement par le fait de comprendre un problème sous deux angles différents, et donc de dénombrer un ensemble de deux façons différentes.4
5
##### Définition formelle6
7
Pour rédiger un double comptage, on peut simplement comprendre un ensemble de deux manières différentes.8
Une autre méthode répandue est de partir d'un couple d'éléments $(x,A)$ qui vérifie une certaine propriété $\mathcal{P}$. Ensuite on se demande combien peut-on choisir de $x$, puis combien de $A$ existent tels que $(x,A)$ vérifie $\mathcal{P}$. On raisonne aussi dans l'autre sens: on compte le nombre de $A$ possibles puis le nombre de $x$ qui vérifient que $(x,A)$ satisfait $\mathcal{P}$.9
10
##### Exemple de rédaction11
12
Considérons l'ensemble des couples $(x,A)$ où $x$ est un entier compris entre $1$ et $n$ et $A$ est une partie de $[\![1,n]\!]$ contenant $k$ éléments, dont $x$, et essayer de voir cet ensemble de deux manières différentes. 12
Considérons l'ensemble des couples $(x,A)$ où $x$ est un entier compris entre $1$ et $n$ et $A$ est une [[sous-ensemble|partie]] de $[\![1,n]\!]$ contenant $k$ éléments, dont $x$, et essayer de voir cet ensemble de deux manières différentes. 13
14
* D'un côté, on peut ainsi fixer $A$, il y a ainsi $\displaystyle\binom{n}{k}$ telles parties. Puis $A$ possède $k$ éléments donc on a $k$ possibilités pour $x$ tel que $(x,A)$ vérifie notre condition. Cela nous donne donc $\displaystyle k\binom{n}{k}$ d'un côté.15
16
* De l'autre côté, on peut fixer $x$, il y a donc $n$ possibilités. Puis, pour construire $A$, on a déjà $x$, il nous reste plus qu'à prendre $k-1$ éléments de $[\![1,n]\!] \backslash \{x\}$ (ensemble à $n-1$ éléments), il y a alors $\displaystyle\binom{n-1}{k-1}$ telles parties. Cela nous donne donc $\displaystyle n\binom{n-1}{k-1}$.17
18
19
Finalement on trouve la relation 20
$$21
\displaystyle k\binom{n}{k}=\displaystyle n\binom{n-1}{k-1}22
$$23
en égalisant nos deux comptages !23
en égalisant nos deux comptages !24
25
Bien sûr, on pourrait se dire que cette relation se déduit d'un simple calcul. Ceci dit, la combinatoire a surtout pour but de mieux comprendre le sens des objets, et ainsi cela permet de généraliser plus facilement qu'en trouvant des méthodes calculatoires qui marcheront uniquement pour chaque cas isolé.Revision 7799
10/26/2026, 8:52:28 AM · Sequoia
Updated text
Compare with revision 77973 changed lines
1
##### Définition intuitive2
3
Un double-comptage est une manière de trouver de jolies relations en combinatoire, simplement par le fait de comprendre un problème sous deux angles différents, et donc de dénombrer un ensemble de deux façons différentes.4
5
##### Définition formelle6
7
Pour rédiger un double comptage, on part souvent d'un couple d'éléments $(x,A)$ qui vérifie une certaine propriété $\mathcal{P}$. Ensuite on se demande combien peut-on choisir de $x$, puis combien de $A$ existent tels que $(x,A)$ vérifie $\mathcal{P}$. On raisonne aussi dans l'autre sens: on compte le nombre de $A$ possibles puis le nombre de $x$ qui vérifient que $(x,A)$ satisfait $\mathcal{P}$.7
Pour rédiger un double comptage, on peut simplement comprendre un ensemble de deux manières différentes.8
Une autre méthode répandue est de partir d'un couple d'éléments $(x,A)$ qui vérifie une certaine propriété $\mathcal{P}$. Ensuite on se demande combien peut-on choisir de $x$, puis combien de $A$ existent tels que $(x,A)$ vérifie $\mathcal{P}$. On raisonne aussi dans l'autre sens: on compte le nombre de $A$ possibles puis le nombre de $x$ qui vérifient que $(x,A)$ satisfait $\mathcal{P}$.8
9
##### Exemple de rédaction10
11
Considérons l'ensemble des couples $(x,A)$ où $x$ est un entier compris entre $1$ et $n$ et $A$ est une partie de $[\![1,n]\!]$ contenant $k$ éléments, dont $x$, et essayer de voir cet ensemble de deux manières différentes. 12
13
* D'un côté, on peut ainsi fixer $A$, il y a ainsi $\displaystyle\binom{n}{k}$ telles parties. Puis $A$ possède $k$ éléments donc on a $k$ possibilités pour $x$ tel que $(x,A)$ vérifie notre condition. Cela nous donne donc $\displaystyle k\binom{n}{k}$ d'un côté.14
15
* De l'autre côté, on peut fixer $x$, il y a donc $n$ possibilités. Puis, pour construire $A$, on a déjà $x$, il nous reste plus qu'à prendre $k-1$ éléments de $[\![1,n]\!] \backslash \{x\}$ (ensemble à $n-1$ éléments), il y a alors $\displaystyle\binom{n-1}{k-1}$ telles parties. Cela nous donne donc $\displaystyle n\binom{n-1}{k-1}$.16
17
18
Finalement on trouve la relation 19
$$20
\displaystyle k\binom{n}{k}=\displaystyle n\binom{n-1}{k-1}21
$$22
en égalisant nos deux comptages !23
24
Bien sûr, on pourrait se dire que cette relation se déduit d'un simple calcul. Ceci dit, la combinatoire a surtout pour but de mieux comprendre le sens des objets, et ainsi cela permet de généraliser plus facilement qu'en trouvant des méthodes calculatoires qui marcheront uniquement pour chaque cas isolé.Revision 7797
10/26/2026, 8:46:16 AM · Sequoia
Added exercise "Mes premiers doubles-comptages"
linked exercisesNoneMes premiers doubles-comptages
Revision 7796
10/26/2026, 8:43:55 AM · Sequoia
Concept created
##### Définition intuitive
Un double-comptage est une manière de trouver de jolies relations en combinatoire, simplement par le fait de comprendre un problème sous deux angles différents, et donc de dénombrer un ensemble de deux façons différentes.
##### Définition formelle
Pour rédiger un double comptage, on part souvent d'un couple d'éléments $(x,A)$ qui vérifie une certaine propriété $\mathcal{P}$. Ensuite on se demande combien peut-on choisir de $x$, puis combien de $A$ existent tels que $(x,A)$ vérifie $\mathcal{P}$. On raisonne aussi dans l'autre sens: on compte le nombre de $A$ possibles puis le nombre de $x$ qui vérifient que $(x,A)$ satisfait $\mathcal{P}$.
##### Exemple de rédaction
Considérons l'ensemble des couples $(x,A)$ où $x$ est un entier compris entre $1$ et $n$ et $A$ est une partie de $[\![1,n]\!]$ contenant $k$ éléments, dont $x$, et essayer de voir cet ensemble de deux manières différentes.
* D'un côté, on peut ainsi fixer $A$, il y a ainsi $\displaystyle\binom{n}{k}$ telles parties. Puis $A$ possède $k$ éléments donc on a $k$ possibilités pour $x$ tel que $(x,A)$ vérifie notre condition. Cela nous donne donc $\displaystyle k\binom{n}{k}$ d'un côté.
* De l'autre côté, on peut fixer $x$, il y a donc $n$ possibilités. Puis, pour construire $A$, on a déjà $x$, il nous reste plus qu'à prendre $k-1$ éléments de $[\![1,n]\!] \backslash \{x\}$ (ensemble à $n-1$ éléments), il y a alors $\displaystyle\binom{n-1}{k-1}$ telles parties. Cela nous donne donc $\displaystyle n\binom{n-1}{k-1}$.
Finalement on trouve la relation
$$
\displaystyle k\binom{n}{k}=\displaystyle n\binom{n-1}{k-1}
$$
en égalisant nos deux comptages !
Bien sûr, on pourrait se dire que cette relation se déduit d'un simple calcul. Ceci dit, la combinatoire a surtout pour but de mieux comprendre le sens des objets, et ainsi cela permet de généraliser plus facilement qu'en trouvant des méthodes calculatoires qui marcheront uniquement pour chaque cas isolé.