Necklace (combinatorics) (original) (raw)
조합론에서 목걸이(영어: necklace)는 순환군의 작용에 대한 문자열의 궤도이다.
| Property | Value |
|---|---|
| dbo:abstract | In combinatorics, a k-ary necklace of length n is an equivalence class of n-character strings over an alphabet of size k, taking all rotations as equivalent. It represents a structure with n circularly connected beads which have k available colors. A k-ary bracelet, also referred to as a turnover (or free) necklace, is a necklace such that strings may also be equivalent under reflection. That is, given two strings, if each is the reverse of the other, they belong to the same equivalence class. For this reason, a necklace might also be called a fixed necklace to distinguish it from a turnover necklace. Formally, one may represent a necklace as an orbit of the cyclic group acting on n-character strings over an alphabet of size k, and a bracelet as an orbit of the dihedral group. One can count these orbits, and thus necklaces and bracelets, using Pólya's enumeration theorem. (en) En combinatoire, un collier de k perles de longueur n est un mot circulaire ou encore une classe d'équivalence de suites de n symboles sur un alphabet de taille k, en considérant comme équivalents tous les décalages circulaires de la suite. Un collier peut être vu comme étant formé de n perles de k couleurs enfilés en cercle. Un bracelet, aussi appelé collier libre ou collier reversible est une classe d'équivalence de suites de symboles sous les deux opération de décalage circulaire et de réflexion ou retournement. Dans l'exemple ci-contre, le bracelet est la classe d'équivalence du mot ABCBAAC ; selon que l'on lit dans sens direct ou le sens inverse, il y a deux colliers, qui sont les classes des mots ABCBAAC et CAABCBA. En termes techniques, un collier est une orbite de l'action du groupe cyclique d'ordre n, alors qu'un bracelet est une orbite de l'action du groupe diédral. (fr) 조합론에서 목걸이(영어: necklace)는 순환군의 작용에 대한 문자열의 궤도이다. (ko) В комбинаторике -цветное ожерелье длины — это класс эквивалентности -символьных строк над алфавитом размера , где эквивалентными считаются строки, получающиеся друг из друга , или циклическим сдвигом. К примеру, для , ожерельем будет множество . Ожерелье можно визуально представить как структуру из связанных в кольцо бусин, имеющих возможных цветов (цвета соответствуют символам в алфавите): для этого надо взять одно из слов данного класса эквивалентности, мысленно продеть через его символы нитку и соединить ее начало и конец. -цветный браслет длины , о котором говорят как об обращаемом (или свободном) ожерелье определяется аналогично как класс эквивалентности строк длины в -символьном алфавите, однако эквивалентными в данном случае считаются строки, получающиеся друг из друга вращением, зеркальной симметрией или комбинацией этих преобразований. Если прибегнуть к визуальному представлению браслетов в виде бус, их отличие от ожерелий будет заключаться в том, что ожерелья запрещается переворачивать, а браслеты — разрешается. По этой причине ожерелье может называться также фиксированным ожерельем. Например, ожерелье, соответствующее строке , отличается от ожерелья, соответствующего строке , однако из этих двух строк получается один и тот же браслет (ведь две эти строки получаются друг из друга зеркальной симметрией). С точки зрения алгебры ожерелье можно представить как орбиту циклической группы действия над -символьными строками, а браслет — как орбиту диэдральной группы. Можно подсчитать эти орбиты, а следовательно, число таких ожерелий и браслетов, с помощью теоремы перечисления Пойа. (ru) Inom kombinatoriken är ett k-närt halsband med längden n en ekvivalensklass av strängar med längden n över ett alfabet av storleken k, där alla rotationer (utan carry) är ekvivalenta. Det motsvarar en struktur bestående av n cirkulärt förbundna pärlor av upp till k olika färger. Ett k-närt armband, även kallat ett vändbart (eller fritt) halsband, är ett halsband sådant att strängarna även är ekvilalenta under reflektion. Det vill säga att om en sträng är identisk med en annan sträng i omvänd ordning, så tillhör de samma ekvivalensklass. Av denna anledning kan man kalla ett halsband för ett fast halsband för att skilja det från ett vändbart. Tekniskt sett kan man klassificera ett halsband som en bana i den cykliska gruppen av strängar bestående av n tecken och ett armband som en bana i den dihedrala gruppen. Detta gör att man kan tillämpa på halsband och armband. (sv) У комбінаториці k-колірне намисто довжини n — це клас еквівалентності (групування, для якого існує відношення еквівалентності) n-символьних рядків над алфавітом розміру k, вважаючи всі повороти еквівалентними. Намисто представляє структуру з n зв'язаних у кільце нами́стин, що мають k можливих кольорів. k-колірний браслет, про який кажуть як про оборотне (або вільне) намисто, це намисто, яке збігається з собою при дзеркальній симетрії. Тобто, якщо дано два варіанти намиста, симетричні один одному, вони належать до деякого класу еквівалентності. З цієї причини намисто може називатися також фіксованим намистом, щоб відрізняти його від оборотного намиста. Формально можна представити як намисто орбіту циклічної групи дії над n-символьними рядками, а браслет як орбіту діедральної групи. Підрахувати ці орбіти, а отже, число таких намист і браслетів, можна за допомогою теореми перерахування Поя. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Bracelets33.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.theory.csc.uvic.ca/~cos/inf/neck/NecklaceInfo.html https://web.archive.org/web/20061002130346/http:/www.theory.csc.uvic.ca/~cos/inf/neck/NecklaceInfo.html |
| dbo:wikiPageID | 6226587 (xsd:integer) |
| dbo:wikiPageLength | 7538 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1107550417 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Proofs_of_Fermat's_little_theorem dbr:Binomial_coefficients dbc:Combinatorics_on_words dbc:Enumerative_combinatorics dbr:Permutation dbr:Inversion_(discrete_mathematics) dbr:Atonal_music dbr:Necklace_splitting_problem dbr:Multiset dbr:Möbius_function dbr:Möbius_inversion_formula dbr:Equivalence_class dbr:Alphabet_(computer_science) dbr:Combinatorics dbr:Pólya_enumeration_theorem dbr:String_(computer_science) dbr:Cyclic_group dbr:Euler's_totient_function dbr:Forte_number dbr:Group_action_(mathematics) dbr:Dihedral_group dbr:Circular_shift dbr:Orbit_(group_theory) dbr:Necklace_problem dbr:Lyndon_word dbr:Equivalence_Class_Representative dbr:Moreau's_necklace-counting_function dbr:Stirling_number_of_the_second_kind dbr:File:Bracelets33.svg dbr:File:Bracelets222.svg dbr:File:Partition_necklaces_by_integer_partition.svg dbr:File:Tantrix_tiles_ryg.svg |
| dbp:wikiPageUsesTemplate | dbt:Cite_journal dbt:Cite_web dbt:Main dbt:MathWorld dbt:OEIS dbt:Reflist dbt:Sfrac |
| dcterms:subject | dbc:Combinatorics_on_words dbc:Enumerative_combinatorics |
| gold:hypernym | dbr:Class |
| rdfs:comment | 조합론에서 목걸이(영어: necklace)는 순환군의 작용에 대한 문자열의 궤도이다. (ko) In combinatorics, a k-ary necklace of length n is an equivalence class of n-character strings over an alphabet of size k, taking all rotations as equivalent. It represents a structure with n circularly connected beads which have k available colors. Formally, one may represent a necklace as an orbit of the cyclic group acting on n-character strings over an alphabet of size k, and a bracelet as an orbit of the dihedral group. One can count these orbits, and thus necklaces and bracelets, using Pólya's enumeration theorem. (en) En combinatoire, un collier de k perles de longueur n est un mot circulaire ou encore une classe d'équivalence de suites de n symboles sur un alphabet de taille k, en considérant comme équivalents tous les décalages circulaires de la suite. Un collier peut être vu comme étant formé de n perles de k couleurs enfilés en cercle. Un bracelet, aussi appelé collier libre ou collier reversible est une classe d'équivalence de suites de symboles sous les deux opération de décalage circulaire et de réflexion ou retournement. (fr) В комбинаторике -цветное ожерелье длины — это класс эквивалентности -символьных строк над алфавитом размера , где эквивалентными считаются строки, получающиеся друг из друга , или циклическим сдвигом. К примеру, для , ожерельем будет множество . Ожерелье можно визуально представить как структуру из связанных в кольцо бусин, имеющих возможных цветов (цвета соответствуют символам в алфавите): для этого надо взять одно из слов данного класса эквивалентности, мысленно продеть через его символы нитку и соединить ее начало и конец. (ru) Inom kombinatoriken är ett k-närt halsband med längden n en ekvivalensklass av strängar med längden n över ett alfabet av storleken k, där alla rotationer (utan carry) är ekvivalenta. Det motsvarar en struktur bestående av n cirkulärt förbundna pärlor av upp till k olika färger. Tekniskt sett kan man klassificera ett halsband som en bana i den cykliska gruppen av strängar bestående av n tecken och ett armband som en bana i den dihedrala gruppen. Detta gör att man kan tillämpa på halsband och armband. (sv) У комбінаториці k-колірне намисто довжини n — це клас еквівалентності (групування, для якого існує відношення еквівалентності) n-символьних рядків над алфавітом розміру k, вважаючи всі повороти еквівалентними. Намисто представляє структуру з n зв'язаних у кільце нами́стин, що мають k можливих кольорів. Формально можна представити як намисто орбіту циклічної групи дії над n-символьними рядками, а браслет як орбіту діедральної групи. Підрахувати ці орбіти, а отже, число таких намист і браслетів, можна за допомогою теореми перерахування Поя. (uk) |
| rdfs:label | Collier (combinatoire) (fr) 목걸이 (조합론) (ko) Necklace (combinatorics) (en) Ожерелье (комбинаторика) (ru) Halsband (kombinatorik) (sv) Намисто (комбінаторика) (uk) |
| owl:sameAs | freebase:Necklace (combinatorics) wikidata:Necklace (combinatorics) dbpedia-fa:Necklace (combinatorics) dbpedia-fr:Necklace (combinatorics) dbpedia-ko:Necklace (combinatorics) dbpedia-ru:Necklace (combinatorics) dbpedia-sv:Necklace (combinatorics) dbpedia-uk:Necklace (combinatorics) https://global.dbpedia.org/id/2mU1E |
| prov:wasDerivedFrom | wikipedia-en:Necklace_(combinatorics)?oldid=1107550417&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Tantrix_tiles_ryg.svg wiki-commons:Special:FilePath/Bracelets222.svg wiki-commons:Special:FilePath/Partition_necklaces_by_integer_partition.svg wiki-commons:Special:FilePath/Bracelets33.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Necklace_(combinatorics) |
| is dbo:wikiPageDisambiguates of | dbr:Necklace_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:Bracelet_(combinatorics) dbr:Necklace_(mathematics) dbr:Bracelet_(mathematics) |
| is dbo:wikiPageWikiLink of | dbr:Proofs_of_Fermat's_little_theorem dbr:Monic_polynomial dbr:208_(number) dbr:Permutation dbr:Double_counting_(proof_technique) dbr:Index_of_combinatorics_articles dbr:Necklace_(disambiguation) dbr:Necklace_splitting_problem dbr:Multiplication_(music) dbr:Anhemitonic_scale dbr:Combinatorics_on_words dbr:Pólya_enumeration_theorem dbr:Cycle dbr:246_(number) dbr:Edgar_Gilbert dbr:Factorization_of_polynomials_over_finite_fields dbr:Forte_number dbr:Augmented_sixth_chord dbr:Circular_shift dbr:Bracelet_(combinatorics) dbr:Necklace_polynomial dbr:Necklace_problem dbr:Lyndon_word dbr:The_Geometry_of_Musical_Rhythm dbr:Necklace_(mathematics) dbr:Bracelet_(mathematics) |
| is foaf:primaryTopic of | wikipedia-en:Necklace_(combinatorics) |
