Combien de nombres a 16 chiffres est il possible de creer, sans répéter aucun chiffre plus de 3 fois

[james31]

Bonsoir a tous,

Je seche sur un probleme de math qui ne parait pas si difficile.

Commencons par un exemple simple:
Combien de nombre a 9 chiffres existent ils sans commencer par un 0.
On a initialement 10^9 possibilites.
La contrainte du 0 nous donne 9x10^8 possibilites.
La contrainte de ne pas reutiliser un chiffre nous donne:
9x9! possibilites (premier chiffre a 9 possibilites, le deuxieme aussi, le troisieme 9 ...)

Probleme: si je veux exclure tous les nombres ou l on utilise plus de 3 fois le meme chiffres, comment puis je faire?]

Ceci nous amene au probleme final:
16 chiffres composant un nombre, pas de 0 pour commencer, pas le droit de reutiliser le meme chiffres plus de 3 fois.
nombre initiale de possibilites: 10^16
apres la conditions: pas de zero; 9x10^15 possibilites.
derniere conditions: pas de chiffre qui se repetent plus de 3 fois... la je ne vois pas comment faire.

Merci de votre aide par avance

Bonne soirée

ps: désolé pour les accents, clavier qwerty.

[acx01b]

salut

un bon "brute force" :

je dirais que le résultat est égal à 9/10 du nombre de :
nombres à 16 ne contenant pas 4 fois le même chiffre

pour calculer ce nombre tu peux regarder si tu as utilisé 4,5,6, .. 10 chiffres différents dans tes 16 chiffres

ensuite calculer le nombre de façon de les choisir parmi 10, et enfin le nombre permutation de ta suite de chiffres

ça devrait prendre 5 minutes à calculer comme ça

[james31]

Quand tu parles de brute force, parles tu de faire un programme ou juste des "maths".

Je dois avouer ne pas vraiment suivre ton raisonement, si tu pouver me donner une idée plus précise peut etre en commencant le raisonnement (si ca prend 5 minutes ).

Merci et bonne soirée

[acx01b]

16 = 3 + 3 + 3 + 3 + 3 + 1
= 3 + 3 + 3 + 3 + 2 + 2
= 3 + 3 + 3 + 2 + 2 + 2 + 1
= ...
tu écris toutes les possibilités

ensuite si tu prends 3 + 3 + 3 + 2 + 2 + 2 + 1,
tu l'interprètes comme 3 fois un chiffre, 3 fois un autre, 3 fois encore un autre,
2 fois encore encore un autre, 2 fois ... et enfin une fois un dernier chiffre

pour compter le nombre de nombres correspondant à cette configuration, il faut compter combien de choix tu peux faire : il faut choisir 3 chiffres (parmis 10) qui seront répétés 3 fois, 3 (parmis 7) qui seront répétés 2 fois, et 1 qui sera répété une fois

= C(10,3) * C(7,3) * C(4,1) possibilités,

enfin il faut compter le nombre de permutations de ta combinaison =
16! / (3! * 3! * 3! * 2! * 2! * 2! * 1!)

[james31]

Merci pour ta réponses.

Les possibilites pour creer 16 comme tu me l as expliqué au début de ton message sont tres tres nombreuses mais si j ai bien comprit:
1/ Je les liste toutes
2/ pour chacune d entre elles je calcule les C(n,p) necessaire.
3/ pour ce qui est des permutations, je calcul les permutations possibles pour cette possibilité
4/ J additionne les combinaisons + les permutations
5/ je prend la deuxieme possibilite et je reprend a l etape 2, c est bien ca?

Je suis un peu fatigué mais j espere bien avoir comprit

Bonne soirée et merci de me confirmer tout ca

[acx01b]

non les partages de 16 en nombres <= 3 ne sont pas très nombreux,

3+3+3+3+3+1 est le même partage que 1+3+3+3+3+3 ...

donc il suffit d'écrire tes partages, et les nombres de tes partages par ordre décroissant comme j'ai fait pour n'en oublier aucun

3 + 3 + 3 + 3 + 3 + 1
3 + 3 + 3 + 3 + 2 + 2
3 + 3 + 3 + 3 + 2 + 1 + 1
3 + 3 + 3 + 3 + 1 + 1 + 1 + 1
3 + 3 + 3 + 2 + 2 + 2 + 1
3 + 3 + 3 + 2 + 2 + 1 + 1 + 1
3 + 3 + 3 + 2 + 1 + 1 + 1 + 1 + 1
3 + 3 + 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1
3 + 3 + 2 + 2 + 2 + 2 + 2
...

