QDV 12 & H 63 (2): Combinatoriennes, ...
Bonjour amies combinatoriennes et amis combinatoriens.
Nous vous proposons de continuer l'hommage H63 rendu à Louis Comtet en ouvrant un second fil QDV 12 & H63(2) afin d'éviter toute cacophonie dans le fil QDV 11 & H63(1), entre questions et réponses enchevêtrées.
Ce "topic" est donc la suite de la QDV 11 & H63(1). En route :
Comtet 21 :
Soit la suite de Fibonnaci $f_n$ définie par $f_1=f_2=1$ et $f_{n+1}= f_n+f_{n-1}$. Démontrez que : $$f_{n+1}= \sum_{k=0}^{\lfloor \dfrac{n}{2} \rfloor} \binom{n-k}{k} $$
Comtet 22 :
Soit la suite de Fibonnaci $f_n$ définie par $f_1=f_2=1$ et $f_{n+1}= f_n+f_{n-1}$. Démontrez que : $$ f_{2n} =\sum_{k=1}^{n} f_k \binom{n}{k} $$
Comtet 23 :
Résoudre dans $\N$, $$\binom{n}{2}=m^2.$$
Amicalement. Bernard p/o Le Comité Du Vendredi
Nous vous proposons de continuer l'hommage H63 rendu à Louis Comtet en ouvrant un second fil QDV 12 & H63(2) afin d'éviter toute cacophonie dans le fil QDV 11 & H63(1), entre questions et réponses enchevêtrées.
Ce "topic" est donc la suite de la QDV 11 & H63(1). En route :
Comtet 21 :
Soit la suite de Fibonnaci $f_n$ définie par $f_1=f_2=1$ et $f_{n+1}= f_n+f_{n-1}$. Démontrez que : $$f_{n+1}= \sum_{k=0}^{\lfloor \dfrac{n}{2} \rfloor} \binom{n-k}{k} $$
Comtet 22 :
Soit la suite de Fibonnaci $f_n$ définie par $f_1=f_2=1$ et $f_{n+1}= f_n+f_{n-1}$. Démontrez que : $$ f_{2n} =\sum_{k=1}^{n} f_k \binom{n}{k} $$
Comtet 23 :
Résoudre dans $\N$, $$\binom{n}{2}=m^2.$$
Amicalement. Bernard p/o Le Comité Du Vendredi
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Notons $A_{n+1}$ l'ensemble des suites finies à valeurs dans $\{1,2\}$ dont la somme des éléments fait $n$. Pour $k$ dans $\mathbb{Z}$, notons
$A_{n+1}^k$ les éléments de $A_{n+1}$ qui contiennent $n-k$ termes.
Si $A_{n+1}^k$ est non-vide, on a $(n-k)\le \sum x_i=n\le 2(n-k)$, d'où $0\le k\le n/2$ et
$\displaystyle |A_{n+1}|= \sum_{k=0}^{\big\lfloor \tfrac{n}{2} \big\rfloor} |A_{n+1}^k|= \sum_{k=0}^{\big\lfloor \tfrac{n}{2} \big\rfloor} \binom{n-k}{k} $.
En effet si la somme de $n-k$ termes fait $n$, il y en a $n-2k$ qui valent $1$, et $k$ qui valent $2$, il suffit de choisir la place des "2".
Il est aisé de voir que l'on a la récurrence $|A_{n+1}|=|A_n|+|A_{n-1}|$ (découper suivant le dernier terme).
Comme $|A_{1}|=1=f_1$ et $|A_{2}|=1=f_2$, on a part récurrence $|A_n|=f_n$ pour tout $n$, et en particulier
$\displaystyle f_{n+1}=|A_{n+1}|= \sum_{k=0}^{\big\lfloor \tfrac{n}{2} \big\rfloor} \binom{n-k}{k} $.
On multiplie par $8$ et on ajoute $1$ dans les deux membres de $n(n-1)/2 =m^2$.
Il vient $(2n-1)^2 - 8m^2=1$ ou encore $x^2-8y^2=1$
Avec l'Alpertron on trouve :
Le comtet 14 n'a pas été traité .Et-il trivial ? j'avoue que j'ai oublié la solution,si mes souvenirs sont bons le problème est assez difficile.
Bonne reste de journée
Pas de souci Joseph, le Comtet 14 n'est pas oublié http://www.les-mathematiques.net/phorum/read.php?17,796056,796198#msg-796198
de même que les Comtet 5 et Comtet 15. Nous allons y revenir.
Amicalement.
En efffet, comme dit Cidrolin, l'équation dans $\N$ : $\binom{n}{2}=m^2$ équivaut à :$(2n-1)^2 - 8m^2=1$, soit : $x^2-2y^2=1$, avec : $x:=2n-1, y:=2m$. C'est une équation de Fermat, que Jean Itard nous a enseigné à dénommer ainsi, contre le chauvinisme anglo-saxon qui désigne indûment cette équation sous le nom de "Pell".
Réciproquement, si $x^2-2y^2=1$, alors forcément $y$ est pair et $x$ est impair, et les solutions sont $x_{k}$ et $y_{k}$ avec : $(1+\sqrt{2})^{2k}=x_{k}+y_{k}\sqrt{2}$, ce sont une partie des unités de l'anneau $\Z[\sqrt{2}]$. On avait traité ce problème dans "Le Petit Archimède" sous la forme plus paradoxale : un carré n'est pas un triangle, mais trouver les nombres carrés qui sont aussi triangulaires. Cela vient d'Euler je crois. Les nombres figurés sont comme la préhistoire de la Combinatoire. J'avais signalé cela à ma fille l'an dernier, elle faisait 36 ans. Comme le temps passe.
Là je suis à la bourre mais si vous voulez on en reparlera.
Bonne continuation.
RC
problème du vol de canards [size=x-small](on va les prendre l'aile dans le sac)[/size]:)
Dans le ciel volent $210$ canards, en formant un triangle.
C'est possible puisque $8 \times210+1$ est un carré parfait.
Un chasseur tire vers eux. Il n'en touche aucun.
Mais les canards se reforment en $2$ triangles de $105$ canards.
C'est possible puisque $8 \times105+1$ est un carré parfait.
Déterminer toutes les nombres possibles de canards pour
lesquels ce partage en $2$ vols égaux est possible.
Souvenirs ...
Il peut même en tuer un, c'est pas gentil mais ça fait un autre problème.
Merci de répondre au Comtet 14 dans ce fil : http://www.les-mathematiques.net/phorum/read.php?17,796056,796198#msg-796198
Comtet 21 :
(tu) aléa.
Voici le résultat esthétique de ce doux mélange de Fibonacci et de Pascal :
Référence : Posamentier-Lehmann - The fabulous Fibonacci Numbers - Prometheus Books - page 91.
Une autre méthode par les séries génératrices :
$$F(x) = \sum_{n=1}^{\infty} f_n x^{n-1} = \frac {1}{1 - x - x^2}= \frac {1}{1 - x (1+x)}=1+x(1+x)+x^2(1+x)^2+...+x^n(1+x)^n+...=$$
$$\binom{0}{0}+\binom{1}{0} x + \big[ \binom{2}{0}+\binom{2}{1} \big] x^2+ \big[ \binom{3}{0}+\binom{3}{1} \big] x^3+... $$
En développant et en identifiant.
Référence : Putnam and Beyond - Gelca&Andreescu - ex 872.
Comtet 24
Résoudre dans $\N$, $$\binom{n}{3}=m^2.$$
Comtet 25
Une relation entre deux ensembles $E$ et $F$ est un triplet $(E, \Gamma, F)$ où $\Gamma$ est un sous-ensemble du produit $E \times F$, soit une collection de couples dont la première composante est dans E et la seconde dans F.
Soit un ensemble $E$ de cardinal $n$ et un ensemble $F$ de cardinal $p$ : quel est le nombre de relations de $E$ vers $F$ ?
Amicalement.
Comme j'ai dit, je tiens beaucoup aux coefficients binomiaux généralisés $(_{k}^{\alpha })=\frac{\alpha (\alpha -1)...(\alpha -k+1)}{k!}$ (et $(_{0}^{\alpha })=1$) pour $\alpha \in \C$ et $k\in \N$. Ces coefficients satisfont à la plupart des identités classiques concernant les coefficients binomiaux. D'abord la relation de récurrence de Pascal : $(_{k}^{\alpha })=(_{~k}^{\alpha -1})+(_{k-1}^{\alpha -1})$, et aussi : $k(_{k}^{\alpha })=\alpha (_{k-1}^{\alpha -1})$, et sa fille : $k(k-1)(_{k}^{\alpha })=\alpha (\alpha -1)(_{k-2}^{\alpha -2})$, et toutes les suivantes. Et aussi, fondamentale, l'identité de Vandermonde : $\underset{k=0}{\overset{p}{\sum }}(_{k}^{\alpha })(_{p-k}^{~\beta })=(_{~p}^{\alpha +\beta })$. Le seul impératif, c'est que l'indice inférieur de $(_{k}^{\alpha })$ soit un entier naturel.
D'après cette définition, si $n\in \N$, si $k\in \N$ et si $k>n$, alors : $(_{k}^{n})=0$. Cela découle aussi, bien sûr, de la définition combinatoire du coefficient binomial dans le cas où ses arguments sont des entiers naturels.
Pourquoi rapellé-je tout ça ? C'est que l'égalité en question n'est autre que : $\underset{k=0}{\overset{n}{\sum }}(_{~~k}^{n-k})=F_{n+1}$. Et vue ainsi, elle se prouve par une simple récurrence. Libre à nous ensuite, de déterminer le nombre de termes de cette suite qui sont non nuls, pour avoir le $\overset{\left\lfloor \frac{n}{2}\right\rfloor }{\underset{k=0}{\sum }}(_{~k}^{n-k})$.
Je n'aime pas présenter comme bs le triangle de Pascal. Je disais toujours à mes élèves : le triangle de Pascal est un tableau carré (!). Je ne sais pas bien représenter des tableaux ici, mais ce n'est pas difficile à comprendre, si $n$ est le numéro de la ligne, et $k$ le numéro de la colonne, alors à la $n$-ème ligne et $k$-ème colonne du tableau, on écrit la valeur de $(_{k}^{n})$. Si $k>n$, on aura $0$, c'est pourquoi la moitié des coefficients (à peu près) seront nuls et la partie "utile" de notre tableau aura l'air d'un triangle, d'où son nom. Les coefficients binomiaux nuls sont des coefficients comme les autres, et la relation de récurrence de Pascal est vraie dans tout le tableau carré, dans la partie nulle comme dans la partie non nulle, et à la frontière des deux.
Alors, l'identité $\underset{k=0}{\overset{n}{\sum }}(_{~~k}^{n-k})=F_{n+1}$ concerne les diagonales ascendantes de notre tableau, dans lesquelles une moitié (à peu près) est constituée de coefficients nuls, mais peu importe. Si l'on considère deux de ces diagonales ascendantes consécutives, la simple relation de Pascal susdite montre que leur somme est la diagonale ascendante suivante.
J'y reviendrai demain
Bonne soirée.
RC
Poursuivons. Soit $S_{n}=\overset{n}{\underset{k=0}{\sum }}(_{~k}^{n-k})$. Alors :
$S_{n}+S_{n+1}=\overset{n}{\underset{k=0}{\sum }}(_{~k}^{n-k})+\overset{n+1}{\underset{k=0}{\sum }}(_{~~~k}^{n+1-k})=\overset{n}{\underset{k=0}{\sum }}(_{~k}^{n-k})+(_{~~0}^{n+1})+\overset{n+1}{\underset{k=1}{\sum }}(_{~~~k}^{n+1-k})$
$=(_{~~0}^{n+1})+\overset{n}{\underset{k=0}{\sum }}(_{~k}^{n-k})+\overset{n}{\underset{i=0}{\sum }}(_{i+1}^{n-i})=1+\overset{n}{\underset{k=0}{\sum }}((_{~k}^{n-k})+(_{k+1}^{n-k}))=1+\overset{n}{\underset{k=0}{\sum }}(_{~~k+1}^{n-k+1})$
$=1+\overset{n+1}{\underset{k=0}{\sum }}(_{~~k+1}^{n-k+1})=(_{~~0}^{n+2})+\overset{n+2}{\underset{j=1}{\sum }}(_{~~~~j}^{n-j+2})=\overset{n+2}{\underset{j=0}{\sum }}(_{~~~~j}^{n+2-j})=S_{n+2}$.
C'est un peu laborieux, mais ce n'est que la traduction calculatoire du fait susmentionné : que la somme de deux diagonales ascendantes consécutives du tableau-triangle de Pascal, par la seule vertu de la relation de récurrence de Pascal : $(_{k}^{\alpha })=(_{~k}^{\alpha -1})+(_{k-1}^{\alpha -1})$, donne la diagonale ascendante d'après.
Cela, c'est ce qu'on peut faire en Math-Sup ou prépa-HEC (pour le moment). Mais il m'est venu une idée.
Mon tableau-triangle de Pascal, on peut le prolonger vers le haut avec des numéros de lignes négatifs, au moyen de la relation de récurrence de Pascal. La ligne numéro $-1$ sera : $1,-1,1,-1,1,-1, ...$. La ligne numéro $-2$ sera : $1,-2,3,-4,5,-6,...$. Et ainsi de suite. Les coefficients de la ligne numéro $n$, avec $n<0$, seront bien toujours les coefficients de $(1+x)^{n}$, qui sera désormais une série entière et non plus un polynôme.
Et alors, on peut demander la valeur de $\overset{+\infty }{\underset{k=0}{\sum }}(_{~k}^{n-k})$, avec telle ou telle méthode connue de sommation de série divergente. C'est Comtet 21 bis.
Bonne dimanchade.
RC
Résoudre dans $\N$, $$\binom{n}{3}=m^2.$$
Les solutions sont : $n=3,4,50$.
J'ai trouvé une merveilleuse démonstration de cette proposition. Mais la marge est trop étroite pour la contenir.
@+.
RC
Une relation entre deux ensembles $E$ et $F$ est un triplet $(E, \Gamma, F)$ où $\Gamma$ est un sous-ensemble du produit $E \times F$, soit une collection de couples dont la première composante est dans $E$ et la seconde dans $F$.
Soit un ensemble $E$ de cardinal $n$ et un ensemble $F$ de cardinal $p$ : quel est le nombre de relations de $E$ vers $F$ ?
..................................................
Si j'ai bien compris, les ensembles $E$ et $F$ étant donnés, une relation est déterminée par son graphe $\Gamma $, qui est une partie du produit cartésdien $E\times F$. Le nombre de ces relations me semble donc être le nombre de parties de ce produit cartésien, c'est-à-dire : $2^{np}$. Non ?
Je m'intéressais à cela au temps lointain des dites "maths-modernes", plutôt avec $E=F$, et alors on cherchait le nombre de relations particulières : réflexives, symétriques, antisymétriques, transitives, d'équivalence, d'ordre (partiel, total). Pour certaines, c'est facile ; le nombre de relations d'équivalence est le nombre de partitions, nombre de Bell, mais pour d'autres ce l'est moins.Voir Comtet, tiens justement, tome I, p. 71.
Bonne dimanchade.
RC
Merci Raymond pour les développements autour du Comtet 21 et pour le Comtet 21bis.
Comtet 23 : (tu) Cidrolin et Raymond.
Oui, la résolution de cette équation diophantienne revient à rechercher les nombres $N$ qui sont à la fois carrés et triangulaires. Souvenir... et http://oeis.org/search?q=A001110&sort=&language=english&go=Search.
On se ramène effectivement à une équation de Pell-Fermat ainsi, pas de jaloux entre Français et Britanniques : $\binom{n}{2}=m^2$ équivaut à :$(2n-1)^2 - 8m^2=1$, soit : $x^2-2y^2=1$, avec : $x:=2n-1, y:=2m$.
La résolution de cette équation montre qu'on obtient toutes les solutions avec les relations : $x_0=1, y_0=0$, $x_{k+1}=3x_k+y_k, ~~y_{k+1}=2x_k+3y_k$, enfin $n_k=\dfrac{x_k+1}{2}$ et $m_k=\dfrac{y_k}{2}.$
Premières valeurs :
$x_k=1,3,17,99,577,...$ http://oeis.org/search?q=A001541&sort=&language=english&go=Search
$y_k=0,2,12,70,408,...$ http://oeis.org/search?q=A001542&sort=&language=english&go=Search
$n_k=1,2,9,50,289,...$ ($n_0=1<2$ pas possible ici) http://oeis.org/search?q=A0055997&sort=&language=english&go=Search
$m_k=0,1,6,35,204,...$ (avec $m_0=0$ non retenu ici) http://oeis.org/search?q=A001109&sort=&language=english&go=Search
$N_k=0,1, 36,1225,...$ (avec $N_0$ non retenu ici) http://oeis.org/search?q=A001110&sort=&language=english&go=Search
Comtet 23 bis : le vol de canards de Cidrolin
Mise en équation: $T_n=\dfrac{n(n+1)}{2}=2 \dfrac{m(m+1)}{2}=2T_m$ équivalent à : $2(2m+1)^2-(2n+1)^2=1$, soit $2x^2-y^2=1$, soit la petite soeur de l'équation précédente du Comtet 23.
Les solutions $n$ correspondant aux $T_n$ sont ici : http://oeis.org/search?q=A001652&sort=&language=english&go=Search, les solutions $m$ correspondant aux $T_m$ sont là : http://oeis.org/A053141, enfin, les nombres triangulaires doubles d'un nombre triangulaire sommeillent ici : http://oeis.org/search?q=A029549&sort=&language=english&go=Search
Amicalement.
Comtet 24 (tu) Raymond
Dans Proofs from the Book, Chapter 3, est écrit qu'il n'existe pas d'autres solutions que $(3,1),(4,2),(50,140)$ à l'équation $\displaystyle \binom{n}{3}=m^2.$ . Connais-tu une référence de document démontrant ce résultat ? Il n'y en a pas dans Proofs from the Book. Merci.
Amicalement.
Il faut dire qu'il est loin d'être évident, mais j'avais donné une indication dans le {\bf Comtet 18} : il faut faire de même, utiliser la fonction bêta.
Si personne n'a répondu au Comtet 14, peut-être est-ce parce qu'il n'est pas évident
Il y a également ton Comtet 15 qui n'a pas été non plus résolu.
Merci à tou(te)s de répondre aux questions Comtet $k$ avec $1 \leq k \leq 20$ dans le prédent fil.
Amicalement.
Je le laisse encore traîner un peu (car je ne viens pas régulièrement ici). On peut, répétè-je, se servir de la fonction bêta.
Oui, mais dans 4 h environ...
Un carré = un tétraédriq', classiq'
Bonne continuation.
RC
Suite Comtet 24
OK, merci Raymond, dans ce wikiki sur les nombres tétraédriques, on peut lire : "En 1878, A.J. Meyl a démontré qu'il y a seulement trois nombres tétraédriques qui sont également carrés, à savoir, $1, 4$ et $19600$..."
Amicalement.
(tu) Soit un ensemble $E$ de cardinal $n$ et un ensemble $F$ de cardinal $p$, alors le nombre de relations de $E$ vers $F$ est effectivement égal à $2^{np}$. Il y a donc $2^{n^2}$ relations binaires dans l'ensemble $E$. Parmi ces $2^{n^2}$ relations binaires dans $E$, quel est :
Comtet 26 : le nombre de relations réflexives dans $E$ ?
Comtet 27 : le nombre de relations symétriques dans $E$ ?
Comtet 28 : le nombre de relations antisymétriques dans $E$ ?
Amicalement.
D'abord Comtet 24. Résoudre dans $\N$ : $\binom{n}{3}=m^2.$
J'ai signalé qu'il s'agit en fait d'un vieux problème concernant les nombres figurés. La théorie des nombres figurés prend sa source dans la plus ancienne tradition pythagoricienne, qui fait le lien entre les nombres et les formes. Ces formes peuvent être planes ou spatiales, ou pourquoi pas hyperspatiales. Les $n^{2}$ sont les nombres carrés, ça tout le monde le sait, mais les $(_{2}^{n})$ sont les nombres triangulaires, les $(_{3}^{n})$ sont les nombres tétraédriques, les $\frac{n(n+1)(2n+1)}{6}=\overset{n}{\underset{k=1}{\sum }}k^{2}$ sont les nombres pyramidaux, etc.
Vous voyez d'ici la mine de problèmes, dont nous avons visité déjà certains dans ce fil.
Dans le cas présent, c'est : quels sont les nombres qui sont à la fois carrés et tétraédriques ?
Il n'y en a que trois : 1, 4 et $19600=\frac{50\times 49\times 48}{6}=140^{2}$.
Effectivement, ceci a été prouvé par A. Meyl dans les Nouvelles Annales de Mathématiques (2), 17, 1878, p. 464-467, après conjectures de Moret-Blanc et Lucas. Si un pro de Numdam - ou une autre sorte de malin - pouvait nous avoir ce texte, ce serait bien.
C'est lié au problème analogue concernant les nombres qui sont à la fois carrés et pyramidaux, conjecturé par Lucas, et démontré par des procédés non élémentaires par Watson et Ljunggren : la seule solution non triviale de $\frac{n(n+1)(2n+1)}{6}=m^{2}$ est $n=24$. Si un nombre $a$ est à la fois carré et pyramidal, alors $4a$ est à la fois carré et tétraédrique.
Bonne soirée.
RC
Voici la solution de A.J.J.Meyl pour le Comtet 24 : http://archive.numdam.org/ARCHIVE/NAM/NAM_1878_2_17_/NAM_1878_2_17__464_1/NAM_1878_2_17__464_1.pdf
et ici la question 1180 résolue par Edouard Lucas mentionnée par A.J.J. Meyl dans son article : http://archive.numdam.org/ARCHIVE/NAM/NAM_1877_2_16_/NAM_1877_2_16__429_1/NAM_1877_2_16__429_1.pdf
Grand merci, amicalement.
Tu as écrit : << On se ramène effectivement à une équation de Pell-Fermat ainsi, pas de jaloux entre Français et Britanniques >>. Il ne s'agit pas de faire ou non des jaloux (!?) il s'agit d'attribution sérieuse ou non.
1. Jean Itard a écrit dans « Arithmétique et Théorie des Nombres » (« Que Sais-Je ? » N° 1093, p. 90, PUF, 1963) : « Une équation de Fermat - ou encore de Pell comme a écrit Euler par inadvertance - est une équation (...) ».
2. Leonard Eugene Dickson, dans son « History of the Theory of Numbers », Vol. II, Chap. X, a écrit en 1920 : « The very important equation , which has long borne the name of Pell, due to a confusion originating with Euler, should have been designated as Fermat’s equation » (réimpression Chelsea, 1971, p. 341).
3. Edward Everett Whitford, dans « The Pell Equation » (E.E. Whitford, College of the City of New York, 1912), a écrit : « The indeterminate equation of the second degree in two unknowns which is of the form has long been called the Pellian equation, or the Pellian problem ; and it is rarely mentioned by another title. As will be shown, John Pell had but little to do with it » (p. 1), et : « Fermat first proposed the general problem in a letter written to Frenicle » (p.49).
Je pense donc que les gens sérieux se doivent de dénommer cette équation "équation de Fermat".
Bonsoir.
RC
Que vont faire les gens sérieux...
RC
Comtet 26 : le nombre de relations réflexives dans $E$ ? $2^{n(n-1)}$.
Comtet 27 : le nombre de relations symétriques dans $E$ ? $2^{\frac{n(n+1)}{2}}$.
Comtet 28 : le nombre de relations antisymétriques dans $E$ ? $2^{n}\cdot 3^{\frac{n(n-1)}{2}}$.
Sauf erreur. Explications suivent ...
Bonne nuit.
RC
Tu sais lire ? J'ai donné trois références précises, signées, dont deux anglo-saxonnes, et une d'un spécialiste de l'histoire mathématique, Jean Itard, dont la réputation n'est pas à faire, et si tu ne sais pas qui c'est, renseigne-toi. Elles concourent pour désigner cette équation comme j'ai dit. C'est sympa, Wikipedia, ça permet de se croire cultivé à peu de frais. Tout le reste, nationalisme et autre connerie, tu peux te le garder. Bien le bonsoir.
RC
Soit un ensemble $E$ de cardinal $n$. Il y a $2^{n^2}$ relations binaires dans l'ensemble $E$.
Preuve. Une relation binaire dans l'ensemble $E$ est une application de $E\times E$ dans $E$ dans $\{0,1\}$.
Comtet 26 : Parmi ces relations binaires dans $E$, combien de relations réflexives ? $2^{n(n-1)}$.
Preuve. Les images des $n$ couples $(x,x)$ sont toutes fixées, égales à 1, et celles des $n^{2}-n$ couples $(x,y)$, $x\neq y$ sont quelconques.
Comtet 27 : Parmi ces relations binaires dans $E$, combien de relations symétriques ? $2^{\frac{n(n+1)}{2}}$.
Preuve. On peut considérer que $E=\{1,2,...,n\}$. Une relation symétrique dans $E$, considérée comme application de $E\times E$ dans $\{0,1\}$, est déterminée par ses valeurs sur les couples $(x,y)$, $x\leq y$, qui sont au nombre de $\frac{n(n+1)}{2}$.
Comtet 28 : Parmi ces relations binaires dans $E$, combien de relations antisymétriques ? $2^{n}\cdot 3^{\frac{n(n-1)}{2}}$.
Preuve. Considérons toujours que $E=\{1,2,...,n\}$, et considérons toujours une relation dans $E$ comme une application $\mathcal{R}$ de $E\times E$ dans $\{0,1\}$. Les images des couples $(x,x)$ sont quelconques, ce qui fait $2^{n}$ possibilités. Pour chaque couple $(x,y)$ avec $x<y$, on a $3$ possibilités : ou bien $\mathcal{R}(x,y)=0$ et $\mathcal{R}(y,x)=0$, ou bien $\mathcal{R}(x,y)=0$ et $\mathcal{R}(y,x)=1$, ou bien $\mathcal{R}(x,y)=1$ et $\mathcal{R}(y,x)=0$. Or les couples $(x,y)$ avec $x<y$ sont au nombre de $\frac{n(n-1)}{2}$, ce qui fait $3^{\frac{n(n-1)}{2}}$ possibilités pour ces couples, d'où le résultat.
On peut aussi dénombrer les relations : réflexives et symétriques, réflexives et antisymétriques, symétriques et antisymétriques, et pourquoi pas les trois, mais là c'est trop facile.
Bonne journée.
RC
Mais il reste des zones d'ombre.
Dans son Analyse Combinatoire (1970), Louis Comtet dit qu'on ne sait pas dénombrer les relations d'ordre, ni même en donner une estimation, et le répète dans la version anglaise de 1974. C'est la suite A001035 de l'OEIS : http://oeis.org/A001035. Et de même pour les relations transitives, suite A006905 de l'OEIS : http://oeis.org/A006905.
D'après les références de ces notices de l'OEIS, il ne semble pas qu'il y ait du nouveau : les math, ça continue.
Bon dimanche.
RC
En cherchant autre chose (serendipity ...), je suis tombé sur la phrase suivante : « The mathematician Euler erroneously attribued Brouncker's method of solving the equation to Pell, and although history has unearthed the error, the equation is now irrevocably Pell's instead of rightfully the Fermat's equation ». C'est dans : Arthur H. Beiler, Recreations in the theory of numbers, Dover, 1964, p.249.
De plus, si l'on veut vraiment faire l'histoire de la question, avec toute sa complexité, on peut remonter plus haut que les Indiens, aux sources même de notre génie européen, à Archimède et son problème des Boeufs du Soleil. C'est expliqué dans : Jean Itard, Arithmétique et Théorie des Nombres, Que Sais-Je ?, N° 1093, PUF, 1963, p. 101.
Et même au XVIIème siècle, il y a eu à ce sujet toute une histoire complexe d'échanges entre Fermat, Wallis, Brouncker, Frenicle. C'est dire le caractère pauvre et réducteur de la notice du wikiste anonyme cité par H. Ce doit être un indianiste, spécialité au demeurant tout à fait honorable et utile, et même parfois sacrifiée à d'autres exotismes réputés plus intéressants aujourd'hui, mais malheureusement le spécialiste a parfois tendance à ramener tout à sa spécialité.
Bon dimanche à H et à tous.
RC
Ceci étant, je ne suis pas ici depuis bien longtemps, mais il semble exister un contentieux assez lourd entre Raymond Cordier et H.
Quelle est l'origine de ce contentieux ? Mathématique ? Politique ? Comportement sur le forum ?
Entre Raymond Cordier dont les messages n'ont pas toujours été des plus sympathiques (mais qui semble avoir mis de l'eau dans son vin) et H qui utilise un pseudo (et parfois un ton sarcastique) pour ses interventions, difficile de trancher. Les deux ont souvent raison, parfois tort.
Quant aux équations diophantiennes du type $x^2 - D y^2 = \pm 1$ avec $D$ entier 2-libre $\neq 1$, il y a effectivement les deux dénominations (Fermat ou Pell), mais l'usage veut qu'on les nomme Pell-Fermat, ce qui donne un air de réconciliation entre les deux protagonistes.
Ou mieux : on ne les nomme pas, et on se rappelle qu'elles servent essentiellement à déterminer les unités du corps quadratique $\mathbb{Q} (\sqrt D)$ lorsque $D > 0$...
(tu) pour les Comtet 26, 27 et 28.
Comtet 29 : c'est l'ancien capitaine d'artillerie à La Haye A.J.J. Meyl qui a donc le premier résolu le Comtet 24 en 1878 ; rappel :
http://archive.numdam.org/ARCHIVE/NAM/NAM_1878_2_17_/NAM_1878_2_17__464_1/NAM_1878_2_17__464_1.pdf
Que savez-vous de cet ancien capitaine d'artillerie ?
Comtet 30 -> énoncé faux : on ne connaît pas à ce jour de formule toute faite pour calculer le nombre de relations réflexives transitives dans un ensemble $E$ de cardinal $n$. Leur nombre $a(n)$ figure ici, c'est le lien de RC : http://oeis.org/search?q=A006905&sort=&language=&go=Search
Dans Le cas où Card$(E)=3$, il existe ainsi 19 [Faux, c'est 171 d'après le lien] relations transitives possibles, pouvez-vous les exhiber si $E=\{a,b,c\}$ ?
Voir l'énoncé juste ici. [Merci JLT].
Comtet 31 : qui sont les créateurs de ces deux symboles mathématiques $C_{n}^{k}$ et $\binom{n}{k}$ ?
Comtet 32 : on dira qu'un nombre $k$ est "contenu" dans le nombre $n$ et on écrira $k \subset n$ si dans l'écriture de $n$ sous la forme de la somme de puissances de $2$, on retrouve les termes des puissances de 2 utilisées dans l'écriture de $k$.
Exemples : $13=2^3+2^2+2^0$ et $9=2^3+2^0$ et $9 \subset 13$, car on retrouve $2^3$ et $2^0$ dans l'écriture de $13$, mais
$11=2^3+2^1+2^0$ et $6=2^2+2^1$ donc $6$ n'est pas contenu dans $11$.
Montrer que :
Bon dimanche, amicalement.
copier les lettres de Fermat :
Historien des math, c'est un métier. Si un type se mêle de nous apprendre de l'histoire des math et qu'il oublie l'existence de Fermat, c'est comme un historien de l'art qui n'aurait pas entendu parler de Léonard de Vinci. Alors moi ce que je fais, je rigole et je passe mon chemin, je lis autre chose, ce ne sont pas les écrits sérieux qui manquent, sur papier ou sur écran. Je ne me vois pas sauver sa pauvre notice.
On touche là la question du bon usage d'Internet, qui est un outil merveilleux et indispensable (notamment en politique ...) mais qui demande des utilisateurs avertis et circonspects, ce que nous nous efforçons d'être, sans être certains d'y parvenir toujours.
Bien cordialement,
RC
Prolongement Comtet 24 : En France, l'équation de Pell-Fermat est une appelation contrôlée, une espèce d'AOC (mathématique), au même titre que le rosé de Bandol, la boulette d'Avesnes ou encore les bêtises de Cambrai.. Maintenant, il est intéressant de savoir si Pell est un usurpateur et/ou Brahmagupta un précurseur ?
Voilà les biographies signées des trois principaux protagonistes sur le site du Mac Tutor History of Mathematics Archive of the University of St Andrews - Scotland.
Brahmagupta : http://www-history.mcs.st-and.ac.uk/Biographies/Brahmagupta.html
Fermat : http://www-history.mcs.st-and.ac.uk/Biographies/Fermat.html
John Pell : http://www-history.mcs.st-and.ac.uk/Biographies/Pell.html
Sinon, les Comtet 22, 29, 30, 31, 32 restent bien au chaud...
Amicalement.
Par ailleurs les articles de wikipedia sont des oeuvres collectives. Je dis cela car à au moins trois reprises tu as parlé de "l'auteur de la notice" ou de quelque chose d'approchant.
Je trouve que wikipedia est plutôt pas mal. On ne peut évidemment faire confiance aveugle à ses articles mais c'est tout de même utile pour différentes raison : avoir un point de départ pour faire une recherche sur un sujet (quelques mots clés et références bibliographiques), avoir une référence rapide à donner à quelqu'un sur un sujet que l'on maîtrise (et pour lequel on peut donc vérifier que wikipedia ne raconte pas n'importe quoi), avoir rapidement des réponses vraisemblablement correctes sur des sujets non fondamentaux, voir rapidement si un thème est sujet à polémiques ou s'il est consensuel ou qu'il intéresse peu de monde (en regardant notamment la page de discussion), ...
Enfin, comparer un article de wikipedia à un livre spécialisé sur le sujet me semble peu loyal. Il faudrait plutôt comparer différentes encyclopédies entre elles et là wikipedia ne s'en tire, paraît-il, pas si mal que cela (je n'ai pas vérifié).
Le plus gros défaut à mon goût de wikipedia est plutôt du côté de ses contributeurs/administrateurs zélés qui ne donnent pas envie de contribuer, mais c'est une autre histoire.
En effet, je suis assez d'accord. Il est vrai que j'ai un certain goût pour la polémique, genre littéraire qui, comme par ailleurs la caricature, consiste souvent à forcer le trait. J'utilise bien sûr Wikipédia quand j'ai besoin de me remémorer rapidement quelque chose. Je le conseille aux élèves de prépa-HEC pour trouver rapidement les renseignements nécessaires sur les lois de probabilité semi-classiques pour eux, etc.
Mais moi, je n'aime pas ce concept d'écrit anonyme. J'aime prendre la responsabilité de ce que j'écris.
Et si une notice traite de l'équation de Fermat-"Pell" sans mentionner Fermat, ce n'est pas sérieux. Mais ce n'est pas si grave, des écrits pas sérieux, il y en a partout, sur papier ou sur écran.
@bs
Pell n'est pas un usurpateur, il n'y est pour rien si Euler s'est trompé. Ce sont ses congénères anglo-saxons qui ont propagé le bobard, sans doute par chauvinisme, à quelques exceptions près, notamment celles que j'ai citées. C'est une bonne chose que chaque nation soit fière des réalisations de ses enfants, dans tous les domaines, et les mette à l'honneur, à condition de ne pas les usurper.
Je considère que l'équation de Fermat est de Fermat comme l'andouille est de Vire, et je n'envisage pas de suivre le troupeau, et je préfère me conformer à la vérité et au message de mon vénéré maître Jean Itard. Je désignerai désormais cette équation sous le nom de Fermat-"Pell", cela me semble le compromis maximum acceptable, boudiou !
Bonne soirée.
RC
NB. Si vous passez par Beaumont-de-Lomagne, visitez la maison de Fermat, mais rendez vous aussi à la charcuterie Micouleau. Profitez-en tant qu'on peut encore manger du porc ... Regardez sur le site de Robert Ferréol la belle spirale d'Archimède en saucisse de Toulouse ...
Tu as écrit "réflexives" pour transitives".
Bonne soirée.
RC
> > Profitez-en tant qu'on peut encore manger du
> porc ...
>
> Quel coquin ce Raymond ! Incorrigible !
... Chassez le naturiste, il revient au bungalow ...
Je l'avais oublié, celui-ci.
Rappelons la définition canonique des nombres de Fibonacci : $F_{0}=0,F_{1}=1,F_{n+2}=F_{n+1}+F_{n}$.
Il est bien-connu que $F_{n}=\frac{\alpha ^{n}-\beta ^{n}}{\alpha -\beta }$, où $\alpha =\frac{1+\sqrt{5}}{2},\beta =\frac{1-\sqrt{5}}{2}$, racines de l'équation : $x^{2}-x-1=0$, qui est l'équation caractéristique de la récurrence régissant la suite $F_{n}$.
Dès lors, c'est évident : $\overset{n}{\underset{k=0}{\sum }}(_{k}^{n})F_{k}=\overset{n}{\underset{k=0}{\sum }}(_{k}^{n})\frac{\alpha ^{k}-\beta ^{k}}{\alpha -\beta }=\frac{1}{\alpha -\beta }(\overset{n}{\underset{k=0}{\sum }}(_{k}^{n})\alpha ^{k}-\overset{n}{\underset{k=0}{\sum }}(_{k}^{n})\beta ^{k})$
$=\frac{1}{\alpha -\beta }((\alpha +1)^{n}-(\beta +1)^{n})=\frac{1}{\alpha -\beta }(\alpha ^{2n}-\beta ^{2n})=F_{2n}$. Epicétou.
J'aime beaucoup Leonardo Bigollo, dit Léonard de Pise, dit Fibonacci, qui est en quelque sorte le père du renouveau des mathématiques européennes, et donc mondiales.
J'aimerais bien avoir le Liber Abaci, avec traduction, car je ne sais pas grand'chose en latin.
J'ai une foule de problèmes concernant cette suite, dont celui-ci, que j'ai déjà posé sur ce forum. Démontrer que le produit de deux nombres de Fibonacci, autres que $0$ et $1$, n'est jamais un nombre de Fibonacci.
Et aussi celui-ci. Démontrer que la suite complexe : $Z_{n}=\overset{n}{\underset{k=1}{\prod }}(1-2i\cos \frac{k\pi }{n+1})$, où $i^{2}=-1$, est en fait une suite réelle très connue, et reconnaître cette suite.
Bonne soirée.
RC
Moi, je ne partage pas la vue-du-monde bisounours qu'on essaie de nous imposer, tout lisse, tous gentils, cette guimauve écoeurante qui dégouline de nos télés. On se dispute ? C'est qu'on est vivants. Tu n'es pas le roi Salomon pour savoir qui a raison et qui a tort. Moi j'ai mes vues, les autres ont les leurs, c'est comme ça chez nous les Gaulois.
Tu dis : << quant aux équations diophantiennes du type $x^2 - D y^2 = \pm 1$ avec $D$ entier 2-libre $\neq 1$, il y a effectivement les deux dénominations (Fermat ou Pell), mais l'usage veut qu'on les nomme Pell-Fermat, ce qui donne un air de réconciliation entre les deux protagonistes. >> C'est pas indispensable, la réconciliation.
<< Ou mieux : on ne les nomme pas, et on se rappelle qu'elles servent essentiellement à déterminer les unités du corps quadratique $\mathbb{Q} (\sqrt D)$ lorsque $D > 0$...>> Tout faux. Ne pas les nommer, c'est vraiment la fuite devant le problème, toujours bisounours, c'est vraiment pas glorieux. Et qu'elles servent à cela, c'est TON avis, ce n'est pas l'avis général, ce n'est pas le mien en tout cas. On peut penser qu'une équation diophantienne a un intérêt pour elle-même, qu'elle trouve en elle-même sa propre fin, comme beaucoup de problèmes en math, pour la beauté de la chose.
Bonne soirée.
RC
On dira qu'un nombre $k$ est "contenu" dans le nombre $n$ et on écrira $k \subset n$ si dans l'écriture de $n$ sous la forme de la somme de puissances de $2$, on retrouve les termes des puissances de 2 utilisées dans l'écriture de $k$.
Montrer que : $\displaystyle k \subset n \Longleftrightarrow \binom{n}{k}$ est impair.
Là j'ai la flemme de rédiger, mais j'ai retrouvé dans mes papiers un résultat qui implique celui-ci. Soient $m$ et $n$ des entiers positifs et $p$ un nombre premier. Alors, $v_{p}((_{~~n}^{m+n}))$ est le nombre de retenues qui apparaissent lorsque l'on effectue à la main, à l'ancienne, l'addition de $m$ et de $n$ écrits dans la base $p$. Ceci se démontre avec la formule de LeGendre : $v_{p}(n!)=\overset{+\infty }{\underset{k=1}{\sum }}\left\lfloor \frac{n}{p^{k}}\right\rfloor $, somme qui n'a qu'un nombre fini de termes non nuls.
J'avais suggéré quelque chose comme ça dans un précédent problème, mais à l'époque, ma suggestion s'était révélée inopérante, et quelqu'un de plus malin (JLT je crois) avait trouvé bien mieux, et bravo pour lui. Peut-être en ira-t-il de même aujourd'hui. Mais je garantis le résultat général que j'ai donné, et qu'il implique bien le résultat demandé.
Bonne soirée.
RC
J'ai bien pris acte de votre réponse (la seule que j'ai eu, d'ailleurs), et je vous en remercie.