Forum des énigmes mathématiques :
ENIGMA 11: Constructeurs de lettres

Bonsoir,

Ca fait longtemps que j'ai pas posté une énigme qui utilise un peu plus de mathématiques !


On va prendre n un entier naturel non nul...

On construit un alphabet à n caractères puis on forme les mots qui ne contiennent pas deux fois la même lettre.

Pouvez vous me calculer le nombre de mots ainsi formés?

^{Une petite précision aux bacheliers qui veulent s'intéresser à cette énigme:
On admet que:}




A vous

_{P.S: Comme d'habitude, une petite démonstration mathématique est fortement recommandée pour avoir son smiley !}

bonjour


les mots de 1 lettre: n
2 lettres: n*(n-1)
3 lettres: n*(n-1)(n-2)
..
mots de n lettres: n!

=(k=1 à n) (n!/k!)=n!(k=1 à n) 1/k!

si on suppose que n tend vers l'infini (comme suggéré par l'aide)
on obtient: e*n! mots

Bonjour,

Nombre de mots à 1 lettres : n = n!/(n-1)!

Nombre de mots à 2 lettres : n*(n-1) = n!/(n-2)!

Nombre de mots à 3 lettres : n*(n-1)*(n-2) = n!/(n-3)!

...

Nombre de mots à n lettres : n*(n-1)*(n-2)*...*1 = n!/1!

Il suffit donc de faire la somme de tout ceci, en factorisant par n! :

N = n!*(1 + 1/2! + 1/3! + 1/4! + ... + 1/(n-1)!)

Cette expression n'est pas tellement simplifiable.

Et je ne vois pas trop à quoi sert l'indication de la limite à l'infini donnée dans l'énoncé, à part donner une approximation ...

Bonjour,

Pour un mot de 1 caractère, on a n mots possible.
Pour un mot de 2 caractères, on a n(n-1) mots possibles...

Pour un mot de k caractères, on a n!/(n-k)! mots possibles (avec k < n)

Pour un mot de n caractères, on a n! caractères.

En posant 0!=1, on obtient que le nombre de mots possible est .

Ceci peut s'écrire comme une fonction de Bessel.

Merci pour l'énigme

Bonjour,

Si on cherche le nombre de mots à k lettres dont toutes sont différentes, il est égal à .
En effet, il faut choisir k lettres parmi n () à partir desquelles on réordonne les k lettres. (k!)

or

d'où le nombre de mots au total est



Bon je ne vois pas où e peut intervenir! A part qu'un équivalent en +infini est e.n! mais bon...

Ma réponse est donc . (moins 1 si on ne compte pas le mot vide)

Bonjour

Soit un entier compris entre et . Il y a manières de choisir lettres distinctes parmi les que comporte l'alphabet, et façons de former un mot avec ces lettres.

Le nombre de mots cherché est donc :





Posons

On a



Et donc, .

est donc un entier compris entre et .

est donc la partie entière de n!e - 1.

Les premières valeurs de M sont : 1, 4, 15, 64, 325, 1956, 13699, 109600, 986409, 9864100, ...

Cordialement
Frenicle

