fundo

O polinomial Sidi de grau n - ou o (n + 1) ^th Sidi polinomial - é definido como se segue.

Os polinômios Sidi têm várias propriedades interessantes, mas seus coeficientes também. A última forma a sequência OEIS A075513 .

Tarefa

Escreva um programa completo ou uma função que, dado um número inteiro não negativo n , imprima ou retorne a soma absoluta dos coeficientes do polinômio Sidi de grau n , ou seja,

Essas somas formam a sequência OEIS A074932 .

Se preferir indexação baseada em 1, você pode tomar um inteiro positivo n vez e calcular a soma absoluta dos coeficientes do n ^º Sidi polinomial.

Como esse é o código-golfe , você deve tornar seu código o mais curto possível. Todas as regras padrão se aplicam.

Casos de teste (com base em 0)

 n           Σ

 0           1
 1           3
 2          18
 3         170
 4        2200
 5       36232
 6      725200
 7    17095248
 8   463936896
 9 14246942336

Casos de teste (com base em 1)

 n           Σ

 1           1
 2           3
 3          18
 4         170
 5        2200
 6       36232
 7      725200
 8    17095248
 9   463936896
10 14246942336

05AB1E , 10 bytes

Ý©¹c®>¹m*O

Usa a codificação CP-1252 . Experimente online!

Python 2 , 43 bytes

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

Experimente online!

Uma abordagem diferente

Desde que publiquei esse desafio, tentei encontrar uma solução recursiva para esse problema. Embora eu tenha falhado em usar nada além de caneta e papel, consegui transformar a fórmula do golfe em um problema prático - pelo menos para certas definições de prático - o que tornava mais fácil a análise.

Imagine um game show com candidatos k + m que funciona da seguinte maneira.

Na rodada 1, todos os candidatos precisam realizar uma determinada tarefa o mais rápido possível. Os k candidatos que realizam a tarefa ganham mais rapidamente 1 k $ (um quilodólar) cada e avançam para a terceira rodada.

Na segunda rodada, os m candidatos restantes terão uma segunda chance de se juntar aos outros k . Cada candidato recebe uma pergunta. Se responderem à pergunta corretamente, ganham 1 k $ e avançam para a rodada 3. No entanto, se não responderem à pergunta, serão eliminados do jogo. Isso significa que a terceira rodada terá entre k e k + m candidatos, dependendo de quantos podem responder suas perguntas.

A Rodada 3 consiste em m mais concursos semelhantes à Rodada 1. Em cada competição, os participantes precisam realizar uma determinada tarefa. Ao contrário da rodada 1, apenas um candidato recebe um prêmio, mas todos os candidatos participam do próximo concurso. Cada concurso paga duas vezes mais que o concurso anterior; o primeiro paga 2 k $ e o último 2 ^m k $ .

Observe que, como todos os prêmios têm o poder de dois, saber quanto dinheiro um candidato ganhou significa que sabemos se eles avançaram para a rodada 3 e qual das competições da rodada 3 ganhou.

Suponha que você esteja assistindo ao game show e a rodada 1 já tenha terminado, para saber quais k candidatos já atingiram a rodada 3 e quais m ainda estão presos na rodada 2. De quantas maneiras o dinheiro restante do prêmio pode ser distribuído?

Uma vez que sabemos que do segundo redondos m candidatos avançaram para round 3, é fácil de calcular os resultados possíveis para este cenário específico. Se j candidatos avançarem, haverá um total de k + j candidatos na rodada 3 e, portanto, k + j possíveis resultados para cada concurso. Com m competições individuais na rodada 3, isso gera (k + j) ^m resultados para todas as m competições.

Agora, j pode assumir qualquer valor entre 0 e m , dependendo de quais candidatos respondem corretamente na rodada 2. Para cada valor fixo de j , existem ^m C _j combinações diferentes de j candidatos que poderiam ter avançado para a rodada 3. Se chamarmos o número total de resultados possíveis para k candidatos da terceira rodada e m candidatos da segunda rodada g (m, k) , obtemos a seguinte fórmula.

Se fixarmos k = 1 , obtemos o seguinte caso especial, que constitui nossa nova abordagem para resolver o problema original.

Uma fórmula recursiva

Agora, suponha que você tenha adormecido durante os comerciais após a primeira rodada e acordei bem a tempo de ver quem ganhou o último concurso da terceira rodada e, portanto, o grande prêmio de 2 ^m k $ . Você não tem nenhuma outra informação, nem mesmo quanto prêmio em dinheiro esse candidato ganhou no total. De quantas maneiras o prêmio em dinheiro restante pode ser distribuído?

Se o vencedor foi um dos m candidatos da segunda rodada, já agora que eles devem ter avançado para a terceira rodada . Portanto, efetivamente temos k + 1 candidatos na rodada 3, mas apenas m - 1 candidatos na rodada 2. Como conhecemos o vencedor do último concurso, há apenas m - 1 concursos com resultados incertos, então há g (m - 1, k + 1) resultados possíveis.

