QDV 11 & H63 (1): (dé)comptes avec Comtet!

Pour avoir été collé par Comtet à Saint louis dans les années 70, je répondrai à Comtet 2 : en se ramenant à $a+b=1$, il s'agit de déterminer le mode pour une loi binomiale de paramètres $n$ et $\dfrac{a}{a+b}$

Comtet 4 : soit $E$ avec $|E|=n$. Comptez les $A_1,\dots, A_k$ avec

$A_1\subset A_2\subset\dots A_k\subset E$.

Bonjour,

Gilles et Comtet 2 : d'acord avec ton approche mais quelle est la réponse ? Si tu te souviens quarante ans plus tard de la question posée par L.Comtet en colle, n'hésite pas à la proposer dans ce fil en Comtet 5 ou autre.

aléa et Comtet 3 : tu as bien compris que l'ensemble fini $E$ posséde $n$ éléments et que la partie $A$ de $E$ en possède $q$.
Oui pour le ?

Amicalement.

@bs: oui, j'ai fait une erreur ?

@ JLT: on peut éviter la formule du multinôme grâce une bijection bien choisie.

Re,

Après réunion de la commission de validation des réponses, non aléa tu n'as pas fait d'erreur pour le Comtet 3 (tu)

Merci pour vos Comtet 4 et Comtet 5.

Amicalement.

Comtet 6 : $\displaystyle I(k) = \binom{2k}{k}$. Y a-t-il une preuve combinatoire plus jolie que la formule de récurrence de Wallis ?

$2\sin\vartheta = -i\left(e^{i\vartheta} - e^{-i\vartheta}\right)$ ?

e.v.

Re,

Il n'est pas interdit de développer ses solutions...

Comtet 6 : Ju'x (tu) aléa.

Une autre méthode en commençant par une IPP : $$ I(k)=\dfrac{2}{\pi}\int_{0}^{\frac{\pi}{2}} ( 2 \sin \theta)^{2k} \,\mathrm d\theta=\dfrac{2}{\pi}\int_{0}^{\frac{\pi}{2}} ( 2 \sin \theta)^{2k-1} ( 2 \sin \theta) \,\mathrm d\theta $$

Comtet 7 :

Combien de triangles et de parallélogrammes dans le dessin ci-dessous, en considérant qu'il existe n rangées, et non pas 10 rangées.
Comtet 8 :

Soit $n \in \N^{*}$,$P\in \R[X]$ tel que deg$(P)=n$ et $\forall k \in \{0,1,...,n\}$,$P(k)=\dfrac{1}{\binom{n+1}{k}}$.
Calculer $P(n+1)$.

Amicalement.

La moitié de Comtet 1 généralisé : $a_{m}(n)=\binom{m+n-1}{m-1}$; problème 887 dans Putnam and beyond, Gelca et Andreescu, Springer. Ce bouquin propose aussi Comtet 6 dans le chapitre de combinatoire.

L'autre motié de {\bf Comtet 1}, avec le résultat d'Eric : $A_m(n) = \dbinom{m+n}{n}$. C'est aussi le nombre de solutions entières naturelles ordonnées de l'inéquation $x_1 + \dotsb x_m \leqslant n$.

Comtet 8
Sans problème avec les polynômes d'interpolation de Lagrange sur $\{0,1,...,n\}$, définis par $L_{i}(j)=\delta _{ij}$ (symbole de Kronecker), en sorte que : $L_{i}(x)=\frac{x(x-1)...(x-i+1)(x-i-1)...(x-n)}{i(i-1)...(i-i+1)(i-i-1)...(i-n)}=\frac{1}{i!(-1)^{n-i}(n-i)!(x-i)}\underset{h=0}{\overset{n}{\prod }}(x-h)$, d'où :
$L_{i}(n+1)=\frac{(-1)^{n-i}}{i!(n-i)!(n+1-i)}(n+1)!=(-1)^{n-i}(_{~i}^{n+1})$.
On a donc : $P(x)=\underset{i=0}{\overset{n}{\sum }}P(i)L_{i}(x)$, et par suite :
$P(n+1)=\underset{i=0}{\overset{n}{\sum }}P(i)L_{i}(n+1)=\underset{i=0}{\overset{n}{\sum }}(-1)^{n-i}=\underset{j=0}{\overset{n}{\sum }}(-1)^{j}$, ce qui donne $1$ si $n$ est pair et $0$ sinon.
Modulo les erreur[size=medium]e[/size]s de calcul.
La simplicité de la solution finale (si elle est exacte) laisse présumer qu'il y aurait une méthode plus simple que je n'ai su voir.
Et encore une fois, ça se trouve où dans Comtet ?

