Jumlah Absolut dari Koefisien Polinomial Sidi

28

Latar Belakang

Sidi polinomial derajat n - atau (n + 1) th Sidi polinomial - didefinisikan sebagai berikut.

definisi polinomial Sidi

Polinomial Sidi memiliki beberapa sifat yang menarik, tetapi demikian juga koefisiennya. Bentuk terakhir dari urutan OEIS A075513 .

Tugas

Menulis sebuah program penuh atau fungsi yang, diberikan bilangan bulat non-negatif n , cetakan atau hasil penjumlahan absolut dari koefisien dari Sidi polinomial derajat n , yang

definisi output yang diinginkan

Jumlah ini membentuk urutan OEIS A074932 .

Jika Anda lebih suka pengindeksan 1 berbasis, Anda dapat mengambil bilangan bulat positif n bukan dan menghitung jumlah absolut dari koefisien dari n th Sidi jumlahnya banyak.

Karena ini , Anda harus membuat kode sesingkat mungkin. Semua aturan standar berlaku.

Test case (berbasis-0)

 n           Σ

 0           1
 1           3
 2          18
 3         170
 4        2200
 5       36232
 6      725200
 7    17095248
 8   463936896
 9 14246942336

Uji kasus (berbasis 1)

 n           Σ

 1           1
 2           3
 3          18
 4         170
 5        2200
 6       36232
 7      725200
 8    17095248
 9   463936896
10 14246942336
Dennis
sumber

Jawaban:

46

Python 2 , 43 byte

f=lambda n,k=1:k/n or n*f(n,k+1)+k*f(n-1,k)

Cobalah online!

Pendekatan yang berbeda

Sejak saya memposting tantangan ini, saya mencoba mencari solusi rekursif untuk masalah ini. Sementara saya gagal menggunakan tidak lebih dari pena dan kertas, saya berhasil mengubah formula menjadi golf menjadi masalah praktis - setidaknya untuk definisi praktis tertentu - yang membuatnya lebih mudah untuk dianalisis.

Bayangkan sebuah game show dengan kandidat k + m yang berfungsi sebagai berikut.

Di babak 1, semua kandidat harus menyelesaikan tugas tertentu secepat mungkin. The k kandidat yang menyelesaikan tugas yang tercepat menang 1 k $ (satu kilodollar) masing-masing dan maju ke putaran 3.

Di babak 2, m kandidat yang tersisa mendapatkan kesempatan kedua untuk bergabung dengan k lainnya . Setiap kandidat ditanyai pertanyaan. Jika mereka menjawab pertanyaan dengan benar, mereka menang 1 k $ dan maju ke putaran 3. Namun, jika mereka gagal menjawab pertanyaan, mereka tersingkir dari permainan. Ini berarti ronde 3 akan memiliki antara k dan k + m kandidat, tergantung pada berapa banyak yang dapat menjawab pertanyaan mereka.

Round 3 terdiri dari m lebih kontes yang mirip dengan putaran 1. Dalam setiap kontes, peserta harus menyelesaikan tugas tertentu. Tidak seperti putaran 1, hanya satu kandidat yang menerima hadiah, tetapi semua kandidat dapat berpartisipasi dalam kontes berikutnya. Setiap kontes membayar dua kali lipat dari kontes sebelumnya; yang pertama membayar 2 k $ dan yang terakhir 2 m k $ .

Perhatikan bahwa karena semua hadiah adalah kekuatan dua, mengetahui berapa banyak hadiah uang yang diperoleh seorang kandidat berarti kita tahu jika mereka maju ke putaran 3 dan yang mana dari kontes putaran 3 yang mereka menangkan.

Asumsikan Anda sedang menonton acara pertandingan dan bulat 1 sudah berakhir, sehingga Anda tahu mana k calon telah mencapai putaran 3 dan yang m kandidat masih tertahan di putaran 2. Dalam berapa banyak cara dapat hadiah uang yang tersisa akan didistribusikan?

Setelah kita tahu yang mana dari putaran kedua ini m kandidat telah maju ke putaran 3, mudah untuk menghitung kemungkinan hasil untuk skenario tertentu. Jika j kandidat maju, ada k + j total kandidat di babak 3, dan dengan demikian k + j hasil yang mungkin untuk setiap kontes. Dengan m kontes individu di babak 3, ini membuat (k + j) m hasil untuk semua kontes m .

Sekarang, j dapat mengambil nilai apa pun antara 0 dan m , tergantung pada kandidat mana yang menjawab dengan benar di babak 2. Untuk setiap nilai fix dari j , ada m C j kombinasi yang berbeda dari kandidat j yang bisa maju ke putaran 3. Jika kita memanggil jumlah total hasil yang mungkin untuk k ronde 3 kandidat dan m ronde 2 kandidat g (m, k) , kita mendapatkan rumus berikut.

rumus untuk g

Jika kami memperbaiki k = 1 , kami mendapatkan kasus khusus berikut, yang merupakan pendekatan baru kami untuk menyelesaikan masalah aslinya.

hubungan antara Sigma dan g

Formula rekursif

Sekarang, anggaplah Anda tertidur selama iklan setelah ronde 1, dan bangun tepat waktu untuk melihat siapa yang memenangkan kontes terakhir ronde 3 dan dengan demikian hadiah utama 2 m k $ . Anda tidak memiliki informasi lain, bahkan berapa total hadiah uang yang dimenangkan oleh kandidat. Dalam berapa cara sisa uang hadiah dibagikan?

Jika pemenang adalah salah satu m kandidat putaran 2, kita sudah sekarang bahwa mereka harus maju ke putaran 3 . Dengan demikian, kita secara efektif memiliki k + 1 kandidat di babak 3, tetapi hanya m - 1 kandidat di babak 2. Karena kita tahu pemenang dari kontes terakhir, hanya ada kontes m - 1 dengan hasil yang tidak pasti, sehingga ada g (m - 1, k +1) kemungkinan hasil.

Jika pemenangnya adalah salah satu kandidat k yang melewati putaran 2, perhitungannya menjadi sedikit lebih rumit. Seperti sebelumnya, hanya ada ronde m - 1 yang tersisa, tetapi sekarang kami masih memiliki kandidat k di ronde 3 dan m kandidat di ronde 2. Karena jumlah ronde 2 kandidat dan jumlah ronde 3 berbeda, hasil yang mungkin tidak dapat dihitung dengan doa sederhana g . Namun, setelah ronde 2 kandidat pertama menjawab - benar atau salah - jumlah ronde 2 cocok sekali lagi dengan kontes m - 1 ronde 3. Jika kandidat maju, ada k + 1 ronde 3 kandidat dan dengan demikian g (m - 1, k + 1)kemungkinan hasil; jika kandidat dieliminasi, jumlah kandidat ronde 3 tetap pada k dan ada g (m - 1, k) hasil yang mungkin. Karena kandidat maju atau tidak, ada g (m - 1, k + 1) + g (m - 1, k) hasil yang mungkin menggabungkan kedua kasus ini.

Sekarang, jika kita menambahkan hasil potensial untuk semua kandidat k + m yang bisa memenangkan hadiah utama, hasilnya harus cocok dengan g (m, k) . Ada kontestan m babak 2 yang mengarah ke g (m - 1, k + 1) hasil potensial masing-masing, dan k babak 3 kontestan yang mengarah ke g (m - 1, k + 1) + g (m - 1, k) yang Kesimpulannya, kita mendapatkan identitas berikut.

rumus rekursif untuk g

Bersama dengan base case

kasing dasar untuk g

dua formula ini mencirikan fungsi g sepenuhnya.

Implementasi golf

Sementara

g=lambda m,k=1:0**m or(m+k)*g(m-1,k+1)+k*g(m-1,k)

(49 byte, 0**mmenghasilkan 1 kali m turun ke 0 ) atau genap

g=lambda m,k=1:m<1 or(m+k)*g(m-1,k+1)+k*g(m-1,k)

(48 byte, mengembalikan True, bukan 1 ) akan menjadi solusi yang valid, masih ada byte yang harus disimpan.

Jika kita mendefinisikan fungsi f yang mengambil nomor n dari ronde 1 kandidat bukan jumlah m dari ronde 2 kandidat sebagai argumen pertama, yaitu,

