Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques LycéeOn parle exclusivement de maths, niveau lycée. TerminaleForum de terminale DénombrementTopics traitant de dénombrement [tout]Lister tous les topics de mathématiques
Niveau terminale
Partager :

Question limite programme (Combinatoires)

Posté par
Ljubo 05-07-08 à 19:40

On montre tout d'abord en question 1) que pn x kn-p = p+kn kp+k

Puis, en développant [(1+X)-X]^n à l'aide de la formule du binome de Newton, montrer que (de p=0 à n-k) (-1)^p x pn kp+k=O
Si quelqu'un a une idée, merci d'avance!

Posté par
Nicolas_75 Correcteurre : Question limite programme (Combinatoires) 06-07-08 à 17:12

Bonjour,

Tu es 100 % sur de l'énonce, lettre par lettre ?
En effet, j'arrive à un résultat proche, mais pas exact.
J'ai aussi pu me tromper.

Nicolas

Posté par
xunilre : Question limite programme (Combinatoires) 06-07-08 à 17:15

bonjour,

moi aussi j'étais en train de le chercher.

la première égalité est bonne quand à la somme ... donc merci de corriger l'énoncé si erreur.

Posté par
Ljubore : Question limite programme (Combinatoires) 06-07-08 à 17:23

En effet il y a erreur de ma part, toutes mes excuses...
Il s'agit de (de p=0 à n-k) (-1)^p x pn x kn-p=O

Personnellement j'ai utilisé (1-1)^n pour montrer que cette expression vaut 0, mais il est précisé dans l'énoncé qu'il faut utiliser [(1+X)-X]^n, mais par cette méthode je n'arrive pas au résultat.
Merci à vous : )

Posté par
Nicolas_75 Correcteurre : Question limite programme (Combinatoires) 06-07-08 à 17:23

Posté par
Ljubore : Question limite programme (Combinatoires) 06-07-08 à 17:28

Désolé, j'ai un peu de mal avec les formules mathématiques sur l'ordinateur

Posté par
Nicolas_75 Correcteurre : Question limite programme (Combinatoires) 06-07-08 à 17:33

3$1=1^n

3$1=\left((1+X)-X\right)^n

On applique le binôme de Newton :

3$1=\Bigsum_{0\le p\le n}(-1)^p{n\choose p}X^p(1-X)^{n-p}

On applique à nouveau le binôme de Newton :

3$1=\Bigsum_{0\le p\le n}(-1)^p{n\choose p}X^p\Bigsum_{0\le k\le n-p}{n-p\choose k}X^{n-p-k}

On regroupe les sommes :

3$1=\Bigsum_{0\le p\le n\\0\le k\le n-p}(-1)^p{n\choose p}{n-p\choose k}X^{n-k}

Or, en s'aidant d'un petit schéma, on voit que
3$0\le p\le n\\0\le k\le n-p
est équivalent à :
3$0\le k\le n\\0\le p\le n-k

Donc :

3$1=\Bigsum_{0\le k\le n\\0\le p\le n-k}(-1)^p{n\choose p}{n-p\choose k}X^{n-k}

On sépare les sommes :

3$1=\Bigsum_{0\le k\le n}\left(\Bigsum_{0\le p\le n-k}(-1)^p{n\choose p}{n-p\choose k}\right)X^{n-k}

Pour que le membre de droite soit égal à 1, il faut que tous les coefficients de
X^{n-k} (pour n < k) soient nuls, donc :

3$\fbox{\Bigsum_{0\le p\le n-k}(-1)^p{n\choose p}{n-p\choose k}=0}

Sauf erreur.

Nicolas

Posté par
Ljubore : Question limite programme (Combinatoires) 06-07-08 à 17:56

Merci beaucoup : )
Je ne comprends pas par contre les deux premières applications du binôme, sachant que l'on part de [(1+X-X]^n, n'est ce pas égal à (de 0 à n) pn x (1+X)^(n-p) x (-X)^p ?

Posté par
Ljubore : Question limite programme (Combinatoires) 06-07-08 à 18:11

Si ça y est j'ai compris, par contre il doit s'agir de (1+X)^n et non (1-X)^n je pense.
Merci beaucoup à vous !

Posté par
Ljubore : Question limite programme (Combinatoires) 06-07-08 à 18:21

Si j'ai finalement quand même une question. Pourquoi peut-on regrouper les sommes?

Posté par
Nicolas_75 Correcteurre : Question limite programme (Combinatoires) 06-07-08 à 18:59

C'est bien 1+X. Faute de frappe.

On peut toujours regrouper les sommes.

Posté par
Ljubore : Question limite programme (Combinatoires) 06-07-08 à 19:06

Pour une addition de sommes je comprends bien mais même quand il s'agit d'un produit de sommes? Je ne comprends pas vraiment pourquoi, n'y a t-il pas plus de termes dans le produit de sommes qu'il n'y en a si on réunit les deux ? Je suis dans le flou ^^

