Casses têtes combinatoires niveau terminale
Bonjour,
le titre est trompeur, j'aimerais poster quelques questions inspirées d'exercices d'un manuel de terminale C de 1980, où j'ai rencontré des difficultés (chapitre sur les entiers naturels). Donc des problèmes que l'on peut résoudre, si possible, sans séries génératrices et outils trop évolués.
Déjà : le nombre de permutations des n lettres de l'alphabet, où aucune lettre ne se retrouve à sa place. On arrive vite à une formule de récurrence Bn = (n-1) (Bn-1 + Bn-2) (en testant sur des petits cas on a B3 = 2 et B4 = 9 )
On peut résoudre cette récurrence sans fonction génératrice en posant Cn = Bn -nBn-1 ;
J'ai trouvé Cn = (-1) ^n et après du calcul, si mes souvenirs sont bons (pas gardé mon brouillon), Bn est la sommes de 0 à n des
n!/(n-k) ! (-1)^k
Formule qui a l'air de marcher. Ma question est : peut-on la simplifier et l'expliciter encore de la même façon que la somme des coefs binomiaux est 2^n ? Je ne sais pas et je n'ai pas trouvé comment simplifier une somme d'arrangements.
le titre est trompeur, j'aimerais poster quelques questions inspirées d'exercices d'un manuel de terminale C de 1980, où j'ai rencontré des difficultés (chapitre sur les entiers naturels). Donc des problèmes que l'on peut résoudre, si possible, sans séries génératrices et outils trop évolués.
Déjà : le nombre de permutations des n lettres de l'alphabet, où aucune lettre ne se retrouve à sa place. On arrive vite à une formule de récurrence Bn = (n-1) (Bn-1 + Bn-2) (en testant sur des petits cas on a B3 = 2 et B4 = 9 )
On peut résoudre cette récurrence sans fonction génératrice en posant Cn = Bn -nBn-1 ;
J'ai trouvé Cn = (-1) ^n et après du calcul, si mes souvenirs sont bons (pas gardé mon brouillon), Bn est la sommes de 0 à n des
n!/(n-k) ! (-1)^k
Formule qui a l'air de marcher. Ma question est : peut-on la simplifier et l'expliciter encore de la même façon que la somme des coefs binomiaux est 2^n ? Je ne sais pas et je n'ai pas trouvé comment simplifier une somme d'arrangements.
Réponses
-
Le deuxième problème qui m'a posé des difficultés insurmontables est le suivant : on considère E l'ensemble des entiers de l'intervalle [1,n] et ses sous-ensembles formés de p entiers.
Les premières questions sont faisables : le nombre de sous-ensembles F est les combinaisons de k parmis n et si on fixe l'entier 1 dans F, ce sont les combinaisons de (k-1) parmis (n-1).
Ensuite, on range les p entiers de F dans l'ordre croissant et on suppose que 1 est dans F. On considère la somme des différences entre tous les entiers : à 1 on associe la différence (x2 -1), à x2 on associe (x3-x2), à xp on associe (n+1-xp), j'ai trouvé que cette somme des p différences fait n (téléscopage évident).
On demande d'en déduire :
1) Le nombre d'ensembles ordonnés de p entiers strictement positifs ayant n pour somme.
2) Le nombre d'ensembles ordonnés de p entiers positifs ou nuls ayant n pour somme.
3) Le nombre d'ensembles ordonnés de p entiers au moins égaux à 2 ayant n pour somme.
J'avoue que j'ai même du mal à comprendre la question 1. en testant sur des petits cas ça ne m'a pas aidé beaucoup, pour n = 10 on a {1;2;3;4} et {1;2;7} et {1;3;6} et {1;4;5} et {1;9} ce qui fait 5 si on fixe 1 dans F.
En considérant la somme des différences, on a bien une somme de p entiers qui fait n. Mais ceux-ci, contrairement à l'ensemble initial, ne sont pas forcément ordonnés, et peuvent se répéter. Bref ... -
Le premier problème est connu sous le nom de problème des dérangements .
$B_n/n!$ converge vers $1/e$ et pour $n\ge 2$, $B_n$ est l'entier le plus proche de $n!/e$. -
bonjour
Ce sont les permutations sans points fixes, qu'on appelle aussi les dérangements.
J'ai juste un doute sur le (-1)^k dans ta formule
A priori cette formule se se simplifie pas plus
Pour plus de renseignements:
Dérangements -
Ah d'accord, effectivement j'ai entendu parler des dérangements ; mais bon la convergence de cette somme n'était pas posée dans l'exo. ;-)
Non le (-1)^k a l'air d'être bon, dans le lien on dirait sous réserve de confirmation, qu'ils ont juste présenté la formule un peu différemment en sortant le n! et en sommant à l'envers. -
Pour ton deuxième problème, je soupçonne l'énoncé d'être complètement foireux. L'auteur de l'énoncé appelle sans doute "ensemble ordonné de $p$ entiers" un $p$-uple d'entiers $(u_1,\ldots,u_p)\in \N^p$. On ne demande pas que les $u_i$ soient rangés dans l'ordre croissant, ni qu'il n'y ait pas de répétition.
PS. Je confirme que le $(-1)^k$ est bien là pour le premier dénombrement. On peut aussi le voir par le principe d'inclusion-exclusion. -
C'est possible que l'énoncé soit foireux, ça me rassure si la difficulté ne vient pas de moi.
Je vais essayer de reprendre l'énoncé avec votre indication.
Mais cela dit on aurait pu se poser une question de combinatoire sur les ensembles ordonnés de p éléments dont la somme fait n, comme pour mon exemple avec n = 10 ? C'est juste que probablement ce qui précède dans l'exo n'a aucun lien avec ce problème ? -
Un petit extrait de l'annexe de dénombrement de Garet-Kurtzmann
-
J'ai posté ici-même il y a peu une récurrence pour le nb. $D_n$ de dérangements de $n$ objets :
$$
D_{n+1} = n(D_n+D_{n-1})
$$ -
Et pour l'aspect historique, on peut lire l'article de L. Takacs, https://pdfs.semanticscholar.org/36dc/e671b6be4df9edaeba80e40f4c094907363e.pdf
-
Donc si j'en conclus les théorèmes postés par Aléa, la réponse à la première question est les combinaisons de p-1 parmis n-1, à la deuxième question, les combinaisons de p parmis n, à la troisième question, les combinaisons de p-2 parmis n-2.
Et effectivement sauf si j'ai mal lu, ces p-uplets ne sont pas ordonnés et sont avec des répétitions.
L'énoncé qui parlait d'ensembles ordonnés (et non de p-uplets) induisait donc bien en erreur ... ce qui n'enlève rien à la qualité de ce bouquin. -
J'ai commencé à regarder si on pouvait résoudre le premier exo différemment, avec des séries génératrices, je tombe sur des équations différentielles pas sympas de prime abord.
-
Quelqu'un a une idée de la solution si on remplace les p-uplets par des ensembles à p éléments ordonnés par la relation d'ordre usuelle sur N et dont la somme des p éléments fait n ?
-
Parlons plutôt de suites (strictement ?) croissantes de longueur $p$ d'entiers (strictement positifs ?) dont la somme vaut $n$. Soit $W(p,n)$ leur nombre. On a une formule de récurrence pas très sympa mais facile à établir, et une initialisation $W(1,n)=1$.
-
Petite erreur dans ce que j'ai dit hier,
2) Le nombre de p-uplets de p entiers positifs ou nuls ayant n pour somme.
Ca fait combinaisons de (p-1) parmis (n+p-1), suffit d'établir une bijection entre les p-uplets en question (Z1, ... , Zp) dont la somme fait n avec (Z1+1, ... , Zp +1) dont la somme fait (n+p) et on se ramène au cas 1. Je ne sais pas si mon explication et rigoureuse mais la formule marche ...
3) Le nombre de p-uplets de p entiers au moins égaux à 2 ayant n pour somme.
Idem ici on fait une bijection avec un ensemble dont la somme vaut (n-p) et donc il y a combinaisons de (p-1) parmis (n-p-1) -
Je vais essayer de trouver cette formule de récurrence GaBuZoMeu. On peut la résoudre ensuite avec des outils élémentaires ?
-
Disons que $W(p,n)$ est le nombre de suites croissantes (au sens large) de $p$ entiers strictement positifs de somme $n$. Ce triangle est répertorié dans OEIS, sous la forme équivalente d'un dénombrement de partitions.
Pas de formule close, des relations de récurrence (faciles à programmer), une série génératrice à $p$ fixé, une série génératrice en deux variables pas très chouette.
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
- 68 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 14
+10 Invités