Le nombre mots de k lettres sans répétition est égal au nombre d'arrangements A(n,k)=n!/(n-k)!.
Le nombre de mots total est donc égal à : Sn= Somme (k=1,k=n) n!/(n-k)!.
Sn= n ! [Somme (k=0,k=n-1) 1/k!]
Sn= n ![ [Somme (k=0,k=oo) 1/k!] - [Somme (k=n,k=oo) 1/k!]
Sn = n! [e-sn]= n!e-n!sn.
On peut donner un majorant et un minorant de n!sn.
sn= Somme (k=n,k=oo) 1/k!] < 1/n! [1+(1/n) + (1/n)2+(1/n)3+…..]=1/n! [1/(1-(1/n)] =1/[(n-1)!(n-1)], donc n !sn < n/(n-1)
Par ailleurs n ! sn = [1+ 1/(n+1)+ 1/(n+1)(n+2) + …]>1
Donc Sn est tel que :
(n !e) - n/(n-1)  < Sn < n!e -1
Le seul nombre entier de cet intervalle est E(n!e -1)= E(n!e) -1
Sn= E(n!e) -1

Bonjour,

Pour n = 1, on a 1 mot ("a")
Pour n = 2, on a 4 mots ("a", "b", "ab", "ba")
Pour n = 3, on a 18 mots(3 façons de prendre 1 ou 2 lettres parmi 3, donc 3x4=12 mots de 1 ou 2 lettres, et 3! mots de 3 lettres).

On peut conjecturer que le nombres de mots qu'on peut réaliser avec n caractères, sans avoir 2 caractères identiques est: n.n!

C'est vrai pour n = 1, 2 et 3.
Si c'est vrai pour une valeur n donnée, le nombre de mot qu'on pourra créer avec n+1 lettres est:
(n+1).n.n! + (n+1)! =  n.(n+1)! + (n+1)! = (n+1).(n+1)!
(n+1 façons de choisir n lettres parmi n+1 et (n+1)! mots de n+1 lettres)

Ma réponse, donc: avec un alphabet de n lettres, on peut créer n.n! mots ne comportant pas deux fois la même lettre.

Avec 26 lettres, par exemple, on peut composer 26x26! 10²⁸ mots sans deux lettres identiques.
_{(10 milliards de milliards de milliards, bonjour le dictionnaire!)}

A+  

bonjour monrow,
elle a l'air interéssante cette énigme,
on a un alphabet de n lettre
Il y a n mots a "1" lettres
Il y a n(n-1) mots a "2" lettres
Il y a n(n-1)(n-2) mots a "3" lettres
...
Il y a n(n-1)(n-2)...2 mots a "n-1" lettres
Il y a n! mots a "n" lettres
Donc on fait la petite somme
en bidouillant avec les factorielles, on a facilement:

Voila, ca peut peut-être se simplifier mais le fond y est
Je voispas trop le rapport avec l'expression donnée pour les bacheliers, surtout que e étant un transitif, et le nombre de mots formés étant un naturel, y a quand même un truc bizarre: le nombre peut pas être lié a un transitif
bon, bah voila

Bonsoir,

Huumm, j'ai du mal à comprendre ce que vient faire le rappel !

Pour un entier naturel n, on peut former des mots de longueur k ().
Pour chaque longueur, sachant qu'il n'y a pas de répétition, et en tenant compte de l'ordre (on a affaire à des arrangements), on a .

Ainsi, on a pour former l'ensemble des mots (intelligibles ou non), possibilités.
Après, on peut éventuellement travailler sur l'écriture de ce résultat...
)-1  ~ n!(1+e) lorsque n tend vers . _{(d'après le rappel, qu'on peut prouver par un DSE de e^z)}

Merci pour l'énigme.

n²x n puissance n²

Bonsoir Monrow

Pour avoir un mot à p caractères on a A_n^p possibilités, donc pour avoir n'importe quel mot on a _p=1-->n A_n^p=_p=1-->nn!/(n-p)! = n! ._p=1-->n1/(n-p)! =
n! . _p=0-->n-11/p!, or  un alphabet est d'habitude constitué de plus de 25 lettres donc n-1 est suffisament grand pour avoir _p=0-->n-11/p! e
je réponds donc n!.e.

merci pour l'énigme .

bonjour,

avec n caractères sans lettres répétées on peut former des mots de longueur k 1kn;
pour former un mot de k lettres distinctes il faut
a) choisir k lettres parmi les n caractères de l'alphabet: il y a choix possibbles
b)former tous les mots possibles avec ces k lettres :il y en a k!
donc N_k le nombre de mots de longueur k répondant à la question est k!
N_k=(n!/(k!(n-k)!))k!=n!/(n-k)!
N_n=n!/0!=n!
N₁=n!/(n-1)!=n

le nombre de mots formés de lettres distinctes issues de l'alphabet à n caractères est égal à la somme des N_k
n!/(n-k)!=n!

merci pour cette énigme mathématique j'espère ne pas avoir fait une de mes habituelles étourderies