Posté par
xunilre : Question limite programme (Combinatoires) 06-07-08 à 20:58

re,

juste nicolas, pourquoi as t-on ton équivalence pour 0\le p \le n-k ?

Posté par
Ljubore : Question limite programme (Combinatoires) 06-07-08 à 21:46

Mais si tous les coefficients de X^(n-k) valent 0 alors la somme vaut 0 et non 1, non?

Posté par
Ljubore : Question limite programme (Combinatoires) 06-07-08 à 22:14

C'est bon j'ai enfin compris, et beh... (c'est une question que j'ai trouvé d'un DS posé au lycée Louis-Le-Grand). Merci pour votre aide

Posté par
Nicolas_75 Correcteurre : Question limite programme (Combinatoires) 07-07-08 à 08:00

Citation :
Pour une addition de sommes je comprends bien mais même quand il s'agit d'un produit de sommes?


Il ne s'agit pas d'un produit de sommes, mais d'une somme de sommes.

Il faut lire !
3$1=\Bigsum_{0\le%20p\le%20n}\left((-1)^p{n\choose%20p}X^p\left(\Bigsum_{0\le%20k\le%20n-p}{n-p\choose%20k}X^{n-p-k}\right)\right)

Citation :
Je ne comprends pas vraiment pourquoi, n'y a t-il pas plus de termes dans le produit de sommes qu'il n'y en a si on réunit les deux ?


Je ne comprends pas ce que tu dis. Dans la somme regroupée, il y a (n+1)+n+(n-1)+...+1 termes.

Citation :
pourquoi as t-on ton équivalence pour 0=< p =< n-k ?


L'équivalence est entre :
3$\left\{0\le%20p\le%20n\\0\le%20k\le%20n-p\right.
et
3$\left\{0\le%20k\le%20n\\0\le%20p\le%20n-k\right.
Faire un dessin montrant les valeurs possibles de p et k pour s'en convaincre.

Citation :
Mais si tous les coefficients de X^(n-k) valent 0 alors la somme vaut 0 et non 1, non?


Dans mon message, j'ai bien précisé : "pour n < k". C'est une faute de frappe. Il fallait lire : "pour k < n".
Quel est la valeur du coefficient quand k=n ?
3$\Bigsum_{0\le p\le 0}(-1)^p{n\choose p}{n-p\choose n}=(-1)^0{n\choose 0}{n\choose n}=\fbox{1}
Tout va bien.

Citation :
lycée Louis-Le-Grand

Cela me rappelle donc des souvenirs (prépa).

Sauf erreur.

Nicolas

Posté par
xunilre : Question limite programme (Combinatoires) 07-07-08 à 08:07

oui ok c'est bon pour moi

merci

@+

Posté par
Nicolas_75 Correcteurre : Question limite programme (Combinatoires) 07-07-08 à 08:48

Pour l'équivalence, on peut s'appuyer sur ce schéma, où les "X" montrent les valeurs possibles de p et k :

4$\array{3,c.cccBCCC$_k\backslash^p&0&1&2&...&n-1&n\\ \\ \hdash~0&X&X&X&...&X&X\\ \\ 1&X&X&X&...&X&\\ \\ 2&X&X&X&...&&\\ \\ ...&X&X&...&&&\\ \\ n-1&X&X&&&&\\ \\ n&X&&&&&}

Posté par
Nicolas_75 Correcteurre : Question limite programme (Combinatoires) 07-07-08 à 16:51

Ljubo, pourrais-tu nous donner, juste par curiosité, la fin de l'énoncé ?

Merci d'avance,

Nicolas

Posté par
Ljubore : Question limite programme (Combinatoires) 07-07-08 à 22:22

Oui pas de soucis.
3) On pose Bn=(de k=0 à n) (-1)^k x kn x Ak   où les Ak sont des réels. Montrer que An=(de k=0 à n) (-1)^k kn x Bk
4)Application : soit E un ensemble fini non vide cardinal n.Notons Dn le nombre de permutations de E ne laissant aucun élement de E fixe.
Montrer que n!=(de k=0 à n)kn x dk
En déduire que dn=n! x (k=0 à n) (-1)^k/k!

Posté par
Nicolas_75 Correcteurre : Question limite programme (Combinatoires) 08-07-08 à 21:04

3)

3$\Bigsum_{0\le k\le n}(-1)^k{n\choose k}B_k = \Bigsum_{0\le k\le n}(-1)^k{n\choose k} \Bigsum_{0\le p\le k}(-1)^p{k\choose p}A_p

On regroupe les sommes :

3$\Bigsum_{0\le k\le n}(-1)^k{n\choose k}B_k = \Bigsum_{0\le k\le n\\0\le p\le k}(-1)^{k+p}{n\choose k}{k\choose p}A_p

On remplace les indices sous la somme par un arrangement équivalent (faire un schéma similaire, mais différent, de celui du message ci-dessus) :

