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énombement 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?


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 : 2010
Lieu: Paris

dénombrement de façons d'écrure 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 : 2010
Lieu: Paris

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

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 : 3801

dénombrement de façobs 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 : 2010
Lieu: Paris

Dénombrement de façons d'écrier 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çoons d'écrire 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 ed façons 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énpmbrement de façons d'écrire 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 enteir

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 : 3004
Lieu: Fanning Island-?-Lac Tele,Mali

Dénombrement de façnos 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énommbrement de faç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énombrement de façons d'écrir eun 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çons d'éxrire 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 : Tim, Tam et ?

Mots clés des moteurs de recherche

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