Um número de campainha ( OEIS A000110 ) é o número de maneiras de particionar um conjunto de n elementos rotulados (distintos). O número 0 da campainha é definido como 1.

Vejamos alguns exemplos (eu uso colchetes para denotar os subconjuntos e chaves para as partições):

1: {1}
2: {[1,2]}, {[1],[2]}
3: {[1,2,3]}, {[1,2],[3]}, {[1,3],[2]}, {[2,3],[1]}, {[1],[2],[3]}

Existem muitas maneiras de calcular os números de campainha e você pode usar qualquer um deles. Uma maneira será descrita aqui:

A maneira mais fácil de calcular os números de Bell é usar um triângulo numérico semelhante ao triângulo de Pascal para os coeficientes binomiais. Os números dos sinos aparecem nas bordas do triângulo. Começando com 1, cada nova linha no triângulo é construída tomando a última entrada na linha anterior como a primeira entrada e definindo cada nova entrada para o vizinho esquerdo mais o vizinho superior esquerdo:

1
1    2
2    3    5
5    7   10   15
15  20   27   37   52

Você pode usar indexação 0 ou indexação 1. Se você usar a indexação 0, uma entrada de 3deve sair 5, mas deve sair 2se você usar a indexação 1.

Seu programa deve trabalhar até o número 15 da Bell, emitindo 1382958545. Em teoria, seu programa deve ser capaz de lidar com números maiores (em outras palavras, não codifique as soluções). EDIT: você não precisa lidar com uma entrada de 0 (para indexação 0) ou 1 (para indexação 1) porque não é calculada pelo método do triângulo.

Casos de teste (assumindo a indexação 0):

0 ->  1 (OPTIONAL)
1 ->  1 
2 ->  2 
3 ->  5 
4 ->  15 
5 ->  52 
6 ->  203 
7 ->  877 
8 ->  4140 
9 ->  21147 
10 -> 115975 
11 -> 678570 
12 -> 4213597 
13 -> 27644437 
14 -> 190899322 
15 -> 1382958545

As respostas que usam um método interno (como BellB [n] na Wolfram Language) que produz diretamente números de Bell não serão competitivas.

O código mais curto (em bytes) vence.

Geléia , 9 bytes

ṖµṀcæ.߀‘

Isso usa a fórmula

que é fechado sempre que n <2 .

Experimente online!

Como funciona

ṖµṀcæ.߀‘  Main link. Argument: n

Ṗ          Pop; yield A := [1, ..., n-1].
 µ         Begin a new, monadic chain with argument A.
  Ṁ        Maximum; yield n-1.
   c       Combinatons; compute (n-1)C(k) for each k in A.
      ߀   Recursively map the main link over A.
    æ.     Take the dot product of the results to both sides.
        ‘  Increment; add 1 to the result.

JavaScript (ES6), 47 bytes

f=(n,a=[b=1])=>n--?f(n,[b,...a.map(e=>b+=e)]):b
f=(n,a=[b=1])=>--n?f(n,[b,...a.map(e=>b+=e)]):b

O primeiro é indexado a 0, o segundo é indexado a 1.

Haskell, 36 bytes

head.(iterate(last>>=scanl(+))[1]!!)

Usa o método triângulo, manipula corretamente 0, 0 com base.

R , 31 bytes

sum(gmp::Stirling2.all(scan()))

usa a fórmula Número Stirling do Segundo Tipo e calcula esses números com o pacote gmp ; lê de stdin e retorna o valor como um número inteiro grande; falha para 0; 1 indexado.

Mathematica, 24 bytes