bien sûr :
4/ J additionne les "combinaisons x les permutations"

[james31]

Merci de ta patience

Je tenterai ca demain matin et je posterai les details

Si tu peux me donner ton avis sur ma reponse

Je te remercie pour ton aide

Bonne nuit

[james31]

Bonjour

J ai reussit a faire ce que tu m avais dit, le soucis est que je viens de m appercevoir que ton algorithm ne prend pas en compte le fait que le nombre ne puisse pas commencer par 0. Il faut donc changer quelque chose quelque part ... est ce dans les combinaisons ou dans les permutations que cette condition entre en jeu.
Donc le choix du premier nombre est limite, donc il s agit de 1 a 9, sans le 0. Comment faire rentrer cette condition en jeu?

Qu en pensez vous?

edit: je viens de me rendre compte que tu avais ecrit 9/10 du nombre final trouvé, quelqu un peut m expliquer pour 90%, dire que ca ne commence pas par un, enleve exactement 10% du total?

[acx01b]

je pense effectivement que si tu autorises le 0 au début, tu t'apperçois qu'il y en a autant qui commencent par 0, par 1, par 2 .... donc 10% qui commencent par 0

dis moi combien tu trouves comme résultat

[james31]

J ai trouvee 18 possibilitees

J ai ecrit un code matlab pour resoudre le probleme avec ton algo.
Je trouve comme solution:
5694800000000000

Qu en penses tu?

[james31]

Pour verifier mon algo j ai teste avec 4 chiffres composant le nombre et ca ne marche pas, l erreur vient peut etre de mon code(si tu as le temps d y jeter un oeil).

Si je prend 4 chiffres qui compose un nombre, possibilites:
1/ 1+1+1+1
2/ 3+1
3/ 2+2
4/ 2+1+1

Donc 4 possibilites.

1/ J ai quatre chiffre different.
Je choisis donc 1 chiffre parmis 10 puis 1 parmis 9 puis 1 parmis 8 puis 1 parmis 7.
Donc j ai : C(10,1)*C(9,1)*C(8,1)*C(7,1)
Que je multiplie par 4! / ((1!)^4). =5040
2/ Meme procedure:
C(10,3)*C(7,1) * ((4!/(3!*1!))=3360
3/ C(10,2)*C(8,2) *((4!/(2!^2))=7560
4/ C(10,2)*C(9,1)*C(8,1) *((4!)/2!)=38880

Si j additionne tout ca j obtient un nombre bien plus grand que 10 000 (toutes les possibilites de nombres a 4 chiffres) a savoir 49840.

Peux tu m expliquer ce qui ne va pas dans mon raisonnement (j ai essayé d appliquer ton algo a la lettre non?).

Si je ne dit pas de betises le nombre que je suis sensé obtenir est 9990 non?
Pas de 0000, 1111, 2222, ..., 9999 (ce qui revient a repeter 4 fois le meme nombre).

Merci par avance a tous ceux qui pourront m aider

ps: suite a une erreur dans mon code (1 a la place de i), le resultat pour 16 chiffres serait:
3745000000000000

[james31]

J ai re re refait le calcul:
Si je prend 4 chiffres qui compose un nombre, possibilites:
1/ 1+1+1+1
2/ 3+1
3/ 2+2
4/ 2+1+1

Donc 4 possibilites.

1/ J ai quatre chiffre different.
[edit] encore des erreurs, je vais le re faire calmement

Peux tu m expliquer ce qui ne va pas dans mon raisonnement (j ai essayé d appliquer ton algo a la lettre non?).
Je pense bien que je me trompe dans le raisonnement quelque part.

Si je ne dit pas de betises le nombre que je suis sensé obtenir est 9990 non?
Pas de 0000, 1111, 2222, ..., 9999 (ce qui revient a repeter 4 fois le meme nombre).

Merci par avance a tous ceux qui pourront m aider

[acx01b]

1/ C(10,4) * 4! = 5040
2/ C(10,1) * C(9,1) * 4!/3!=360
3/ C(10,2) * 4!/(2!^2)= 270
4/ C(10,1)*C(9,2)* 4!/2!= 4320

total = 9990

et pour N = 16, le vrai résultat est 3745002309048000

[james31]

Merci de ton aide

Tout marche maintenant