Motzkin-Nummern

30

Die n-te Motzkin-Zahl ist die Anzahl der Pfade von (0, 0) bis (n, 0), wobei jeder Schritt die Form (1, -1), (1, 0) oder (1, 1) hat, und der Pfad geht nie unter y = 0.

Hier ist eine Illustration dieser Pfade für n = 1, 2, 3, 4 aus dem obigen Link:

Motzkin-Zahlen

Die gewünschte Sequenz ist OEIS A001006 . OEIS hat einige andere Charakterisierungen der Sequenz.


Sie erhalten eine positive ganze Zahl n als Eingabe. Sie sollten die n-te Motzkin-Nummer ausgeben.

Hier sind die Motzkin-Nummern 1 bis 10:

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

Alle Standardeingabe- und Ausgabemethoden sind zulässig. Es gelten Standardlücken .

Das ist Code Golf. Wenigste Bytes gewinnt.

isaacg
quelle
Was ist die minimale Menge an Motzkin-Zahlen, die wir erzeugen können müssen?
Addison Crump
2
Related
Mego
@FlagAsSpam Alle von ihnen, bis zu Einschränkungen von Zeit / Speicher / Datentyp.
isaacg
Ich denke, Sprachen brauchen jetzt ein Dyck-Wort.
Lirtosiast

Antworten:

15

MATL , 13 bis 14 Bytes

i-2/t.5+hH4Zh

Beispiel:

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

EDIT (16. Juni 2017): Sie können es online ausprobieren! Beachten Sie auch, dass in modernen Sprachversionen (die diese Herausforderung nachholen) die entfernt werden ikönnten.

Erläuterung

Ziemlich einfach, wenn man die Äquivalenz (siehe Gleichung (10)) mit der hypergeometrischen Funktion verwendet :

Bildbeschreibung hier eingeben

Aus der Definition der hypergeometrischen Funktion

Bildbeschreibung hier eingeben

Es ist klar, dass die Reihenfolge der ersten beiden Argumente vertauscht werden kann, wodurch ein Byte eingespart wird.

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
quelle
1
Diese Antwort ist für die kürzeste gebunden und um ungefähr eineinhalb Stunden älter, also akzeptiere ich sie.
Isaacg
Vielen Dank! Ich konnte mir kaum vorstellen, dass MATL überhaupt mit Pyth verbunden sein würde. Es ist so eine schwierige Sprache zu schlagen, gute Arbeit beim Entwerfen!
Luis Mendo
11

Retina , 59-58 Bytes

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

Nimmt unäre Eingaben auf . Eingabe 7 (dh 1111111) dauert eine Weile, ist aber noch in weniger als einer Minute abgeschlossen. Ich würde nicht viel weiter gehen.

Probieren Sie es online aus.

Erläuterung

Eine andere Charakterisierung der Motzkin-Zahlen ist die Anzahl der Saiten aus drei verschiedenen Zeichen, von denen zwei korrekt ausgeglichen sind (daher die enge Beziehung zu den katalanischen Zahlen, die ohne das dritte Zeichen, das unabhängig vom Ausgleich ist, identisch sind).

.NET die Bilanzgruppen sind ziemlich gut an richtig abgestimmt Saiten zu erfassen, so dass wir einfach erzeugen alle Strings der Länge N(mit _, <und >als die drei Zeichen) und dann wir zählen , wie viele von denen sind richtig ausgewogen. ZB für N = 4die gültigen Zeichenfolgen sind:

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

Gegenüber der Definition in der Challenge _entspricht dies einem (1,0)Schritt <nach (1,1)und >nach (1,-1).

Der eigentliche Code :wird als Trennzeichen zwischen den verschiedenen Zeichenfolgen verwendet. Der zweite reguläre Ausdruck ist nur eine Golfform des standardmäßigen .NET- regulären Ausdrucks für ausgeglichene Saiten .

