Denombrement et recurrence
Discussion générale entre passionnés et amateurs de mathématiques sur des sujets mathématiques variés
-
fatal_error
- Modérateur
- Messages: 6610
- Enregistré le: 22 Nov 2007, 13:00
-
par fatal_error » 13 Jan 2011, 17:11
hello,
un
probleme a l'instant trouvé dans le forum lycée :
je restitue l'énoncé :
De combien de manières peut-on compléter un champs de n bits de facon à ce que tous tes champs de n+1 bits soient tous différents les uns des autres.
ex : nous avons 000
si on rajoute un bit 0, on pourrait le rajouter avant le premier zéro, 0x000 ou à la fin... 000x0etc...mais on obtient le même champs, donc on ne compte qu'une seule fois le mot obtenu. En revanche, le 1 donne 4 mots différents.
(1x000, 0x1x00,...)
on se donne un certain mot : 0110.
Combien y-a-t'il de mots différents de, mettons, n bits, issus de ce dernier mot?
la vie est une fête
-
nodjim
- Membre Complexe
- Messages: 3241
- Enregistré le: 24 Avr 2009, 17:35
-
par nodjim » 13 Jan 2011, 19:08
Soit un mot de n chiffres. il y a c chiffres différents.
chaque chiffre c est présent f fois.
Le nombre de mots différents qu'on peut faire est, selon moi:
n!/(f1!*f2!*...fc!)
-
Doraki
- Habitué(e)
- Messages: 5021
- Enregistré le: 20 Aoû 2008, 12:07
-
par Doraki » 13 Jan 2011, 19:23
Je suis pas sur d'avoir compris ta question.
Tu demandes pour tout n>=4, le nombre de mots w à n lettres (sur l'alphabet {0,1}) tels que w contienne quelquepart et dans l'ordre, les lettres 0,1,1,0 ?
Genre pour n=5, il y a 6 mots
00110
01010
01100
01101
01110
10110
?
-
fatal_error
- Modérateur
- Messages: 6610
- Enregistré le: 22 Nov 2007, 13:00
-
par fatal_error » 13 Jan 2011, 20:00
Tu demandes pour tout n>=4, le nombre de mots w à n lettres (sur l'alphabet {0,1}) tels que w contienne quelquepart et dans l'ordre, les lettres 0,1,1,0 ?
pas forcément dans l'ordre.
si le mot contient deux 0 et deux 1, il faut que le mot de n lettres contienne au moins deux 0 et deux 1.
la question subsidiaire (dont je n'ai pas la réponse) étant pour quel type de mot y-t-il le plus de mots "engendrés" par le mot d'origine. (combien de zéro présents dans le mot).
la vie est une fête
-
Doraki
- Habitué(e)
- Messages: 5021
- Enregistré le: 20 Aoû 2008, 12:07
-
par Doraki » 13 Jan 2011, 20:09
Donc les mots issus de "0110" et de "1010" c'est les mêmes mots,
et dans ma liste il faut rajouter les 14 mots
00011
00101
00111
01001
01011
10001
10010
10011
10100
10101
11000
11001
11010
11100
pour arriver à 20 (= 2^n - (2n+2)) mots ?
-
fatal_error
- Modérateur
- Messages: 6610
- Enregistré le: 22 Nov 2007, 13:00
-
par fatal_error » 13 Jan 2011, 20:20
vi.
reste pour un mot quelconque initial (dont on connait le nombre de zéros).
et ce qui va avec, avec quel genre de mots initial (mettons de taille 5), obtient t-on le plus de mots engendrés de taille n
la vie est une fête
-
fatal_error
- Modérateur
- Messages: 6610
- Enregistré le: 22 Nov 2007, 13:00
-
par fatal_error » 13 Jan 2011, 20:21
vi.
reste à trouver pour un mot quelconque initial (dont on connait le nombre de zéros, et mettons de taille 5), et plus intéressant, pour quel type de mot initial a-t-on le plus de mots engendrés de taille n.
la vie est une fête
-
Doraki
- Habitué(e)
- Messages: 5021
- Enregistré le: 20 Aoû 2008, 12:07
-
par Doraki » 13 Jan 2011, 20:26
ce sont les mots qui ont autant de 0 que de 1 qui engendrent le plus de mots.
-
fatal_error
- Modérateur
- Messages: 6610
- Enregistré le: 22 Nov 2007, 13:00
-
par fatal_error » 13 Jan 2011, 20:28
une piste pour le montrer?
la vie est une fête
-
Doraki
- Habitué(e)
- Messages: 5021
- Enregistré le: 20 Aoû 2008, 12:07
-
par Doraki » 13 Jan 2011, 23:17
Ben il faut regarder pour (m,p) fixé tel que m+p = 5, combien y'a de mots engendrés par 0^m.1^p, c'est à dire combien y'a de mots de n lettres contenant au moins m 0s et p 1s ; ou plutôt combien y'a de mots de n lettres qui ne sont pas engendrés par ce machin, c'est à dire qui ont moins de m 0s ou moins de p 1s.
Quand t'as trouvé la formule, tu regarde la croissance quand n grandit, et puis tu compares quand tu fais varier m et p.
-
fatal_error
- Modérateur
- Messages: 6610
- Enregistré le: 22 Nov 2007, 13:00
-
par fatal_error » 14 Jan 2011, 01:28
ui,
perso j'ai
avec N nombre de bits du mot d'origine, s_n, nombre de mots engendrés de taille n, n>N
on pose
et on cherche le min de
De souvenir, on pouvait utiliser une fonction f(x) pour trouver le sens de variation de la suite, mais bon, avec des combi...
Pis là, la soustraction ne m'apporte rien, ou alors chui miraud...
je dois pas avoir une bonne approche, mais jvois pas comment faire
la vie est une fête
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 19 invités