Combinaisons possibles. Éléments de combinatoire
Une combinaison est une sélection non ordonnée d'éléments d'un ensemble fini avec un nombre fixe et sans répétitions d'éléments. Différentes combinaisons doivent différer dans au moins un élément, et l’ordre des éléments n’a pas d’importance. Par exemple, à partir de l'ensemble de toutes les voyelles des lettres latines (AEIOU), vous pouvez faire 10 combinaisons différentes de 3 lettres, formant les triolets non ordonnés suivants :
AEI, AEO, AEU, AIO, AIU, AOU, EIO, EIU, EOU, IOU.
Il est intéressant de noter qu’à partir des mêmes cinq lettres, vous pouvez également obtenir 10 combinaisons différentes si vous les combinez 2 lettres à la fois, ce qui donne les paires non ordonnées suivantes :
AE, AI, AO, AU, EI, EO, UE, IO, UI, OU.
Cependant, si vous combinez les mêmes lettres latines voyelles par 4, vous n'obtiendrez que les 5 combinaisons différentes suivantes :
AEIO, AEIU, AIOU, EIOU, AEOU.
En général, pour désigner le nombre de combinaisons de n éléments différents de m éléments, le symbolisme fonctionnel, d'index ou vectoriel (Appel) suivant est utilisé :
Quelle que soit la forme de notation, le nombre de combinaisons de n éléments par m éléments peut être déterminé à l'aide des formules multiplicatives et factorielles suivantes :
Il est facile de vérifier que le résultat des calculs utilisant ces formules coïncide avec les résultats de l'exemple évoqué ci-dessus avec des combinaisons de voyelles en lettres latines. En particulier, avec n=5 et m=3, les calculs utilisant ces formules donneront le résultat suivant :
Dans le cas général, les formules pour le nombre de combinaisons ont une signification combinatoire et sont valables pour toutes valeurs entières de n et m, telles que n > m > 0. Si m > n et m< 0, то число сочетаний равно 0, так как в этом случае основное множество из n элементов вообще не имеет подмножеств мощности m:
De plus, il est utile de rappeler les nombres limites de combinaisons suivants, qui peuvent être facilement vérifiés par substitution directe dans les formules multiplicatives et factorielles :
Il convient également de noter que la formule multiplicative reste valable même lorsque n est un nombre réel, tant que m est toujours une valeur entière. Cependant, alors le résultat du calcul qui l'utilise, tout en conservant sa validité formelle, perd son sens combinatoire.
IDENTITÉS DES COMBINAISONS
L'utilisation pratique de formules multiplicatives et factorielles pour déterminer le nombre de combinaisons pour des valeurs arbitraires de n et m s'avère peu productive en raison de la croissance exponentielle des produits factoriels de leur numérateur et dénominateur. Même pour des valeurs relativement faibles de n et m, ces produits dépassent souvent les capacités de représentation d'entiers dans les systèmes informatiques et logiciels modernes. De plus, leurs valeurs s'avèrent nettement supérieures à la valeur résultante du nombre de combinaisons, qui peut être relativement faible. Par exemple, le nombre de combinaisons de n=10 par m=8 éléments n'est que de 45. Cependant, pour trouver cette valeur à l'aide de la formule factorielle, il faut d'abord calculer des valeurs beaucoup plus grandes de 10 ! au numérateur et 8 ! au dénominateur :
Pour éliminer les opérations fastidieuses de traitement de grandes quantités, pour déterminer le nombre de combinaisons, vous pouvez utiliser diverses relations de récurrence, qui découlent directement des formules multiplicatives et factorielles. En particulier, la relation de récurrence suivante découle de la formule multiplicative, qui permet de prendre le rapport de ses indices au-delà du signe du nombre de combinaisons :
Enfin, garder l'indice constant fournit la relation de récurrence suivante, qui s'obtient facilement à partir de la formule factorielle du nombre de combinaisons :
Après transformations élémentaires, les trois relations de récurrence résultantes peuvent être représentées sous les formes suivantes :
Si nous additionnons maintenant les côtés gauche et droit des 2 premières formules et réduisons le résultat de n, nous obtenons une relation de récurrence importante, appelée identité de l'addition de nombres combinés :
L'identité d'addition fournit une règle de récurrence de base pour déterminer efficacement le nombre de combinaisons pour de grandes valeurs de n et m, puisqu'elle permet de remplacer les opérations de multiplication dans les produits factoriels par les opérations d'addition plus simples, et pour des nombres de combinaisons plus petits. En particulier, en utilisant l'identité d'addition, il est maintenant facile de déterminer le nombre de combinaisons de n=10 par m=8 éléments, ce qui a été discuté ci-dessus, en effectuant la séquence de transformations récurrentes suivante :
De plus, plusieurs relations utiles pour le calcul de sommes finies peuvent être dérivées de l'identité d'addition, en particulier la formule de sommation par indice, qui a la forme suivante :
Cette relation est obtenue si dans l'addition identité on développe la récurrence le long du terme avec le plus grand exposant tandis que son indice est supérieur à 0. L'exemple numérique suivant illustre ce processus de transformations récurrentes :
La formule de sommation en indice est souvent utilisée pour calculer la somme des puissances des nombres naturels. En particulier, en supposant m=1, en utilisant cette formule, il est facile de trouver la somme des n premiers nombres de la série naturelle :
Une autre version utile de la formule de sommation peut être obtenue en élargissant la récurrence de l'identité d'addition le long du terme ayant le plus petit exposant. L'exemple numérique suivant illustre cette version de transformations récurrentes :
Dans le cas général, à la suite de telles transformations, on obtient la somme des nombres de combinaisons dont les deux indices diffèrent d'un des termes voisins, et la différence des indices reste constante (dans l'exemple considéré, c'est également égal à un). Ainsi, nous obtenons la formule de sommation suivante pour les deux indices des nombres de combinaison :
En plus des relations de récurrence et des formules de sommation évoquées ci-dessus, de nombreuses autres identités utiles pour les nombres combinés ont été obtenues en analyse combinatoire. Le plus important d'entre eux est identité de symétrie, qui ressemble à ceci :
La validité de l'identité de symétrie peut être vérifiée dans l'exemple suivant en comparant les nombres de combinaisons de 5 éléments par 2 et par (5 2) = 3 :
L'identité de symétrie a une signification combinatoire évidente, puisque, en déterminant le nombre d'options pour sélectionner m éléments parmi n éléments, elle établit simultanément le nombre de combinaisons à partir des (nm) éléments non sélectionnés restants. La symétrie indiquée s'obtient immédiatement en remplaçant m par (nm) dans la formule factorielle du nombre de combinaisons :
Les nombres et les identités de combinaison sont largement utilisés dans divers domaines des mathématiques computationnelles modernes. Cependant, leurs applications les plus populaires sont liées au binôme de Newton et au triangle de Pascal.
THÉORÈME BINOMIAL
Pour effectuer diverses transformations et calculs mathématiques, il est important de pouvoir représenter n'importe quelle puissance naturelle d'un binôme algébrique (binôme) sous la forme d'un polynôme. Pour les petites puissances, le polynôme souhaité peut être facilement obtenu en multipliant directement des binômes. En particulier, les formules suivantes pour le carré et le cube de la somme de deux termes sont bien connues du cours de mathématiques élémentaires :
Dans le cas général, pour un degré arbitraire n d'un binôme, la représentation requise sous forme de polynôme est fournie par le théorème du binôme de Newton, qui déclare vraie l'égalité suivante :
Cette égalité est généralement appelée binôme de Newton. Le polynôme de son côté droit est formé par la somme des produits de n termes X et Y du binôme de gauche, et les coefficients devant eux sont appelés binômes et sont égaux au nombre de combinaisons avec des indices, qui sont obtenus grâce à leurs pouvoirs. Compte tenu de la popularité particulière de la formule binomiale de Newton en analyse combinatoire, les termes coefficient binomial et nombre de combinaisons sont généralement considérés comme synonymes.
De toute évidence, les formules de somme au carré et au cube sont des cas particuliers du théorème binomial pour n=2 et n=3, respectivement. Pour gérer des degrés plus élevés (n>3), la formule binomiale de Newton doit être utilisée. Son application pour un binôme du quatrième degré (n=4) est démontrée par l'exemple suivant :
Il convient de noter que la formule binomiale était connue avant même Newton des mathématiciens médiévaux de l’Orient arabe et de l’Europe occidentale. Par conséquent, son nom généralement accepté n’est pas historiquement juste. Le mérite de Newton est d'avoir généralisé cette formule au cas d'un exposant réel arbitraire r, qui peut prendre n'importe quelle valeur rationnelle et irrationnelle positive ou négative. Dans le cas général, une telle formule binomiale de Newton a une somme infinie sur le côté droit et s'écrit généralement comme suit :
Par exemple, avec une valeur fractionnaire positive de l'exposant r=1/2, compte tenu des valeurs des coefficients binomiaux, on obtient le développement suivant :
Dans le cas général, la formule binomiale de Newton pour tout exposant est une version spéciale de la formule de Maclaurin, qui donne le développement d'une fonction arbitraire en une série entière. Newton a montré que pour |z|< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой натуральной степени r = n в правой части также получается конечная сумма из (n+1) первых слагаемых, так как все C(n, k>n) = 0 . Si nous définissons maintenant Z=X/Y et multiplions les côtés gauche et droit par Yn, nous obtenons une version de la formule binomiale de Newton discutée ci-dessus.
Malgré son universalité, le théorème du binôme ne conserve sa signification combinatoire que pour les puissances entières non négatives du binôme. Dans ce cas, il peut être utilisé pour prouver plusieurs identités utiles pour les coefficients binomiaux. En particulier, les formules permettant de sommer les nombres de combinaisons par indice et par les deux indices ont été discutées ci-dessus. L’identité de sommation en exposant manquante peut être facilement obtenue à partir de la formule binomiale de Newton en y mettant X = Y = 1 ou Z = 1 :
Une autre identité utile établit l'égalité des sommes des coefficients binomiaux avec les nombres pairs et impairs. Il s'obtient immédiatement à partir de la formule binomiale de Newton si X = 1 et Y = 1 ou Z = 1 :
Enfin, à partir des deux identités considérées, nous obtenons l'identité de la somme des coefficients binomiaux avec uniquement des nombres pairs ou uniquement impairs :
A partir des identités considérées et de la règle récurrente de suppression des indices sous le signe du nombre de combinaisons, un certain nombre de relations intéressantes peuvent être obtenues. Par exemple, si dans la formule de sommation en exposant nous remplaçons n partout par (n1) et supprimons les indices dans chaque terme, nous obtenons la relation suivante :
En utilisant une technique similaire dans la formule de la somme des coefficients binomiaux avec des nombres pairs et impairs, il est possible de prouver la validité, par exemple, de la relation suivante :
Une autre identité utile vous permet de calculer facilement la somme des produits de coefficients binomiaux situés symétriquement de deux binômes de degrés arbitraires n et k en utilisant la formule de Cauchy suivante :
La validité de cette formule découle de la nécessaire égalité des coefficients pour tout degré m de la variable Z aux côtés gauche et droit de la relation identique suivante :
Dans le cas particulier où n=k=m, compte tenu de l'identité de symétrie, une formule plus populaire pour la somme des carrés des coefficients binomiaux est obtenue :
De nombreuses autres identités utiles pour les coefficients binomiaux peuvent être trouvées dans la littérature abondante sur l'analyse combinatoire. Cependant, leur application pratique la plus célèbre est liée au triangle de Pascal.
LE TRIANGLE DE PASCAL
Le triangle arithmétique de Pascal forme un tableau numérique infini composé de coefficients binomiaux. Ses lignes sont ordonnées par puissances de binômes de haut en bas. Dans chaque ligne, les coefficients binomiaux sont classés par ordre croissant des exposants des nombres de combinaison correspondants de gauche à droite. Le triangle de Pascal s'écrit généralement sous forme isocèle ou rectangulaire.
Plus visuel et courant est le format isocèle, où les coefficients binomiaux, décalés, forment un triangle isocèle infini. Son fragment initial pour les binômes jusqu'au 4ème degré (n=4) a la forme suivante :
En général, le triangle isocèle de Pascal fournit une règle géométrique pratique pour déterminer les coefficients binomiaux, basée sur les identités d'addition et la symétrie des combinaisons de nombres. En particulier, selon l'identité d'addition, tout coefficient binomial est la somme des deux coefficients de la ligne précédente les plus proches de lui. D'après l'identité de symétrie, le triangle isocèle de Pascal est symétrique par rapport à sa bissectrice. Ainsi, chacune de ses droites est un palindrome numérique de coefficients binomiaux. Les caractéristiques algébriques et géométriques indiquées permettent d'étendre facilement le triangle isocèle de Pascal et de trouver systématiquement les valeurs des coefficients binomiaux de puissances arbitraires.
Cependant, pour étudier diverses propriétés du triangle de Pascal, il est plus pratique d'utiliser le format rectangulaire formellement plus strict. Dans ce format, il est spécifié par une matrice triangulaire inférieure de coefficients binomiaux, où ils forment un triangle rectangle infini. Le fragment initial du triangle rectangle de Pascal pour les binômes jusqu'au 9ème degré (n=9) a la forme suivante :
Géométriquement, une telle table rectangulaire est obtenue en déformant horizontalement le triangle isocèle de Pascal. En conséquence, les séries de nombres parallèles aux côtés latéraux du triangle isocèle de Pascal se transforment en verticales et diagonales du triangle rectangle de Pascal, et les lignes horizontales des deux triangles coïncident. Dans le même temps, les règles d'addition et de symétrie des coefficients binomiaux restent valables, même si le triangle rectangle de Pascal perd la symétrie visuelle caractéristique de son homologue isocèle. Pour compenser cela, il devient plus pratique d'analyser formellement les diverses propriétés numériques des coefficients binomiaux pour les horizontales, verticales et diagonales du triangle rectangle de Pascal.
En commençant l'analyse des horizontales du triangle rectangle de Pascal, il est facile de remarquer que la somme des éléments de toute ligne de numéro n est égale à 2n conformément à la formule de sommation des binômes en exposant. Il s'ensuit que la somme des éléments au-dessus de l'une des lignes horizontales portant le numéro n est égale à (2 n 1). Ce résultat devient tout à fait évident si la valeur de la somme des éléments de chaque horizontale est écrite dans le système numérique binaire. Par exemple, pour n=4 cette addition peut s’écrire comme suit :
Voici quelques propriétés plus intéressantes des horizontales qui sont également liées aux puissances de deux. Il s'avère que si le nombre horizontal est une puissance de deux (n=2 k), alors tous ses éléments internes (à l'exception des éléments externes) sont des nombres pairs. Au contraire, tous les nombres d'une ligne horizontale seront impairs si son nombre est inférieur à un puissance de deux (n=2 k 1). La validité de ces propriétés peut être vérifiée en vérifiant la parité des coefficients binomiaux internes, par exemple dans les horizontales n=4 et n=3 ou n=8 et n=7.
Soit maintenant le numéro de ligne du triangle rectangle de Pascal un nombre premier p. Alors tous ses coefficients binomiaux internes sont divisibles par p. Cette propriété est facile à vérifier pour les petites valeurs des nombres de contours premiers. Par exemple, tous les coefficients binomiaux internes de la cinquième horizontale (5, 10 et 5) sont évidemment divisibles par 5. Pour prouver ce résultat pour tout nombre horizontal premier p, vous devez écrire la formule multiplicative de ses coefficients binomiaux comme suit :
Puisque p est un nombre premier et n'est donc pas divisible par m!, le produit des facteurs restants du numérateur de cette formule doit être divisible par m! pour garantir une valeur entière du coefficient binomial. Il s'ensuit que le rapport entre crochets est un nombre naturel N et le résultat souhaité devient évident :
En utilisant ce résultat, nous pouvons établir que les nombres de toutes les droites horizontales du triangle de Pascal, dont les éléments internes sont divisibles par un nombre premier donné p, sont des puissances de p, c'est-à-dire qu'ils ont la forme n=p k. En particulier, si p=3, alors le nombre premier p divise non seulement tous les éléments internes de la rangée 3, comme établi ci-dessus, mais, par exemple, la 9ème horizontale (9, 36, 84 et 126). En revanche, dans le triangle de Pascal il est impossible de trouver une droite horizontale dont les éléments internes soient tous divisibles par un nombre composé. Sinon, le nombre d'une telle ligne horizontale doit être simultanément une puissance de diviseurs premiers du nombre composé par lequel tous ses éléments internes sont divisés, mais cela est impossible pour des raisons évidentes.
Les considérations considérées nous permettent de formuler le critère général suivant pour la divisibilité des éléments horizontaux du triangle de Pascal. Le plus grand commun diviseur (PGCD) de tous les éléments internes de toute ligne horizontale du triangle de Pascal de numéro n est égal au nombre premier p si n=pk ou 1 dans tous les autres cas :
PGCD(Cmn) = ( ) pour tout 0< m < n .
En conclusion de l’analyse des horizontales, il convient de considérer une autre propriété intéressante que possèdent les séries de coefficients binomiaux qui les forment. Si les coefficients binomiaux d'une ligne horizontale portant le numéro n sont multipliés par des puissances successives du nombre 10, puis que tous ces produits sont ajoutés, le résultat est 11 n. La justification formelle de ce résultat est la substitution des valeurs X=10 et Y=1 (ou Z=1) dans la formule binomiale de Newton. L'exemple numérique suivant illustre la réalisation de cette propriété pour n=5 :
L'analyse des propriétés des verticales du triangle rectangle de Pascal peut commencer par l'étude des caractéristiques individuelles de leurs éléments constitutifs. Formellement, chaque m vertical est formé par la séquence infinie suivante de coefficients binomiaux avec un exposant constant (m) et un incrément d'indice :
Évidemment, lorsque m=0, une séquence de uns est obtenue, et lorsque m=1, une série de nombres naturels est formée. Lorsque m=2, la verticale est constituée de nombres triangulaires. Chaque nombre triangulaire peut être représenté sur un plan sous la forme d'un triangle équilatéral, qui est rempli d'objets arbitraires (noyaux) disposés en damier. Dans ce cas, la valeur de chaque nombre triangulaire T k détermine le nombre de noyaux représentatifs, et l'index indique combien de lignes de noyaux sont nécessaires pour le représenter. Par exemple, 4 nombres triangulaires initiaux représentent les configurations suivantes du nombre correspondant de symboles nucléaires « @ » :
Il convient de noter que de la même manière, on peut introduire en considération les nombres carrés S k , qui sont obtenus par la mise au carré des nombres naturels et, en général, les nombres figurés polygonaux formés en remplissant régulièrement des polygones réguliers. En particulier, les 4 nombres carrés initiaux peuvent être représentés comme suit :
Revenant à l'analyse des verticales du triangle de Pascal, on peut noter que la verticale suivante à m=3 est remplie de nombres tétraédriques (pyramidaux). Chacun de ces nombres P k spécifie le nombre de noyaux pouvant être disposés sous la forme d'un tétraèdre, et l'indice détermine combien de couches triangulaires horizontales de rangées de noyaux sont nécessaires pour le représenter dans un espace tridimensionnel. Dans ce cas, toutes les couches horizontales doivent être représentées par des nombres triangulaires successifs. Les éléments des verticales suivantes du triangle de Pascal pour m>3 forment des séries de nombres hypertétraédiques, qui n'ont pas d'interprétation géométrique visuelle sur le plan ou dans l'espace tridimensionnel, mais correspondent formellement à des analogues multidimensionnels de nombres triangulaires et tétraédiques.
Bien que les séries de nombres verticales du triangle de Pascal présentent les caractéristiques de forme individuelles considérées, il est possible pour elles de calculer les sommes partielles des valeurs des éléments initiaux de la même manière, en utilisant la formule de sommation des nombres de combinaisons par indice. . Dans le triangle de Pascal, cette formule a l'interprétation géométrique suivante. La somme des valeurs des n coefficients binomiaux supérieurs de toute verticale est égale à la valeur de l'élément de la verticale suivante, qui se situe une ligne en dessous. Ce résultat est également cohérent avec la structure géométrique des nombres triangulaires, tétraédriques et hypertétraédiques, puisque la représentation de chacun de ces nombres est constituée de couches centrales qui représentent des nombres d'ordre inférieur. En particulier, le nième nombre triangulaire Tn peut être obtenu en sommant tous les nombres naturels représentant ses couches linéaires :
De même, il n’est pas difficile de trouver le nombre tétraédrique Pn en calculant la somme suivante des n premiers nombres triangulaires qui composent ses couches centrales horizontales :
En plus des horizontales et des verticales dans le triangle rectangle de Pascal, on peut tracer des rangées diagonales d'éléments dont l'étude des propriétés présente également un certain intérêt. Dans ce cas, on distingue généralement les diagonales descendantes et ascendantes. Les diagonales descendantes sont parallèles à l'hypoténuse du triangle rectangle de Pascal. Ils sont formés d'une série de coefficients binomiaux avec un incrément des deux indices. En raison de l'identité de symétrie, les diagonales descendantes coïncident dans les valeurs de leurs éléments avec les rangées verticales correspondantes du triangle de Pascal et répètent donc toutes leurs propriétés évoquées ci-dessus. La correspondance indiquée peut être retracée par la coïncidence des valeurs des éléments de la diagonale descendante et de la verticale avec n'importe quel nombre n, si les zéros verticaux ne sont pas pris en compte :
Les diagonales ascendantes forment des séries de nombres géométriquement perpendiculaires à l'hypoténuse du triangle rectangle de Pascal. Ils sont remplis de coefficients binomiaux avec un décrément du plus petit et un incrément de l'exposant. En particulier, les 7 diagonales ascendantes supérieures forment la séquence numérique suivante sans tenir compte des zéros de fin :
De manière générale, le nombre diagonal ascendant n contient les coefficients binomiaux suivants dont la somme des indices de chacun est égale à (n1) :
En raison de l'identité d'addition des nombres combinés, chaque élément diagonal est égal à la somme de deux éléments correspondant en indices des deux diagonales ascendantes précédentes. Cela permet à chaque diagonale ascendante suivante d'être construite par sommation par paires d'éléments horizontaux adjacents des deux diagonales précédentes, élargissant ainsi à l'infini le triangle de Pascal le long de la diagonale. Le fragment suivant du triangle de Pascal illustre la construction d'une diagonale ascendante numéro 8 le long des diagonales numérotées 6 et 7 :
Avec cette méthode de construction, la somme des éléments de toute diagonale ascendante, à partir de la 3ème, sera égale à la somme des éléments des deux diagonales ascendantes précédentes, et les 2 premières diagonales sont constituées d'un seul élément, la valeur dont est 1. Les résultats des calculs correspondants forment la série numérique suivante, selon laquelle vous pouvez vérifier la validité de la propriété considérée des diagonales ascendantes du triangle rectangle de Pascal :
En analysant ces nombres, vous pouvez voir que selon une loi similaire, la séquence bien connue de nombres de Fibonacci est formée, où chaque nombre suivant est égal à la somme des deux précédents, et les deux premiers nombres sont égaux à 1 :
Ainsi, nous pouvons tirer la conclusion importante suivante : les sommes diagonales des éléments du triangle de Pascal constituent la suite de Fibonacci. Cette propriété nous permet d'établir une autre caractéristique intéressante du triangle de Pascal. En développant récursivement la formule de Fibonacci, il est facile de prouver que la somme des n premiers nombres de Fibonacci est égale à (F n+2 1).
Par conséquent, la somme des coefficients binomiaux qui remplissent les n diagonales supérieures est également égale à (F n+2 1). Il s’ensuit que la somme des n premières diagonales du triangle de Pascal est inférieure de 1 à la somme des coefficients binomiaux qui se trouvent sur sa diagonale de nombre (n+2).
En conclusion, il convient de noter que les propriétés considérées des horizontales, verticales et diagonales du triangle de Pascal n'épuisent pas l'immense variété de possibilités qui relient divers aspects mathématiques qui, à première vue, n'ont rien en commun. Ces propriétés inhabituelles nous permettent de considérer le triangle de Pascal comme l’un des systèmes numériques les plus parfaits, dont toutes les capacités ne peuvent être répertoriées et sont difficiles à surestimer.
L'algorithme de calcul du nombre de combinaisons à l'aide du triangle de Pascal est présenté ci-dessous :
Fonction privée SochTT (ByVal n As Integer, ByVal k As Integer) As Double Dim i As Integer Dim j As Integer Dim TT () As Double ReDim TT (n, k) Pour i = 0 To n TT (0, i) = 1 TT (i, i) = 1 Suivant Pour i = 2 À n Pour j = 1 À i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Suivant Suivant SochTT = TT (n, k) Fin de la fonction
Si vous devez calculer le nombre de combinaisons plusieurs fois, il peut être plus pratique de construire le triangle de Pascal une fois, puis de recevoir les données du tableau.
Dim TT () As Double Private Sub CreateTT () ReDim TT (0, 0) BuildTT 0, 0 End Sub Private Function SochTT (ByVal n As Integer, ByVal k As Integer) As Double If n > Ubound (TT) Then BuildTT Ubound (TT) + 1, n SochTT = TT (n, k) End Function Private Sub TerminateTT () ReDim TT (0, 0) End Sub Private Sub BuildTT (ByVal commence en tant qu'entier, ByVal fin en tant qu'entier) Dim i As Integer Dim j Comme entier ReDim Préserver TT (fin, fin) Pour i = début Pour terminer TT (0, i) = 1 TT (i, i) = 1 Suivant Si fin< 2 Then Exit Sub If start < 2 Then start = 2 For i = start To end For j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Next Next End Sub
Vous devez d'abord appeler la procédure CreateTT. Vous pouvez ensuite obtenir le nombre de combinaisons grâce à la fonction SochTT. Lorsque vous n'avez plus besoin du triangle, appelez la procédure TerminateTT. Dans le code ci-dessus, lors de l'appel de la fonction SochTT, si le triangle n'a pas encore été complété au niveau requis, alors il est complété à l'aide de la procédure BuildTT. La fonction récupère ensuite l'élément souhaité du tableau TT et le renvoie.
Dim X () Comme entier Dim Counter () Comme entier Dim K Comme entier Dim N Comme entier Public Sub Soch() Dim i Comme entier N = CInt(InputBox("Enter N")) K = CInt(InputBox("Enter K ")) K = K + 1 ReDim X(N) Pour i = 1 To N X(i) = i Next txtOut.Text = "" ReDim Counter(K) Counter(0) = 1 SochGenerate 1 End Sub Private Sub SochGenerate( ByVal c Comme entier) Dim i Comme entier Dim j Comme entier Dim n1 Comme entier Dim Out() Comme entier Dim X1() Comme entier Si c = K Alors ReDim Out(K) X1 = X Pour i = 1 À K - 1 n1 = 0 Pour j = 1 À N Si X1(j)<>0 Alors n1 = n1 + 1 Si n1 = Compteur(i) Alors Out(i) = X1(j) X1(j) = 0 Sortie pour fin Si Suivant txtOut.Text = txtOut.Text & CStr(Out(i)) Suivant txtOut.Text = txtOut.Text & vbCrLf Else For Counter(c) = Counter(c - 1) To N - c + 1 SochGenerate c + 1 Next End If End Sub
LISTE DES COMBINAISONS DE NOMBRES NATURELS
Pour résoudre de nombreux problèmes pratiques, il est nécessaire de lister toutes les combinaisons de cardinalité fixe qui peuvent être obtenues à partir des éléments d'un ensemble fini donné, et pas seulement de déterminer leur nombre. Compte tenu de la possibilité toujours existante de numérotation entière des éléments de tout ensemble fini, dans la plupart des cas, il est permis de se limiter à l'utilisation d'algorithmes pour énumérer des combinaisons de nombres naturels. Le plus naturel et le plus simple d'entre eux est l'algorithme permettant de lister les combinaisons de nombres naturels dans ordre lexigraphique.
Pour décrire formellement cet algorithme, il convient de supposer que l'ensemble principal, dont toutes les combinaisons de m éléments doivent être listées, forme des nombres naturels consécutifs de 1 à n. Alors toute combinaison de m Du fait de l'ordonnancement, la valeur dans chaque position d'un tel vecteur de combinaisons s'avère naturellement être limitée en valeur d'en haut et d'en bas comme suit : L'algorithme lexigraphique génère séquentiellement de tels vecteurs de combinaison, en commençant par le vecteur lexigraphiquement le plus petit, où toutes les positions contiennent les valeurs minimales possibles suivantes d'éléments égales à leurs indices : Chaque vecteur de combinaison successif est formé à partir de celui actuel après avoir parcouru ses éléments de gauche à droite afin de trouver l'élément le plus à droite qui n'a pas encore atteint sa valeur limite : La valeur d'un tel élément doit être augmentée de 1. Chaque élément à sa droite doit se voir attribuer la plus petite valeur possible, qui est supérieure de 1 à son voisin de gauche. Après ces changements, le prochain vecteur de combinaisons aura la composition élémentaire suivante : Ainsi, le prochain vecteur de combinaison sera lexigraphiquement plus grand que le précédent, puisque les valeurs de leurs éléments initiaux (j1) sont égales en valeur et que la valeur de l'élément en position j est 1 supérieure à celle du précédent. . La relation spécifiée d’ordre lexigraphique croissant est garantie d’être satisfaite à toutes les itérations de l’algorithme. Le résultat est une séquence lexigraphique croissante, qui est complétée par le vecteur de combinaison lexigraphiquement le plus grand, où les éléments dans toutes les positions ont les valeurs maximales suivantes : L'algorithme lexigraphique considéré est illustré par l'exemple suivant, où il est nécessaire de lister par ordre lexigraphique croissant toutes les 15 combinaisons de n=6 premiers nombres naturels par m=4 nombres, c'est-à-dire tous les sous-ensembles possibles à 4 éléments du générateur principal ensemble (1, 2, 3, 4, 5, 6) à partir de 6 éléments. Les résultats des calculs sont présentés dans le tableau suivant : Dans cet exemple, les plus grandes valeurs admissibles de nombres dans les positions des vecteurs de combinaison sont respectivement 3, 4, 5 et 6. Pour faciliter l'interprétation des résultats, dans chaque vecteur de combinaison, l'élément le plus à droite, qui a pas encore atteint sa valeur maximale, est souligné. Les indices numériques des vecteurs de combinaison déterminent leurs numéros par ordre lexigraphique. Dans le cas général, le nombre lexigraphique N de toute combinaison de n éléments par m peut être calculé à l'aide de la formule suivante, où, pour des raisons esthétiques, le symbolisme d'Appel est utilisé pour désigner les nombres de combinaisons : En particulier, les calculs suivants utilisant cette formule pour le nombre de combinaison (1, 3, 4, 6) de n=6 éléments de m=4 dans l'ordre lexigraphique donneront le résultat N=8, qui correspond à l'exemple discuté ci-dessus : Dans le cas général, en utilisant l'identité de la somme des nombres de combinaisons pour les deux indices, il est possible de montrer que le nombre de la combinaison lexigraphiquement la plus petite (1, ... i, ... m) lorsqu'il est calculé à l'aide de ce la formule sera toujours égale à 1 : Il est également évident que le numéro de la combinaison lexigraphiquement la plus grande (m, … nm+i, … n) calculé à l'aide de cette formule sera égal au nombre de combinaisons de n éléments par m : La formule de calcul des nombres de combinaisons lexigraphiques peut être utilisée pour résoudre le problème inverse, où vous devez déterminer le vecteur de combinaison par son numéro dans l'ordre lexigraphique. Pour résoudre un tel problème inverse, il faut l'écrire sous la forme d'une équation, où toutes les valeurs inconnues des éléments du vecteur de la combinaison souhaitée (C 1, ... C i, ... C m ) sont concentrés dans les nombres de combinaisons de son côté droit, et la différence connue L du nombre de combinaisons s'écrit sur le côté gauche de n éléments chacun m et le numéro de la combinaison requise N : La solution de cette équation est fournie par l'algorithme « gourmand » suivant, au cours des itérations duquel les valeurs des éléments du vecteur de la combinaison souhaitée sont sélectionnées séquentiellement. Lors de l'itération initiale, la valeur minimale possible (dans ses limites) de C 1 est sélectionnée, à laquelle le premier terme du côté droit aura une valeur maximale ne dépassant pas L : Maintenant, le côté gauche de L doit être réduit du premier nombre de combinaisons sur le côté droit avec la valeur sélectionnée de C 1, et déterminer de la même manière la valeur de C 2 à la deuxième itération : De même, toutes les itérations suivantes doivent être effectuées pour sélectionner les valeurs de tous les autres éléments C i de la combinaison souhaitée, jusqu'au dernier élément C m : Pour des raisons évidentes, la valeur du dernier élément C m peut être déterminée sur la base de l'égalité de son nombre de combinaisons avec la valeur résiduelle du côté gauche de L : A noter que la valeur du dernier élément de la combinaison C m peut être trouvée encore plus simplement, sans énumérer ses valeurs possibles : La mise en œuvre des itérations de l'algorithme considéré est illustrée par l'exemple suivant, où il faut déterminer des combinaisons avec le nombre N=8 dans l'ordre lexigraphique, si n=6 et m=4 : La capacité algorithmique à déterminer une combinaison par un nombre donné dans un ordre lexigraphique peut être utilisée dans diverses directions. En particulier, lors de la listage des combinaisons par ordre lexigraphique, il faut assurer un retour à toute combinaison obtenue précédemment, il suffit de connaître uniquement son numéro. De plus, il devient possible de générer des combinaisons dans n'importe quel ordre, qui est régulé par une séquence arbitrairement donnée de leurs numéros lexigraphiques. Nous présentons maintenant un algorithme pour générer des combinaisons par ordre lexicographique : 2 pour i:= 1 à k faire A[i] := i; 5 commencer à écrire(A, …, A[k]); 6 si A[k] = n alors p:= p 1 sinon p:= k; 8 pour i:= k jusqu'à p faire A[i] := A[p] + i p + 1 COMBINAISONS AVEC DES ÉLÉMENTS RÉPÉTITIONNELS Contrairement à une combinaison classique, où tous les éléments sont différents, une combinaison avec des répétitions forme une sélection désordonnée d'éléments d'un ensemble fini, où n'importe quel élément peut apparaître indéfiniment souvent et n'est pas nécessairement présent dans un seul exemplaire. Dans ce cas, le nombre de répétitions d'éléments n'est généralement limité que par la longueur de la combinaison, et les combinaisons qui diffèrent dans au moins un élément sont considérées comme différentes. Par exemple, en choisissant 4 nombres éventuellement différents parmi l'ensemble 1, 2 et 3, vous pouvez créer les 15 combinaisons suivantes avec répétitions : 1111 1112 1113 1122 1123 1133 1222 1223 1233 1333 2222 2223 2233 2333 3333.
En général, les combinaisons avec répétitions peuvent être formées en sélectionnant n éléments de types arbitraires. Cependant, ils peuvent toujours être associés à des nombres naturels consécutifs de 1 à n. Ensuite, toute combinaison de m nombres éventuellement différents dans cette plage peut être écrite sous forme vectorielle, en les disposant dans un ordre non décroissant de gauche à droite : Naturellement, avec cette forme de notation, tous les éléments voisins peuvent être égaux grâce à la possibilité de répétitions illimitées. Cependant, chaque vecteur de combinaison avec des répétitions de n éléments par m peut être associé à un vecteur de combinaison de (n+m−1) éléments par m, qui est construit comme suit : Il est clair que pour toutes valeurs des éléments du vecteur f, les éléments du vecteur C sont garantis différents et strictement ordonnés par ordre croissant de leurs valeurs dans la plage de 1 à (n+m1) : La présence d'une correspondance biunivoque entre les éléments des vecteurs de combinaison f et C nous permet de proposer la méthode simple suivante pour lister systématiquement les combinaisons avec répétitions de n éléments par m. Il suffit de lister, par exemple, dans l'ordre lexigraphique, toutes les C combinaisons de (n+m1) éléments de m, en transformant séquentiellement les éléments de chacun d'eux en éléments correspondants de combinaisons à répétitions f en utilisant la formule suivante : En conséquence, une séquence de vecteurs de combinaisons avec des répétitions d'éléments est formée, qui sont disposées dans l'ordre généré en listant les combinaisons correspondantes sans répétitions d'éléments. En particulier, afin d'obtenir la séquence ci-dessus de combinaisons de 3 chiffres 1, 2 et 3 avec des répétitions de 4 chiffres, il est nécessaire de lister par ordre lexigraphique toutes les combinaisons sans répétitions de 6 chiffres 1,2,3,4, 5 et 6 comportent chacun 4 chiffres, en les convertissant comme indiqué. L'exemple suivant montre une telle conversion de la combinaison (1,3,4,6) avec le nombre lexicographique 8 : La correspondance biunivoque entre les combinaisons avec et sans répétitions d'éléments signifie que leurs ensembles sont tout aussi puissants. Ainsi, dans le cas général, le nombre de combinaisons avec répétitions de n éléments par m est égal au nombre de combinaisons sans répétitions de (n+m1) éléments par m. En utilisant la même symbolique pour désigner les nombres de combinaisons avec répétitions f et sans répétitions C, cette égalité peut s'écrire comme suit : Il est facile de vérifier que pour l'exemple considéré ci-dessus, où n=3 et m=4, le nombre de combinaisons de répétitions sera égal à 15, ce qui coïncide avec le résultat de leur listage direct : Il est à noter que contrairement à la version classique, les valeurs des paramètres de combinaison avec des répétitions n et m ne sont pas directement liées les unes aux autres, donc f(n,m)>0 pour toute combinaison de leurs valeurs positives. Les conditions aux limites correspondantes sont déterminées à partir de l'égalité entre les valeurs de (n+m1) et (n1) ou (n+m1) et m : Il devrait également être évident que si m est égal à 1, alors aucune répétition d'éléments n'est possible et, par conséquent, pour toute valeur positive de n>0, l'égalité suivante sera vraie : De plus, pour les nombres de combinaisons avec répétitions pour toute valeur positive de n et m, la relation de récurrence suivante est valable, qui est similaire à l'identité d'addition pour les nombres de combinaisons sans répétitions d'éléments : En fait, il se transforme en l'identité d'addition indiquée lors de la substitution formelle des nombres correspondants de combinaisons sans répétitions dans ses côtés gauche et droit : La relation de récurrence considérée peut être utilisée pour déterminer efficacement les nombres de combinaisons avec répétitions, lorsqu'il est important d'éliminer les opérations à forte intensité de main-d'œuvre de calcul des produits factoriels et de les remplacer par des opérations d'addition plus simples. Dans ce cas, pour calculer la valeur de f(n,m), il suffit d'appliquer cette relation de récurrence jusqu'à obtenir la somme des termes de la forme f(1,m) et f(i,1), où i prend des valeurs comprises entre n et 1. Par définition de la quantité, ces termes sont respectivement égaux à 1 et i. L'exemple suivant illustre l'utilisation de cette technique de transformation pour le cas de n=3 et m=4 : LISTE DES COMBINAISONS BINAIRES Lors de l'implémentation de combinaisons dans le matériel ou de la programmation en langage assembleur, il est important de pouvoir traiter les enregistrements de combinaison au format binaire. Dans ce cas, toute combinaison de n éléments de m doit être spécifiée sous la forme d'un nombre binaire de n bits (B n,...B j,...B 1), où m chiffres unitaires indiquent les éléments du combinaison, et les chiffres (nm) restants ont des valeurs nulles. Évidemment, avec cette forme de notation, différentes combinaisons doivent différer dans la disposition des chiffres du 1, et il n'existe que C(n,m) façons d'arranger m uns ou (nm) zéros dans un ensemble binaire de n bits. Par exemple, le tableau suivant répertorie les 6 combinaisons binaires de ce type, qui fournissent des nombres binaires de 4 bits pour toutes les combinaisons de 4 éléments d'un ensemble arbitraire (E 1 , E 2 , E 3 , E 4 ) par 2 : Dans le cas général, la tâche d'énumération de telles combinaisons binaires se résume à une recherche systématique de tous les ensembles binaires de n bits avec différents arrangements de m un et (nm) zéro bits. Dans sa forme la plus simple, une telle recherche est mise en œuvre par diverses méthodes de transposition de bits adjacents avec décalage (algorithmes de décalage transpositif). Ce sont des algorithmes itératifs et leurs noms reflètent la nature des opérations effectuées à chaque étape. Les procédures itératives des algorithmes de décalage transpositif forment des séquences de combinaisons binaires qui commencent par un ensemble binaire, où tous les uns sont concentrés dans les chiffres de poids faible (à droite), et se terminent lorsque tous les 1 sont dans les chiffres de poids fort ( sur la gauche): Bien qu'elles correspondent dans les combinaisons initiales et finales, ces séquences diffèrent dans l'ordre dans lequel les ensembles binaires intermédiaires sont répertoriés. Cependant, dans tous les cas, chaque combinaison binaire suivante est formée à partir de la précédente suite à l'exécution des opérations de transposition et de décalage correspondantes. Dans le même temps, divers algorithmes de décalage transpositif diffèrent dans la manière dont ils sélectionnent une paire de bits à transposer et un groupe de bits à décaler. Cette spécificité est discutée ci-dessous pour les algorithmes de transposition avec décalage gauche et droite. Dans l'algorithme de transposition avec décalage vers la gauche, à chaque étape, la combinaison binaire suivante est obtenue à partir de la combinaison actuelle en remplaçant la paire de chiffres la plus à gauche 01 par 10 (transposition) et en décalant le groupe de chiffres unitaires de tête, le cas échéant, près de le couple 10 obtenu après la transposition (shift). Si dans ce cas il n'y a pas d'unités dans les premiers chiffres de la combinaison binaire actuelle, alors le décalage n'est pas effectué, même si l'unité principale est obtenue après transposition à cette étape. Le décalage n'est pas non plus effectué lorsqu'il n'y a pas de zéros dans les bits de poids fort avant le couple 10 obtenu après la transposition. Les actions considérées sont illustrées par l'exemple suivant d'exécution de deux itérations successives de cet algorithme, où à une itération (15) seule la transposition (T") est effectuée, et à l'autre itération (16) la transposition est complétée par un décalage ( T"+S") : Dans l'algorithme de transposition par décalage vers la droite, des étapes conceptuellement similaires sont effectuées à chaque étape. Seule la transposition garantit que les bits les plus à droite de 01 sont remplacés par 10 (au lieu de ceux les plus à gauche), puis tous ceux à droite sont décalés vers les bits les moins significatifs. Comme auparavant, le décalage n'est effectué que s'il existe des unités pouvant être décalées vers la droite. Les actions considérées sont illustrées par l'exemple suivant d'exécution de deux itérations successives de cet algorithme, où à une itération (3) seule la transposition (T") est effectuée, et à l'autre itération (4) la transposition est complétée par un décalage ( T"+S") : Il convient de noter que les itérations des deux algorithmes peuvent être écrites sous forme additive si les combinaisons binaires sont interprétées comme des entiers dans le système numérique en base 2. En particulier, pour l'algorithme de transposition avec décalage vers la droite, chaque combinaison binaire suivante (B" n ,…B" j , …B" 1), peut toujours être obtenu à partir de la combinaison courante (B n,…B j,…B 1) en effectuant les opérations d'addition d'entiers à l'aide de la formule additive suivante : Dans cette formule additive, les exposants des puissances de deux f et t désignent respectivement le nombre de chiffres zéro d'ordre inférieur de la combinaison binaire actuelle et le nombre de uns dans une rangée à leur gauche. Par exemple, pour la 4ème combinaison binaire (001110) de n=6 chiffres f =1 et t =3. Par conséquent, calculer la prochaine combinaison binaire à l’aide de la formule additive à l’itération 5 donnera le résultat suivant, équivalent à effectuer les opérations de transposition et de décalage : Pour une analyse comparative des algorithmes de transposition considérés avec décalages gauche et droite, il convient de comparer les séquences de combinaisons binaires qu'ils génèrent dans leurs itérations. Le tableau suivant montre deux de ces séquences de combinaisons binaires de 4 éléments de 2, qui sont obtenues respectivement par les algorithmes de décalage vers la gauche (TSL) et la droite (TSR) : En comparant ces 2 séquences, vous constatez qu’elles sont en miroir inversé. Cela signifie que deux combinaisons binaires qui s'y trouvent à la même distance des extrémités mutuellement opposées de leurs séquences sont une image miroir l'une de l'autre, c'est-à-dire qu'elles coïncident lorsque l'indexation des bits dans l'une d'elles est inversée. Par exemple, le deuxième motif binaire depuis le début de la séquence TSL (0101) est une image miroir du motif binaire (1010) qui est le deuxième depuis la fin de la séquence TSR. En général, toute combinaison binaire avec le numéro i d'une séquence est l'image miroir d'une combinaison binaire avec le numéro (ni+1) d'une autre séquence. Cette relation entre ces séquences est une conséquence de la nature symétrique des opérations de transposition et de décalage dans les deux algorithmes d'énumération de combinaisons binaires considérés. Il convient de noter que le format binaire peut également être utilisé pour enregistrer des combinaisons avec des répétitions d'éléments. Pour ce faire, il est nécessaire d'établir une correspondance biunivoque entre les combinaisons avec répétitions et les combinaisons binaires, qui sont construites comme suit. Soit une combinaison arbitraire avec des répétitions, qui s'obtient en choisissant m éléments éventuellement différents parmi les n éléments du groupe électrogène. Pour établir la correspondance souhaitée, vous devez d'abord ajouter tous les éléments de l'ensemble de formation (cat) à la combinaison, puis trier la concaténation résultante (tri) afin que tous les éléments identiques soient côte à côte. Le résultat est une séquence de (n+m) éléments, où il existe n groupes d’éléments identiques. Il y aura un total de (n+m1) écarts entre éléments, parmi lesquels il y aura (n1) écarts entre groupes d'éléments identiques et m écarts entre éléments au sein des groupes. Pour plus de clarté, vous pouvez placer les symboles « | » dans les espaces indiqués. et en conséquence. Si nous faisons maintenant correspondre 1 aux espaces entre les groupes (|) et 0 à tous les autres espaces (), nous obtenons une combinaison binaire. Il est formé d'un ensemble binaire de (n+m1) bits, où (n1) sont des uns et m zéro bits, dont l'emplacement correspond de manière unique à la combinaison originale avec des répétitions des éléments n à m. La technique de transformation considérée est illustrée par l'exemple suivant de construction d'une combinaison binaire (1001101) utilisant une combinaison à répétitions (BBD) dont les éléments sont sélectionnés dans le groupe électrogène des cinq premières lettres latines : En général, le nombre de ces ensembles binaires détermine le nombre de façons d’organiser (n1) uns (ou m zéros) en (n+m1) chiffres binaires. Cette valeur est évidemment égale au nombre de combinaisons de (n+m1) par (n1) ou par m, soit C(n+m1,n1) ou C(n+m1,m), qui est égal à nombre de combinaisons avec des répétitions f( n,m) de n éléments, m chacun. Ainsi, ayant une correspondance biunivoque entre combinaisons avec répétitions et combinaisons binaires, il est légitime de réduire l'énumération des combinaisons avec répétitions à l'énumération des combinaisons binaires, par exemple en utilisant des algorithmes de transposition avec décalage gauche ou droite. Après cela, il vous suffit de restaurer les combinaisons requises avec des répétitions en utilisant les combinaisons binaires résultantes. Cela peut toujours être fait en utilisant la technique de récupération suivante. Supposons que l'ensemble principal, à partir des éléments dont sont formées des combinaisons avec des répétitions de m éléments pas nécessairement différents, soit ordonné de manière arbitraire de sorte que chacun de ses éléments ait un certain numéro de série de 1 à n. Implémentons également l'énumération des combinaisons binaires de (n+m1) chiffres binaires, où (n1) uns et m zéro chiffres. Chaque combinaison binaire résultante peut être complétée à gauche par un chiffre unitaire fictif, et tous les chiffres unitaires peuvent être numérotés de gauche à droite avec des nombres entiers de 1 à n. Ensuite, le nombre de zéros d'affilée après chaque ième unité de la combinaison binaire sera égal au nombre d'instances du ième élément de l'ensemble principal dans la combinaison correspondante avec répétitions. La technique considérée est illustrée par l'exemple suivant, où, à l'aide d'une combinaison binaire (1001101), on restitue une combinaison avec des répétitions de BBD dont les éléments sont sélectionnés dans le groupe électrogène des cinq premières lettres latines, écrites par ordre alphabétique. , et le surlignage indique les éléments absents dans cette combinaison : En effectuant des actions similaires dans les conditions de cet exemple, vous pouvez lister les 35 combinaisons binaires qui forment des ensembles binaires de 7 bits, où il y a 4 uns et 3 zéros, et restaurer les combinaisons correspondantes avec des répétitions de 5 éléments de 3. L'hiver approchait et Khoma et Suslik décidèrent de s'approvisionner en pois. Toute la journée, ils ont couru vers la grange et ont transporté plusieurs groupes : Khoma, quatre, et Suslik, deux. Le soir, ils comptèrent toutes les cosses qu'ils avaient récoltées et se demandèrent comment diviser ces pois maintenant. Khoma a fait valoir que s'il traînait deux fois plus de pois à la fois que Suslik, il devrait alors obtenir deux fois plus de pois. Suslik a raisonnablement objecté à cela que, premièrement, la vitesse de Khoma est sensiblement inférieure à celle de Suslik, et, deuxièmement, qui sait, peut-être que Khoma ne s'est enfui qu'une ou deux fois, et le reste du temps il était inactif... Aidez vos amis à comprendre au moins un peu cette situation difficile. Déterminez toutes les options possibles quant au nombre de pods que Suslik a apportés et au nombre de Khoma. Dans la première ligne, il y a un nombre pair naturel M – le nombre de pods volés, 2 ≤ M ≤ 1000. Toutes les combinaisons possibles des quantités de cosses apportées par Suslik et Khoma, une combinaison par ligne. Chaque combinaison représente deux entiers non négatifs séparés par un espace : le premier nombre est le nombre de cosses apportées par Suslik, le second – apporté par Khoma. Triez les combinaisons par ordre décroissant du premier nombre. #inclure en utilisant l'espace de noms std ; int main()( entier a, b = 0 ; cin >> une ; tandis que (a >= 0 ) ( cout<<
a
<<
" "
<<
b
<<
"\n"
;
une -= 4 ; b + = 4 ; renvoie 0 ; Soit a le nombre de cosses apportées par Homa et b le nombre de cosses apportées par Suslik. Puisque, selon les conditions du problème, Khoma ne transportait que quatre pods, nous considérerons a = a-4 et b = b + 4 afin d'énumérer ainsi toutes les combinaisons possibles des nombres de pods apportés par Suslik et Khoma. Utilisons également une boucle alors que, qui répétera l'action décrite ci-dessus jusqu'à un \geq 0. Dans la réponse, nous imprimons toutes les combinaisons possibles des nombres de pods apportés par des amis, un par ligne, classés par ordre décroissant du premier nombre. Exemple // Combinaisons de 3 sur 52 pour (int i1 = 0; i1< 50; ++i1)
for (int i2 = i1+1; i2 < 51; ++i2)
for (int i3 = i2+1; i3 < 52; ++i3)
// ...
Nous examinerons ici un problème plus complexe, dont je n'ai pas trouvé de solution dans RuNet (cependant, je donnerai un lien, mais cette formule est clairement incorrecte) - basé sur la combinaison elle-même (dans ce cas, un ensemble de trois chiffres) trouver son index. Supposons, pour être précis, après avoir ordonné i1 = 3, i2 = 7, i3 = 12. Un algorithme de génération typique consiste à générer des combinaisons de 2 sur 52, et pour chacune de ces combinaisons dans une boucle imbriquée, nous générons des combinaisons de 3 sur 50 et vérifions que les indices (i3, i4, i5) dans la combinaison imbriquée le font ne coïncide pas avec les indices (i1, i2) en combinaison externe : Code C++ // COMBINAISON EXTERNE pour (int i1 = 0; i1< 51; ++i1)
for (int i2 = i1+1; i2 < 52; ++i2)
// ВНУТРЕННЕЕ СОЧЕТАНИЕ
for (int i3 = 0; i3 < 50; ++i3)
if (i3 != i1 && i3 != i2)
for (int i4 = i3+1; i4 < 51; ++i4)
if (i4 != i1 && i4 != i2)
for (int i5 = i4+1; i5 < 52; ++i5)
if (i5 != i1 && i5 != i2)
// ...
Code C++ si (i3 >= i1) --i3; si (i3 >= i2) --i2; // similaire pour i4, i5 Exemple de code pour diviser l'index par 2, 3, 47 int get_split_2_3_47_index(int i1, int i2, int i3, int i4, int i5) ( // Indice de la combinaison de 2 sur 52, multiplié par C(3, 50) int offset = ((52*51 - (51-i1) *(52-i1)) / 2 + (i2 - i1 - 1)) * 19600; // "Réindexer" le groupe interne pour que la numérotation soit 0...49 si (i3 > = i1) --i3 ; si (i3 >= i2) --i3 ; si (i4 >= i1) --i4 ; si (i4 >= i2) --i4 ; si (i5 >= i1) --i5 ; if (i5 >= i2) --i5; // Ajoutez maintenant l'indice de la combinaison par 3 // 0 : // SOMME pour n = 0 par i3-1 COMBINAISONS (2, 49-n) // = SOMME pour m = 50-i3 par 49 (m * (m-1) / 2) décalage += (19600 - (((49-i3)*(50-i3)*(99-2*i3)) / 6 - ((49-i3)*(50-i3 )) / 2) / 2); // 1 : // SOMME pour n = i3+1 à i4-1 COMBINAISONS (1, 49-n) offset += (( (48-i3)*(49-i3) - (49-i4)*(50-i4)) / 2); // 2 : // SOMME pour n = i4+1 à i5-1 (1) offset + = (i5 - i4 - 1); renvoie le décalage ; ) En général, je diviserais les algorithmes combinatoires dans les classes suivantes : Nombre de combinaisons Combinaison depuis n Par k appelé un ensemble kéléments sélectionnés à partir des données néléments. Les ensembles qui diffèrent uniquement par l'ordre des éléments (mais pas par leur composition) sont considérés comme identiques ; c'est pourquoi les combinaisons diffèrent des placements. Nombre de combinaisons de n Par k
égal au coefficient binomial Pour une valeur fixe n fonction génératrice de nombres de combinaisons avec répétitions de n Par k est: La fonction génératrice bidimensionnelle des nombres de combinaisons avec répétitions est : Fondation Wikimédia. 2010. 70 soixante-dix 67 68 69 70 71 72 73 40 50 60 70 80 90 100 Factorisation : 2×5×7 Notation romaine : LXX Binaire : 100 0110 ... Wikipédia Nombre de lumière, un nombre conditionnel qui exprime de manière unique l'extérieur conditions pendant la photographie (généralement la luminosité du sujet et la photosensibilité du matériel photographique utilisé). N'importe quelle valeur de E. h. peut être sélectionnée plusieurs fois. combinaisons numéro d'ouverture... ... Grand dictionnaire polytechnique encyclopédique Forme de nombre qui distingue deux objets à la fois par rapport à un seul objet et par rapport à plusieurs objets. Cette forme n'existe pas dans le russe moderne, mais des vestiges de son influence subsistent. Ainsi, des combinaisons de deux tableaux (cf. pluriel... ... Dictionnaire des termes linguistiques Mathématiques combinatoires, combinatoire, une branche des mathématiques consacrée à la résolution de problèmes de choix et d'agencement des éléments d'un certain ensemble, généralement fini, conformément à des règles données. Chacune de ces règles détermine la méthode de construction... ... Encyclopédie mathématique En combinatoire, une combinaison de by est un ensemble d'éléments sélectionnés parmi un ensemble donné contenant différents éléments. Les ensembles qui diffèrent uniquement par l'ordre des éléments (mais pas par la composition) sont considérés comme identiques, ces combinaisons... ... Wikipédia Engagé dans l’étude d’événements dont la survenance n’est pas connue avec certitude. Cela nous permet de juger du caractère raisonnable de l'attente de la survenance de certains événements par rapport à d'autres, bien qu'attribuer des valeurs numériques aux probabilités des événements soit souvent inutile... ... Encyclopédie de Collier 1) identique à l’analyse combinatoire mathématique. 2) Une section de mathématiques élémentaires associée à l'étude du nombre de combinaisons, sous certaines conditions, qui peuvent être composées à partir d'un ensemble fini d'objets donnés... ... Grande Encyclopédie Soviétique - (du grec paradoxos inattendu, étrange) au sens large : une affirmation qui s'écarte fortement de l'opinion généralement acceptée et établie, un déni de ce qui semble « inconditionnellement correct » ; dans un sens plus étroit, deux affirmations opposées, pour... ... Encyclopédie philosophique - (ou le principe des inclusions et des exclusions) une formule combinatoire qui permet de déterminer la cardinalité de l'union d'un nombre fini d'ensembles finis, qui dans le cas général peuvent se croiser... Wikipédia Une théorie mathématique visant à déterminer le nombre de façons différentes de distribuer des objets donnés dans un ordre connu ; est particulièrement important dans la théorie des équations et la théorie des probabilités. Les tâches les plus simples de ce type sont... ... Dictionnaire encyclopédique F.A. Brockhaus et I.A. ÉfronDes données d'entrée
Sortir
Essais
Des données d'entrée
Sortir
6
\\ 6 \; 0 \\ 2 \; 4
11
\\ 11\;0 \\ 7\;4 \\ 3\;8
18
\\ 18\;0 \\ 14\;4 \\ 10\;8 \\ 6\;12 \\ 2\;16
Code du programme
La solution du problème
Indice combiné
Chaque combinaison, permutation, arrangement et autres objets combinatoires peuvent être associés à un index - c'est le nombre dans lequel il apparaît lors de l'itération dans cet algorithme.
Il existe une option pour effectuer une recherche « frontale ». Nous allumons le compteur de combinaisons, prenons l'algorithme ci-dessus et essayons tout jusqu'à ce que nous atteignions l'option souhaitée. Cette option a une complexité temporelle très élevée, nous la rejetterons donc.
Supposons que l'entrée contienne les nombres i1, i2, i3. Tout d'abord, nous devons les disposer par ordre croissant (notez que l'algorithme de génération lui-même, donné ci-dessus, les produit toujours sous forme ordonnée, bien que le concept même de « combinaison » implique un ordre arbitraire).
Cela signifie que nous avons « parcouru » toutes les combinaisons où i1 était égal à 0, 1 et 2.
Pour i1 = 0, nous avons parcouru C(2, 51) combinaisons, puisque les indices i1, i2 traversent toutes les combinaisons de 2 des 51 nombres.
Pour i1 = 1 nous avons parcouru C(2, 50) combinaisons.
Pour i1 = 2 nous avons parcouru des combinaisons C(2, 49).
Au total, nous sommes passés par SUM (de n = 0 à n = i1-1) C(2, 51-n).
Pour i1 = 3, considérons les combinaisons que nous avons parcourues en parcourant l'index i2 (et pour nous, cela commence par i2 = i1+1 = 4).
Lorsque i2 = 4, les combinaisons C(1, 47) sont réussies, lorsque i2 = 5, les combinaisons C(1, 46) sont réussies, lorsque i2 = 6, les combinaisons C(1, 45) sont réussies.
Par analogie complète, pour i2 = 7 on considère les combinaisons parcourues par l'indice i3.
On obtient la formule générale :
L'indice de combinaison requis = SUM (de n = 0 à i1-1) C(2, 51-n) + SUM (de n = i1+1 à i2-1) C(1, 51-n) + SUM (de n = i2+1 à i3-1) C (0, 51-n).Indice de sous-ensemble
En combinatoire, il existe un objet plus complexe : le partitionnement en sous-ensembles. Par exemple, diviser un ensemble de 52 éléments en trois sous-ensembles de, disons, respectivement 2, 3 et 47 éléments, où l'ordre des éléments dans chaque sous-ensemble n'a pas d'importance. (À propos, une combinaison de 2 sur 52 est simplement un cas particulier de division en deux sous-ensembles de 2 et 50 éléments, respectivement).
Encore une fois, chacune de ces partitions a son propre index.
Il s'avère que notre algorithme pour trouver l'index de combinaison peut être modifié pour trouver l'index de partition.
Il est à noter qu'il faut disposer les indices de la « combinaison externe » i1, i2 entre eux, et les indices i3, i4, i5 entre eux, mais indépendamment des deux premiers.
Il convient également de prendre en compte que dans une « combinaison imbriquée », nous travaillons essentiellement avec un ensemble de 50 éléments, mais les indices i3, i4, i5 doivent être « décalés » d'une certaine manière afin qu'ils ne changent pas de 0. à 51, mais de 0 à 49 :
(pour ainsi dire, nous découpons les indices i1, i2 de notre ensemble de 52 éléments, puis décalons l'ensemble restant pour fermer les trous, tandis que les indices i3-i5 sont décalés).
Il faut tenir compte du fait qu’à l’intérieur de chaque combinaison « externe » nous avons exactement C(3, 50) combinaisons « imbriquées ».
L’algorithme se réduira alors à ceci :
COMBINATION_INDEX (i1, i2 sur 52) * COMBINATION_NUMBER BY_3_OF_50 + COMBINATION_INDEX (i3, i4, i5 sur 50 après décalage d'index). Amener les algorithmes à une complexité constante
Je dois tout de suite noter qu'une « erreur » se produit dans la formule si, par exemple, i1 = 0 (on compte la somme pour n = de 0 à -1) ou i2 = 1 (on compte la somme de 1 à 0). En fait, dans de tels cas, la somme correspondante doit être prise égale à zéro et le résultat sera correct.
Je dois également faire attention à la complexité temporelle de nos algorithmes : ils ont une complexité linéaire, à condition de considérer C comme un temps constant. C'est déjà bien mieux que la force brute.
Mais en fait (dans notre cas 52) rien ne nous empêche de réduire l'algorithme à une complexité constante. Pour ce faire, nous appliquerons nos connaissances en mathématiques et calculerons analytiquement tous les montants.
Par exemple, le nombre de combinaisons C(2, K), si vous le « développez » sous la forme d'une formule K ! / ((K-2)! * 2!), se réduit à un polynôme du 2ème degré. Et puisque nous l'avons sous le signe somme, nous pouvons appliquer les formules de la somme des Nièmes puissances des nombres dans la série naturelle (voir Wikipédia) et obtenir un seul polynôme du 3ème degré. Ce qui a évidemment une complexité temporelle constante. (D’ailleurs, « l’erreur » que j’ai citée au début du sous-titre ne se manifeste en aucune façon ; la formule reste correcte).
Je le répète, ceci pour une dimension fixe de l'ensemble de base. Cependant, je suis sûr qu'avec l'aide de la métaprogrammation, vous pouvez « apprendre » au compilateur afin qu'il fasse ce travail à votre place. Épilogue
Dans mon simulateur de poker (Texas Hold'em), je souhaitais calculer et stocker à l'avance les probabilités de gain pour toutes les combinaisons possibles de mes cartes de la main (2 pièces) et de toutes les cartes du flop (3 cartes sur la table). Cela correspond à diviser les 52 ensembles par 2, 3, 47 sous-ensembles.
Calculé et enregistré.
Mais quand est venu le temps de lire les données d'un fichier pour une combinaison spécifique, je ne voulais vraiment pas calculer quelque chose pendant longtemps ou chercher dans un fichier d'un gigaoctet. Maintenant, je détermine simplement le décalage dans le fichier et je lis directement ce dont j'ai besoin.
Il serait intéressant d'avoir un ouvrage de référence sur les algorithmes combinatoires pour tous les objets combinatoires, y compris les permutations, les combinaisons, les placements, les sous-ensembles, les combinaisons avec répétitions, les placements avec répétitions. Formules explicites
Liens
Voyez ce qu'est « Nombre de combinaisons » dans d'autres dictionnaires :
Livres