Zu beachten ist, dass :in jedem Schritt nur eine einzige Zeichenfolge zwischen Zeichenfolgen eingefügt wird, die zweite Regex jedoch mit einer führenden und einer nachfolgenden Zeichenfolge übereinstimmt :(und da Übereinstimmungen sich nicht überlappen können, bedeutet dies, dass benachbarte Zeichenfolgen, die aus einer Vorlage im letzten Schritt generiert wurden, nicht beide übereinstimmen können ). Dies ist jedoch kein Problem, da höchstens einer dieser drei Werte jemals übereinstimmen kann:

  • Wenn die Zeichenfolge, die mit "" endet, _übereinstimmt, ist das Präfix ohne "" _bereits richtig ausgeglichen und / <oder >würde das Gleichgewicht aufheben.
  • Wenn die Zeichenfolge in endend >Streichhölzer, wird der String ausgeglichen mit , dass >, so _oder <würde dieses Gleichgewicht abwerfen.
  • Saiten, die auf enden, <können niemals ausgeglichen werden.
Martin Ender
quelle
Es ist eine Schande, dass '\' eine besondere Bedeutung hat, da sonst die Verwendung von '_ / \' - Zeichen besser zum Sinn der Frage passt.
Neil
9

Python 2, 51 Bytes

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

Verwendet die Formel von Mathworld

Bildbeschreibung hier eingeben

Speichert Zeichen , indem Sie den M[n-1]Begriff in die Summierung wie k=n-1, das gibt M[-1]*M[n-1], mit M[-1]=1als Teil der Anfangsbedingung.

Edit: Ein Buchstabe kürzer, der die Summe rekursiv schreibt:

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

Andere Ansätze, die sich als länger herausstellten:

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)
xnor
quelle
8

Pyth, 15 Bytes

Ls*V+KyMb1+t_K1

Dies definiert eine Funktion y. Probieren Sie es online aus: Demonstration

Erläuterung:

Sei y[n]die n-te Motzkin-Zahl. Ich berechne y[n]mit der Formel

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

Beachten Sie, dass der erste Vektor größer als der zweite ist (außer bei der Berechnung y[0]). In diesem Fall ignoriert Pyth automatisch die 1 am Ende des ersten Vektors, sodass beide Vektoren gleich lang sind.

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)

Diese Formel ist eine Variation einer der in OEIS aufgelisteten Formeln. Es kann ein bisschen dumm sein. Aufgrund der 1 am Ende des ersten Vektors (wodurch die Längen ungleich sind) muss ich der Rekursion eigentlich keinen Basisfall geben. Und ich hatte die Hoffnung, dass die beiden +...1irgendwie golfen können. Es stellt sich heraus, dass ich nicht kann.

Sie können eine ähnliche Rekursion mit einem Punktprodukt von Vektoren gleicher Länge definieren und den Basisfall y[0] = 1mit derselben Byteanzahl definieren.

Jakube
quelle
8

CJam (20 Bytes)

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

Online-Demo

Wie Mego in den Kommentaren zu dieser Frage bemerkte, hängt dies sehr eng mit den katalanischen Zahlen zusammen: Ändern Sie den Index .5in 1und versetzen Sie ihn um eins (oder entfernen Sie ihn .5ganz und lassen Sie den Index unverändert), um katalanische Zahlen zu erhalten.

Die verwendete Wiederholung ist

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

von der OEIS-Seite. Die entsprechende Wiederholung für die katalanischen Nummern ist als aufgeführt

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

Peter Taylor
quelle
6

Im Ernst, 21 Bytes

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

Leiht sich Code aus der Catalan Numbers-Lösung von quintopia aus , insbesondere die Verbesserung, die ich in den Kommentaren vorgenommen habe.

Ich benutze die folgende Formel:

Motzkin-Formel

Da nCkist 0 für k > n, summiere ich den ganzen Weg zu n-1, da diese Werte alle 0 sein werden und somit die Summe nicht beeinflussen.

Probieren Sie es online aus

Erläuterung:

,;╗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
quelle
C(n, 2*k)macht was jetzt
Addison Crump
@FlagAsSpam C(n,k) = nCkoder die Anzahl der Elementkombinationen kaus einem Elementpool n.
Mego
Oh, das macht viel mehr Sinn als ich dachte. +1.
Addison Crump
@FlagAsSpam Ich glaube nicht, dass ich wissen möchte, was Sie dachten, dass es ...
Mego
5

R, 64 Bytes

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

Verwendet auch die Mathworld-Formel von @ xnors Python-Antwort . Dank der Vorrangregeln 2:n-2ist äquivalent zu 0:(n-2).

Testfälle:

