N-е число Моцкина - это число путей от (0, 0) до (n, 0), где каждый шаг имеет форму (1, -1), (1, 0) или (1, 1) и путь никогда не опускается ниже у = 0.

Вот иллюстрация этих путей для n = 1, 2, 3, 4 из ссылки выше:

Желаемая последовательность OEIS A001006 . OEIS имеет некоторые другие характеристики последовательности.

Вам будет дано положительное целое число n в качестве входных данных. Вы должны вывести n-ое число Моцкина.

Вот числа Моцкина с 1 по 10:

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

Все стандартные методы ввода и вывода разрешены. Применяются стандартные лазейки .

Это код гольф. Побеждает несколько байтов.

MATL , 13 14 байтов

i-2/t.5+hH4Zh

Пример:

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

РЕДАКТИРОВАТЬ (16 июня 2017 г.): вы можете попробовать это онлайн! Также обратите внимание, что в современных версиях языка (после этой проблемы) они iмогут быть удалены.

объяснение

Довольно просто, используя эквивалентность (см. Уравнение (10)) с гипергеометрической функцией :

Из определения гипергеометрической функции

Понятно, что порядок первых двух аргументов можно поменять местами, что экономит один байт.

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 байт

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

Принимает участие в одинарных . Ввод 7 (то есть 1111111) занимает довольно много времени, но все же завершается менее чем за минуту. Я бы не пошел намного дальше, чем это.

Попробуйте онлайн.

объяснение

Другая характеристика чисел Моцкина - это число строк трех разных символов, где два из них правильно сбалансированы (отсюда и тесная связь с каталонскими числами, которые одинаковы без третьего символа, который не зависит от балансировки).

Балансировочные группы .NET являются довольно хорошо распознают правильно подобранные строки, так что мы просто генерировать все строки длины N( с использованием _, <а >также трех символов) , а затем мы рассчитываем , сколько из них правильно сбалансированы. Например, для N = 4правильных строк:

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

По сравнению с определением в вызове, _соответствует (1,0)шаг, <к (1,1)и >к (1,-1).

Что касается фактического кода, то :он используется в качестве разделителя между различными строками. Второе регулярное выражение - это просто стандартная форма регулярного выражения .NET для сбалансированных струн .

Следует отметить, что :на каждом шаге между строками вставляется только одна строка, но второе регулярное выражение соответствует начальному и завершающему :(и поскольку совпадения не могут перекрываться, это означает, что смежные строки, сгенерированные из одного шаблона на последнем шаге, не могут совпадать ). Тем не менее, это не проблема, потому что максимум один из этих трех может когда-либо совпадать:

• Если строка, заканчивающаяся на _совпадения, префикс без этого _уже сбалансирован правильно, и <или >будет сбрасывать этот баланс.
• Если строка, заканчивающаяся на >совпадения, строка сбалансирована с этим >, так что _или <будет сбрасывать этот баланс.
• Строки, заканчивающиеся на, <никогда не могут быть сбалансированы.

Python 2, 51 байт

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

Использует формулу из Mathworld

Сохраняет символы, помещая M[n-1]термин в сумму как k=n-1, что дает M[-1]*M[n-1], M[-1]=1как часть начального условия.

Изменить: на один символ короче написание суммы рекурсивно:

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

Другие подходы, которые оказались дольше:

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 байт

Ls*V+KyMb1+t_K1

Это определяет функцию y. Попробуйте онлайн: демонстрация

Объяснение:

Позвольте y[n]быть-число nМоцкина. Я рассчитываю y[n]по формуле

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

Обратите внимание, что первый вектор больше, чем второй (кроме случаев расчета y[0]). В этом случае Pyth автоматически игнорирует 1 в конце первого вектора, так что оба вектора имеют одинаковую длину.

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)

Эта формула является разновидностью одной из формул, перечисленных в OEIS. Это может быть немного глупо. Из-за 1 в конце первого вектора (что делает длины неравными), мне фактически не нужно давать рекурсию базовый случай. И я надеялся, что эти двое +...1могут быть как-то в гольфе. Оказывается, я не могу.

