Nomor Motzkin

30

Nomor Motzkin ke-n adalah jumlah jalur dari (0, 0) ke (n, 0) di mana setiap langkah berbentuk (1, -1), (1, 0) atau (1, 1), dan jalur tidak pernah masuk di bawah y = 0.

Berikut ilustrasi jalur ini untuk n = 1, 2, 3, 4, dari tautan di atas:

Nomor Motzkin

Urutan yang diinginkan adalah OEIS A001006 . OEIS memiliki beberapa karakterisasi lain dari urutan.


Anda akan diberi bilangan bulat positif n sebagai input. Anda harus menampilkan Nomor Motzkin ke-n.

Berikut adalah nomor Motzkin 1 hingga 10:

1, 2, 4, 9, 21, 51, 127, 323, 835, 2188

Semua metode input dan output standar diperbolehkan. Celah standar berlaku.

Ini kode golf. Bytes paling sedikit menang.

isaacg
sumber
Berapakah jumlah minimum angka Motzkin yang harus dapat kami hasilkan?
Addison Crump
2
Terkait
Mego
@ FlagAsSpam Semuanya, hingga batasan waktu / memori / tipe data.
isaacg
Saya pikir bahasa membutuhkan kata-kata Dyck bawaan sekarang.
lirtosiast

Jawaban:

15

MATL , 13 14 byte

i-2/t.5+hH4Zh

Contoh:

>> matl i-2/t.5+hH4Zh
> 6
51

EDIT (16 Juni 2017): Anda dapat mencobanya online! Perhatikan juga bahwa dalam versi modern bahasa (yang setelah tanggal tantangan ini) yang idapat dihapus.

Penjelasan

Cukup mudah, menggunakan kesetaraan (lihat persamaan (10)) dengan fungsi hypergeometric :

masukkan deskripsi gambar di sini

Dari definisi fungsi hypergeometric

masukkan deskripsi gambar di sini

jelas bahwa urutan dua argumen pertama dapat dipertukarkan, yang menghemat satu byte.

i         % input                                                   
-2/       % divide by -2
t.5+      % duplicate and add 0.5
h         % horizontal concatenation into a vector                               
H         % number 2
4         % number literal                                          
Zh        % hypergeometric function with three inputs (first input is a vector)
Luis Mendo
sumber
1
Jawaban ini terikat untuk yang terpendek, dan lebih tua sekitar satu setengah jam, jadi saya menerimanya.
isaacg
Terima kasih! Saya hampir tidak bisa membayangkan MATL bahkan akan diikat dengan Pyth. Ini bahasa yang sulit dikalahkan, pekerjaan yang bagus mendesainnya!
Luis Mendo
11

Retina , 59 58 byte

