Bonjour,
J'aurais besoin d'une indication (pas la réponse!) pour résoudre le problème suivant :
Soit f(n,m,k) le nombre de mots binaires avec n 1 et m 0 tels qu'il n'y ait pas k 1 consécutifs. Trouver une relation de récurrence pour f avec trois termes exactement dans le membre droit.
J'arrive à trouver la réponse en forme explicite (un coefficient binomial avec pleins de termes dedans) mais pas de relation de récurrence...
Relation de récurrence à 3 variables
13 messages
- Page 1 sur 1
par prof2mathenligne@gmail.co » 02 Mai 2015, 13:35
à mon avis tu dois avoir faux: si on te demande une relation de récurrence c'est qu'on ne peut pas trouver directement la formule explicite...
par Ben314 » 02 Mai 2015, 14:39
Pour fabriquer un tel mot
- Soit tu rajoute un 0 à la fin d'un mot avec n 1, m-1 0 et pas k 1 consécutifs : f(n,m-1,k) possibilités.
- Soit tu rajoute un 1 à la fin d'un mot avec n-1 1, m 0 et pas k 1 consécutifs : f(n-1,m,k) possibilités MAIS le mot en question ne doit pas se terminer 0111...1 (avec k-1 1) et il y a f(n-k,m-1,k) tels mots.
Conclusion : f(n,m,k)=f(n-1,m,k)+f(n,m-1,k)-f(n-k,m-1,k)
(il y a sans doute d'autres relations... mais celle là correspond aux consignes)
- Soit tu rajoute un 0 à la fin d'un mot avec n 1, m-1 0 et pas k 1 consécutifs : f(n,m-1,k) possibilités.
- Soit tu rajoute un 1 à la fin d'un mot avec n-1 1, m 0 et pas k 1 consécutifs : f(n-1,m,k) possibilités MAIS le mot en question ne doit pas se terminer 0111...1 (avec k-1 1) et il y a f(n-k,m-1,k) tels mots.
Conclusion : f(n,m,k)=f(n-1,m,k)+f(n,m-1,k)-f(n-k,m-1,k)
(il y a sans doute d'autres relations... mais celle là correspond aux consignes)
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius
par t.itou29 » 02 Mai 2015, 19:51
Ben314 a écrit:Pour fabriquer un tel mot
- Soit tu rajoute un 0 à la fin d'un mot avec n 1, m-1 0 et pas k 1 consécutifs : f(n,m-1,k) possibilités.
- Soit tu rajoute un 1 à la fin d'un mot avec n-1 1, m 0 et pas k 1 consécutifs : f(n-1,m,k) possibilités MAIS le mot en question ne doit pas se terminer 0111...1 (avec k-1 1) et il y a f(n-k,m-1,k) tels mots.
Conclusion : f(n,m,k)=f(n-1,m,k)+f(n,m-1,k)-f(n-k,m-1,k)
(il y a sans doute d'autres relations... mais celle là correspond aux consignes)
Merci ! Ca faisait pas mal de temps que j'étais bloqué sur cette question alors qu'en fait c'est pas trop compliqué (toujours pareil quand on voit la solution :ptdr: )
Maintenant il faut que j'utilise les fonctions génératrice pour trouver une forme "explicite" sous forme d'une somme avec des factorielles, si j'y arrive et si ma formule avec des coeffs binomiaux est vraie ça va faire une belle identité !
par t.itou29 » 02 Mai 2015, 20:06
prof2mathenligne@gmail.co a écrit:à mon avis tu dois avoir faux: si on te demande une relation de récurrence c'est qu'on ne peut pas trouver directement la formule explicite...
C'est probable, voici mon raisonnement:
1) On divise n par (k-1):
2) on regroupe les 1 en q+1 groupes séparés par un 0 entre les deux (q groupe de k-1 et 1 de r)
3) il reste m-q 0 à placer dans n+1 emplacements (choix avec répétion):
Et il s'agit du nombre de mots souhaité.
par Ben314 » 02 Mai 2015, 20:30
Effectivement ça déconne complètement ton raisonnement :
Prenons par exemple n=7, k=4, et m=3 tu as n=q(k-1)+r avec q=2 et r=1 donc ta méthode, consiste à intercaler m-q=1 unique 0 dans un des "interstices" de 111011101
a) Déjà, des "interstices", en comptant celui du début et le dernier, tu en as pas n+1=8 mais n+q+1=10
b) Ensuite, que tu mette le 0 dans le 4em ou le 5em "interstice", ça fait la même configuration d'arrivée 1110011101 donc tu compte plusieurs fois certains éléments.
c) Par contre, toujours avec ta méthode, il est impossible d'obtenir la configuration 1101101101 pourtant parfaitement "dans les clous" donc il y a certains élément que tu ne compte pas du tout.
Bilan... pas terrible...
Prenons par exemple n=7, k=4, et m=3 tu as n=q(k-1)+r avec q=2 et r=1 donc ta méthode, consiste à intercaler m-q=1 unique 0 dans un des "interstices" de 111011101
a) Déjà, des "interstices", en comptant celui du début et le dernier, tu en as pas n+1=8 mais n+q+1=10
b) Ensuite, que tu mette le 0 dans le 4em ou le 5em "interstice", ça fait la même configuration d'arrivée 1110011101 donc tu compte plusieurs fois certains éléments.
c) Par contre, toujours avec ta méthode, il est impossible d'obtenir la configuration 1101101101 pourtant parfaitement "dans les clous" donc il y a certains élément que tu ne compte pas du tout.
Bilan... pas terrible...
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius
par t.itou29 » 02 Mai 2015, 20:39
Ben314 a écrit:Effectivement ça déconne complètement ton raisonnement :
Prenons par exemple n=7, k=4, et m=3 tu as n=q(k-1)+r avec q=2 et r=1 donc ta méthode, consiste à intercaler m-q=1 unique 0 dans un des "interstices" de 111011101
a) Déjà, des "interstices", en comptant celui du début et le dernier, tu en as pas n+1=8 mais n+q+1=10
b) Ensuite, que tu mette le 0 dans le 4em ou le 5em "interstice", ça fait la même configuration d'arrivée 1110011101 donc tu compte plusieurs fois certains éléments.
c) Par contre, toujours avec ta méthode, il est impossible d'obtenir la configuration 1101101101 pourtant parfaitement "dans les clous" donc il y a certains élément que tu ne compte pas du tout.
Bilan... pas terrible...
Dans ton exemple tu a pris des groupes de 3 au lieu de 2 (le nombre d'élément des groupes complets q est le quotient dans la division de n par k-1 et non k), avec des groupes de 2 ça marche je crois
par t.itou29 » 02 Mai 2015, 20:40
Ben314 a écrit:Effectivement ça déconne complètement ton raisonnement :
Prenons par exemple n=7, k=4, et m=3 tu as n=q(k-1)+r avec q=2 et r=1 donc ta méthode, consiste à intercaler m-q=1 unique 0 dans un des "interstices" de 111011101
a) Déjà, des "interstices", en comptant celui du début et le dernier, tu en as pas n+1=8 mais n+q+1=10
b) Ensuite, que tu mette le 0 dans le 4em ou le 5em "interstice", ça fait la même configuration d'arrivée 1110011101 donc tu compte plusieurs fois certains éléments.
c) Par contre, toujours avec ta méthode, il est impossible d'obtenir la configuration 1101101101 pourtant parfaitement "dans les clous" donc il y a certains élément que tu ne compte pas du tout.
Bilan... pas terrible...
Oui effectivement faut que je revois ça...
J'avais essayé avec 2 exemples et ça marchait, j'avais dû avoir de la chance dans le choix des exemples
Pour les remarques a et b j'ai choisi n+1 justement pour ne pas compter deux fois certaines config et pour la c ça doit marcher quand il y a assez de 0 pour aller dans tous les interstices, toujours est-il que ça marche pas dans le cas général...
par Ben314 » 03 Mai 2015, 08:57
Si ça t'intéresse, il y a une façon assez naturelle d'obtenir une formule donnant f(n,m,k) :
On prend n,m,k fixés (pour éviter les indices de partout)
Si\in{\mathbb N}^{m+1}\text{ t.q. }n_0+n_1+...+n_m=s\})
alors ={s+m\choose m})
Or=\text{card}(B)\)
où \in{\mathbb N}^{m+1}\text{ t.q. }n_0+n_1+...+n_m=n\text{ et } n_i<k\text{ pour tout }i\})
Naturellement, pour tout
on introduit \in{\mathbb N}^{m+1}\text{ t.q. }n_0+n_1+...+n_m=n\text{ et } n_j\geq k\})
et on utilise le principe d'inclusion-exclusion.
On prend n,m,k fixés (pour éviter les indices de partout)
Si
Or
Naturellement, pour tout
et on utilise le principe d'inclusion-exclusion.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius
par Ben314 » 03 Mai 2015, 09:05
Si ça t'intéresse, il y a une façon assez naturelle d'obtenir une formule donnant f(n,m,k) :
On prend n,m,k fixés (pour éviter les indices de partout)
On a=\text{card}(A)\)
où \in{\mathbb N}^{m+1}\text{ t.q. }n_0+n_1+...+n_m=n\text{ et } n_i<k\text{ pour tout }i\})
Naturellement, pour tout on introduit \in{\mathbb N}^{m+1}\text{ t.q. }n_0+n_1+...+n_m=n\text{ et } n_j\geq k\})
et on utilise le principe d'inclusion-exclusion.
Rappel : Si\in{\mathbb N}^{m+1}\text{ t.q. }n_0+n_1+...+n_m=s\})
alors ={s+m\choose m})
On prend n,m,k fixés (pour éviter les indices de partout)
On a
Naturellement, pour tout
et on utilise le principe d'inclusion-exclusion.
Rappel : Si
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius
par t.itou29 » 04 Mai 2015, 16:57
Ben314 a écrit:Si ça t'intéresse, il y a une façon assez naturelle d'obtenir une formule donnant f(n,m,k) :
On prend n,m,k fixés (pour éviter les indices de partout)
On a
Naturellement, pour tout
et on utilise le principe d'inclusion-exclusion.
Rappel : Si
Je vais essayer , merci !
par t.itou29 » 10 Mai 2015, 17:27
Ben314 a écrit:Si ça t'intéresse, il y a une façon assez naturelle d'obtenir une formule donnant f(n,m,k) :
On prend n,m,k fixés (pour éviter les indices de partout)
On a
Naturellement, pour tout
et on utilise le principe d'inclusion-exclusion.
Rappel : Si
J'ai enfin pris le temps d'y réfléchir ce weekend. Voici ce que j'ai fait:
On a
D'après le principe d'inclusion/exclusion:
Or
Après je ne sais pas si la somme est "calculable" ? J'ai pas encore essayé mais à première vue...
par Ben314 » 10 Mai 2015, 18:57
Sur le principe, c'est exactement ça, (modulo que c'est des réunion et pas des intersection).
Après, j'ai pas regardé si c'est la même chose que ce que j'avais trouvé (le papier est depuis longtemps parti à la poubelle)
Et enfin, ça m'étonnera un peu que ça se simplifie le truc en question.
Après, j'ai pas regardé si c'est la même chose que ce que j'avais trouvé (le papier est depuis longtemps parti à la poubelle)
Et enfin, ça m'étonnera un peu que ça se simplifie le truc en question.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius
13 messages
- Page 1 sur 1
Qui est en ligne
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 107 invités
Tu pars déja ?
Fais toi aider gratuitement sur Maths-forum !
Créé un compte en 1 minute et pose ta question dans le forum ;-)
Identification
Pas encore inscrit ?
Ou identifiez-vous :