Вы можете определить аналогичную рекурсию с точечным произведением векторов равной длины и определить базовый случай y[0] = 1с тем же количеством байтов.

CJam (20 байтов)

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

Онлайн демо

Как было отмечено Mego в комментариях по этому вопросу, это очень тесно связано с числами каталонских: изменить .5к 1и смещение индекса на единицу (или просто удалить .5полностью и оставить индекс без изменений) , чтобы получить номера каталонской.

Повторение используется

a (n + 2) - a (n + 1) = a (0) * a (n) + a (1) * a (n-1) + ... + a (n) * a (0). [Бернхарт]

со страницы OEIS. Соответствующее повторение каталонских чисел указано как

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

Серьезно, 21 байт

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

Занимает некоторый код из решения Quintopia Catalan Numbers , в частности, улучшение, которое я сделал в комментариях.

Я использую следующую формулу:

Поскольку nCk0 для k > n, я суммирую всю дорогу до n-1, так как все эти значения будут 0 и, следовательно, не влияют на сумму.

Попробуйте онлайн

Объяснение:

,;╗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 байта

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

Использует также формулу Mathworld для ответа @ xnor's python . Благодаря правилам приоритета, 2:n-2эквивалентно 0:(n-2).

Тестовые случаи:

> 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 байт

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

Для развлечения вот 37-байтовая версия

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

и 52-байтовая версия

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

Желе , 17 14 13 байт

×US;
1;HÇƓ¡1ị

При этом используется рекуррентное отношение из ответа @ PeterTaylor . Попробуйте онлайн!

Как это работает

×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 байта

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

35-байтовая версия:

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

Пари / ГП , 38 36 26 байт

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

Попробуйте онлайн!

Используя уравнение (11) из MathWorld :

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

$\binom{n}{k}_2$$\binom{n}{k}_2$$x^{n + k}$$(1 + x + x^2)^n$

05AB1E , 13 12 байт

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

Попробуйте онлайн!

Хотя в большинстве ответов используется формула или рекуррентное отношение, это простой метод подсчета.

Каждый возможный путь через сетку представлен списком его координат y. Для n сегментов имеется всего (n + 1) точек, но первая и последняя обязательно равны 0, так что оставляется (n-1) точек для указания.

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

Теперь у нас есть список путей (не включая начальный и конечный 0). По построению, ни один из них никогда не опускается ниже 0. Однако некоторые из них имеют недопустимые уклоны (например, скачок от 0 до 2), поэтому нам нужно отфильтровать их.

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

Ÿэто колеблющийся диапазон встроенный. Если есть какая-либо пара несмежных чисел, она заполнит пропущенные числа (например, [0, 2] становится [0, 1, 2]). Только законные пути останутся без изменений.

Возможно, более интуитивно понятным способом проверки недопустимых уклонов будет üαà(утверждение, что максимум парных абсолютных разностей равен 1). Однако при этом пропускается плоский путь [0, 0, ... 0], который стоит одного дополнительного байта для исправления.

Наконец, обратите внимание, что реальный код используется .øтам, где используется это объяснение 0.ø. Вместо того, чтобы окружать путь нулями, он окружает неявный ввод двумя копиями пути. Это переворачивает систему координат вверх ногами и наизнанку, но в остальном эквивалентно.

Stax , 12 байт

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

Запустите и отладьте его

Я не знаю, как делать необычные математические наборы, но это, по сути, зависит от конструкции динамического программирования.

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

Рубин, 50

прямая реализация рекуррентного отношения.

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

Brain-Flak , 90 байт

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

Попробуйте онлайн!

${\binom{n}{0}}_2 - {\binom{n}{2}}_2$$\binom{n}{k}_2$$C_n = \binom{2n}{n} - \binom{2n}{n+1}$

ES6, 44 байта

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

Прямой порт рекурсивного решения Python @ xnor. Необходимо, n<1?1:потому n<1||что сделает f(0)возврат true.

Haskell , 55 байтов

Простая реализация рекурсии.

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

Попробуйте онлайн!