Se o vencedor for um dos k candidatos que pularam a segunda rodada, o cálculo se tornará um pouco mais complicado. Como antes, restam apenas rondas m - 1 , mas agora ainda temos k candidatos na ronda 3 e m na ronda 2. Dado que o número de candidatos da ronda 2 e o número de concursos da ronda 3 são diferentes, os resultados possíveis não podem ser calculado com uma simples chamada de g . No entanto, após o candidato do primeiro turno 2 responder - correta ou incorretamente - o número de candidatos do segundo turno coincide mais uma vez com os concursos de m - 1 do turno 3. Se o candidato avançar, haverá k + 1 round 3 candidatos e, portanto, g (m - 1, k + 1)Possíveis resultados; se o candidato for eliminado, o número de candidatos da terceira rodada permanece em ke existem g (m - 1, k) possíveis resultados. Como o candidato avança ou não, existem g (m - 1, k + 1) + g (m - 1, k) possíveis resultados combinando esses dois casos.

Agora, se adicionarmos os resultados em potencial para todos os candidatos k + m que poderiam ter ganho o grande prêmio, o resultado deve corresponder a g (m, k) . Existem m concorrentes da segunda rodada que levam a g (m - 1, k + 1) a resultados potenciais cada, e k concorrentes da terceira rodada que levam a g (m - 1, k + 1) + g (m - 1, k) uns. Resumindo, obtemos a seguinte identidade.

Juntamente com o caso base

essas duas fórmulas caracterizam a função g completamente.

Uma implementação de golfe

Enquanto

g=lambda m,k=1:0**m or(m+k)*g(m-1,k+1)+k*g(m-1,k)

(49 bytes, 0**mgera 1 uma vez que m cai para 0 ) ou mesmo

g=lambda m,k=1:m<1 or(m+k)*g(m-1,k+1)+k*g(m-1,k)

(48 bytes, retorna True em vez de 1 ) seriam soluções válidas, ainda há bytes a serem salvos.

Se definirmos uma função f que usa o número n dos candidatos da primeira rodada em vez do número m dos candidatos da segunda rodada como primeiro argumento, ou seja,

nós obtemos a fórmula recursiva

com estojo

Finalmente, temos

então a implementação do Python

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

( k/ngera 1 uma vez n = k ) resolve a tarefa em questão com a indexação baseada em 1.

Mathematica, 33 32 bytes

Salvo um byte graças a JungHwan Min .

Binomial[#,r=0~Range~#].(r+1)^#&

Pitão - 13 12 bytes

Apenas implementa a fórmula sem a (-1)^kparte.

sm*.cQd^hdQh

Conjunto de Teste .

MATL , 12 bytes

t:XnG:QG^*sQ

A entrada é baseada em 0.

Experimente online!

Explicação

Considere a entrada 5como um exemplo.

t      % Take n implicitly. Duplicate
       % STACK: 5, 5
:      % Range [1 2 ...n]
       % STACK: 5, [1 2 3 4 5]
Xn     % N-choose-k, vectorized
       % STACK: [5 10 10 5 1]
G:Q    % Push [2 3 ... n+1]
       % STACK: [5 10 10 5 1], [2 3 4 5 6]
G^     % Raise to n
       % STACK: [5 10 10 5 1], [32 243 1024 3125 7776]
*      % Multiply, element-wise
       % STACK: [160 2430 10240 15625 7776]
s      % Sum of array
       % STACK: 36231
Q      % Add 1. Display implicitly
       % STACK: 36232

R, 36 bytes

sum(choose(n<-scan(),0:n)*(0:n+1)^n)

A vetorização de R é útil aqui ao aplicar a fórmula.

J , 19 bytes

+/@((!{:)*>:^{:)@i.

Usa indexação baseada em um.

Experimente online!

Explicação

+/@((!{:)*>:^{:)@i.  Input: integer n
                 i.  Range [0, 1, ..., n-1]
   (           )@    Operate on that range
             {:        Get the last value, n-1
          >:           Increment, range becomes [1, 2, ..., n]
            ^          Exponentiate. [1^(n-1), 2^(n-1), ..., n^(n-1)]
    ( {:)              Get the last value, n-1
     !                 Binomial coefficient. [C(n-1, 0), C(n-1, 1), ..., C(n-1, n-1)]
         *             Multiply
+/@                  Reduce by addition

Máximos, 39 bytes

f(n):=sum(binomial(n,k)*(k+1)^n,k,0,n);

PARI / GP, 35 bytes

n->sum(k=0,n,binomial(n,k)*(k+1)^n)

Axioma, 39 bytes

f(n)==sum(binomial(n,i)*(i+1)^n,i=0..n)

código de teste e resultados

(35) -> [[i,f(i)] for i in 0..9]
   (35)
   [[0,1], [1,3], [2,18], [3,170], [4,2200], [5,36232], [6,725200],
    [7,17095248], [8,463936896], [9,14246942336]]

Geléia , 9 bytes

cR×R‘*ƊS‘

Experimente online!

Como funciona

cR×R‘*ƊS‘ - Main link. Argument: n (integer)        e.g.   5
 R        - Range from 1 to n                              [1, 2, 3, 4, 5]
c         - Binomial coefficient                           [5, 10, 10, 5, 1]
      Ɗ   - Last three links as a monad:
   R      -   Link 1: Range from 1 to n                    [1, 2, 3, 4, 5]
    ‘     -   Link 2: Increment                            [2, 3, 4, 5, 6]
     *    -   Link 3: To the power of n                    [32, 243, 1024, 3125, 7776]
  ×       - Multiply, pairwise                             [160, 2430, 10240, 15625, 7776]
       S  - Sum                                            36231
        ‘ - Increment                                      36232