Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
178 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

QDV 12 & H 63 (2): Combinatoriennes, ...

Envoyé par Norbert Verdier 
A Raymond Cordier,

J'ai bien pris acte de votre réponse (la seule que j'ai eu, d'ailleurs), et je vous en remercie.
JLT
Re: QDV 12 & H 63 (2): Combinatoriennes, ...
il y a six années
avatar
Pour Comtet 32, je n'ai pas d'idée élémentaire plus rapide que ce que propose RC mais je remarque qu'il découle du théorème de Lucas :
[fr.wikipedia.org]
bs
Re: QDV 12 & H 63 (2): Combinatoriennes, ...
il y a six années
avatar
Bonjour,

Comtet 22 thumbs down RC avec la formule de Binet.
Dans Putnam and Beyond, Gelca et Andreescu attribuent cette relation $ \displaystyle f_{2n} =\sum_{k=1}^{n} f_k \binom{n}{k} $ à Ernesto Cesàro. Exercice 861.

Amicalement.
Re: QDV 12 & H 63 (2): Combinatoriennes, ...
il y a six années
avatar
Comtet 30. Dans Le cas où $\left| E\right|=3 $, il existe $19$ relations transitives possibles dans $E$, pouvez-vous les exhiber si $E=\{a,b,c\}$ ?
On n'est pas des petits Sixièmes des années '70, pour faire de tels exercices ! Je préfère vous raconter une anecdote. À cette époque reculée des dites "math-modernes", je faisais mes débuts dans la carrière, d'abord comme maître-auxiliaire. Les pauvres professeurs chenus n'en pouvaient mais. Je me souviens d'une collègue que je voyais comme vieille, quoiqu'à la réflexion elle le fût sans doute moins que je ne le suis à ce jour, et qui arrivait le matin en nous demandant, à nous les jeunes, de lui expliquer pourquoi la relation vide était symétrique, antisymétrique et transitive, mais non réflexive - du moins si l'ensemble est non vide. Ce dont nous nous acquittions volontiers, mais non sans difficultés ...
Heureusement, aujourd'hui, nous savons qu'on apprend toujours, et par exemple j'apprends beaucoup depuis que j'ai eu la bonne idée de venir sur ce forum.
Bonne journée, bonne semaine,
RC
bs
Re: QDV 12 & H 63 (2): Combinatoriennes, ...
il y a six années
avatar
Bonjour,

Comtet 32 : JLT thumbs down RC

Si on écrit $n$ et $k $ en base $p$ premier : $n=n_jp^j+n_{j-1}p^{j-1}+\cdots +n_1p+n_0$ et $k=k_jp^j+k_{j-1}p^{j-1}+\cdots +k_1p+k_0$, avec le même indice $j$, quitte à compléter pour $k$ avec des zéros, alors un théorème de Lucas dit que : .
$$\displaystyle \binom{n}{k} \equiv \binom{n_0}{k_0} \binom{n_1}{k_1} ...\binom{n_j}{k_j} ~~($mod $p)$$

Lien de JLT : [fr.wikipedia.org]\%C3\%A9or\%C3\%A8me_de_Lucas et preuve dans FGN - Algèbre 1 - exercice 4.24.

Pour $p=2$ : $\displaystyle \binom{n}{k} $ est impair ssi $\displaystyle \binom{n_i}{k_i} \equiv 1 ~~($mod$2)$ pour tout $0\leq i \leq j$ avec $n_i$ et $k_i$ appartenant à $\{0,1\}$, c'est à dire ssi $0 \leq k_i \leq n_i$ pour tout $i$, c'est à dire $\displaystyle k \subset n $.
Dans l'écriture de $n$ en base $2$, quand $n_i=1$, alors $k_i=0$ et $k_i=1$ fournissent deux coefficients binomiaux impairs. Le nombre de coefficients binmiaux sur la $n$_ième ligne est donc égal à $d_n=(n_0+1)(n_1+1)...(n_j+1)=2^{c_n}$ où $c_n$ est le nombre de chiffes $1$ dans l'écriture de $n$ en base$2$.

