Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 21-05-2011 01:55:00

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

Dénombrrement de façons d'écrire un entier

Combien y-a-t-il de façons d'écrire un entier n>0 avec m>0 entiers >0, l'ordre comptant.
Par exemple 25=5+20=20+5 constituent  déjà deux façons d'écrire 25 avec 2 entiers.

Question bonus:La même chose avec m entiers positifs ou nuls?



Annonces sponsorisées :

Un mathématicien complet est topologiquement fermé!
  • |
  • Répondre

#0 Pub

 #2 - 21-05-2011 03:19:25

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1986
Lieu: Paris

dénombrement de façons d'éxrire un entier

[TeX]C_{n-1}^{m-1}[/TeX]
Je n'ai pas encore de preuve, mais j'ai une relation de récurrence, donc j'imagine que c'est possible ainsi ?

 #3 - 21-05-2011 14:31:45

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1986
Lieu: Paris

Dénombrement de façons d'écrire un eniter

Avec les nombres qui peuvent être positifs ou nuls, je trouve :
[TeX]C_{n+m-1}^n[/TeX]
Pareil, pas encore de démo, mais je pense que par récurrence y a moyen de faire quelque chose ?

 #4 - 21-05-2011 18:52:35

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

dénombrement dr façons d'écrire un entier

(n-1)!/[(m-1)!*(n-m)!]=C(n-1;m-1)

 #5 - 22-05-2011 02:26:59

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1986
Lieu: Paris

Dénombrement de façons d'éccrire un entier

Je reviens pour exposer mon raisonnement.

J'appelle f(n,m) le nombre de manières de décomposer un nombre n comme somme de m entiers strictement positifs. Cela suppose évidemment m <= n.

Etablissons une formule de récurrence sur la fonction f.
Je choisis deux entiers n et m, vérifiant [latex]1 < m \le n[/latex]
Je dois décomposer l'entier n comme somme de m entiers.
Pour le premier de la somme, j'ai le choix entre n-m+1 entiers : de 1 à n-m+1. En effet, il est supérieur à 1, et ne peut pas dépasser n-m+1 car tous les autres sont supérieurs à 1 aussi, et la somme dépasserait n.
Supposons qu'il vaut k, compris donc entre 1 et n-m+1
Ensuite, j'ai pour les autres f(n-k,m-1) : décomposer n-k comme somme de m-1 entiers.

J'obtiens la relation de récurrence suivante :
[TeX]f(n,m)=\sum_{k=1}^{n-m+1}f(n-k,m-1)[/TeX]
N'étant pas sûr de pouvoir conclure à partir de là, j'ai calculé les premières valeurs de la suite :
[TeX]f(n,1)=1[/latex] : 1 seule manière de décomposer n comme somme de ... 1 entier

[latex]f(n,2)=n-1[/latex] : n-1 choix (entre 1 et n-1) pour le premier entier, pas de choix pour le second.

Ensuite avec la formule de récurrence :
[latex]f(n,3)=\frac{(n-1)(n-2)}2[/TeX]
Je conjecture donc :
[TeX]f(n,m)=C_{n-1}^{m-1}[/TeX]
Je vais donc montrer par récurrence sur n que
[TeX]C_n^m=\sum_{k=1}^{n-m+1}C_{n-k}^{m-1}[/TeX]
(pour chaque n, la relation signifie que l'égalité est vérifiée pour tout m inférieur ou égal à n)

Je change d'indice parce que ça me plait pas, et j'arrive à la relation de récurrence que je veux montrer :
[TeX]C_n^m=\sum_{k=m-1}^{n-1}C_{k}^{m-1}[/TeX]
n=1 : n=m=1, et
[TeX]1=C_1^1=\sum_{k=0}^{0}C_{k}^{0}=1[/TeX]
je suppose vrai pour n : je prends un m inférieur ou égal à n

Relation de Pascal :
[TeX]C_{n+1}^{m}=C_{n}^{m}+C_{n}^{m-1}[/TeX]
et je peux appliquer la relation de récurrence au rang n
(je passe le cas m=1 qui se vérifie aisément, et je suppose 1<m<n)
[TeX]C_{n+1}^{m}=\sum_{k=m-1}^{n-1}C_{k}^{m-1}+\sum_{k=m-2}^{n-1}C_{k}^{m-2}
=C_{m-2}^{m-2}+\sum_{k=m-1}^{n-1}\left(C_{k}^{m-1}+C_{k}^{m-2}\right)
=1}+\sum_{k=m-1}^{n-1}C_{k+1}^{m-1}
=C_{m-1}^{m-1}+\sum_{k=m}^{n}C_{k}^{m-1}
=\sum_{k=m-1}^{n}C_{k}^{m-1}
[/TeX]
ce qui prouve la relation au rang n+1