3$\Bigsum_{0\le k\le n}(-1)^k{n\choose k}B_k = \Bigsum_{0\le p\le n\\p\le k\le n}(-1)^{k+p}{n\choose k}{k\choose p}A_p

Or 3${n\choose k}{k\choose p}={n\choose p}{n-p\choose k-p} (facile à montrer), donc :

3$\Bigsum_{0\le k\le n}(-1)^k{n\choose k}B_k = \Bigsum_{0\le p\le n\\p\le k\le n}(-1)^{k+p}{n\choose p}{n-p\choose k-p}A_p

On sépare à nouveau les sommes :

3$\Bigsum_{0\le k\le n}(-1)^k{n\choose k}B_k = \Bigsum_{0\le p\le n}(-1)^{p}{n\choose p} \left\{\Bigsum_{p\le k\le n}(-1)^k{n-p\choose k-p} \right\} A_p

Dans la dernière somme, on fait le changement d'indice 3$k\to k+p :

3$\Bigsum_{0\le k\le n}(-1)^k{n\choose k}B_k = \Bigsum_{0\le p\le n}(-1)^{p}{n\choose p} \left\{\Bigsum_{0\le k\le n-p}(-1)^{k+p}{n-p\choose k} \right\} A_p

3$\Bigsum_{0\le k\le n}(-1)^k{n\choose k}B_k = \Bigsum_{0\le p\le n}(-1)^{\fbox{2p}}{n\choose p} \left\{\Bigsum_{0\le k\le n-p}(-1)^{k}{n-p\choose k} \right\} A_p

On reconnaît dans l'accolade le développement de 3$(1-1)^{n-p} :

3$\Bigsum_{0\le k\le n}(-1)^k{n\choose k}B_k = \Bigsum_{0\le p\le n}{n\choose p} (1-1)^{n-p} A_p

Or 3$(1-1)^{n-p} est nul sauf quand 3$p=n :

3$\Bigsum_{0\le k\le n}(-1)^k{n\choose k}B_k = {n\choose n} 0^0 A_n

3$\Bigsum_{0\le k\le n}(-1)^k{n\choose k}B_k = A_n

CQFD

Sauf erreur.

Nicolas

Posté par
Nicolas_75 Correcteurre : Question limite programme (Combinatoires) 08-07-08 à 21:14

4)a)

Le nombre de permutations de |[1;n]| est n!

Pour trouver toutes ces permutations, on peut :
- garder n points fixes ({n\choose n}=1 choix possible) et permuter sans point fixe les n-n=0 autres points (D0 choix possibles)
- garder n-1 points fixes ({n\choose n-1} choix possibles) et permuter sans point fixe les n-(n-1)=1 autres points (D1 choix possibles)
- garder n-2 points fixes ({n\choose n-2} choix possibles) et permuter sans point fixe les n-(n-2)=2 autres points (D2 choix possibles)
...
- garder n-n=0 points fixes ({n\choose n-n}=1 choix possible) et permuter sans point fixe les n-(n-n)=n autres points (Dn choix possibles)

Donc :

3$n!=\Bigsum_{0\le k\le n}{n\choose n-k}d_k

3$\fbox{n!=\Bigsum_{0\le k\le n}{n\choose k}d_k}

Posté par
Nicolas_75 Correcteurre : Question limite programme (Combinatoires) 08-07-08 à 21:20

4)b)

Comme 3$(-1)^{2k}=1, on déduit de la question précédente :

3$n!=\Bigsum_{0\le k\le n}(-1)^k{n\choose k}(-1)^kd_k

On pose 3$A_k=(-1)^kd_k. Alors :

3$n!=\Bigsum_{0\le k\le n}(-1)^k{n\choose k}A_k

On déduit alors de 3) :

3$A_n=\Bigsum_{0\le k\le n}(-1)^k{n\choose k}k!

3$(-1)^nd_n=\Bigsum_{0\le k\le n}(-1)^k{n\choose k}k!

3$(-1)^nd_n=\Bigsum_{0\le k\le n}(-1)^k\frac{n!}{(n-k)!}

3$(-1)^nd_n=\Bigsum_{0\le k\le n}(-1)^k\frac{n!}{(n-k)!}

3$d_n=\Bigsum_{0\le k\le n}(-1)^{k-n}\frac{n!}{(n-k)!}

3$d_n=\Bigsum_{0\le k\le n}(-1)^{n-k}\frac{n!}{(n-k)!}

3$d_n=n!\Bigsum_{0\le k\le n}(-1)^{n-k}\frac{1}{(n-k)!}

Dans la somme, on procède au changement d'indice 3$k\to n-k :

3$d_n=n!\Bigsum_{0\le k\le n}(-1)^{k}\frac{1}{k!}

3$\fbox{d_n=n!\Bigsum_{0\le k\le n}\frac{(-1)^{k}}{k!}}


Rechercher
Menu
Espace membre
13 visiteurs
Changer d'île

Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :

Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1741 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !