Tam Sayı Bölüntüleri Hesaplama

Bir pozitif tam sayının sıra gözetmeksizin pozitif tam sayıların toplamı olarak kaç farklı biçimde yazılabileceğini, yani p(n) bölüntü sayısını hesaplar.

Sonuç

11

Nasıl hesaplanır?

Araç, p(n) bölüntü sayısını bulur: n sayısının, sırası önemsiz pozitif tam sayıların toplamı olarak yazılış biçimleri; yani 3+1 ile 1+3 aynıdır. Para üstü yinelemesiyle bir tablo kurulur: p(0) = 1 ile başlanır, sonra her parça boyutu k = 1, 2, …, n için j, k'dan n'ye giderken p(j) = p(j) + p(j − k) güncellenir. Tüm parça boyutları kullanılınca p(n) cevaptır. Girdi 0 ile 250 arasında bir tam sayı olmalıdır; 7,6 gibi ondalıklı bir değer ya da 250'nin üstü sonuç vermez. p(0) = 1 kabul edilir. Sayılar hızla büyür: p(100) = 190.569.292 ve p(250) = 230.793.554.364.681 hâlâ tam olarak gösterilir. Araç bölüntüleri listelemez, yalnızca sayar.

Örnek hesaplama

n = 6 alalım. 1, 2, …, 6 boyutlu parçalara adım adım izin verilince tablo p(6) = 11 ile biter. Hepsini yazarak doğrulayabiliriz: 6; 5+1; 4+2; 4+1+1; 3+3; 3+2+1; 3+1+1+1; 2+2+2; 2+2+1+1; 2+1+1+1+1; 1+1+1+1+1+1. Toplam 11 farklı toplam eder. Karşılaştırma için p(10) = 42; n 6'dan 10'a çıkarken sayı yaklaşık dört katına çıkar.

Bu örneği deneyin →

Sık yapılan hatalar

  • Sıralamaları farklı bölüntü saymak. 4+1+1, 1+4+1 ve 1+1+4 tek bir bölüntüdür; sıralı toplamları saymak kompozisyonları verir ve bunlar çok daha fazladır (2n−1).
  • Tek parçalı bölüntüyü unutmak. n sayısının kendisi de bir bölüntüdür (6'nın tek başına yazılması).
  • 7,6 gibi ondalıklı bir sayı girmek: araç sonuç vermez, tam sayı girin.
  • 250'nin üstünde bir n girmek. Araç orada yaklaşık bir değer değil, sonuç vermez.
  • Farklı parçalı ya da tam k parçalı bölüntüleri p(n) ile karıştırmak. Bu araç kısıtsız tüm bölüntüleri sayar.

Kaynaklar

Bu hesaplama hakkında

Bir pozitif tam sayı n'nin bölüntüsü, sırasının önemli olmadığı pozitif tam sayıların toplamı olarak yazılma biçimidir — örneğin 4 sayısı, 4, 3+1, 2+2, 2+1+1 veya 1+1+1+1 şeklinde bölüntülenebilir ve bu da p(4) = 5 sonucunu verir. Bu hesaplayıcı, tüm bu farklı toplamları sayan bir dinamik programlama yinelemesiyle p(n) değerini 0 ile 250 arasındaki her n için hesaplar.

Matematikçiler ve kombinatorik öğrencileri, bölüntü sayımını sayılar teorisinde temel bir konu olarak kullanır; altta yatan yineleme bağıntısı bilgisayar biliminde de karşımıza çıkar — yarışmacı programcılar, para üstü kombinasyonları, üretici fonksiyonlar ve diğer kombinatorik sayma görevleriyle ilgili problemler için bölüntü sayma algoritmaları uygular.

Bu faydalı oldu mu?

En fazla 3 tepki seçebilirsiniz.

Editörlerden not

p(n) değeri 3+1 ile 1+3'ü aynı bölüntü sayar; yani n özdeş nesneyi yığınlara ayırma yollarını ölçer, sıralı toplamları değil. Hızla büyür: p(10) 42 iken p(100) 190.569.292 olur. Girdi 0 ile 250 arasında bir tam sayıdır; ondalıklı bir değer sonuç vermez. Sizi bölüntülere getiren problem neydi?

Yorumlar

  • İlk yorumu siz yazın.

Popüler hesaplayıcılar

Tüm Hesaplayıcılar