N-ta liczba Motzkina to liczba ścieżek od (0, 0) do (n, 0), gdzie każdy krok ma postać (1, -1), (1, 0) lub (1, 1), oraz ścieżka nigdy nie spada poniżej y = 0.

Oto ilustracja tych ścieżek dla n = 1, 2, 3, 4 z powyższego linku:

Pożądana sekwencja to OEIS A001006 . OEIS ma kilka innych charakterystyk sekwencji.

Jako dane wejściowe otrzymasz dodatnią liczbę całkowitą n. Powinieneś podać n-ty numer Motzkina.

Oto numery Motzkin od 1 do 10:

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

Wszystkie standardowe metody wejścia i wyjścia są dozwolone. Obowiązują standardowe luki .

To jest kod golfowy. Wygrywa najmniej bajtów.

MATL , 13 14 bajtów

i-2/t.5+hH4Zh

Przykład:

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

EDYCJA (16 czerwca 2017 r.): Możesz spróbować online! Należy również pamiętać, że we współczesnych wersjach języka (które stanowią wyzwanie po tej dacie) imożna je usunąć.

Wyjaśnienie

Całkiem proste, używając równoważności (patrz równanie (10)) z funkcją hipergeometryczną :

Z definicji funkcji hipergeometrycznej

jasne jest, że kolejność pierwszych dwóch argumentów może być zamieniona, co oszczędza jeden bajt.

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)

Retina , 59 58 bajtów

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

Pobiera dane wejściowe jednoargumentowe . Wejście 7 (tj. 1111111) Zajmuje sporo czasu, ale nadal kończy się w mniej niż minutę. Nie poszedłbym znacznie dalej.

Wypróbuj online.

Wyjaśnienie

Inną charakterystyką liczb Motzkina jest liczba łańcuchów trzech różnych znaków, przy czym dwa z nich są odpowiednio zrównoważone (stąd ścisły związek z liczbami katalońskimi, które są takie same bez trzeciego znaku niezależnego od równoważenia).

Grupy równoważące .NET są całkiem dobre w wykrywaniu poprawnie dopasowanych ciągów, więc po prostu generujemy wszystkie ciągi długości N(używając _, <i >jako trzy znaki), a następnie liczymy, ile z nich jest poprawnie zrównoważonych. Np. Dla N = 4prawidłowych ciągów są:

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

W porównaniu z definicją w wyzwaniu, _odpowiada (1,0)kroku, <do (1,1)i >z (1,-1).

Jeśli chodzi o rzeczywisty kod, :jest on używany jako separator między różnymi łańcuchami. Drugie wyrażenie regularne to po prostu golfowa forma standardowego wyrażenia regularnego .NET dla zbalansowanych ciągów .

Należy zauważyć, że :pomiędzy ciągami znaków na każdym kroku jest tylko jeden , ale drugi wyrażenie regularne pasuje do wiodącego i końcowego :(a ponieważ dopasowania nie mogą się pokrywać, oznacza to, że sąsiednie ciągi wygenerowane z jednego szablonu w ostatnim kroku nie mogą się zgadzać ). Nie stanowi to jednak problemu, ponieważ co najwyżej jedna z tych trzech może się równać:

• Jeśli ciąg znaków zakończony _dopasowaniami, prefiks bez tego _jest już poprawnie zrównoważony i / <lub >zrzuciłby tę równowagę.
• Jeśli łańcuch zakończony >dopasowaniami, zostanie zrównoważony z tym >, tak _lub <zrzuci tę równowagę.
• Ciągi kończące się na <nigdy nie mogą być zrównoważone.

Python 2, 51 bajtów

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

Wykorzystuje formułę z Mathworld

Zapisuje znaki, umieszczając M[n-1]termin w podsumowaniu jako k=n-1, co daje M[-1]*M[n-1], M[-1]=1jako część warunku początkowego.

Edycja: O jeden znak krótszy zapis sumy rekurencyjnie:

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

Inne podejścia, które okazały się dłuższe:

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)

Pyth, 15 bajtów

Ls*V+KyMb1+t_K1

To definiuje funkcję y. Wypróbuj online: demonstracja

Wyjaśnienie:

Niech y[n]będzie n-tym numerem Motzkina. Obliczam y[n]według wzoru

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

Zauważ, że pierwszy wektor jest większy niż drugi (z wyjątkiem obliczeń y[0]). W takim przypadku Pyth automatycznie ignoruje 1 na końcu pierwszego wektora, więc oba wektory mają równą długość.

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)

