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

2»

Réponses

  • JLT
    JLT
    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 :
    http://fr.wikipedia.org/wiki/Théorème_de_Lucas
  • bs
    bs
    Bonjour,

    Comtet 22 (tu) 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.
  • Raymond Cordier
    Raymond Cordier
    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
    bs
    Bonjour,

    Comtet 32 : JLT (tu) 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 : 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.
    Pour La Science - n°129 - Juillet 1988

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

    Amicalement.26176
  • JLT
    JLT
    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
    bs
    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 : http://oeis.org/search?q=A006905&sort=&language=&go=Search
    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é (td) (me suis mélangé les pinceaux avec une autre suite...), merci JLT.

    Amicalement.
  • JLT
    JLT
    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$.
  • AitJoseph
    AitJoseph
    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
  • Juge Ti
    Juge Ti
    Comtet 31 : D'après Jeff Miller http://jeff560.tripod.com/stat.html, la notation $\displaystyle\binom{n}{k}$ est due à Andreas von Ettingshausen. Wikipedia est d'accord : http://en.wikipedia.org/wiki/Andreas_von_Ettingshausen. Pour $C_n^k$ je n'ai pas trouvé.
  • Raymond Cordier
    Raymond Cordier
    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
    bs
    Bonjour,

    Comtet 31 (tu) Juge Ti, voici un troisième lien qui confirme ta réponse sur le mathématicien à l'origine du symbole $\displaystyle\binom{n}{k}$ : http://www.math93.com/index.php/histoire-des-maths/les-symboles-menu/128-histoire-des-symboles-mathematiques#a10 §10.
    Rien trouvé non plus pour l'origine de $C_n^k$...Si vous connaissez, merci :)

    Amicalement.
  • bs
    bs
    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.
  • Cidrolin
    Cidrolin
    Dans History of Mathematical Notations: Vol. II par Florian Cajori,

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

    26189
  • Cidrolin
    Cidrolin
    Sur archive.org ils ont aussi l'édition de 1886.

    et
    26190
  • Raymond Cordier
    Raymond Cordier
    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
  • aléa
    aléa
    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
    JLT
    Apparemment les $C_n^p$ s'utilisent aussi dans quelques autres pays :


  • JLT
    JLT
    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
    bs
    Bonjour,

    (tu) à 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 : http://www.les-mathematiques.net/phorum/read.php?17,797753,798711#msg-798711
    (tu) à 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.

    (tu) à 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 http://www.les-mathematiques.net/phorum/read.php?17,797753,798025#msg-798025 de Raymond et le Comtet 33 http://www.les-mathematiques.net/phorum/read.php?17,797753,798746#msg-798746 de Joseph avec récompense proposée par Joseph à celui qui résoudra cet exercice :)

    Amicalement.
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 20

Matricule_63NicoLeProfPhilippe MalotSatoVassilliabiguine_equationpozzarsamok +12 Invités