---

Et moi, je voudrais vous poser une devinette littéraire.
Louis Comtet a publié toute son oeuvre sous son nom, sauf un livre sous un pseudonyme qui était une anagramme de son nom. Il y a un écrivain français du XXème siècle qui a fait le contraire, qui a publié un livre sous son nom et tous les autres (du moins à ma connaissance) sous un pseudonyme qui était une anagramme de son nom. Qui était-ce ?
Bonne soirée.
RC

Comtet 3
D'accord avec aléa, c'est le nombre de parties $X$ de $E\setminus A$.
On peut poser plein de problème analogues, un peu plus compliqués, en prépa-HEC 1ère année.
Cordialement,
RC

Bonsoir,

Il est possible que certains exercices proposés jusqu'à cette minute figurent sur les Comtet, je n'ai pas vérifié, mais ils ont été choisis pour l'instant dans d'autres manuels, Eric en a d'ailleurs repéré deux. Les références de tous ces exercices seront mentionnées un peu plus tard.

Comtet 7 : Eric (tu) Raymond. Cet exercice est proposé avec trois étoiles (dur+dur+dur) dans un recueil de Terminale S, mais seul le calcul du nombre de parallélogrammes est demandé.

Le résultat rappelé précédemment par Eric dans l'exemple 4.10 que l'on trouve dans A path to combinatorics for undergraduates, Andreescu & Feng, Birkhäuser, est le nombre de parallélogrammes figurant dans un triangle équilatéral de longueur $n$ :


Comtet 8 : Raymond (tu)
Sans utiliser les polynômes d'interpolation de Lagrange :
Si $n$ pair, considérer $Q=P-P(n+1-X)$ et montrer que $Q=0$
Si $n$ impair, considérer $Q=(X+1)P - (n+1-X)P(n-X)$ et montrer que $Q=0$.

Comtet 1 : deuxième partie Eric (tu) duroc avec les notations $b_m(n)$ et $B_m(n)$ et non $a_m(n)$ et $A_m(n).$
Reste la première partie moins connue, avec extension pour $a_3(n)$ et $A_3(n)$ éventuellement.

RC : pourquoi ne pas appeler ta devinette littéraire Comtet 9 ? Merci.

Amicalement.

Re,

Pour la soirée :

Comtet 10 : Soit $E$ un ensemble fini à $n>0$ éléments. Combien existe-t-il de couples $(X,Y) \in \big(\mathcal{P}(E)\big)^2$ tels que $X \cap Y$ soit un singleton ?

Comtet 11 : En notant $(n,k)$ le pgcd de $n$ et $k$ avec $n \geq k>0$, montrer que $\dfrac{n}{(n,k)}$ divise $\binom{n}{k}.$

Comtet 12 : Soit $n$ un entier positif. Quel est le pgcd des nombres : $$\binom{2n}{1}, \binom{2n}{3}, \binom{2n}{5}, \dots, \binom{2n}{2n-1} ? $$

Reste (résiste) : première partie Comtet 1 + Comtet 2+ Comtet 5.

Merci pour vos réponses .

Amicalement.

Comtet 1: $A_2(n)=(n+1)+{{n+1}\choose 2}$ et $a_2(n)=A_2(n)-A_2(n-1)$.