Un zoli triangle : en noir, les coefficients binomiaux impairs dans le triangle de Pascal.

[attachment 26176 TriPascal.JPG]

Pour La Science - n°129 - Juillet 1988


"Y a plus que" Comtet 29,30 et 31.

Amicalement.
JLT
Re: QDV 12 & H 63 (2): Combinatoriennes, ...
il y a six années
avatar
Le Comtet 30 m'a l'air faux. Par exemple, on a les relations transitives telles que $xRy\iff ((x,y)=(a,b) \wedge x=y)$ pour un certain couple $(a,b)$. Le choix du couple donne 6 possibilités, et de plus on peut décider librement que $1R1$ ou non, $2R2$ ou non, $3R3$ ou non. Donc on a déjà au moins 48 relations transitives. En fait il me semble qu'il y en a 184 mais j'ai peut-être mal compté.
bs
Re: QDV 12 & H 63 (2): Combinatoriennes, ...
il y a six années
avatar
Re,

Oui JLT, effectivement l'énoncé du Comtet 30 ici est faux, il faut lire :

Comtet 30 (le vrai) : on ne connaît pas à ce jour de formule toute faite pour calculer le nombre de relations transitives dans un ensemble $E$ de cardinal $n$. Leur nombre $a(n)$ figure ici, c'est le lien de Raymond : [oeis.org]
Dans le cas où Card$(E)=0,$ il existe 1 seule relation transitive, c'est l'unique relation dans l'ensemble vide cher à Meu,
dans le cas où Card$(E)=1,$ il existe 2 relations transitives sur les 2 relations binaires...,
dans le cas où Card$(E)=2,$ il existe 13 relation transitives parmi les 16 relations binaires,
dans le cas où Card$(E)=3,$ il existe 171 relations transitives parmi les 512 relations binaires.

Pouvez-vous les exhiber si $E=\{a,b,\}$ et si $E=\{a,b,c\}$, JLT n'est pas bien loin...

Pardon pour cette erreur d'énoncé thumbs up (me suis mélangé les pinceaux avec une autre suite...), merci JLT.

Amicalement.
JLT
Re: QDV 12 & H 63 (2): Combinatoriennes, ...
il y a six années
avatar
Pour $E=\{1,2,3\}$ :

1) Si deux éléments distincts ne sont jamais en relation : 8 relations possibles.

2) Si les seuls couples d'éléments distincts qui sont en relation sont $(a,b)$ : on a $6\times 8= 48$ relations possibles (6 pour le choix de $(a,b)$ et il faut multiplier par 8 selon que $a$, $b$ ou $c$ sont en relation avec eux-mêmes ou non).

3) Si les seuls couples d'éléments distincts qui sont en relation sont $(a,b)$ et $(b,a)$ : on a $3\times 2= 6$ relations possibles (3 pour le choix de $\{a,b\}$ et il faut multiplier par 2 selon que $c$ est en relation avec lui-même ou non).

4) Si les seuls couples d'éléments distincts qui sont en relation sont $(a,c)$ et $(b,c)$ : $3\times 8 =24$ relations possibles.

5) $(c,a)$ et $(c,b)$ : $3\times 8 =24$ relations possibles.

6) $(a,b)$, $(b,c)$, $(a,c)$ : $6\times 8= 48$ relations possibles.

7) $(a,b)$, $(b,a)$, $(a,c)$, $(b,c)$ : $3\times 2=6$ relations possibles (à noter que $(a,a)$ et $(b,b)$ sont nécessairement en relation).

8) $(c,a)$, $(c,b)$, $(a,b)$, $(b,a)$ : $3\times 2=6$ relations possibles.

9) Tous les éléments de $E$ sont en relation : 1 relation possible.

Au total : $8+48+6+24+24+48+6+6+1=171$.
Re: QDV 12 & H 63 (2): Combinatoriennes, ...
il y a six années
Bonsoir