definisi f dalam hal g

kami mendapatkan formula rekursif

rumus rekursif untuk f

dengan kasus dasar

kasing dasar untuk f

Akhirnya, kita punya

hubungan antara Sigma dan f

jadi implementasi Python

f=lambda n,k=1:k/n or n*f(n,k+1)+k*f(n-1,k)

( k/nmenghasilkan 1 sekali n = k ) menyelesaikan tugas yang ada dengan pengindeksan berbasis 1.

Dennis
sumber
8

Mathematica, 33 32 byte

Disimpan satu byte berkat JungHwan Min .

Binomial[#,r=0~Range~#].(r+1)^#&
alephalpha
sumber
4

Pyth - 13 12 byte

Cukup laksanakan formula tanpa (-1)^kbagian.

sm*.cQd^hdQh

Test Suite .

Maltysen
sumber
3

MATL , 12 byte

t:XnG:QG^*sQ

Input berbasis 0.

Cobalah online!

Penjelasan

Pertimbangkan input 5sebagai contoh.

t      % Take n implicitly. Duplicate
       % STACK: 5, 5
:      % Range [1 2 ...n]
       % STACK: 5, [1 2 3 4 5]
Xn     % N-choose-k, vectorized
       % STACK: [5 10 10 5 1]
G:Q    % Push [2 3 ... n+1]
       % STACK: [5 10 10 5 1], [2 3 4 5 6]
G^     % Raise to n
       % STACK: [5 10 10 5 1], [32 243 1024 3125 7776]
*      % Multiply, element-wise
       % STACK: [160 2430 10240 15625 7776]
s      % Sum of array
       % STACK: 36231
Q      % Add 1. Display implicitly
       % STACK: 36232
Luis Mendo
sumber
2

R, 36 byte

sum(choose(n<-scan(),0:n)*(0:n+1)^n)

Vektorisasi R sangat berguna di sini saat menerapkan rumus.

Billywob
sumber
2

J , 19 byte

+/@((!{:)*>:^{:)@i.

Menggunakan pengindeksan berbasis satu.

Cobalah online!

Penjelasan

+/@((!{:)*>:^{:)@i.  Input: integer n
                 i.  Range [0, 1, ..., n-1]
   (           )@    Operate on that range
             {:        Get the last value, n-1
          >:           Increment, range becomes [1, 2, ..., n]
            ^          Exponentiate. [1^(n-1), 2^(n-1), ..., n^(n-1)]
    ( {:)              Get the last value, n-1
     !                 Binomial coefficient. [C(n-1, 0), C(n-1, 1), ..., C(n-1, n-1)]
         *             Multiply
+/@                  Reduce by addition
mil
sumber
1

Maxima, 39 byte

f(n):=sum(binomial(n,k)*(k+1)^n,k,0,n);
rahnema1
sumber
1

PARI / GP, 35 byte

n->sum(k=0,n,binomial(n,k)*(k+1)^n)
alephalpha
sumber
0

Aksioma, 39 byte

f(n)==sum(binomial(n,i)*(i+1)^n,i=0..n)

kode uji dan hasil

(35) -> [[i,f(i)] for i in 0..9]
   (35)
   [[0,1], [1,3], [2,18], [3,170], [4,2200], [5,36232], [6,725200],
    [7,17095248], [8,463936896], [9,14246942336]]
RosLuP
sumber
0

Jelly , 9 byte

cR×R‘*ƊS‘

Cobalah online!

Bagaimana itu bekerja

cR×R‘*ƊS‘ - Main link. Argument: n (integer)        e.g.   5
 R        - Range from 1 to n                              [1, 2, 3, 4, 5]
c         - Binomial coefficient                           [5, 10, 10, 5, 1]
      Ɗ   - Last three links as a monad:
   R      -   Link 1: Range from 1 to n                    [1, 2, 3, 4, 5]
    ‘     -   Link 2: Increment                            [2, 3, 4, 5, 6]
     *    -   Link 3: To the power of n                    [32, 243, 1024, 3125, 7776]
  ×       - Multiply, pairwise                             [160, 2430, 10240, 15625, 7776]
       S  - Sum                                            36231
        ‘ - Increment                                      36232

sumber