Числа Моцкина

30

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

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

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

isaacg
источник
Какой минимальный набор чисел Моцкина мы должны сгенерировать?
Эддисон Крамп
2
Связанные
Мего
@FlagAsSpam Все они, вплоть до ограничений по времени / памяти / типу данных.
Исаак
Я думаю, что языки нуждаются в встроенных словах Дейка.
lirtosiast

Ответы:

15

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)
Луис Мендо
источник
1
Этот ответ привязан к самому короткому и более старшему примерно на полтора часа, поэтому я его принимаю.
Исаак
Благодарность! Я с трудом мог представить, что MATL будет связан с Питом. Это такой сложный язык для битья, хорошая работа по его разработке!
Луис Мендо
11

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 для сбалансированных струн .

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

  • Если строка, заканчивающаяся на _совпадения, префикс без этого _уже сбалансирован правильно, и <или >будет сбрасывать этот баланс.
  • Если строка, заканчивающаяся на >совпадения, строка сбалансирована с этим >, так что _или <будет сбрасывать этот баланс.
  • Строки, заканчивающиеся на, <никогда не могут быть сбалансированы.
Мартин Эндер
источник
Жаль, что «\» имеет особое значение, иначе использование символов «_ / \» будет лучше соответствовать духу вопроса.
Нил
9

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)
XNOR
источник
8

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с тем же количеством байтов.

Jakube
источник
8

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

Питер Тейлор
источник
6

Серьезно, 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
Mego
источник
C(n, 2*k)что делает сейчас?
Аддисон Крамп
@FlagAsSpam C(n,k) = nCk, или количество комбинаций kэлементов из пула nэлементов.
Мего
О, это имеет больше смысла, чем я думал. +1.
Аддисон Крамп
@FlagAsSpam Я не думаю, что хочу знать, что вы думаете, это было ...
Мего
5

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
plannapus
источник
5

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&
Чип Херст
источник
4

Желе , 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.
Деннис
источник
2

Mathematica, 44 42 34 байта

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

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

Coefficient[(1+x+1/x)^#,x]/#&[#+1]&
alephalpha
источник
2

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

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

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

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

MNзнак равно1N+1(N+11)2

(NК)2(NК)2ИксN+К(1+Икс+Икс2)N

alephalpha
источник
14-байты Samau функции , используя первое определение коэффициента трехчлена: );;7 2D$ⁿ$)╡$÷. Я не буду публиковать его как ответ, потому что язык новее, чем вопрос.
алефальфа
Публиковать это просто замечательно, вам просто нужно добавить заявление об отказе от участия в конкурсе, потому что, как вы сказали, язык новее, чем вопрос.
Алекс А.
2

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.ø. Вместо того, чтобы окружать путь нулями, он окружает неявный ввод двумя копиями пути. Это переворачивает систему координат вверх ногами и наизнанку, но в остальном эквивалентно.

Grimmy
источник
2

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])
рекурсивный
источник
1

Рубин, 50

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

g=->n{n<2?1:(3*(n-1)*g[n-2]+(2*n+1)*g[n-1])/(n+2)}
Уровень реки St
источник
1

Brain-Flak , 90 байт

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

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

(N0)2-(N2)2(NК)2СNзнак равно(2NN)-(2NN+1)

Nitrodon
источник
0

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.

Нил
источник