Sum[k^#/k!,{k,0,∞}]/E&

-13 bytes de @Kelly Lowder!

Geléia , 14 12 11 bytes

ṫ0;⁸+\
1Ç¡Ḣ

Experimente online!

Não atingiu exatamente os pontos fortes do Jelly com entrada dinâmica ¡, Ṫ sempre modificando a matriz e a falta de um átomo precedente (um byte ;@ou reverso ṭ).

CJam (19 bytes)

Xa{X\{X+:X}%+}qi*0=

Demonstração online

Dissecação

Xa         e# Start with an array [1]
{          e# Repeat...
  X\       e#   Put a copy of X under the current row
  {X+:X}%  e#   Map over x in row: push (X+=x)
  +        e#   Prepend that copy of last element of the previous row to get the next row
}
qi*        e# ... input() times
0=         e# Select the first element

MATL , 14 bytes

:dtEw1Zh1Ze/Yo

A entrada é baseada em 0. Experimente online!

Explicação

Isso usa a fórmula

onde _p F _q ( a ₁ , ..., a _p ; b ₁ , ..., b _q ; x ) é a função hipergeométrica generalizada .

:      % Implictly input n. Push array [1 2 ... n]
d      % Consecutive differences: array [1 ... 1] (n-1 entries)
tE     % Duplicate, multiply by 2: array [2 ... 2] (n-1 entries)
w      % Swap
1      % Push 1
Zh     % Hypergeometric function
1Ze    % Push number e
/      % Divide
Yo     % Round (to prevent numerical precision issues). Implicitly display

Python , 42 bytes

f=lambda n,k=0:n<1or k*f(n-1,k)+f(n-1,k+1)

Experimente online!

A fórmula recursiva vem da colocação de nelementos em partições. Para cada elemento, por sua vez, decidimos se deve colocá-lo:

• Em uma partição existente, da qual existem kopções
• Para iniciar uma nova partição, o que aumenta o número de opções kpara elementos futuros

De qualquer maneira, diminui o número restante nde elementos a serem colocados. Portanto, temos a fórmula recursiva f(n,k)=k*f(n-1,k)+f(n-1,k+1)e f(0,k)=1, com f(n,0)o n-ésimo número de Bell.

Python 2 , 91 bytes

s=lambda n,k:n*k and k*s(n-1,k)+s(n-1,k-1)or n==k
B=lambda n:sum(s(n,k)for k in range(n+1))

Experimente online!

B (n) calculado como uma soma dos números de Stirling do segundo tipo.

MATLAB, 128 103 bytes

function q(z)
r(1,1)=1;for x=2:z
r(x,1)=r(x-1,x-1);for y=2:x
r(x,y)=r(x,y-1)+r(x-1,y-1);end
end
r(z,z)

Bastante auto-explicativo. Omitir um ponto e vírgula no final de uma linha imprime o resultado.

25 bytes salvos graças a Luis Mendo.

R , 46 bytes

r=1;for(i in 1:scan())r=cumsum(c(r[i],r));r[1]

Experimente online!

MATL , 19 18 bytes

1i:"t@q@:qXn*sh]0)

Usa entrada com base em 0. Com base na relação de recorrência

Experimente online!

Ohm , 15 bytes

2°M^┼ⁿ^!/Σ;αê/≈

Experimente online!

Usa o forumla de Dobinski (funciona mesmo para B (0) yay ).

Explicação

2°M^┼ⁿ^!/Σ;αê/≈
2°        ;     # Push 100
  M             # Do 100 times...
   ^             # Push index of current iteration
    ┼ⁿ           # Take that to the power of the user input
      ^!         # Push index factorial
        /        # Divide
         Σ       # Sum stack together
           αê   # Push e (2.718...)
             /  # Divide
              ≈ # Round to nearest integer (Srsly why doesn't 05AB1E have this???)

Python (79 bytes)

B=lambda n,r=[1]:n and B(n-1,[r[-1]+sum(r[:i])for i in range(len(r)+1)])or r[0]

Demonstração online no Python 2, mas também funciona no Python 3.

Isso cria o triângulo de Aitken usando uma lambda recursiva para um loop de golfe.

Haskell , 35 bytes

(%0)
n%k|n<1=1|m<-n-1=k*m%k+m%(k+1)

Experimente online!

Fórmula explicada na minha resposta em Python .

J, 17 bytes

0{]_1&({+/\@,])1:

Usa o método de cálculo do triângulo.

Experimente online!

Explicação

0{]_1&({+/\@,])1:  Input: integer n
               1:  The constant 1
  ]                Identity function, get n
   _1&(       )    Call this verb with a fixed left argument of -1 n times
                   on itself starting with a right argument [1]
             ]       Get right argument
       {             Select at index -1 (the last item)
            ,        Join
        +/\@         Find the cumulative sums
0{                 Select at index 0 (the first item)

Python 3 , 78 bytes

from math import*
f=lambda n:ceil(sum(k**n/e/factorial(k)for k in range(2*n)))

Decidi tentar seguir uma rota diferente para o cálculo. Isso usa a fórmula de Dobinski, indexada a 0, não funciona para 0.

Experimente online!

Python 3 , 68 60 bytes

Construção recursiva simples do triângulo, mas é extremamente ineficiente para fins práticos. O cálculo do número da 15ª campainha faz com que o tempo limite do TIO seja excedido, mas funciona na minha máquina.

Isso usa a indexação 1 e retorna em Truevez de 1.

f=lambda r,c=0:r<1or c<1and f(r-1,r-1)or f(r-1,c-1)+f(r,c-1)

Experimente online!

Obrigado a @FelipeNardiBatista por salvar 8 bytes!

PHP , 72 bytes

função recursiva indexada 1

function f($r,$c=0){return$r?$c?f($r-1,$c-1)+f($r,$c-1):f($r-1,$r-2):1;}

Experimente online!

PHP , 86 bytes

Indexado a 0

for(;$r++<$argn;)for($c=~0;++$c<$r;)$l=$t[$r][$c]=$c?$l+$t[$r-1][$c-1]:($l?:1);echo$l;

Experimente online!

PHP , 89 bytes

função recursiva indexada em 0

function f($r,$s=NULL){$c=$s??$r-1;return$r>1?$c?f($r-1,$c-1)+f($r,$c-1):f($r-1,$r-2):1;}

Experimente online!

Alice , 22 bytes

/oi
\1@/t&wq]&w.q,+k2:

Experimente online!

Isso usa o método do triângulo. Para n = 0, calcula B (1), que é convenientemente igual a B (0).

Explicação

Este é um modelo padrão para programas que recebem entradas no modo ordinal, processam no modo cardinal e produzem o resultado no modo ordinal. UMA1 foi adicionado ao modelo para colocar esse valor na pilha abaixo da entrada.

O programa usa a pilha como uma fila circular em expansão para calcular cada linha do triângulo. Durante cada iteração após a primeira, um zero implícito abaixo da pilha se torna um zero explícito.

1     Append 1 to the implicit empty string on top of the stack
i     Get input n
t&w   Repeat outer loop that many times (push return address n-1 times)
q     Get tape position (initially zero)
]     Move right on tape
&w    On iteration k, push this return address k-1 times
      The following inner loop is run once for each entry in the next row
.     Duplicate top of stack (the last number calculated so far)
q,    Move the entry k spaces down to the top of the stack: this is the appropriate entry
      in the previous row, or (usually) an implicit zero if we're in the first column
+     Add these two numbers
k     Return to pushed address: this statement serves as the end of two loops simultaneously
2:    Divide by two: see below
o     Output as string
@     Terminate

A primeira iteração assume efetivamente uma profundidade inicial da pilha igual a zero, apesar do 1 necessário no topo da pilha. Como resultado, o 1 acaba sendo adicionado a si mesmo e o triângulo inteiro é multiplicado por 2. Dividir o resultado final por 2 fornece a resposta correta.

Pari / GP , 36 bytes

n->n!*Vec(exp(exp(x+O(x^n++))-1))[n]

Experimente online!