> 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
quelle
5

Mathematica, 31-30 Bytes

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

Zum Spaß gibt es hier eine 37-Byte-Version

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

und 52-Byte-Version

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

Jelly , 17 14 13 Bytes

×US;
1;HÇƓ¡1ị

Dies verwendet die Wiederholungsrelation aus @ PeterTaylors Antwort . Probieren Sie es online!

Wie es funktioniert

×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
quelle
2

Mathematica, 44 42 34 Bytes

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

Eine 35-Byte-Version:

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

Pari / GP , 38 36 26 Bytes

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

Probieren Sie es online!

Verwenden Sie Gleichung (11) von MathWorld :

Mn=1n+1(n+11)2

woher (nk)2ist ein Trinomialkoeffizient . Per Definition,(nk)2 ist der Koeffizient von xn+k in der Expansion von (1+x+x2)n.

Alephalpha
quelle
Eine 14-Byte- Samau- Funktion unter Verwendung der ersten Definition des Trinomialkoeffizienten:);;7 2D$ⁿ$)╡$÷ . Ich werde es nicht als Antwort posten, da die Sprache neuer ist als die Frage.
alephalpha
Das Posten ist in Ordnung, Sie müssen lediglich einen Haftungsausschluss hinzufügen, der besagt, dass die Einsendung nicht für den Gewinn qualifiziert ist, da, wie Sie sagten, die Sprache neuer ist als die Frage.
Alex A.
2

05AB1E , 13 12 Bytes

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

Probieren Sie es online!

Während die meisten Antworten eine Formel oder eine Wiederholungsrelation verwenden, ist dies ein einfacher Zählansatz.

Jeder mögliche Pfad durch das Gitter wird durch die Liste seiner y-Koordinaten dargestellt. Für n Segmente gibt es insgesamt (n + 1) Punkte, aber der erste und der letzte Punkt sind notwendigerweise 0, so dass (n-1) Punkte angegeben werden müssen.

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

Wir haben jetzt eine Liste von Pfaden (die anfängliche und die letzte 0 sind noch nicht enthalten). Konstruktionsbedingt unterschreitet keiner von ihnen den Wert 0. Einige von ihnen haben jedoch unzulässige Steigungen (z. B. von 0 auf 2 springen), sodass wir sie herausfiltern müssen.

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

Ÿist der Schwankungsbereich eingebaut. Wenn es ein Paar nicht benachbarter Zahlen gibt, werden die fehlenden Zahlen ausgefüllt (z. B. wird [0, 2] zu [0, 1, 2]). Nur legale Pfade bleiben unverändert.

Eine vielleicht intuitivere Möglichkeit, nach illegalen Gefällen zu üαàsuchen, wäre (setzen Sie das Maximum der paarweisen absoluten Unterschiede auf 1). Hierbei fehlt jedoch der flache Pfad [0, 0, ... 0], dessen Korrektur ein zusätzliches Byte kostet.

Beachten Sie schließlich, dass der tatsächliche Code verwendet, wo diese Erklärung verwendet 0.ø. Anstatt den Pfad mit 0en zu umgeben, wird die implizite Eingabe mit zwei Kopien des Pfads umgeben. Dies stellt das Koordinatensystem auf den Kopf und verkehrt herum, ist aber ansonsten gleichwertig.

Grimmig
quelle
2

Stax , 12 Bytes

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

Führen Sie es aus und debuggen Sie es

Ich weiß nicht, wie man ausgefallene mathematische Schriftsätze erstellt, aber dies beruht im Wesentlichen auf einer dynamischen Programmierkonstruktion

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

Rubin, 50

einfache Implementierung der Wiederholungsrelation.

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

Brain-Flak , 90 Bytes

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

Probieren Sie es online!

Berechnet (n0)2-(n2)2, woher (nk)2ist ein Trinomialkoeffizient . Ich konnte diese Formel nirgendwo finden, kann sie also nicht referenzieren, aber sie kann auf dieselbe Weise wie die analoge Formel bewiesen werdenCn=(2nn)-(2nn+1).

Nitrodon
quelle
0

ES6, 44 Bytes

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

Einfache Portierung der rekursiven Python-Lösung von @ xnor. Braucht n<1?1:denn n<1||würde f(0)wiederkommen true.

Neil
quelle