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

dénombremznt de façons 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énombrzment de façons d'écrire 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 : 3263

Dénombrement de façons d'écrirre 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énombement de façons d'écrire 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énombrzment de façons 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 de façons d'écrire un etnier

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'écrrie 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ébombrement 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

dénombrement de façobs 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

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