Ta formuła jest odmianą jednej z formuł wymienionych w OEIS. To może być trochę głupie. Ze względu na 1 na końcu pierwszego wektora (co powoduje, że długości są nierówne), tak naprawdę nie muszę nadawać rekurencji podstawowego przypadku. Miałem nadzieję, że te dwa +...1można jakoś zagrać w golfa. Okazuje się, że nie mogę.

Możesz zdefiniować podobną rekurencję za pomocą iloczynu kropkowego o wektorach o jednakowej długości i zdefiniować wielkość liter y[0] = 1przy użyciu tej samej liczby bajtów.

CJam (20 bajtów)

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

Demo online

Jak zauważył Mego w komentarzach do pytania, jest to bardzo ściśle związane z liczbami katalońskimi: zmień indeks .5na 1i przesunąć indeks o jeden (lub po prostu usuń .5całkowicie i pozostaw indeks bez zmian), aby uzyskać liczby katalońskie.

Zastosowano powtarzalność

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

ze strony OEIS. Odpowiednie powtórzenie liczb katalońskich jest wymienione jako

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

Poważnie, 21 bajtów

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

Pożycza trochę kodu z rozwiązania Catalan Numbers firmy Quintopia , w szczególności ulepszenia, które wprowadziłem w komentarzach.

Używam następującej formuły:

Ponieważ nCkwynosi 0 k > n, sumuję do samego końca n-1, ponieważ wszystkie te wartości będą równe 0, a zatem nie będą miały wpływu na sumę.

Wypróbuj online

Wyjaśnienie:

,;╗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

R, 64 bajty

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

Wykorzystuje również formułę Mathworld w odpowiedzi na python @ xnor . Dzięki regułom pierwszeństwa 2:n-2jest równoważne z 0:(n-2).

Przypadki testowe:

> 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

Mathematica, 31 30 bajtów

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

Dla zabawy, oto 37-bajtowa wersja

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

i wersja 52-bajtowa

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

Galaretka , 17 14 13 bajtów

×US;
1;HÇƓ¡1ị

Wykorzystuje relację powtarzalności z odpowiedzi @ PeterTaylor . Wypróbuj online!

Jak to działa

×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.

Mathematica, 44 42 34 bajty

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

A 35 bytes version:

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

Pari/GP, 38 36 26 bytes

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

Try it online!

Using equation (11) from MathWorld:

$M_n = \dfrac{1}{n + 1} \dbinom{n + 1}{1}_2$

where $\binom{n}{k}_2$ is a trinomial coefficient. By definition, $\binom{n}{k}_2$ is the coefficient of $x^{n + k}$ in the expansion of $(1 + x + x^2)^n$.

05AB1E, 13 12 bytes

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

Try it online!

While most answers use a formula or recurrence relation, this is a simple counting approach.

Each possible path through the grid is represented by the list of its y coordinates. For n segments, there are a total of (n+1) points, but the first and last one are necessarily 0, so that leaves (n-1) points to specify.

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

We now have a list of paths (not yet including the initial and final 0). By construction, none of them ever go below 0. However, some of them have illegal slopes (e.g. jump from 0 to 2), so we need to filter them out.

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

Ÿ is the fluctuating range built-in. If there's any pair of non-adjacent numbers, it will fill in the missing numbers (e.g. [0, 2] becomes [0, 1, 2]). Only legal paths will be left unchanged.

A perhaps more intuitive way to check for illegal slopes would be üαà (assert the maximum of pairwise absolute differences equals 1). However, this misses the flat [0, 0, ... 0] path, which costs one extra byte to fix.

Finally, note that the actual code uses .ø where this explanation uses 0.ø. Instead of surrounding the path with 0s, this surrounds the implicit input with two copies of the path. This turns the coordinate system upside-down and inside-out, but is otherwise equivalent.

Stax, 12 bytes

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

Run and debug it

I don't know how to do fancy math typesetting, but this essentially relies on a dynamic programming construction

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

Ruby, 50

straightforward implementation of the recurrence relation.

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

Brain-Flak, 90 bytes

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

Try it online!

Computes ${\binom{n}{0}}_2 - {\binom{n}{2}}_2$, where $\binom{n}{k}_2$ is a trinomial coefficient. I couldn't find this formula anywhere, so I can't reference it, but it can be proved in the same way as the analogous formula $C_n = \binom{2n}{n} - \binom{2n}{n+1}$.

ES6, 44 bytes

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

Straightforward port of @xnor's recursive Python solution. Needs n<1?1: because n<1|| would make f(0) return true.

Haskell, 55 bytes

Straightforward implementation of the recursion.

a n|n>2=((2*n+1)*a(n-1)+(3*n-3)*a(n-2))`div`(n+2)
a n=n

Try it online!