Problèmes de combinatoire

[invitee75a2d43]

Bonjour, j´ai deux problèmes de deux exos différents où je n´avance absolument pas. Je n´ai que des résultats partiels mais je n´arrive pas à prouver ce qu´on me demande. Il s´agit de la chose suivante:

On a deux entiers k et n, 2 <= k <= n et n <= 3
On définit P(n,k) comme le nombre de parties de [1,n] inter IN à k éléments qui ne contiennent pas deux entiers consécutifs.

J´ai calculé P(n,2) = (n-1)(n-2)/2
On me demande de démontrer que P(n,k) = P(n-1,k) + P(n-2,k-1)

J´ai essayé par récurrence mais j´ai cafouillé. Dans la question d´après on me demande de prouver par réccurence que:

P(n,k) = (n-k+1)! /k!(n-2k+1)!

Je suppose qu´il faut utiliser le résultat de la première question pour prouver la deuxième égalité. Mais après bien des essais je n´ai plus d´idées.

Quelqu´un pourrait-il me mettre sur la voie s´il a une idée?

Merci d´avance

christophe
-----

[invite986312212]

je suppose que n>=3 et pas le contraire (?)
une partie de {1,..,n} qui répond aux conditions, ou bien elle contient n ou bien elle ne le contient pas. Si elle ne le contient pas, tu peux lui faire correspondre la partie de {1,..,n-1} à k éléments non consécutifs. Cette correspondance est bijective. Si elle contient n, elle ne peut contenir (n-1) et donc on peut lui faire correspondre la partie de {1,..(n-2)} à (k-1) éléments non consécutifs. Là aussi il y a bijection.

[invitee75a2d43]

je suppose que n>=3 et pas le contraire (?)

oui tu supposes bien pardon, petite erreur d´énoncé de ma part.