Kısıtlı Parçalanma Hesaplayıcı

Bir n tam sayısının sıra gözetmeksizin tam olarak k pozitif parçanın toplamı olarak kaç yolla yazılabileceğini, yani p(n,k) değerini hesaplar.

Nasıl hesaplanır?

Araç, n sayısının tam olarak k pozitif parçaya, sıra önemsiz olacak şekilde, kaç farklı biçimde bölünebileceğini sayar (yani 7+2+1 ile 1+2+7 aynı parçalanmadır). Bir tabloyu p(n, k) = p(n − 1, k − 1) + p(n − k, k) yinelemesiyle doldurur ve p(0, 0) = 1 değerinden başlar. İlk terim içinde 1'e eşit bir parça bulunan parçalanmaları (o parçayı çıkarın), ikinci terim ise tüm parçaları en az 2 olanları (her parçadan 1 çıkarın) kapsar. İki girdi de tam sayı olmalıdır; 3,6 gibi ondalıklı bir değer sonuç vermez. n 0 ile 200 arasında olmalı, k ise n'yi aşmamalıdır; aksi halde sonuç çıkmaz. n sıfırdan büyükken k = 0 girilirse sayı 0 olur.

Örnek hesaplama

10 sayısını tam olarak 3 pozitif tam sayının toplamı olarak kaç farklı şekilde yazabiliriz? Yineleme p(10, 3) = p(9, 2) + p(7, 3) = 4 + 4 = 8 verir. Sıralayınca doğrulanır: 8+1+1, 7+2+1, 6+3+1, 6+2+2, 5+4+1, 5+3+2, 4+4+2 ve 4+3+3. Sayılar hızla büyür: n = 200 ve k = 100 için araç 190.569.292 döndürür.

Bu örneği deneyin →

Sık yapılan hatalar

  • Sıralı toplamları saymak: burada 7+2+1 ile 1+2+7 aynı parçalanmadır; elle sıralı dizilimleri sayarsanız çok daha büyük bir sayı bulursunuz.
  • Tam k parçalı p(n, k) ile en fazla k parçalı parçalanmaları karıştırmak; ikincisi daha büyük bir sayıdır.
  • Sıfırı parça olarak kabul etmek: her parça en az 1 olmalıdır.
  • k'yi n'den büyük girmek: bu kadar pozitif parçaya bölünemez ve sonuç çıkmaz.
  • 3,6 gibi bir ondalık girip yuvarlanmasını beklemek: araç sonuç vermez, bu yüzden tam sayı girin.

Kaynaklar

Bu hesaplama hakkında

p(n,k), bir n pozitif tam sayısını sırasız olarak tam olarak k pozitif parçanın toplamı şeklinde yazma yollarının sayısını verir. p(n,k) = p(n−1,k−1) + p(n−k,k) şeklindeki klasik yineleme ile hesaplanır; bu yineleme, en küçük parçanın 1 olup olmadığına ya da her parçadan 1 çıkarılıp çıkarılamayacağına göre ayrışır.

Bu kısıtlı sayım, daha genel parçalanma fonksiyonu p(n)'in ve sayılar teorisi ile kombinatorikte kullanılan üretici fonksiyon tekniklerinin bir yapı taşıdır. Bir sayının sabit sayıda parçaya kaç şekilde ayrılabileceğinin sürekli karşılarına çıktığı matematik öğrencileri, yarışma programcıları ve tam sayı parçalanmaları üzerine çalışan araştırmacılar tarafından kullanılır.

Bu faydalı oldu mu?

En fazla 3 tepki seçebilirsiniz.

Editörlerden not

Sonuca güvenmek için iki hızlı kontrol var. k = 1'den 10'a kadar p(10, k) değerleri 1, 5, 8, 9, 7, 5, 3, 2, 1 ve 1 çıkar; toplamları 42'dir, yani 10'un tüm bölümlenmelerinin sayısı. En fazla 3 parça için sayı ise ilk üçün toplamı olan 14'tür, tam 3 parça için çıkan 8 değil. Girdiler n = 200'e kadar gidiyor. Bunu bir bulmaca, programlama yarışması ya da ispat için mi kullanıyorsunuz?

Yorumlar

  • İlk yorumu siz yazın.

Popüler hesaplayıcılar

Tüm Hesaplayıcılar