Il y a  n !/(n-1)! mots de 1 lettre
Il y a  n !/(n-2)! mots de 2 lettres
Il y a  n !/(n-3)! mots de 3 lettres
Il y a  n !/(n-4)! mots de 4 lettres
.etc....
Il y a  n !/(n-n)! mots de n lettres


On doit sommer tout ça et J.K. Horn a trouvé que cela fait :

[e*n ! -1]      où  [] est la partie entière

A+
Torio

J'essaie d'incorporer du LaTeX mais je ne sais pas comment faire pour qu'il apparaisse sous forme compilée. J'espère quand même être lisible...

J'appelle "bons mots" les mots ne contenant pas deux fois la même lettre.
Soit p(n) le nombre de bons mots construits sur un alphabet de n lettres.

Première méthode:
Avec les n lettres de l'alphabet, on peut former:
*n mots (tous bons) de 1 lettre
*n(n-1) bons mots de 2 lettres
...
*n(n-1)...n(n-1)..(n-q+1) bons mots de q lettres
...
*n! bons mots de n lettres
D'où une première forme pour la réponse:
$ p(n)=\sum_{q=1}^n n(n-1)..(n-q+1)$

En mettant n! en facteur, cela donne quelque chose de plus esthétique mais pas plus facile à calculer:

$p(n)=n!\Sum_{q=1}^n(1/(n-q)!)$

ou encore
$p(n)=n!\Sum_{k=0}^{n-1}(1/k!)$

Deuxième méthode:
Si l'alphabet comporte k+1 lettres, les bons mots sont:
*les mots de 1 lettre (il y en a k+1)
*les mots de 1 lettre suivie d'un bon mot de  k lettres (il y en a (k+1)p(k))
D'où la formule de récurrence:
p(k+1)=(k+1)(1+p(k)).
En partant de p(1)=1, on calcule p(n) de proche en proche.
On peut aussi écrire la formule de récurrence sous la forme
p(k+1)/(k+1)! = 1/k!+p(k)/k!
En sommant ces égalités pour k de 1 à n-1, on retrouve la dernière formule obtenue par la première méthode.

Remarque: appelons "bon mot maximal" un bon mot utilisant toutes les lettres. Si l'alphabet comporte n lettres, il y a n! bons mots maximaux.

Le rappel fait avec l'énoncé prouve que le rapport
"nombre de bons mots/nombre de bons mots maximaux" tend vers e quand n tend vers +l'infini.

Merci pour cette énigme

Bonjour,

Le nombre de mots de longueur sur un alphabet de caractères sans qu'il y aie répétition de caractères est , avec et , bien entendu.

Le nombre de mots total est exactement

Je ne vois pas tellement l'utilité de la somme infinie ici, on ne nous dit rien de plus sur n. Il est vrai que cette somme partielle s'approche très rapidement de e mais l'énoncé ne donne aucune préférence pour les valeurs de n, je reste dans le cas général sans approximation.

Isis

Former un mot de m lettres (1mn) qui ne contient pas deux fois la même lettre revient à choisir à choisir m lettres parmi n le nombre de mots ainsi formés est n!/(n-m)! (Arrangement)

Le nombre total de mots sera donc n!/(n-m)! pour m variant de 1 à n
En factorisant n! et en appelant n-m=k on obtient n!1/k! pour k variant de 0 à n-1

bonjour,

voyons ce que ça donne pour les premières valeurs de n:

n=1:
1 caractère, donc 1! mot de 1 caractère.
n=2:
2 caractères, donc 2! mots de 2 caractères + 2 fois 1! mot de 1 caractère.
n=3:
3 caractères, donc 3! mots de 3 caractères + 3 fois 2! mots de 2 caractères + 3 fois 1! mot de 1 caractère.
n=4:
4 caractères, donc 4! mots de 4 caractères + 4 fois 3! mots de 3 caractères + 6 fois 2! mots de 2 caractères + 4 fois 1! mot de 1 caractère.
n=5:
5 caractères, donc 5! mots de 5 caractères + 5 fois 4! mots de 4 caractères + 10 fois 3! mots de 3 caractères + 10 fois 2! mots de 2 caractères + 5 fois 1! mot de 1 caractère.
...
n=k:
mots

