Denombrement et recurrence

[fatal_error]

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?

[nodjim]

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]

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]

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).

[Doraki]

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]

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

[fatal_error]

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.

[Doraki]

ce sont les mots qui ont autant de 0 que de 1 qui engendrent le plus de mots.

[fatal_error]

une piste pour le montrer?

[Doraki]

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]

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