Comtet 10
Il existe une bijection entre les couples $(X,Y)\in \mathfrak{P}(E)\times \mathfrak{P}(E)$ tels que $X\cap Y=\emptyset $ et les applications $f$ de $E$ dans $\{0,1,2\}$, par : $X=f^{-1}(1)$,$Y=f^{-1}(2)$. Le nombre de ces couples est donc : $3^{n}$ .
Pour chaque $a_{i}\in E$, le nombre de couples $(X,Y)\in \mathfrak{P}(E)\times \mathfrak{P}(E)$ tels que $X\cap Y=\{a_{i}\}$ est donc : $3^{n-1}$. La réponse est donc : $n\cdot 3^{n-1}$.
Bien cordialement,
RC

Comtet 2 : $\displaystyle {n\choose k} a^k b^{n-k}$ où $k$ est la partie entière de $\displaystyle \frac{n+1}{\frac{b}a+1}$

Comtet 11 : $n$ divise $n\binom{n-1}{k-1}=k\binom{n}{k}$.

Notons $d$ le PGCD de $n$ et $k$, alors $n/d$ divise $(k/d)\binom{n}{k}$. Or, $k/d$ est premier avec $n/d$, donc $n/d$ divise $\binom{n}{k}$.

{\bf Comtet 15} (si je puis me permettre...). Si $0 \leqslant k < n$, montrer que

$$\sum_{j=0}^k \binom{n}{j} a^{n-j} b^j = (n-k) \binom{n}{k} \int_b^{a+b} t^k (a+b-t)^{n-k-1} \, \textrm{d}t.$$

Référence : Comtet, Analyse Combinatoire Tome 1, PUF, 1970, page 91.

Comtet 12. La référence est erronée. Il s'agit du n°2 de 1971, p. 201-202.

Bonsoir,

(tu) aléa pour Comtet 1 .
Il est cependant possible d'écrire pour tout $n$ : $A_2(n) = \lfloor \big( \dfrac{n}{2}+1 \big)^2 \rfloor$.
Les relations pour $a_3(n)$ et $A_3(n)$ sont un peu plus délicates à obtenir.

Comtet 16 : Soit $E_n$ l'ensemble des nombres de $n$ chiffres en base 10, chiffres choisis parmi les éléments de l'ensemble $\{1,2,\dots,8,9\}.$
Calculer $\displaystyle S_n = \sum_{x \in E_n} x.$

Comtet 17 : Avec ou sans trop de calculs, montrer que :

$$\sum_{k=1}^{n} k \binom{n}{k}^2 = n \binom{2n-1}{n-1}$$

Comtet 18 :
$1)$ Soit la suite $(u_n)_n$ définie par $u_0=1$ car $\binom{0}{0}=1$ et $$u_n=\sum_{k=0}^{n} \dfrac{1}{\binom{n}{k}}, $$ si cette suite $(u_n)_n$ converge, quelle est sa limite ?

$2)$ Montrer que $$u_n=\sum_{k=0}^{n} \dfrac{1}{\binom{n}{k}}= \dfrac{n+1}{2^{n+1}}\sum_{k=1}^{n+1} \dfrac{2^k}{k}$$

Bonne nuit.

Comtet 17: la trivialité $(1+X)^{2n} = (1+X)^n(1+X)^n$ se réécrit
\[
\sum_{k=0}^{2n} \binom{2n}{k}X^k = \left(\sum_{k=0}^n \binom{n}{k} X^k\right)^2,
\]
d'où en dérivant formellement,
\[
\sum_{k=1}^{2n} k\binom{2n}{k} X^{k-1} = 2\left(\sum_{k=1}^n k\binom{n}{k}X^{k-1}\right)\left(\sum_{k=0}^n \binom{n}{k} X^k\right).
\]
On identifie alors le terme d'ordre $n-1$ dans chacun des membres. On obtient
\[
n\binom{2n}{n} = 2\sum_{k=1}^n k\binom{n}{k}^2
\]
La relation $n \binom{2n}{n} = 2 n\binom{2n-1}{n-1}$ donne finalement
\[
n\binom{2n-1}{n-1} = \frac{n}{2} \binom{2n}{n} = \sum_{k=1}^n k\binom{n}{k}^2.
\]

Edit : correction faite.

{\bf Comtet 18}. On utilise la fonction beta qui, rappelons-le, est définie par

$$\beta(x,y) = \int_0^1 t^x (1-t)^y \, \textrm{d}t$$