Ma réponse est donc:
Avec un alphabet de n caractères, on peut former mots.


Merci pour l'énigme.

si n est fixé on peut former n mots d'une lettre.
nombre de mots de 2 lettres:il faut prendre 2 lettres parmi n:c'est une combinaison de 2 dans n.ces 2 lettres étant choisies on peut les placer de 2 facons différentes.

nombre de mots de 3 lettres:il faut prendre 3 lettres parmi n;c'est une combinaison de 3 parmi n.ces 3 lettres étant choisies on a 3! dispositions possibles.
en raisonnant de meme jusqu'à avoir un mot de n lettres

le nombres de mots possibles est:
(k=1 à k=n) de ((combinaison de k parmi n)*k!)
qui est égal à (k=1 à k=n) de (n!/((n-k)!))
qui est aussi égal à
n!*(k=o à k=n-1) de (1/k!)

je ne sais pas si on peut simplifier plus ce résultat

Il y a n mots d'une lettre, n(n-1) mots de deux lettres, jusqu'à n! mots de n-1 lettres, et n! mots de n lettres. Soit en sens inverse, un total de  n!(1+1/1!+...+1/(n-1)!)
Or e*n!=n!(1+1/1!+...+1/(n-1)!)+1+exp(t)/(n+1) avec 0<t<1: dès que n>1, exp(t)/(n+1)<1
Donc  n!(1+1/1!+...+1/(n-1)!)= E(e*n!)-1 , avec E partie entière

Bonjour,

On construit un alphabet à n caractères, puis on forme tout les mots qui ne contiennent pas deux fois la même lettre.

On forme donc tout les mots de 1 lettre
puis on forme donc tout les mots de 2 lettres qui ne contiennent pas deux fois la même lettre
puis on forme donc tout les mots de 3 lettres qui ne contiennent pas deux fois la même lettre
puis on forme donc tout les mots de 4 lettres qui ne contiennent pas deux fois la même lettre
...
puis on forme donc tout les mots de n-1 lettres qui ne contiennent pas deux fois la même lettre
puis on forme donc tout les mots de n lettres qui ne contiennent pas deux fois la même lettre.

Le nombre de mots total est la somme du nombre de mots formés à chaque étape.

Le nombre de mots de k lettres que l'on peut former avec n lettres est le nombre de tirages différents de k lettres parmis n (ou arrangements de n lettres k à k) que l'on peut effectuer en tenant compte de l'ordre et sans remise.

Ce nombre est

Le nombre total de mots (appelons le N) est égal à la somme des pour k allant de 1 à n.






Je poste bien que je sois troublé par l'indice qui me fais penser à un certain DL : me suis-je arrêté trop tôt? (à condition de ne pas mettre complètement "planté" ) Pas grave, je mangerai du pour les fêtes.

Bonjour, et bonnes fêtes



Si est le nombre de mots obtenu avec n lettres selon les règles exposées, alors est obtenu en formant d'abord les (n+1) mots de 1 lettre, puis les mots de plus de 1 lettre débutant par chaque lettre de cet alphabet de (n+1) lettres à laquelle on accole un mot constitué avec un alphabet de n lettres, après avoir retiré cette première lettre par laquelle débute ce nouveau mot :

Cette relation fait furieusement penser à la relation plus simple
et si , alors

Etudions alors la suite définie par
On établit sans peine que

D'où on déduit (par récurrence, et parce que ) que

et pour n très grand :

le nombres des mots est  factoriel n

ENIGME CLOTUREE

Bon la réponse était évdemment

L'indice était là juste pour mettre le résultat sous une autre forme comme celle faite par frenicle et nofutur2... C'était de ma faute, il fallait que je prècise de déterminer ce nombre en fonction de n! et e, c'est pour celà que je lui ai donnée 3 *** ...

Merci pour votre participation

Bonjour

