Un dénombrement

Bernard39
Bernard39
dans Combinatoire et Graphes
Bonjour, je dois démontrer que : $$\sum_{p=0}^n (-1)^p C^p_n p^{n-1}=0.$$ (Extrait d'un des deux écrits de l'agreg interne 2013).
Quelqu'un peut-il me donner une piste ?
Cordialement.

Réponses

  • h
    h
    À défaut d'avoir une idée lumineuse on peut toujours tenter une récurrence sur $n$. Je n'ai pas essayé mais la stratégie semble raisonnable. Je n'ai pas vu mieux mais je n'ai pas réfléchi très longtemps.
  • Siméon
    Siméon
    On peut considérer le développement limité pour $t\to 0$ de $(1-e^t)^n$.
  • Guego
    Guego
    La somme à calculer est le coefficient en $x^n$ de $(1+x)^n f_n(x)$ où $f_n(x) = \displaystyle \sum_{p=0}^{+\infty} (-1)^p p^{n-1}x^n$.
    Or, on peut montrer par récurrence que $(1+x)^nf_n(x)$ est un polynôme de degré $n-1$. (pour passer de $n$ à $n+1$, remarquer que $f_{n+1}(x) = xf_n '(x)$). D'où le résultat.
  • zephir
    zephir
    Bonjour,

    Pour tout $k\le n-1$, dériver $k$ fois $f(x)=(x - 1)^n$ par la pensée et constater que $f^{(k)}(0)=0$.
    Astuce de taupin, aussi vieille que la taupe;-)
  • Rouletabille
    Rouletabille
    Ou bien : différences finies.
    Ou bien : formule d'inversion de Désiré André.
    Lien avec les nombres de Stirling.
  • Siméon
    Siméon
    Mon indication initiale étant assez allusive, je détaille un peu : en posant $S_k = \sum_{p=0}^n (-1)^p C_n^p p^k$, la formule de Taylor-Young à l'ordre $n$ s'écrit
    \[
    (1-e^{t})^n = \sum_{k=0}^n \frac{S_k}{k!} t^k + o(t^n),\quad t \to 0.
    \]
    Comme par ailleurs $(1-e^t)^n \sim (-t)^n$. On en déduit que $S_k = \begin{cases}0 & \text{si } 0 \leq k \leq n-1\\
    (-1)^n n! & \text{si } k = n\end{cases}$.

    Remarque : ceux qui n'aiment pas l'analyse peuvent considérer à la place la série de Taylor formelle.
  • Bernard39
    Bernard39
    Merci beaucoup !
  • Bernard39
    Bernard39
    Bon en fait, j'ai essayé de reprendre chacune de vos suggestions, et je n'y parviens pas.

    @Siméon : en partant d'un développement limité j'obtiens $$(1-e^t)^n=\big(-t-\frac{t^2}{2}-\cdots -\frac{t^n}{n}+o(t^n)\big)^n$$ et je ne parviens pas à en déduire ta formule $$(1-e^{t})^n = \sum_{k=0}^n \frac{S_k}{k!} t^k + o(t^n),\quad t \to 0.$$
    @Guego : j'écris $$(1+x)^nf_n(x)=\sum_{k=0}^n C^k_n x^k \sum_{p=0}^{+\infty} (-1)^p p^{n-1} x^n$$ mais je ne parviens pas à en déduire que j'ai bien $\sum_{p=0}^n (-1)^p C^p_n p^{n-1}$ qui est le coefficient en $x^n$ de cela.

    @zephir : pourquoi a-t-on alors $f^{(k)}(0)=0$, plus en détails ?

    Merci à vous.
  • bisam
    bisam
    @TriAdmissible :
    Pour la méthode de Siméon, tu pars dans le mauvais sens. Commence par appliquer la formule du binôme, puis effectue un DL des exponentielles.
    Ensuite, par unicité des coeffs d'un DL tu en déduis le résultat annoncé en utilisant le fait que 1-e^t est équivalent à -t en 0.
    À mon avis, c'est la méthode la plus simple...

    Pour la méthode de Zephir, c'est lui qui s'est trompé. Je pense qu'il voulait dire $f^{(k)}(1)=0$ pour $k\in [0,n-1]$... mais je ne sais pas exactement où il comptait te faire aller avec ça.

    Enfin, pour la méthode de Guego, là encore il y a un problème car la série qu'il évoque est grossièrement divergente !
  • Jer anonyme
    Jer anonyme
    Qui se soucie de convergence si le calcul marche formellement ?
  • bisam
    bisam
    Certes, on peut négliger la convergence et faire les calculs formellement...

    Mais en fait, le problème vient surtout du fait qu'il y a une coquille dans ce que Guego voulait dire.
    Il faut en fait considérer $f_n:x\mapsto \sum\limits_{p=0}^{+\infty}(-1)^p p^{n-1}x^p$ et non $x^n$ comme il était écrit.
    Dans ce cas, il y a convergence sur $\left]-1,1\right[$... et tout se passe bien.
  • bisam
    bisam
    On doit aussi pouvoir montrer (par exemple par la formule du crible, et à un facteur (-1)^n près) que le nombre évoqué par TriAdmissible est le nombre de surjections d'un ensemble à n-1 éléments vers un ensemble à n éléments.
  • Bernard39
    Bernard39
    @bisam : merci beaucoup, j'ai bien compris la méthode de Siméon avec ton aide.

    Je vais regarder les autres méthodes quand j'aurai un peu plus de temps.
  • RTM
    RTM
    D'ailleurs, c'est la méthode de Siméon que prônait le sujet par la question précédente.
  • Amtagpa
    Amtagpa
    Voir par exemple le corrigé de l'épreuve donné par ev ici : http://www.les-mathematiques.net/phorum/read.php?6,811208,1015681#msg-1015681

    Sinon pour éclaircir la méthode de zephir, on a pour $0\le k\le n-1$, $f^{(k)}(1)=0$ soit $\sum\limits_{p=0}^n C_n^p (-1)^{n-p} p(p-1)\cdots(p-k+1)=0$. Et comme la famille $\bigl(1,X,X(X-1),\ldots,X(X-1)\cdots(X-(n-1)+1)\bigr)$ constitue une base de $\R_{n-1}[X]$, on obtient le résultat.
  • CechLM
    CechLM
    Rouletabille écrivait : http://www.les-mathematiques.net/phorum/read.php?34,1017583,1017775#msg-1017775
    [Inutile de recopier un message présent sur le forum, même de 3ans en arrière. Un lien suffit. AD]
    Que voulez-vous dire par formule d'inversion de Désiré André ?
  • Math Coss
    Math Coss
    Visiblement, c'est connu comme formule d'inversion de Pascal sur wikipedia.
  • CechLM
    CechLM
    Comment l'appliquez vous ici ? (a(n) = , b(n) = )
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 3

HéhéhéMathurin +1 Invité