J'ai donc bien [latex]\fbox{f(n,m)=C_{n-1}^{m-1}}[/latex]

Si les entiers de la somme peuvent être nuls, la relation de récurrence devient :
[TeX]g(n,m)=\sum_{k=0}^{n}g(n-k,m-1)[/TeX]
car le premier nombre de la somme, k, peut prendre toutes les valeurs entre 0 et n.

Une analyse similaire donne le résultat :
[TeX]\fbox{g(n,m)=C_{n+m-1}^{n}}[/TeX]

 #6 - 22-05-2011 06:56:56

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

Dénombrement de façons d'écrie un entier

Bravo LOOping amis pour quelqu'un qui si connait en Dénombrement ou pas j'attends encore une autre solution!


Un mathématicien complet est topologiquement fermé!

 #7 - 24-05-2011 01:06:51

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

dénombrement de façins d'écrire un entier

Je donnerais une autre solution que LOOping demain.


Un mathématicien complet est topologiquement fermé!

 #8 - 24-05-2011 16:57:27

Nicouj
Professionnel de Prise2Tete
Enigmes résolues : 27
Messages : 330

dénombrement de façons d'éctire un entier

Je ramasse n cailloux et je les aligne de la gauche vers la droite.
Je ramasse m-1 petits bâtons et j'essaie de voir ou je peux poser ces petits bâtons entre les cailloux pour séparer m tas de cailloux.

Si j'ai au moins autant de bâtons que de cailloux alors c'est impossible
     n <= m-1  ==> f(n, m-1) = 0
Si j'ai 1 bâton de moins que de cailloux alors il n'y a qu'un façon de placer les bâtons.
    f(n, n-1) = 1
Si je n'ai pas de bâton à placer je ne peux faire que mon tas de n
    f(n, 0) =1
Sinon :
1) soit je pose mon premier bâton après le premier caillou et je sépare les n-1 cailloux restants avec m-2 bâtons restants
2) soit je ne pose pas de bâton après le premier caillou. Il me reste donc a poser m-1 bâtons entre les n-1 cailloux restants :

f(n, m-1) = f(n-1, m-2) + f(n-1, m-1)

C'est donc le même procédé que la construction d'un triangle de Pascal


Si on aime pas les caillous et les batons : combien existe t'il de mots de n+m-1 bits qui commencent par un 1 et finissent par un 1 et contiennent exactement
m-1 zéro jamais consécutifs.

 #9 - 24-05-2011 17:22:56

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

Dénombrement de façons d'écrire un ntier

Je donne déjà ma réponse promise pour la seconde question.
Notons [latex]f(n,m)[/latex] le nombre de n-uplet vérifiant [latex]n_1+...+n_m=n[/latex]

Soit [latex]\sum_{n\geq 0} a_nx^n[/latex] une série entière alors
[TeX](\sum_{n\geq 0} a_nx^n)^m=\sum_{n\geq 0} \ \ \ \sum_{\small{n_1+...+n_m=n}}a_{n_1} ... a_{n_m}x^n\[/latex] d'où en prenant les [latex]a_n=1[/TeX][TeX](1-x)^{-m}=\sum_{n\geq 0}f(n,m)x^n[/TeX]
or les coefficients de la première série sont les coefficients binomiaux généralisés

