Notation coefficients binomiaux
Bonjour,
de mon temps le coefficient binomial était noté $C_n^p$ et le nombre de $p$-listes d'un ensemble à $n$ éléments $A_n^p$.
Actuellement, on utilise pour les coefficients binomiaux la notation $\binom{n}{p}$.
Y a-t-il une notation "standard" pour le nombre de $p$-listes ?
Bonne journée.
F.
de mon temps le coefficient binomial était noté $C_n^p$ et le nombre de $p$-listes d'un ensemble à $n$ éléments $A_n^p$.
Actuellement, on utilise pour les coefficients binomiaux la notation $\binom{n}{p}$.
Y a-t-il une notation "standard" pour le nombre de $p$-listes ?
Bonne journée.
F.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Je ne connais pas d'autre notation pour le nombre d'arrangements de n objets p à p.
Cordialement.
possible....une $p$-liste peut contenir plusieurs fois le même élément, mais pas un p-arrangement, c'est ça ?
Bonne soirée
F.
"Euh ... sur une liste de commissions, il n'y a pas deux fois le même produit" Sur les miennes, si ! Quand elle devient longue, ça arrive de marquer 2 fois "pain".
Cordialement.
pas d'ordre et pas répétition --> combinaison --> $C_n^p$
ordre et pas répétition --> arrangement --> $A_n^p$
ordre et répétition --> p-liste --> $L_n^p$ (inusité)
Je crois que la notation verticale de la combinaison est la notation anglaise. Effectivement, elle se propage. Personnellement, je préfère le bon vieux "C". Beaucoup plus explicite que cette fausse matrice.
Cette notation anglaise est une horreur.
-- Schnoebelen, Philippe
Pourquoi a-t-on (un 'on' qui ne vise personne et tout le monde à la fois, moi y compris) laissé se développer la notation anglophone ?
A priori, elle est plus compliquée à former que la notation $C_n^p$ et n'a pas le bon goût de pouvoir s'écrire en notation fonctionnelle comme $C(n, p)$ sans ambiguïté.
A bientôt.
Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
J'ai peine à y voir un anglicisme: Alain Comtet utilisait déjà les $\binom{n}{p}$ dans les années 1970.
Pour moi, les $C_n^p$ et les $A_n^p$ sont surtout liés à une période de l'enseignement secondaire où on prétendait être capable d'enseigner le dénombrement, chose dont j'ai toujours douté.
-- Schnoebelen, Philippe
Si on sort des cas bien encadrés par des théorèmes, une preuve de dénombrement écrite en langage naturel revient le plus souvent, si on la formalise, à exhiber une application d'un ensemble produit vers l'ensemble que l'on veut dénombrer, les caractères injectif et surjectif étant considérés comme allant de soi.
Dans ces circonstances, un élève n'a aucune procédure pour faire la différence entre une "preuve" juste et une "preuve" fausse. Certains élèves vont naturellement produire des "preuves" justes, d'autres non, sans que l'enseignant ait vraiment de poids là-dessus; il pourra juste face à une "preuve" fausse la démonter en exhibant le défaut d'injectivité (fréquent) ou de surjectivité (plus rare).
A contrario, une preuve formelle, qui exhibe des bijections et les démontre va souvent être considérée comme lourde, comme une complication inutile qui embrouille.
La pratique du dénombrement est un équilibre subtil entre intuition et formalisme; on n'est pas égaux là-dessus. Tu parlais de géométrie et d'arithmétique, il y a là aussi une part d'intuition, mais au moins le cadre hypothético-déductif est suffisamment solide pour faire la différence entre une preuve correcte et une preuve fausse, même pour quelqu'un qui n'a pas su produire la preuve.
Sur ce forum, nous avons parlé abondamment de ces questions de notations. Qui pourra exhumer les fils de discussion naguère consacrés à cette question ?
La notation anglo-saxonne $\binom{n}{p}$ est à l'évidence « as bad as possible » (*) puisqu'elle présente une confusion avec un vecteur de $\mathbb R^2$. Mais nous avons capitulé encore une fois devant la force brute du suzerain occidental. Les anciennes notations $C_n^p$ et $A_n^p$ sont bien meilleures et c'est une très bonne idée de PetitLutinMalicieux de leur adjoindre $L_n^p$, à quoi on pourrait ajouter le quatrième de ses cas, pas d'ordre et répétition, qui donne les combinaisons avec répétitions, jadis notées $\Gamma_n^p$ ou $K_n^p$.
J'ai raconté que j'avais eu l'idée d'organiser mon cours de prépa-HEC en définissant $C_n^p$ comme coefficient binomial, la formule $\displaystyle (1+x)^{n}=\underset{k=0}{\overset{n}{\sum }}C_{n}^{k}x^{k}$ étant une définition de $C_n^p$. Les propriétés de $C_n^p$ en découlent, y compris l'expression de ce nombre comme
$C_{n}^{p}=\frac{n(n-1)...(n-p+1)}{p!}$, qui est à mon avis la bonne pour ce nombre. Je définissais par ailleurs ensuite $\binom{n}{p}$ comme le nombre de $p$-parties d'un $n$-ensemble, et l'égalité $C_n^p= \binom{n}{p}$ était un théorème. J'ai déjà raconté tout ça, mais c'est enfoui dans les sables du million et quelques de messages du forum.
Cela dit, on ne peut bien sûr revenir sur la notation $\binom{n}{p}$. Ce n'est pas la seule notation anglo-saxonne que nous avons été contraints d'adopter. Il y a aussi $\ln$, $\tan$, $\sinh$ et autres hyperboliques. C'est comme ça.
Bonne journée.
Fr. Ch.
[small](*) Aussi mauvaise que possible.[/small]
D'ailleurs, Chaurien, pour illustrer les dangers des raisonnements imprécis, je me souviens qu'il y avait une erreur dans le corrigé du problème de concours général sur les coloriages du tétraèdre écrit par tes compères Ferréol et Casiro.
Ce n'est plus le cas aujourd'hui et le programme de Term ne fait pas mention de ces notions qu'on n'a de toutes façons pas le temps de présenter donc on cuisine.
Je viens de terminer ce chapitre, les élèves qui s'en sortent sont ceux qui voient naturellement les partitions mais, faute de pratique ensembliste, la mise en forme s'apparente plus à de la poésie qu'à des maths.
Exemple tout bête dans ma feuille de TD : Soit $n\geq 2$ un entier et $L$ un alphabet à $n$ lettres.
Combien de mots de $4$ lettres avec $2$ lettres doublées peut-on former ?
Rédaction ?
@gai requin : ton énoncé n'est pas très clair, mais en admettant que le mot aaab convient, je rédigerais ainsi :
On peut former en tout $n\times n\times n\times n = n^4$ mots avec lettres doublées ou non. Cherchons le nombre de mots sans lettres doublées. Si $x_1x_2x_3x_4$ est un tel mot, alors on a $n$ choix pour $x_1$, $n-1$ choix pour $x_2$ (puisque $x_2$ est une lettre quelconque autre que $x_1$), $n-1$ choix pour $x_3$ et $n-1$ choix pour $x_4$, donc $n(n-1)^3$ mots.
Par conséquent le nombre de mots avec lettres doublées est $n^4-n(n-1)^3$.
"Deux lettres doublées" signifie que le mot contient deux fois une lettre $l$ et deux fois une autre lettre $m$.
Soit $A$ l'ensemble des tels mots.
Pour $\{l,m\}\subset L$, on note $A_{\{l,m\}}$ le sous-ensemble de $A$ des mots contenant les lettres $l,m$.
On a $\mathrm{card} A_{\{l,m\}}=\binom{4}{2}=6$.
De plus, les $A_{\{l,m\}}$ sont deux à deux disjoints et $A=\bigcup\limits_{\{l,m\}\subset L}A_{\{l,m\}}$.
D'après le principe additif, $\mathrm{card} A=6\times\mathrm{card}\{\{l,m\}\subset L\}=6\times\binom{n}{2}=3n(n-1)$.
Que pense aléa des deux dénombrements proposés ?
Soit maintenant $p$ un entier tel que $4\leq p\leq n+2$.
Combien de mots de $p$ lettres contenant exactement deux lettres doublées non triplées peut-on former ?
C'est une ébauche de preuve, mais ce n'est pas une preuve, quoique les assertions avancées soient justes.
Ca peut servir d'introduction à la preuve de gai requin, quoique j'aurais été plus précis encore que lui car je n'aurais pas écris directement la multiplication mais plutôt constaté que j'avais une somme de nombres égaux.
"@aléa : Oui, mais quand on l'enseignait en TC, les élèves avaient l'habitude des ensembles, des bijections ... depuis la 6ème."
Je pense que c'est un peu idéalisé.
Les ensembles et bijections étaient beaucoup travaillés en 6e, 5e, moins après.
Les très bons élèves (moi) s'en souvenaient, les autres non, et le travail sur le dénombrement ne s'appuyait pas vraiment dessus, mais plutôt sur la reconnaissance de situations connues, et de recettes de cuisine plus ou moins caricaturales (par exemple: si l'ordre est important, on met Anp, sinon Cnp)
Soit $1\leq p\leq n$ des entiers.
Ecrire $\sum\limits_{k=p}^n\binom{k-1}{p-1}$ à l'aide d'une seule combinaison, en utilisant si possible un raisonnement combinatoire.
On choisit 2 lettres parmi n, indépendamment de l'ordre (les mots avec "l" et "m" sont les mêmes que les mots avec "m" et "l") et sans répétition ("m" est une "autre lettre" que "l" selon l'énoncé). C'est donc une combinaison.
Pour chaque couple de lettres précédemment choisies, on tire 2 places dans le mot parmi 4, indépendamment de l'ordre ("l" en première et 3ème place donne le même mot que "l" en 3ème et 1ère place) et sans répétition (on ne sélectionne pas deux fois la même place dans le mot). C'est donc une combinaison.
La quantité de possibilités est donc $C_n^2C_4^2=\frac{n(n-1)}{2}\frac{4\times 3}{2}=3n(n-1)$.
À noter : Si on avait les lettres par paire, sans dire que $m\neq l$, on aurait eu un tirage sans ordre mais avec répétition. Comme quoi, ce tirage arrive aussi. Merci Chaurien pour la notation $\Gamma_n^p=K_n^p$ que je ne connaissais pas. (ou que j'avais oubliée).
Pour le deuxième exercice de gai requin : je choisis déjà une paire de lettres distinctes, ce sont celles qui sont doublées. J'ai $n(n-1)/2$ choix. Je choisis deux emplacements pour la lettre qui vient en premier dans l'alphabet : $p(p-1)/2$ choix. Je choisis deux emplacements pour l'autre lettre : $(p-2)(p-3)/2$ choix. Sur les $p-4$ emplacements restants je dois mettre $p-4$ lettres distinctes, toutes différentes des deux premières. Cela donne $(n-2)(n-3)\cdots(n-p+3)$ choix. En multipliant tous ces nombres, j'obtiens $[n(n-1)\cdots (n-p+3)]\times p(p-1)(p-2)(p-3)/8$ choix.
Pour le troisième exercice, j'obtiens $\binom{n}{p}$. En effet, choisir $x_1<\cdots<x_p$ dans l'intervalle $\{1,\ldots,n\}$ revient à choisir $k=x_p$, puis $p-1$ nombres dans $\{1,2,\ldots,k-1\}$.
Une autre démonstration consiste à utiliser la formule de Pascal et on obtient une somme télescopique.
ln, tan, sinh, ça passe encore (surtout que tg, pour les élèves, est l’abréviation de… :-D)
Mais pour celle des coefficients binomiaux, ben on peut faire de la résistance et continuer à utiliser l’ancienne.
-- Schnoebelen, Philippe
On a $\mathrm{card}A_{(c,\{l,m\})}=\dfrac{p!}{2!\times 2!}$ (cf anagrammes).
De plus, il y a $\binom{n}{p-2}\times\binom{p-2}{2}$ tels couples $(c,\{l,m\})$.
Donc il y a $\binom{n}{p-2}\times\binom{p-2}{2}\times\dfrac{p!}{2!\times 2!}$ mots cherchés.
Pour les autres, lire des solutions informelles ne les fait pas progresser, j'en suis convaincu, c'est pourquoi je pense qu'un enseignement de dénombrement à un large public qui n'a pas accès au formalisme doit avoir des prétentions modestes.
Dans l'idéal, on aurait le temps...
-Soit $G$ un groupe fini agissant sur un ensemble fini $X$. Alors pour tout $x\in X$, $\card \{y\mid \exists g\in G, y = gx\} = \frac{\card(G)}{\card(\stab(x))}$ avec $\stab(x) := \{g\in G \mid g x = x\}$ (i.e. le "stabilisateur" de $x$; résultat à la base de l'équation aux classes).
Ce résultat est un résultat de dénombrement en fait.
Les raisonnements incluant $n!=\card (\mathfrak S_n)$ y font souvent implicitement référence (on ne parle pas d'autre chose quand on dit qu'on "peut diviser par $k!$ puisque l'ordre de ces $k$ objets ne compte pas").
Exemples.
1°) Soient $L$ un ensemble totalement ordonné, $a,b\in L$ tels que $a<b$, et $E_{a,b}:= \left \{f\in \{a,b\}^4 \mid \card \left (f^{-1} \left (\{a\} \right) \right )= 2 \right\}$. Alors $\mathfrak S_4$ agit transitivement sur $E_{a,b}$ via $\sigma, f \mapsto f \circ \sigma$ et l'application (i.e. le quadruplet) $(a,a,b,b)$ admet pour stabilisateur un ensemble à $4$ éléments identifié à $\mathfrak S_2 \times \mathfrak S_2$.
Par suite $\card (E_{a,b})= \frac{4!}{4} = 6$.
Si $L$ est fini de \cardinal $n$, il y a $\frac{n(n-1)} 2$ couples d'éléments de $L$ de la forme $(a,b)$ avec $a<b$ (identifiables des parties à $2$ éléments de $L$).
On en déduit $\card \left (\bigcup_{a,b\in L, a<b} E_{a,b}\right)=3n(n-1)$
2°) Soient $n,d$ deux entiers naturels.
On fait à nouveau agir $\mathfrak S_n$ sur $\{1,\ldots,d\}^{\{1,\ldots,n\}}$ par composition à droite i.e. $\sigma,f \mapsto f \circ \sigma$. Alors pour toutes fonctions $f,g$ de $\{1,\ldots,n\}$ dans $\{1,\ldots,d\}$, il existe $\sigma \in \mathfrak S_n$ tel que $f\circ \sigma = g$ si et seulement si pour tout $i\in \{1,\ldots,d\}$, $f^{-1} \left ( \{i\}\right ) = g^{-1} \left ( \{i\}\right )$.
Soient $m_1,\ldots,m_d$ des entiers naturels dont la somme vaut $n$. On pose $F_{m_1,\ldots,m_d}:= \left \{f \in \{1,\ldots,d\}^{\{1,\ldots,n\}}\big | \forall k \in \{1,\ldots,d\},f^{-1} \left ( \{k\}\right ) =m_k \right \}$.
Le stabilisateur d'un élément $f$ de $F_{m_1,\ldots,m_d}$ s'identifie au produit des ensembles de permutations de $f^{-1}\left ( \{i\}\right )$ lorsque $i$ parcourt $\{1,\ldots,d\}$ et donc est de cardinal égal à $\prod_{i=1}^d m_i!$.
Par suite $$ \binom{n}{m_1,\ldots,m_d} := \card \left (F_{m_1,\ldots,m_d} \right)= \frac{n!}{\prod_{i=1}^d m_i !} \tag{1}
$$On note ci-dessous $\Phi := \{1,\ldots,d\}^{\{1,\ldots,n\}}$
Soient $A$ un anneau commutatif et $a_1,\ldots,a_d\in A$. Alors par distributivité de la multiplication sur l'addition, $(\sum_{i=1}^d a_i)^n = \sum_{f \in \Phi} \prod_{j=1}^n a_{f(j)}$. Mais $\left (F_{m_1,\ldots,m_d}\right)_{m \in \N^d, m_1+\cdots+m_d = n}$ est une partition de $\Phi$ et d'autre part pour tout $m\in \N^d$ dont la somme vaut $n$, $f\mapsto \prod a_{f(j)}$ est constante sur $F_{m_1,\ldots,m_d}$ et de valeur $\prod_{i=1}^d a_i^{m_i}$ d'où, avec les notations de $(1)$, la fameuse formule dite "du multinôme" : $$(a_1+\cdots+a_d)^n = \sum_{m_1+\cdots+m_d = n} \binom {n}{m_1,...,m_d} \prod_{i=1}^d a_i ^{m_i} \tag{2}
$$ Une autre conséquence de ce que les $m\mapsto F_{m_1...m_d} $ forment une partition de $\Phi$ est bien sûr l'égalité $$d^n = \sum_{m_1+\cdots+m_d = n} \binom n {m_1,...,m_d} \tag 3
$$Ces résultats sont amplement vulgarisés dans le cas particulier où $d=2$ cependant le cas où $d$ est quelconque ne pose pas de difficultés supplémentaires à mon avis avec le bon point de vue en tout cas (seules les notations s'alourdissent).
Ils découvrent souvent ce lien en 1ère année après le bac...
Quant à la notation, j'aime bien la notation $\binom{n}{p}$, parce qu'elle s'adapte à plein d'autres domaines que le dénombrement,e n particulier dans le cadre des séries entières : \[\forall x\in ]-1,1[, (1+x)^{\alpha}=\sum_{k=0}^{+\infty} \binom{\alpha}{k} x^k\] ou encore pour définir les polynômes $P_k = \binom{X}{k}$ pour $k\in\N$.
Je ne vois pas pourquoi on ne pourrait pas utiliser $\C_X^k$.
-- Schnoebelen, Philippe
On dispose de $4n$ cartes ($n\geq 2$), une carte $C$ étant la donnée d'un couple $(h,c)$, où $h\in1,n$ s'appelle la hauteur de $C$ et $c\in\{\spadesuit,\heartsuit,\diamondsuit,\clubsuit\}$ s'appelle la couleur de $C$.
Soit $p$ un entier tel que $4\leq p\leq n+2$.
On appelle main toute combinaison de $p$ cartes parmi ces $4n$.
Une double paire $h,k$ ($h\neq k$) est une main avec exactement deux cartes de hauteur $h$ et deux cartes de hauteur $k$, les autres cartes ayant des hauteurs deux à deux différentes.
Combien y a-t-il de doubles paires ?
$\binom {n}{2}\binom {4}{2}^2\binom {n-2}{p-4}\binom {4}{1}^{p-4} $ ?
On ne l'a pas fait de la même manière mais on trouve la même chose. ;-)
Soit $1\leq q\leq p\leq n$ des entiers et $L$ un alphabet à $n$ lettres.
Combien y a-t-il de mots de $p$ lettres qui utilisent exactement $q$ lettres distinctes ?
J'ai fait étudier le cas $p=6$ à mes élèves en devoir maison. :-D
Ok, tu viens d'éditer...
A une telle partition $P$, on peut associer de manière unique des entiers $1\leq m_1<m_2<\ldots <m_r$ et des entiers naturels non nuls $n_1,\ldots,n_r$ tels que $n_1+\cdots+n_r=q$ et $n_1m_1+\cdots+n_rm_r=p$.
Par exemple, avec $p=6$, $q=3$ et la partition $6=1+1+4$, on a $r=2$, $n_1=2,m_1=1,n_2=1,m_2=4$.
Avec ces notations, le nombre de mots de $p$ lettres qui utilisent $q$ lettres distinctes est :$$p!A^n_q\sum_P\frac 1{\prod n_i!\prod (m_i!)^{n_i}}.$$Par exemple, le nombre de mots de $6$ lettres utilisant $3$ lettres distinctes est $6!A^n_3\left(\dfrac 1{2!4!}+\dfrac 1{2!3!}+\dfrac 1{3!(2!)^3}\right)=90n(n-1)(n-2)$.
Je pense qu'une autre méthode donnerait la formule : $\binom{n}{q}S(p, q)$, où $S(p, q)$ est le nombre de surjections de $p$ sur $q$.
On sait que : $S(p, q) = \sum_{k=0}^{q}(- 1)^{q-k}\binom{q}{k}k^{p}$.
Cordialement
Se donner un mot de $p$ lettres utilisant $q$ lettres distinctes, c'est se donner $q$ lettres et une surjection de $1,p$ dans l'ensemble de ces $q$ lettres.
Je vais regarder si on peut tirer quelque chose de nos deux façons de compter...
J'avais nommé un segment [TG], un jour. Un élève me demande si j'ai fait exprès de choisir ce nom. Je dis un truc comme "Quoi donc ? Ah oui, TG ta gueule, non c'était pas volontaire".
Lui, étonné : "bah non, monsieur, Tarn-et-Garonne !". On était dans le 82, il était sérieux.
Par exemples :
- pour $q = p - 1$, les deux formules donnant $S(p, q) = p!.q!.G(q, p)$ où $G(q, p)$ est la forme générale de ce que tu mets entre-parenthèses dans ton exemple, on trouve $S(p, q) = p!.\dfrac{p - 1}{2}$.
- pour $q = p - 2$, on trouve $S(p, q) = \dfrac{p!.(p - 2).(3p - 5)}{24}$ (et cette formule n'est pas aisée à trouver autrement).
* pour $q = p - 3$ on trouve....
Cordialement. (tu)
Pour tout entier $p\geq 3$,$$S(p,p-3)=\sum_{k=0}^{p-3}(-1)^{p-3-k}\binom{p-3}{k}k^p=\frac{p!(p-2)(p-3)^2}{48}.$$
C'est mignon comme anecdote michael. ^^
On retrouve aussi la fameuse égalité : $n! = \sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}k^n$.
Pour tout $q\in\mathbb N$, $P_q:p\mapsto\dfrac{S(p+q,p)}{(p+q)!}$ est un polynôme de degré $q$ qui s'annule en $0$.
En particulier, $P_q$ est entièrement déterminé par les images de $1,2,\ldots,q$ (par interpolation par exemple).
Par exemple, pour $q=7$, on obtient pour tout $p\in\mathbb N$,$$S(p+7,p)=(p+7)!P_7(p)=\frac{(p+7)!p^2(p+1)(9p^4+54p^3+51p^2-58p+16)}{5806080}.$$
Pour tous $q$ et $p\geq 1$,$$S(p+q+1,p)=p\big(S(p+q,p)+S(p+q,p-1)\big).$$D'où, pour la suite de polynôme $(P_q)$ définie dans mon message précédent, $$(p+q+1)P_{q+1}(p)=p\big(P_q(p)+P_{q+1}(p-1)\big).$$Comme $P_0=1$, cette formule de récurrence permet de calculer les $P_q$ de proche en proche, ce que je me suis empressé de faire sous maple !
Une petite vérification :
Il existe une formule simple : $P_q(p)$ est le coefficient de $x^q$ dans le développement en série entière de $\left(\dfrac{e^x-1}x\right)^p$. Cela prouve au passage que $P_q$ est un polyôme de degré $q$ en $p$ (car combinaison linéaire des $\displaystyle{p\choose k}$ pour $k$ de 1 à $q$). On peut faire le calcul à la main pour les petites valeurs de $q$.
Si on a le droit d'utiliser Maple, la commande donne instantanément (pour $q=101$) la factorisation de $P_q(p)$.
Je me pose une question : pourquoi peut-on factoriser $p^2(p+1)$ dans $P_q(p)$ quand $q\geq3$ est impair ?
Effectivement, on retrouve très rapidement plusieurs $P_q$ donnés dans ce fil en cravachant.