Comtet 33

Cas particulier (1992)

Soient $n$ et $p$, avec $p \leq n$, deux entiers naturels non nuls, et $A_{n,p}$ l'ensemble des matrices $p-$lignes et à éléments dans l'ensemble $\{1,2,........,n\},$ telles que chaque colonne est constituée d'éléments distincts deux à deux.
Soit $k$ un entier vérifiant $p \leq k\leq n$, $M$ un élément de $A_{n,p}$ et $m$ un entier vérifiant $1 \leq m \leq p$.
On dit que la matrice $M$ est $m-$équilibrée ssi quel que soit l'ensemble $B$ à $p$ éléments de $\{1,...,k\},$ il existe une colonne de $M$ telle que le cardinal de l'intersection de cette colonne avec $B$ vaut $m$.

Quel est le plus petit nombre de colonnes d'une matrice $m-$équilibrée ? nombre qui dépend de certains indices.

Possibilité d'envoi d'un livre surprise pour le Résolveur s'il accepte .

Merci
Re: QDV 12 & H 63 (2): Combinatoriennes, ...
il y a six années
avatar
Comtet 31 : D'après Jeff Miller [jeff560.tripod.com], la notation $\displaystyle\binom{n}{k}$ est due à Andreas von Ettingshausen. Wikipedia est d'accord : [en.wikipedia.org]. Pour $C_n^k$ je n'ai pas trouvé.
Re: QDV 12 & H 63 (2): Combinatoriennes, ...
il y a six années
avatar
Il y a trois jours, j'ai posé la question de sommer la série divergente $\overset{+\infty }{\underset{k=0}{\sum }}(_{~k}^{n-k})$, pour $n\in \Z$, avec telle ou telle méthode connue de sommation de série divergente (Borel, Hardy, ou autre), en guise de question Comtet 21 bis.
Il me semble avoir trouvé $\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^{n+1}$. Qu'en dites-vous ?
Bonne nuit.
RC
bs
Re: QDV 12 & H 63 (2): Combinatoriennes, ...
il y a six années
avatar
Bonjour,

Comtet 31 thumbs down Juge Ti, voici un troisième lien qui confirme ta réponse sur le mathématicien à l'origine du symbole $\displaystyle\binom{n}{k}$ : [www.math93.com] §10.
Rien trouvé non plus pour l'origine de $C_n^k$...Si vous connaissez, merci :)

Amicalement.
bs
Re: QDV 12 & H 63 (2): Combinatoriennes, ...
il y a six années
avatar
Bonjour,

Comtet 30

Pour $E=\{a,b\}$ , exhibons les relations transitives :

1) Les relations type $\{(a,b)\}$, on a $2\times 4= 8$ relations possibles (2 pour le choix de $(a,b)$ ou $(b,a)$ et il faut multiplier par $2^2$ selon que $a$ ou $b$ sont en relation avec eux-mêmes ou non).

2) On n'a ni $(a,b)$, ni $(b,a)$ mais les quatre autres relations possibles : $\{(a,a),(b,b)\}$, ou $\{(a,a)\}$, ou $\{(b,b)\}$ ou enfin $a$ et $b$ ne sont en relation avec personne.

3) On a la relation où tout le monde côtoie tout le monde $\{(a,a),(a,b),(b,b),(b,a)\}$

d'où $a(2)= 8+1+4=13$ CQFD.

Vrai que c'est peut-être plus rapide d'exhiber les trois relations non transitives : $\{(a,b),(b,a)\}$, $\{(a,b),(b,a),(a,a)\}$, $\{(a,b),(b,a),(b,b)\}$.

Amicalement.
Re: QDV 12 & H 63 (2): Combinatoriennes, ...
il y a six années
avatar
Dans History of Mathematical Notations: Vol. II par Florian Cajori,

il est écrit que c'est Whitworth qui utilise $C_n^p$ le premier.

