Nombre de rangements
Bonjour,
Je n'arrive pas à trouver le nombre de chiffres total et le nombre de $1$ et le nombre d'emplacements pour les $1$.
Je n'arrive pas à trouver le nombre de chiffres total et le nombre de $1$ et le nombre d'emplacements pour les $1$.
Réponses
-
C'est les stars and bars.
Theorème 2 : https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)
en particulier ce passage : https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)#Theorem_two_2 -
J'ai avancé un peu. C'est pas si dur en fait.
On commence par un $0$ donc par exemple si la n-ième boite contient les $p$ boules on a, pour la n-ième boite :
$0 0 \cdots 0 1 \cdots 1 0$ car on finit par un $0$ et le $1$ commence au rang $n+1$. Il y a donc $n+p+1$ chiffres.
On commence et on finit par $0$, il y a donc $n+p-1$ façons de placer les $1$ qui sont au nombre de $p$.
Le nombre de rangement possible est $\binom{n+p-1}{p}$
Est-ce une justification correcte de se baser que sur ce cas particulier ?
La question 2, le nombre de solutions dans $\N^n$ est $\binom{n+p-1}{p}$.
Par contre je bloque pour les solutions dans $(\N^{*})^n$ ... -
Bonjour
Soit tu as un trou dans le cerveau ou bien c'est du foutage de tout ceux qui cherchent à t'aider.
En effet regarde ci-dessous le message (2815 haut de page) que tu as posté il y a 6h. Genre de message que tu postes régulièrement !!!
http://www.les-mathematiques.net/phorum/read.php?12,2029166,2030626#msg-2030626
[Pour obtenir l'adresse d'un message, mets la souris sur la recopie du titre du fil, sous le nom de l'auteur du message, Clic droit > Copier l'adresse du lien, que tu colles où tu veux. AD] -
Ok désolé c'est une mauvaise habitude que j'ai depuis des années dur de s'en débarrasser :-o
Soit $n=3$ et $p=2$
On a $x_1+x_2+x_3=2$
On sait que les solutions dans $\N^3$ sont au nombre de $2$ parmi $3+2-1=4$ donc au nombre de $6$
On veut les solutions de $(\N^{*})^3$ on enlève les cas $x_1=0$ ou $x_2=0$ ou $x_3=0$ ou $x_1=x_2=0$ ou $x_2=x_3=0$ ou $x_1=x_3=0$
Ce qui donne $6-6=0$ solutions dans $(\N^{*})^3$ On conjecture que pour $n>p$ il n'y a aucune solution dans $(\N^{*})^3$
Prenons $n=2$ et $p=3$
On a $x_1+x_2=3$
Le nombre de solutions est $4$. On enlève les cas $x_1=0$ ou $x_2=0$ ce qui donne $1$ solution possible dans $(\N^{*})^2$.
Je ne vois pas de conjecture.
Je ne vois pas trop comment en déduire le cas général, sachant qu'il faut utiliser la question précédente. Je sèche. -
Bon Ok, au moins tu as essayé.
Alors voici une indication
Soit une solution $(x_1,...x_n)\in N^n$ de l'équation.
Alors $(x_1,...x_n)+(1,....1) \in (N^*)^n$ est une solution de .... -
Tu dis ça parce que c'est le résultat de la question d'avant mais tu sais pas du tout pourquoi c'est ça. Justifie.Oshine a écrit:La question 2, le nombre de solutions dans $\N^n$ est $\binom{n+p-1}{p}$.
Et ensuite, ton raisonnement est très mathématique et pas intuitif du tout, c'est terrible. Forcément si $x_1+x_2+x_3=2$ et que les $x_i \geq 1$, il y a forcément un problème. Pas besoin de dénombrer les cas à exclure... Pareil pour $x_1+x_2=3$. Tu peux trouver toi-même les uplets solutions sans $0$. Si on considère l'ordre, il n'y a pas 1 mais 2 couples solutions.
Et sinon, quand tu dis que tu as pas les bonnes habitudes, je prends ça encore comme de la vantardise. Il y a peut-être quelques génies (dont je ne fais nullement partie) qui devant certains problèmes complexes n'éprouvent pas le besoin de regarder des cas particuliers ou de faire des dessins pour établir une démo générale. Mais clairement, tu nous as montré que tu n'étais pas un génie, il me semble... -
J'espère un jour pouvoir trouver un exercice de dénombrement tout seul mais j'ai vraiment du mal. C'est le chapitre le de MPSI où j'éprouve le plus de difficultés.
L'ensemble des $\{x_i | i \in [|1,n|] \}$ est l'ensemble des $n$ boites numérotées de $1$ à $n$.
Alors $(x_1+1) + (x_2+1) + \cdots (x_n+1) = p+n$ où les $x_i +1$ sont solution de $(\N^{*})^n$.
D'après la question précédente, le nombre de solution est $\displaystyle\binom{p+2n-1}{n+p}= \displaystyle\binom{p+2n-1}{n-1}$ (j'ai remplacé dans la formule de la question $1$ $p$ par $p+n$).
C'est bizarre le corrigé donne $\displaystyle\binom{p-1}{p-n}= \displaystyle\binom{p-1}{n-1}$, j'ai un $2n$ en trop dans le coefficient binomial.
1
Par contre d'après la formule du corrigé, on voit bien que si $n>p$ le coefficient binomial est nul. -
Pourtant, bd t'a tout dit avec la translation de $1$.
$(x_1,..,x_n) \in \mathbb{N}^{*n}$ est de somme $p$ si et seulement si $(x_1-1,...,x_n-1) \in ????$ est de somme ????
donc le cardinal de l'ensemble de ces uplets est, par la question d'avant, égal à ???? -
Oui mais il a mis un $+1$ alors que mon corrigé un $-1$.
Avec un $+1$ on obtient $p+n$ alors qu'avec $-1$ on obtient $p-n$.
Mais je me dis que les 2 marchent, alors pourquoi le résultat final est différent ?
J'ai presque le même résultat, juste un $2n$ en trop dans le haut du coefficient binomial. -
Pourquoi le résultat final est différent alors ?
-
Voici la correction :
Pour trouver le nombre de solutions dans $(\N^{*})^n$ on écrit l'équation : $(x_1-1)+ \cdots+ (x_n-1)=p-n$ où $(x_1-1, \ldots ,x_n-1)$ appartient à $\N^n$.
Pour qu'il y ait des solutions, il faut évidemment $p \geq n$. Le nombre de solutions s'obtient en remplaçant $p$ par $p-n$ dans le résultat précédent.
Il y a donc $\displaystyle\binom{p-n}{p-1}=\displaystyle\binom{p-1}{n-1}$ solutions et pour $n>p$ ce coefficient est nul. -
Tu résonnes au lieu de raisonner.
Formule le raisonnement et tu verras pourquoi tu as faux. -
Je pense avoir compris. Voici mon raisonnement.
Il faut soustraire $1$ à chaque $x_i$ et non ajouter $1$ car si $x_i \in \N^{*}$ alors $x_i -1 \in \N$ et on veut se ramener au cas $x_i \in \N$ pour utiliser la question précédente.
Si on ajoute $1$ alors $x_i \in \N^{*}$ implique $x_i +1 \in \N^{*}$ et on ne peut pas utiliser la question précédente. -
Bon, j'abandonne. Tu n'as rien compris. Que tu ajoutes 1 à une certaine équation ou que tu retires 1 à une certaine équation (et je dis volontairement "certaine" sans plus de détail) cela revient au même.
C'est-à-dire que tu as la paresse ou l'incapacité d'écrire ou de faire un raisonnement élémentaire.
Mettre les points sur "i" à ta place n'est pas une bonne chose et c'est inutile. -
Tu ne veux pas compléter mes ???? sérieux ? Je regrette tellement que tu n'aies pas d'oral. On te donne des conseils, des pistes et tu t'en fous, c'est clairement quelque chose de sanctionnable à l'oral, moins à l'écrit...
-
Bd2017 vous me faites des devinettes alors que je suis nul en combinatoire. En rajoutant des $1$ on obtient un résultat différent du corrigé et ça ne marche pas. Il faut soustraire $1$. Et si on ajoute $1$ à $x_i$ déjà non nul, il reste non nul donc on ne peut pas utiliser la question d'avant.
@Alexique
$(x_1, \cdots ,x_n) \in (\N^{*})^n$ est de somme $p$ si et seulement si $(x_1-1, \cdots ,x_n-1) \in \N^n$ est de somme $p-n$
donc le cardinal de l'ensemble de ces uplets est, par la question d'avant, égal à $\displaystyle\binom{p-1}{p-n}=\displaystyle\binom{p-1}{n-1}$. -
Ok... Ca me permet de savoir que tu m'as lu et compris parce que sinon, j'ai juste l'impression que tu t'en fiches et que tu passes à un autre topic direct...
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 65 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 69 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 314 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
Qui est en ligne 11
+8 Invités