égaux à [latex]\frac{-m(-m-1)(-m-2)...(-m-n+1}{n!}=\frac{(m+n-1)!}{n!(m-1)!}=\binom{m+n-1}{n}[/latex].


Un mathématicien complet est topologiquement fermé!

 #10 - 25-05-2011 03:35:00

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 2989
Lieu: Fanning Island-?-Lac Tele,Mali

Dénombremet de façons d'écrire un entier

L'énoncé du probleme ne précise pas qu'il faille se restreindre a l'addition. Donc en utilisant la soustraction on a une infinité de manieres...

25 = 26 - 1 = 27 -2 = 28 - 3, etc..


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #11 - 25-05-2011 06:59:54

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

Dénombrement de ffaçons d'écrire un entier

C'est vrai. Mais c'est tout de suite plus facile!


Un mathématicien complet est topologiquement fermé!

 #12 - 25-05-2011 08:18:15

Nicouj
Professionnel de Prise2Tete
Enigmes résolues : 27
Messages : 330

dénombrrment de façons d'écrire un entier

pour le deux, on a toujours n cailloux et m-1 bâtons.
Cette fois on peut commencer ou finir par un bâton et on peut placer plusieurs bâtons d'affilé.
Combien de manières existent-il de placer m-1 bâtons sur n+m-1 emplacements ?
[TeX]C^{m-1}_{n+m-1} = C^{n}_{n+m-1}[/TeX]
vous vous compliquez la vie :p

 #13 - 25-05-2011 09:06:31

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

dénombrement de façond d'écrire un entier

Sans aucun doute mais au moins cela porte à généralisation...


Un mathématicien complet est topologiquement fermé!
 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pif, Paf et ?

Mots clés des moteurs de recherche

Mot clé (occurences)
Ecrire 15 comme la somme de deux nombres entiers (22) — Denombrement (8) — Enigmes denombrement (4) — Ecrire le nombre 15 comme une somme de deux produits (4) — Ecrire 25 comme la somme d un nombre entier et du produit de deux nombres entiers (4) — Ecrire 25 comme la somme d un nombre entier et du produit de deux nombre entier (3) — Comment decomposer 14 en somme de nombres entiers pour que le produit de ces nombres soit le plus grand possible (3) — Les deux maniere d ecrire (3) — Differentes facon d ecrire enigme (2) — Nombre de maniere de decomposer un nombre en somme (2) — Nombre de facon d ecrire un entier avec des entiers (2) — Ecrire le nombre 15 comme un produit de deux sommes (2) — Plusieurs facon d ecrire 25 (2) — Nombre de facons d ecrire un entier comme somme d entiers (2) — La somme de 2010 nombres entiers strictement positifs est 2011 (2) — La somme de 2010 nombres entier differents et strictement positif vaut 2011 (2) — Ecrire 15 comme la somme de deux nombres entiers. (2) — Ecrire de differentes facons un chiffre en ce2 (2) — Ecrire 25 comme la somme d un nombre entier (2) — Combien de maniere peut on ecrire somme de (2) — Differente facon d ecrire les nombres ce2 (2) — Nombre de manieres d ecrire un entier comme la somme (2) — Ecrire 25 comme la somme d un nombre entier et du produit (1) — Ecrire entier comme somme (1) — Decomposer 20 en produits de nombre entier positifs (1) — Decomposer un nombre en une somme (1) — Enigme differente facon d ecrire (1) — Combiens de facons peut on decomposer un nombre entier (1) — De combien de facons peut on ecrire 20 comme somme (1) — Toutes les facon d ecrire le chiffre 2 (1) — Differentes facons d ecrire 1205 (1) — Combien de facon peut ton ecrire en ou in (1) — 25 comme la somme de deux nombres entiers (1) — Manieres de decomposer un nombre entier somme (1) — Nombre de facon d ecrire un entier (1) — Ecrire 25 comme la somme d un nombre entier et du produit de 2 nombres entiers (1) — Enigmes batons (1) — Decomposer nombre 1 de deux facons (1) — Plusieur facon d ecrire un m (1) — Ecrire 25 comme la somme de deux nombres entiers (1) — Combien de facon d ecrire scene (1) — Ecrire le nombre 15 comme un produit de deux nombres (1) — La somme de 2009 nombres entiers strictement positifs (1) — Nombre de facons d ecrire un entier comme somme (1) — Les facon d ecrire un nombre (1) — Conbien de facon d ecrire la? (1) — Ecrire 54 de 5 facon differentes (1) — Enigme : ecrire 25 avec 5 batons ? (1) — Enigme denombrement (1) — Ecrire nombre differentes facons (1) — Ecrire 15 comme la somme de deux produits (1) — Ecrire de plusieurs facon comme la somme d entiers (1) — Les deux facon d ecrire l (1) — Decomposer de deux facons (1) — Ecrire un entier m (1) — Nombre de maniere d ecrire un nombre comme une somme (1) — Combien de facon on peut decompose un nombre (1) — Peut on ecrire le nombre 15 en differente facon (1) — Combien de facon pour d2composer un entier en qdditions (1) — 8 manieres d ecrire nombre entier avec 8 et 0 (1) — Ecris 15 comme la somme de 2 nombres entiers (1) — Ecrire les chiffres de deux manieres differentes (1) — Plusieur facons d ecrire 2 (1) — Le nombre 27 peut s ecrirr de plusieurs facon (1) — Peut on ecrire de diferente facon assad (1) — (1) — Ecrire des chiffres de toutes facon (1) — Nombre la somme de sa maniere entiere (1) — Differente facon d ecrire les chiffres (1) — Toutes les facons possible 10 comme somme de 3 entier compris entre 1 et 6 (1) — Comment ecrire 5 facons un nombre (1) — Autre facon d ecrire les nombres (1) — Ecrire un nombre de plusieurs facon differente (1) — Differente maniere d ecrire looping (1) — Tau_r(n) facons d ecrire maths en somme (1) — De combien de maniere peut on ecrire un mot (1) — Ecrire 15 comme la somme de deux nombres entiers la reponse (1) — Choix de nombre entier de somme 1 (1) — Ecrire 20 comme une somme entier (1) — 5 facons differentes pour decomposer un nombre (1) — Differentes facons de decomposer des nombres (1) — Somme de nombre entier (1) — Ecrire 25 comme la somme d un nombre entier et du produit de 2nombres entiers (1) — Decomposer de 3 manieres diferente (1) — 15 comme la somme de deux nombres entier (1) — Le produit de deux nombres ce2 (1) — Nombre de maniere (1) — Y a-t-il plusieurs manieres d ecrire@ (1) — Ecrire enigme en batton (1) — Decomposer des nombres de differentes facons (1) — Reponse ecrire 25comme la somme de deux nombre entiers (1) — Facons de decomposer 20 (1) — Diferante facon d ecrire un nombre (1) — Somme entiers decomposition entier (1) — Ecrire 15 comme le produit de deux sommes (1) — Ecrire 25 avec des 2 (1) — Nombre de facons de decomposer un nombre en somme de k nombres (1) — Reponse enigme decomposer 14 en une somme de nombre entier pour que le produit de ces nombres soit le plus grand possible (1) — Combien de facon peut on decomposer le nombre 6 (1) — Facons ecrire nombre (1) — Deux facon de decomposer (1) — Maniere de decomposer (1) — Decompose de 2 manieres (1) — Decomposition 21 somme en chiffre positif (1) — Les facon decrire 2 (1) — Ecrire le nombre 15 comme une somme de deux produits de nombres entiers (1) — Enigme avec le mot les premiers cailloux (1) — Combien de facon differentes de decomposer un nombre en somme (1) — Le plus grand nombre entier des centaines (1) — Decomposer un nombre en une somme de plusieurs (1) — Ecrire 25 comme la somme d un nombre entier et produit de deux nombres entiers (1) — Ecrire un nombre de plusierus faconss a 3 chiffres + ce2 (1) — Decomposer de plusieurs maniere un nombre (1) — Ecrire 15 la somme de deux nombres entiers (1) — 5 manieres d ecrire un nombre (1) — 2 facons d ecrire discussion (1) — Differente facon d ecrire un nombre (1) — Decompose. ce nombre de plusieure. manieres (1) — 3 facon pour deconbose un nombre (1) — Plusieur facon d ecrire grenouille (1) — De combien de facons peut-on ecrire un nombre comme un produit de deux entiers positifs? (1) — Denomnrement (1) — Facons d ecrire aucun (1) — Differentes facons de decomposer un nombre ce2 (1) — Ecrire 25 comme la somme d un nombre entier etdu produit de deux nombres entier (1) — Ecrire 12 comme produit de 3 entier different (1) — Nombre entier differente facon d ecrire (1) — Combien de facon peux-tu ecrire un nombre (1) — Ecrire un entier comme somme (1) — De combien facon peut-on ecrire un nombre (1) — Nombre facon d ecrire un entier comme somme de n entiers (1) — Plusieur facon d ecrire 5 (1) — Facon d ecrire 138 avec des nombres premiers (1) — Decomposer un chiffre de 3 maniere differente (1) — Ecrire un nombre comme un produit de deux sommes (1) — Enigmede combien de facon peut on ecrire cuissot (1) — Les facons pour decomposer les nombres (1) — Differentes manieres pour somme =15 (1) — Differentes facons d ecrire un nombre ce2 (1) — Ecrire un nombre comme un produit de deux entiers (1) — Ecrire un nombre de differentes manieres ce2 (1) — N-uplet de somme k (1) — Represent chaque nombre de 2 facons differentes (1) — Combien de facon peut-on ecrire les nombre comme produit de deux entiers positifs ? (1) — Nombre de facon d ecrire un entier n comme la somme de k chiffres (1) — Les deux facons d ecrire (1) — Combien y a t il de facon d ecire oi (1) — Ecrire un chiffre de plusieur maniere (1) — Nombre de facon d ecrire un entier comme somme (1) — Nombre de facons de decomposer un entier en somme d entiers (1) — 2les facons d ecrire (1) — Ecrire le nombre 24 comme un produit de deux sommes (1) — Combien se facon d ecrire jerome (1) — Ecrire le nombre quinze comme un produit de deux sommes (1) — Ecrire un nombre de plusieurs facons (1) — Chiffre plusieurs facon d ecrire (1) — Combien y a-t-il de facon d ecrire un nombre (1) — Toutes les facon de faire le nombre 75 (1) — Ecrire de 5 facons differentes le nombre 38.17 (1) — De facon a pouvoir dialoguer...et puis les ecris restent..... (1) — Decomposition entier en somme de deux produits (1) —

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete