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

Dénombrement de façon d'écrire 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'écrire un etier

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

Dénombreent de 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 : 2010
Lieu: Paris

Dénombrement de façons d'écriire 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'écrre 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énombremment de 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énombrement d 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énolbrement de façons d'écrire un entier

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

fénombrement 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 façons d'écrier 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'écriee 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çons d'écrire un enier

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