et où l'on montre que, si $p,q \geqslant 1$ sont entiers, on a $\beta(p,q) = \dfrac{\Gamma(p) \Gamma(q)}{\Gamma(p+q)} = \dfrac{(p-1)!(q-1)!}{(p^+q-1)!}$. Or

$$\frac{1}{\binom{n}{k}} = \frac{k! (n-k)!}{n!} = (n+1) \, \beta(k+1,n-k+1) = (n+1) \int_0^1 t^k (1-t)^{n-k} \, \textrm{d}t$$

de sorte que

$$\sum_{k=0}^n \frac{1}{\binom{n}{k}} = (n+1) \int_0^1 (1-t)^n \sum_{k=0}^n \left ( \frac{t}{1-t} \right)^k \, \textrm{d}t = (n+1) \int_0^1 \frac{(1-t)^{n+1}-t^{n+1}}{1-2t} \, \textrm{d}t$$

et le changement $u=1-2t$ fournit

\begin{align*}
\sum_{k=0}^n \frac{1}{\binom{n}{k}} &= \frac{n+1}{2^{n+1}} \int_{-1}^1 \frac{(1+u)^{n+1} - (1-u)^{n+1}}{u} \, \textrm{d}u \\
&= \frac{n+1}{2^{n+2}} \sum_{k=0}^n \left ( \int_{-1}^1 (1+u)^k \textrm{d}u + \int_{-1}^1 (1-u)^k \textrm{d}u \right ) \\
&= \frac{n+1}{2^{n+2}} \sum_{k=1}^{n+1} \frac{2^k}{k}.
\end{align*}

On ne sait pas trop à qui attribuer en premier cette identité. On la trouve dans la fascicule de Gould (1972), et on la trouve aussi dans un article de Staver de 1947.

C'est la même idée que pour le {\bf Comtet 14}.

{\bf Références}.

{\bf A. M. Rockett}, {\it Sums of the inverses of binomial coefficients}, Fibonacci Quat. 19 (1981), 433--437.

{\bf T. Staver}, {\it Om summasjon av potenser av binomialkoeffisienten}, Norsk Matematisk Tiddskrift 29 (1947), 97--103.

{\bf B. Sury}, {\it Sums of the reciprocals of binomial coefficients}, European J. Combin. 14 (1993), 351--355.

{\bf T. Trif}, {\it Combinatorial sums and series involving inverses of binomial coefficients}, Fibonacci Quat. 38 (2000), 79--84.

Bonjour. Ce matin, j'ai eu des problèmes de connexion. Voici le message que j'ai envoyé à 9 h.

Comtet 16.
Soit $b\in \N$, $b\geq 2$. Pour $n\in \N^{*}$, soit $E_{n}$ l'ensemble des nombres dont l'écriture en base $b$ comporte $n$ chiffres, dont aucun n'est $0$. Le cardinal de $E_{n}$ est : $(b-1)^{n}$. A chacun des nombres $x\in E_{n}$, on peut associer son "complémentaire" $\sigma (x)$ obtenu en remplaçant chaque chiffre $u$ par $b-u$. On définit ainsi une application involutive $\sigma $ de $E_{n}$ dans lui-même. Pour tout $x\in E_{n}$, on a : $x+\sigma (x)=b\frac{b^{n}-1}{b-1}$, d'où la somme demandée : $\frac{1}{2}(b-1)^{n}b\frac{b^{n}-1}{b-1}$$=\frac{b}{2}(b-1)^{n-1}(b^{n}-1)$.
On peut aussi trouver la somme des carrés, et même des cubes des nombres éléments de $E_{n}$, et résoudre les mêmes problèmes avec l'ensemble $F_{n}$ de ces nombres dont les chiffres sont tous distincts (si $n\leq b-1$). On avait déjà parlé de ce genre de problème avec Marre.
Bon dimanche.
RC

un truc que j'ai surement copié dans Comtet (à défaut de me rappeler ce sur quoi j'ai été collé il y a 36 ans...):
Comtet 19: un recouvrement d'un ensemble fini E étant une famille finie de parties de E dont l'union est E, déterminer le nombre de ces recouvrements en fonction du cardinal de E.