Yıldızlar ve çubuklar (kombinatorikler) - Stars and bars (combinatorics)

Bağlamında kombinatoryal matematik, yıldızlar ve barlar belirli bir şeyi türetmek için grafiksel bir yardımdır kombinatoryal teoremler. Tarafından popülerleştirildi William Feller klasik kitabında olasılık. Birçok basit sorunu çözmek için kullanılabilir sayma problemleri örneğin, koymanın kaç yolu olduğu gibi n ayırt edilemez toplar k ayırt edilebilir kutular.^[1]

Teoremlerin ifadeleri

Yıldızlar ve çubuklar yöntemi genellikle temel kombinatoriklerin aşağıdaki iki teoremini kanıtlamak için özel olarak tanıtılmaktadır.

Teorem bir

Herhangi bir çift için pozitif tam sayılar n ve k, sayısı k-demetler nın-nin pozitif toplamı olan tamsayılar n sayısına eşittir (k - 1) - bir kümenin eleman alt kümeleri n - 1 element.

Bu sayıların her ikisi de tarafından verilir binom katsayısı ${displaystyle extstyle {n-1 k-1'i seç}}$. Örneğin, ne zaman n = 3 ve k = 2, teorem tarafından sayılan tupllar (2, 1) ve (1, 2) 'dir ve ${displaystyle {binom {3-1} {2-1}} = 2}$ onların.

Teorem iki

Herhangi bir pozitif tam sayı çifti için n ve k, sayısı k-demetler nın-nin negatif olmayan toplamı olan tamsayılar n sayısına eşittir çoklu kümeler nın-nin kardinalite k - 1 beden setinden alınır n + 1.

Her iki numara da tarafından verilir çoklu set numarası ${displaystyle sol (! {binom {n + 1} {k-1}}! ight)}$veya eşdeğer olarak binom katsayısı ${displaystyle {binom {n + k-1} {k-1}} = {binom {n + k-1} {n}}}$ veya çoklu set numarası ${displaystyle {ig (}! {binom {k} {n}}! {ig)}}$. Örneğin, ne zaman n = 3 ve k = 2, teorem tarafından sayılan demetler (3, 0), (2, 1), (1, 2) ve (0, 3) ve ${displaystyle sol (! {binom {3 + 1} {2-1}}! ight) = 4}$ onların.

Yıldızlar ve çubuklar yöntemiyle kanıtlar

Teorem bir

Varsayalım ki n nesneler (temsil eden yıldızlar; aşağıdaki örnekte n = 7) yerleştirilecek k kutular (örnekte k = 3), tüm bölmeler en az bir nesne içerecek şekilde. Bölmeler ayırt edilebilirdir (diyelim ki 1 ila k) ama n yıldızlar değildir (bu nedenle konfigürasyonlar yalnızca yıldız sayısı her bölmede bulunur). Dolayısıyla bir konfigürasyon bir kteoremin ifadesinde olduğu gibi pozitif tamsayıların -tuple. Yıldızları kutulara yerleştirerek başlamak yerine yıldızları bir çizgi üzerine yerleştirerek başlayın:

Burada birinci bölme için yıldızlar soldan alınacak, ardından ikinci bölme için yıldızlar vb. Böylece, birinci yıldızın ikinci bölmeye gittiği ve ilk yıldızın üçüncü bölmeye gittiği bilindikten sonra konfigürasyon belirlenecektir. Bu yerleştirilerek gösterilebilir k − 1 ayırma Barlar yerlerde arasında iki yıldız. Hiçbir kutunun boş kalmasına izin verilmediğinden, belirli bir yıldız çifti arasında en fazla bir çubuk olabilir:

Görüntüle n yıldızları tanımlayan sabit nesneler olarak n − 1 yıldızlar arasındaki boşluklar, her birinde bir çubuk olabilir veya olmayabilir (bir bölme bölümü). Bir konfigürasyon seçilerek elde edilir k − 1 bu boşlukların aslında bir bar içermesi; bu nedenle var ${displaystyle {binom {n-1} {k-1}}}$ olası konfigürasyonlar (bakınız kombinasyon ).

Teorem iki

Bu durumda, yıldızları kutulara bölen çubuklarla bir yıldız ve çubuk dizisi olarak bir demetin temsili değişmez. Negatif olmamanın zayıflatılmış kısıtlaması (pozitiflik yerine), bir kişinin iki yıldız arasına birden çok çubuk yerleştirilebileceği ve ayrıca ilk yıldızdan önce veya son yıldızdan sonra çubuk yerleştirebileceği anlamına gelir. Böylece, örneğin ne zaman n = 7 ve k = 5, tuple (4, 0, 1, 2, 0) aşağıdaki diyagramla gösterilebilir.

Bu bir bire bir yazışma istenen formdaki demetler ve değiştirilen seçimler arasında k − 1 boşluklar n + 1 mevcut boşluklar veya eşdeğer olarak (k − 1) -element çokbir boyut kümesinden çizilmiş kümeler n + 1. Tanım gereği, bu tür nesneler çok noktalı sayı ile sayılır ${displaystyle sol (! {binom {n + 1} {k-1}}! ight)}$.

Bu nesnelerin de binom katsayısı ile sayıldığını görmek için ${displaystyle {binom {n + k-1} {n}}}$, istenen düzenlemelerin aşağıdakilerden oluştuğunu gözlemleyin n + k − 1 nesneler (n yıldızlar ve k − 1 Barlar). Yıldızların pozisyonlarını seçmek aynen k − 1 için kalan noktalar k − 1 Barlar. Yani yıldızların konumlarının seçilmesi tüm düzenlemeyi belirler, bu nedenle düzenleme ile belirlenir. ${displaystyle {binom {n + k-1} {n}}}$ seçimler. Bunu not et ${displaystyle {binom {n + k-1} {n}} = {binom {n + k-1} {k-1}}}$, düzenlemenin pozisyon seçimi yapılarak da belirlenebileceği gerçeğini yansıtmaktadır. k − 1 Barlar.

Örnekler

Eğer n = 5, k = 4 ve bir dizi boyut k {a, b, c, d} ise ★ | ★★★ || ★ çoklu kümeyi {a, b, b, b, d} veya 4-demetini (1, 3, 0, 1) temsil eder. Bu örnek için herhangi bir çoklu kümenin temsili şu şekilde olacaktır: n = 5 yıldız ve k - 1 = 3 çubuk.

Birçok temel kelime problemleri kombinatoriklerde yukarıdaki teoremlerle çözülür. Örneğin, Amber, Ben ve Curtis arasında yedi tane ayırt edilemeyen bir dolarlık madeni para dağıtmanın yollarının sayısını saymak isterse, her biri en az bir dolar alırsa, dağıtımların temelde üç pozitif tuple'a eşit olduğu gözlemlenebilir. toplamı 7 olan tamsayılar (Buradaki ilk giriş Amber'e verilen madeni para sayısıdır, vb.) Böylece yıldızlar ve çubuklar ile uygulanır. n = 7 ve k = 3 ve var ${displaystyle extstyle {7-1 3-1'i seçin} = 15}$ madeni paraları dağıtmanın yolları.

Ayrıca bakınız

• Oniki kat yol
• Bölme (sayı teorisi)

Referanslar

daha fazla okuma

• Pitman Jim (1993). Olasılık. Berlin: Springer-Verlag. ISBN  0-387-97974-3.
• Weisstein, Eric W. "Çoklu at". Mathworld - Bir Wolfram Web Kaynağı. Alındı 18 Kasım 2012.