[attachment 26189 Capture.JPG]

Le livre de Whitworth (ed 1870) est disponible ici [archive.org].

Malheureusement Cajori cite l'édition de $1886$ à la page $121$.
Re: QDV 12 & H 63 (2): Combinatoriennes, ...
il y a six années
avatar
Sur archive.org ils ont aussi l'édition de 1886.

et
[attachment 26190 Capture.JPG]
figure page 70


Re: QDV 12 & H 63 (2): Combinatoriennes, ...
il y a six années
avatar
Aparemment ce livre de Whitworth a eu un grand succès : j'ai une version papier de sa 5ème édition "much enlarged" de 1901, réimprimée en 1959, et je vous en joins une page intéressante. Mais une question demeure. La notation $C_{r}^{n}$ de Whitworth n'est pas notre notation $C_{n}^{p}$, qui a eu cours chez nous durant plus d'un siècle à vue de nez, puisque le cardinal du "gros" ensemble est en haut, juste comme dans $(_{p}^{n})$. On doit donc continuer la recherche.
Bonne nuit.
RC
[attachment 26210 Whitworth-combi-1.pdf]
Re: QDV 12 & H 63 (2): Combinatoriennes, ...
il y a six années
avatar
Déjà est-ce que $C^p_n$ (et sa soeur $A^p_n$) existent ailleurs qu'en France ? Je croyais (peut être à tort) que c'était une production du génie pédagogique français -- le même qui aujourd'hui écrit dans les programmes des lycées: "on note, comme en probabilités (là je m'étrangle), $\overline{A}$ le complémentaire de $A$.
JLT
Re: QDV 12 & H 63 (2): Combinatoriennes, ...
il y a six années
avatar
Apparemment les $C_n^p$ s'utilisent aussi dans quelques autres pays :

[pl.wikipedia.org]\%C3\%B3rze\%C5\%84
[am.wikipedia.org]\%E1\%88\%B5\%E1\%89\%A5\%E1\%88\%B0%E1\%89\%A3



Edité 1 fois. La dernière correction date de il y a six années et a été effectuée par JLT.
JLT
Re: QDV 12 & H 63 (2): Combinatoriennes, ...
il y a six années
avatar
Quant au complémentaire, je trouvais la notation $\overline{A}$ bien pratique, plus lisible que $A^c$ par exemple dans des formules telles que $\overline{A\cup B}=\overline{A}\cap \overline{B}$. L'ennui c'est qu'elle rentre en conflit avec la notation de l'adhérence.
bs
Re: QDV 12 & H 63 (2): Combinatoriennes, ...
il y a six années
avatar
Bonjour,

thumbs down à JLT pour avoir exhibé avec brio dans le cadre du Comtet 30 les 171 relations transitives qui se promènent parmi les 512 relations binaires dans l'ensemble $E=\{a,b,c\}$, ça se passe ici : [www.les-mathematiques.net]
thumbs down à moi pour avoir exhibé dans le cadre du Comtet 30 les 13 relations transitives parmi les 16 relations binaires dans l'ensemble $E=\{a,b\}$, ça se passe un peu plus haut.

thumbs down à Cidrolin pour avoir trouvé que c'est William Allen Whitworth qui a utilisé $C_r^n$ le premier, même si "le $C_{r}^{n}$ de Whitworth n'est pas notre notation $C_{n}^{p}$, qui a eu cours chez nous durant plus d'un siècle, car le cardinal du "gros" ensemble est en haut" chez Whitworth, bien vu RC.

Subsistent le Comtet 21bis [www.les-mathematiques.net] de Raymond et le Comtet 33 [www.les-mathematiques.net] de Joseph avec récompense proposée par Joseph à celui qui résoudra cet exercice :)

Amicalement.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 136 310, Messages: 1 317 638, Utilisateurs: 24 007.
Notre dernier utilisateur inscrit liny195.


Ce forum
Discussions: 872, Messages: 11 248.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page