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'écrrie 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çons d'écrire nu 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 ed 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 : 3176

dénombrement de façons d'écrore 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énombrement de façons d'écrire ub 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énobrement 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 de façonns 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 daç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çons d'écrrie 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'écrire un enteir

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'écrie 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 entizr

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 (numériquement) à la petite énigme suivante : 

Un berger a 10 moutons, ils meurent tous sauf 9, combien en reste-t-il ?

Sujets similaires

Mots clés des moteurs de recherche

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