Dénombrement !!

[mayele]

Bonjour à tous ! J'ai un exercice qui me pose quelques soucis!

On note Vn le nombre de parties de [1,n] ne contenant pas d'entiers consecutifs. Montrer que pour tout n>=3, on a Vn= Vn-1+Vn-2.

J'ai pensé à deux voies, l'une je dirai analytique en faisant une récurrence double sur n car cette suite ressemble à la suite de fibonacci, pour l'étape d'initialisation au rang n=3 ça marche sans problème ! Après c'est pour le rang n et n+1 que ça bloque car je ne sais pas dénombrer un ensemble qui serait bijectif avec [1,n] ne contenant pas d'entiers consécutifs.... Du moins je ne sais pas trop où aller avec ça !!

L'autre voie pourrait être combinatoire, en raisonant comme pour le triangle de pascal mais là encore ...

[Nightmare]

Salut !

Pour compter le nombre de parties total qui ne contiennent pas d'entiers consécutifs, il suffit de compter le nombre de parties à m éléments ( ) non consécutifs et de les additionner.

Or, choisir (avec ) non consécutifs revient à choisir quelconques dans et on a donc possibilités.

Pour conclure, c'est effectivement le triangle de pascal !

[ffpower]

Sinon, simplement distinguer les parties qui contiennent n et les parties qui contiennent pas n

[Skullkid]

Dans le même ordre d'idées que ffpower, on peut dire que les parties de |[1,n]| qui nous intéressent sont de deux types :

- Celles qui ne contiennent pas n, et qui sont alors exactement les parties de |[1,n-1]| sans entiers consécutifs.
- Celles qui contiennent n, et qui alors ne contiennent pas n-1 et sont donc exactement les avec P décrivant l'ensemble des parties de |[1,n-2]| sans entiers consécutifs.

[mayele]

Merci beaucoup pour vos réponses, parce que je trouve ça intéressant mais ç'est comme même évident au début le dénombrement, et donc j'aimerai bien avoir la rigueur pour bien rédiger les exos surtout en probas...

Mais j'ai l'impression que les idées de Nightmare et Skullkid se complètent en ce sens que pour Nightmare, tu dénombres le nombre de parties d'un ensemble [1,n] ne contenant pas d'entiers consécutifs en gros trouver la valeur de Vn, c'est ce que j'avais fait mais là ou j'ai vraiment séché c'est pour Vn-1 qui serait le nombre de parties d'un ensemble [1,n-1] ne contenant pas d'entiers consécutifs (et ne contenant pas n) et ensuite Vn-2 qui serait le nombre de parties d'un ensemble [1,n-2] ne contenant pas d'entiers consécutifs ( et ne contenant pas n et n-1) et je me demande s'il ne contient pas l'ensemble des entiers consécutifs définis par Vn ou bien je confonds totalement :we: enfin j'ai du mal à entrevoir l'égalité des parties...

Et sinon avec un raisonnement par récurrence, ça marche pas ou bien c'est pas adapté ???

[mayele]

Quelqu'un peut me répondre pleasee :id:

[Skullkid]

Pour la récurrence, ça ne marchera pas puisqu'il faut déjà avoir une relation entre le rang n et les précédents, et c'est précisément cette relation qu'on souhaite obtenir.

[Ben314]

Salut,
A mon avis, vu l'énoncé, la réponse adaptée est celle de ffpower (détaillée par skullkid) : celle de Nightmare te donnerais directement la valeur de Vn ce qui ne semble pas être la logique de l'exercice.

Quand à la récurrence, qu'est ce que tu veut écrire ?
Je ne vois vraiment pas à quoi peut te servir l'hypothèse V(n-1)=V(n-2)+V(n-3) pour montrer que V(n)=V(n-1)+V(n-2) alors que tu n'a pour le moment aucune formule du type V(n)=quelque chose !!!

Edit : Grilled par Skullkid qui dit... la même chose...