citation :
C'était de ma faute, il fallait que je prècise de déterminer ce nombre en fonction de n! et e

Je trouve pas que c'est une vrai faute vue le nbre d'étoiles affecté à l'énigme .

En fait je crois qu'il y a eu beaucoup de smileys non mérités(y compris le mien, à propos un grand merci à toi Monrow, mais en fait j'aurais pas discuté ta décision si c'était un poisson bien mérité, _{attention même si tu le fera après ce poste} )

D'autre part je viens de lire la démo de Frenicle que je trouve vraiment très interessante et que je crois la seule démo qui a bien expliqué la formule finale E(n!e)-1 (avec je suppose la démo de Nofutur que j'ai pas lu ...).

Franchement un grand bravo à Frénicle et à Nofutur .

_{J'ai peu être aimé la démo de Frénicle car j'ai réfléchi à l'idée de remplacer la somme par la différence entre 2 sommes qui tendent vers l'infini mais j'ai pas continuer car j'avais pas en tête l'idée de la partie entière.}

à tous ceux qui ont trouvé (même aux autres )

master_och>> C'est qu'il y avait des smiley de plus () mais bon ... j'ai compté juste pour tous ceux qui ont trouvé le sigma

citation :
C'est qu'il y avait des smiley de plus

j'espère que ce sera toujours pareil

La décision en fin de compte reste la tienne .

En fait Monrow, c'est maintenant que je me suis rappelé, je t'ai envoyé un mail dans lequel je te demandais si les réponses sous forme de sigma seront accéptés ou pas mais j'ai pas eu de réponse, ne l'as tu pa recu

Il est normal qu'aucune indication, même mineure, ne soit donnée par e-mail ...

Et bah justement jamo, je lui ai dit dans mon email que s'il croit que ma question est illégale il me le signal, et d'ailleur on a parlé de ce problème dans un autre topic(que je vais chercher) et on m'a dit que je peux poser des questions sur les énigmes en cours aux posteurs d'énigmes et c'est a lui de décider s'il répond ou pas ...

En voici le lien .

Bonsoir
=> monrow
Voilà ce que j'avais envie de répondre mais je ne l'ai pas fait de peur du poisson peut-être mais qu'aurais-je  obtenu ? Merci

En appelant A _nⁱ le nombre de groupements avec ordre de i lettres choisies parmi n , le nombre de mots que l'on peut former est égal à la somme de ces A_nⁱ depuis 1 jusque n





donc (hic) ( en négligeant ) je dirai que le nombre de mots = la partie entière de   

A+

Salut geo3

Dommage , mais je pense que je t'aurais donné un smiley puisque je n'ai pas corrigé le fait de trouver le résultat en fonction de n! et e et qu'il suffisait de laisser le sigma

olala, je suis furax, j'ai mal conclue...
alors que j'avais tout bien fait sur le papier!! connerie de latex!

simon92 >> c'est à ça que sert l'aperçu !

oui oui!! je sais ! je sais! en plus j'ai pas fait les combinatoires et tout, j'ai réfléchit! au moins 2 grandes minutes
c'est pas grave, moi je vote pour que Isiss gagne ce mois ci car elle est fait des superbe démo (bon la, c'était pas extraordinaire) mais depuis un mois, elle est présente

Rebonsoir
En effet dommage
Le e m'a un peu perturbé
Je pense qu'avec le sigma la réponse finale est



et non  



Ce n'est pas pareil ( je peux me tromper)
Bravo à frenicle et à Nofutur2 pour avoir introduit le e avec détails.
A+

citation :

C'est pas la même chose, non?

Rebonsoir
Mais



est différent de



A+

je me suis embruillé avec la même chose... le mot vide est il un mot

En théorie des langages, je crois que s'en est un, mais ...

Bonjour Bonjour

Cet exo est tiré du Concours Communs Polytechniques - option PSI :

citation :
Soit un alphabet à "n" caractères. Déterminer l'expression de , le nombre de mots que l'on peut écrire en utilisant une fois au plus chaque caractère. Montrer que où E représente la partie entière.