Kolye (kombinatorikler) - Necklace (combinatorics)

Muhtemel uzunluktaki bilezik modelleri n
karşılık gelen k-nci tam sayı bölümü
(bölümleri ayarla kadar dönme ve yansıma)
3 bilezikler 3 kırmızı ve 3 yeşil boncuk ile. Ortadaki kiral yani 4 tane var kolyeler.
Üçgendeki kutuyu (6,9) karşılaştırın.
11 bilezikler 2 kırmızı, 2 sarı ve 2 yeşil boncuk ile. En soldaki ve en sağdaki dört tanesi kiral, yani 16 tane var kolyeler.
Üçgendeki kutuyu (6,7) karşılaştırın.
16 Tantrix karolar, 16'ya karşılık gelir kolyeler 2 kırmızı, 2 sarı ve 2 yeşil boncuk ile.

İçinde kombinatorik, bir k-ary kolye uzunluk n bir denklik sınıfı (bir denklik ilişkisinin olduğu bir gruplama) n-karakter Teller bir alfabe boyut k, hepsini alıyor rotasyonlar eşdeğer olarak. Bir yapıyı temsil eder n dairesel bağlantılı boncuklar k mevcut renkler.

Bir k-ary bilezik, ayrıca bir devir (veya Bedava) kolye, dizelerin de yansıma altında eşdeğer olabileceği bir kolyedir. Yani, iki dizge verildiğinde, her biri diğerinin tersi ise, aynı denklik sınıfına aittirler. Bu nedenle bir kolyeye aynı zamanda sabit kolye onu ciro kolyesinden ayırmak için.

Resmi olarak, bir kolyeyi bir yörünge of döngüsel grup oyunculuk açık n-karakter dizileri ve bir yörünge olarak bir bilezik dihedral grubu. Bu yörüngeleri ve dolayısıyla kolyeleri ve bilezikleri kullanarak sayabiliriz. Pólya'nın sayım teoremi.

Eşdeğerlik sınıfları

Kolye sayısı

Var

farklı k- uzunlukta kolyeler n, nerede dır-dir Euler'in totient işlevi.[1] Bu doğrudan Pólya'nın sayım teoremi döngüsel grubun eylemine uygulanır tüm işlevler kümesi üzerinde hareket etmek .Ayrıca orada

farklı uzunlukta kolyeler n tam olarak k farklı renkli boncuklar bunlar İkinci türün Stirling numarası.

(sıra A054631 içinde OEIS ) ve (sıra A087854 içinde OEIS ) ile ilişkilidir Binom katsayıları:

ve

Bilezik sayısı

Toplam var

farklı k- uzunlukta bilezikler n, nerede Nk(n) sayısı k- uzunlukta kolyelern. Bu, Pólya'nın eylemine uygulanan yönteminden kaynaklanmaktadır. dihedral grubu .

Farklı boncuk durumu

Belirli bir dizi için n hepsi farklı olan, döndürülmüş kolyeleri aynı sayan bu boncuklardan yapılan farklı kolyelerin sayısı, n!/n = (n - 1) !. Bunun nedeni, boncukların doğrusal olarak sıralanabilmesidir. n! yollar ve n Böyle bir siparişin dairesel geçişlerinin hepsi aynı kolyeyi verir. Benzer şekilde, döndürülmüş ve yansıyan bilezikleri aynı şekilde sayan farklı bileziklerin sayısı, n!/2n, için n ≥ 3.

Boncukların hepsi farklı değilse, tekrarlanan renklere sahipse, daha az kolye (ve bilezik) vardır. Yukarıdaki kolye sayma polinomları, mümkün olan her şeyden yapılmış kolyelerin sayısını verir. çoklu kümeler boncuklar. Polya'nın desen envanteri polinomu Her boncuk rengi için değişken kullanarak sayma polinomunu rafine eder, böylece her bir tek terimliğin katsayısı belirli bir boncuk kümesindeki kolye sayısını sayar.

Aperiodik kolyeler

Bir periyodik olmayan kolye uzunluk n bir rotasyon denklik sınıfı boyuta sahip olmak nyani, böyle bir sınıftaki bir kolyenin iki farklı rotasyonu birbirine eşit değildir.

Göre Moreau'nun kolye sayma işlevi, var

farklı k- periyodik olmayan uzunlukta kolyeler n, nerede μ ... Möbius işlevi. İki kolye sayma işlevi aşağıdakilerle ilişkilidir: toplamın tüm bölenlerin üzerinde olduğu nile eşdeğer olan Möbius dönüşümü -e

Her periyodik olmayan kolye tek bir Lyndon kelimesi Lyndon kelimeleri oluşsun diye temsilciler periyodik olmayan kolyeler.

Ayrıca bakınız

Referanslar

  1. ^ Weisstein, Eric W. "Kolye". MathWorld.

Dış bağlantılar