+`(\D*)1(1*)
:$1<$2:$1>$2:$1_$2:
:(_|()<|(?<-2>)>)+:(?!\2)

Mengambil input di unary . Input 7 (yaitu 1111111) membutuhkan waktu cukup lama tetapi masih lengkap dalam waktu kurang dari satu menit. Saya tidak akan melangkah lebih jauh dari itu.

Cobalah online.

Penjelasan

Karakterisasi yang berbeda dari angka-angka Motzkin adalah jumlah string dari tiga karakter yang berbeda, di mana dua dari mereka seimbang dengan benar (maka hubungan dekat dengan angka Catalan, yang sama tanpa karakter ketiga yang independen dari balancing).

Grup penyeimbang .NET cukup bagus dalam mendeteksi string yang cocok dengan benar, jadi kami hanya menghasilkan semua string panjang N(menggunakan _, <dan >sebagai tiga karakter) dan kemudian kami menghitung berapa banyak dari mereka yang diseimbangkan dengan benar. Misalnya untuk N = 4string yang valid adalah:

____
__<>
_<_>
_<>_
<__>
<_>_
<>__
<<>>
<><>

Dibandingkan dengan definisi dalam tantangan, _sesuai dengan (1,0)langkah, <ke (1,1)dan >untuk (1,-1).

Adapun kode aktual, :digunakan sebagai pemisah antara string yang berbeda. Regex kedua hanyalah bentuk golf dari standar .NET regex untuk string seimbang .

Yang perlu diperhatikan adalah hanya ada satu : disisipkan di antara string di setiap langkah, tetapi regex kedua cocok dengan leading dan trailing :(dan karena match tidak bisa tumpang tindih, ini berarti bahwa string yang berdekatan yang dihasilkan dari satu template di langkah terakhir tidak dapat keduanya cocok dengan keduanya ). Namun, ini bukan masalah, karena paling tidak satu dari ketiganya bisa cocok:

  • Jika string berakhiran _ kecocokan, awalan tanpa itu _sudah seimbang dengan benar, dan <atau >akan membuang keseimbangan itu.
  • Jika string berakhir dengan >kecocokan, string seimbang dengan itu >, jadi _atau <akan membuang keseimbangan itu.
  • String yang berakhiran <tidak pernah bisa seimbang.
Martin Ender
sumber
Sayang sekali bahwa '\' memiliki makna khusus jika tidak menggunakan karakter '_ / \' akan lebih cocok dengan semangat pertanyaan.
Neil
9

Python 2, 51 byte

M=lambda n:n<1or sum(M(k)*M(n-2-k)for k in range(n))

Menggunakan formula dari Mathworld

masukkan deskripsi gambar di sini

Menghemat karakter dengan memasukkan M[n-1]istilah ke dalam penjumlahan sebagaik=n-1 , yang memberi M[-1]*M[n-1], dengan M[-1]=1sebagai bagian dari kondisi awal.

Sunting: Satu char lebih pendek menulis jumlah secara rekursif:

M=lambda n,k=0:n<1or k<n and M(k)*M(n-2-k)+M(n,k+1)

Pendekatan lain yang ternyata lebih lama:

M=lambda n,i=0:n and(i>0)*M(n-1,i-1)+M(n-1,i)+M(n-1,i+1)or i==0
M=lambda n:+(n<2)or(3*~-n*M(n-2)+(n-~n)*M(n-1))/(n+2)
Tidak
sumber
8

Pyth, 15 byte

Ls*V+KyMb1+t_K1

Ini mendefinisikan suatu fungsi y. Cobalah online: Demonstrasi

Penjelasan:

Biarkan y[n]menjadi nNomor Motzkin -th. Saya menghitung y[n]dengan rumus

y[n] = dot product of (y[0], ..., y[n-1], 1) and (y[n-2], ..., y[0], 1)

Perhatikan bahwa vektor pertama lebih besar dari vektor kedua (kecuali saat menghitung y[0]). Jika demikian, maka Pyth secara otomatis mengabaikan angka 1 pada akhir vektor pertama, sehingga kedua vektor memiliki panjang yang sama.

Ls*V+KyMb1+t_K1
L                 define a function y(b), which returns:
      yMb            compute the list [y[0], y[1], ..., y[b-1]]
     K               assign it to K
  *V                 vectorized multiplication of
    +K   1             * K with a 1 at the end
          +t_K1        * reverse(K), remove the first element, and append 1
 s                   return the sum (dot product)

Formula ini adalah variasi dari salah satu formula yang terdaftar di OEIS. Mungkin sedikit bodoh. Karena angka 1 pada akhir vektor pertama (yang membuat panjangnya tidak sama), saya tidak benar-benar harus memberikan rekursi sebagai case dasar. Dan saya punya harapan, bahwa keduanya +...1bisa bermain golf entah bagaimana. Ternyata saya tidak bisa.

Anda dapat mendefinisikan rekursi yang sama dengan produk titik dengan vektor dengan panjang yang sama dan mendefinisikan kasing y[0] = 1dengan dengan jumlah byte yang sama.

Jakube
sumber
8

CJam (20 byte)

.5X]{__W%.*:++}qi*W=

Demo online

Seperti yang dicatat Mego dalam komentar pada pertanyaan, ini sangat erat terkait dengan angka Catalan: ubah .5ke 1dan offset indeks dengan satu (atau cukup hapus.5 seluruhnya dan biarkan indeks tidak berubah) untuk mendapatkan angka Catalan.

Perulangan yang digunakan adalah

a (n + 2) - a (n + 1) = a (0) * a (n) + a (1) * a (n-1) + ... + a (n) * a (0). [Bernhart]

dari halaman OEIS. Perulangan yang sesuai untuk nomor Catalan terdaftar sebagai

a (n) = Sum_ {k = 0..n-1} a (k) a (n-1-k).

Peter Taylor
sumber
6

Serius, 21 byte

,;╗r`;τ╜█@;u@τ╣║\*`MΣ

Pinjam beberapa kode dari solusi Catalan Numbers quintopia , khususnya peningkatan yang saya buat di komentar.

Saya menggunakan rumus berikut:

formula motzkin

Karena nCk0 untuk k > n, saya menjumlahkan semua jalan n-1, karena nilai-nilai itu semua akan 0 dan dengan demikian tidak mempengaruhi penjumlahan.

Cobalah online

Penjelasan:

,;╗r`;τ╜█@;u@τ╣║\*`MΣ
,;╗                    push input, dupe, store one copy in register 0
   r                   push range(0, n) ([0,n-1])
    `             `M   map the function:
     ;τ╜█@               dupe k, push C(n, 2*k), swap with k
          ;u@τ╣║\        push the kth Catalan number
                 *       multiply
                    Σ  sum
Mego
sumber
C(n, 2*k)lakukan apa sekarang?
Addison Crump
@ FlagAsSpam C(n,k) = nCk, atau jumlah kombinasi kitem dari kumpulan nitem.
Mego
Oh, itu jauh lebih masuk akal daripada yang kupikirkan sebelumnya. +1.
Addison Crump
@FlagAsSpam Saya rasa saya tidak ingin tahu apa yang Anda pikirkan ...
Mego
5

R, 64 byte

f=function(n)ifelse(n<2,1,f(n-1)+sum(rev(s<-sapply(2:n-2,f))*s))

Menggunakan juga rumus Mathworld dari jawaban python @ xnor . Berkat aturan prioritas, 2:n-2setara dengan0:(n-2) .

Kasus uji:

> f(0)
[1] 1
> f(1)
[1] 1
> f(5)
[1] 21
> f(10)
[1] 2188
> sapply(0:20,f)
 [1]        1        1        2        4        9       21       51      127
 [9]      323      835     2188     5798    15511    41835   113634   310572
[17]   853467  2356779  6536382 18199284 50852019
plannapus
sumber
5

Mathematica, 31 30 byte

AppellF1[-#/2,.5,-#/2,2,4,4]&

Untuk bersenang-senang, inilah versi 37 byte

Hypergeometric2F1[(1-#)/2,-#/2,2,4]&

dan versi 52 byte

SeriesCoefficient[1-x-Sqrt[1-2x-3x^2],{x,0,#+2}]/2&
Chip Hurst
sumber
4

Jelly , 17 14 13 byte

×US;
1;HÇƓ¡1ị

Ini menggunakan relasi perulangan dari jawaban @ PeterTaylor . Cobalah online!

Bagaimana itu bekerja

×US;      Define a helper link. Left argument: a (list)

×U        Multiply (×) a by its reverse (U).
  S       Compute the sum of the resulting list.
   ;      Prepend it to a.
          Return the result.

1;HÇƓ¡1ị  Define the main link.

1         Set the left argument to 1.
 ;H       Append the half of 1 to 1. Result: [1, 0.5].
    Ɠ     Read an integer n from STDIN.
   Ç ¡    Call the helper link (Ç) n times.
      1ị  Retrieve the result at index 1.
Dennis
sumber
2

Mathematica, 44 42 34 byte

Sum[#!/(i!(i+1)!(#-2i)!),{i,0,#}]&

Versi 35 byte:

Coefficient[(1+x+1/x)^#,x]/#&[#+1]&
alephalpha
sumber
2

Pari / GP , 38 36 26 byte

n->(1+x+x^2)^n++/n\x^n++%x

Cobalah online!

Menggunakan persamaan (11) dari MathWorld :

M.n=1n+1(n+11)2

(nk)2(nk)2xn+k(1+x+x2)n

alephalpha
sumber
A 14-byte Samau fungsi menggunakan definisi pertama dari koefisien trinomial: );;7 2D$ⁿ$)╡$÷. Saya tidak akan mempostingnya sebagai jawaban karena bahasanya lebih baru dari pertanyaan.
alephalpha
Posting itu baik-baik saja, Anda hanya perlu menambahkan sangkalan bahwa kiriman tidak memenuhi syarat untuk menang karena, seperti yang Anda katakan, bahasanya lebih baru daripada pertanyaan.
Alex A.
2

05AB1E , 13 12 byte

ÝI<ãʒ.øDŸQ}g

Cobalah online!

Sementara sebagian besar jawaban menggunakan rumus atau hubungan perulangan, ini adalah pendekatan penghitungan sederhana.

Setiap jalur yang mungkin melalui grid diwakili oleh daftar koordinat y-nya. Untuk n segmen, ada total (n + 1) poin, tetapi yang pertama dan terakhir adalah 0, sehingga meninggalkan (n-1) poin untuk ditentukan.

Ý           # range [0..n]
 I<         # n - 1
   ã        # cartesian power

Kami sekarang memiliki daftar jalur (belum termasuk awal dan akhir 0). Dengan konstruksi, tidak satu pun dari mereka yang berada di bawah 0. Namun, beberapa dari mereka memiliki lereng ilegal (misalnya melompat dari 0 ke 2), jadi kita perlu menyaringnya.

ʒ      }g   # count how many paths satistfy the following condition
 0.ø        # surround with 0
      Q     # is equal to
    DŸ      # its own fluctuating range

Ÿadalah rentang bawaan yang berfluktuasi . Jika ada pasangan angka yang tidak berdekatan, itu akan mengisi angka yang hilang (mis. [0, 2] menjadi [0, 1, 2]). Hanya jalur hukum yang akan dibiarkan tidak berubah.

Cara yang mungkin lebih intuitif untuk memeriksa lereng ilegal adalah üαà (menyatakan maksimum perbedaan absolut berpasangan sama dengan 1). Namun, ini melewatkan jalur flat [0, 0, ... 0], yang membutuhkan satu byte tambahan untuk memperbaikinya.

Akhirnya, perhatikan bahwa kode aktual menggunakan tempat penjelasan ini digunakan 0.ø. Alih-alih mengelilingi jalan dengan 0s, ini mengelilingi input implisit dengan dua salinan jalur. Ini mengubah sistem koordinat terbalik dan dalam-luar, tetapi sebaliknya setara.

Grimmy
sumber
2

Stax , 12 byte

îu¬@Y≤ÅÉÑ(πε

Jalankan dan debug itu

Saya tidak tahu bagaimana melakukan penyusunan huruf matematika yang mewah, tetapi ini pada dasarnya bergantung pada konstruksi pemrograman yang dinamis

M(0) = 1
M(1) = 1
M(n + 1) = M(n) + sum(M(k) * M(n - k - 1) for k in [0..n-1])
rekursif
sumber
1

Ruby, 50

implementasi langsung dari hubungan perulangan.

g=->n{n<2?1:(3*(n-1)*g[n-2]+(2*n+1)*g[n-1])/(n+2)}
Level River St
sumber
1

Brain-Flak , 90 byte

(([{}]<(())>)<{({}()<{<>([({})]({}[({})]({}<>{}<>)))<>}<>>)}>){({}()<{}>)}{}({}{}[{}{}]<>)

Cobalah online!

(n0)2-(n2)2(nk)2Cn=(2nn)-(2nn+1)

Nitrodon
sumber
0

ES6, 44 byte

f=(n,k=0)=>n<1?1:k<n&&f(k)*f(n-2-k)+f(n,k+1)

Port langsung dari solusi Python rekursif @ xnor. Dibutuhkan n<1?1:karena n<1||akan membuat f(0)kembali true.

Neil
sumber