[Question]
  [
### Background
The Sidi polynomial of degree \$n\$ – or the \$(n + 1)\$th Sidi polynomial – is defined as follows.
$$S\_n(x) = \sum^n\_{k=0}s\_{n;k}x^n \text{ where } s\_{n;k} = (-1)^k\binom n k (k+1)^n$$
The Sidi polynomials have several interesting properties, but so do their coefficients. The latter form OEIS sequence [A075513](https://oeis.org/A075513).
### Task
Write a full program or a function that, given a non-negative integer \$n\$, prints or returns the absolute sum of the coefficients of the Sidi polynomial of degree \$n\$, that is
$$\Sigma\_n = \sum^n\_{k=0}|s\_{n;k}|$$
These sums form OEIS sequence [A074932](https://oeis.org/A074932).
If you prefer 1-based indexing, you can take a positive integer \$n\$ instead and compute the absolute sum of the coefficients of the \$n\$th Sidi polynomial.
Because this is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), you must make your code as short as possible. All standard rules apply.
### Test cases (0-based)
```
 n           Σ
 0           1
 1           3
 2          18
 3         170
 4        2200
 5       36232
 6      725200
 7    17095248
 8   463936896
 9 14246942336
```
### Test cases (1-based)
```
 n           Σ
 1           1
 2           3
 3          18
 4         170
 5        2200
 6       36232
 7      725200
 8    17095248
 9   463936896
10 14246942336
```
  
[Answer]
# [Python 2](https://docs.python.org/2/), 43 bytes
```
f=lambda n,k=1:k/n or n*f(n,k+1)+k*f(n-1,k)
```
[Try it online!](https://tio.run/nexus/python2#FYvBCoAgEAXP9RXvIrVpxHYM@hjDjNjaQvp/09sww@S4Xv7egoc6WXmRSfEk6BD7IiyTlYojO6Eca8GpSF6PvWcHZlra5k2nfujMHGCYQweDcqN8RPkH "Python 2 – TIO Nexus")
### A different approach
Ever since I posted this challenge, I tried to come up with a recursive solution to this problem. While I failed using nothing more than pen and paper, I managed to turn the formula to golf into a practical problem – at least for certain definitions of practical – which made it easier to analyze.
Imagine a game show with \$k + m\$ candidates that works as follows.
In round 1, all candidates have to accomplish a certain task as fast as they can. The \$k\$ candidates that accomplish the task the fastest win \$$1\$ each and advance to round 3.
In round 2, the \$m\$ remaining candidates get a second chance to join the other \$k\$. Each candidate is asked a question. If they answer the question correctly, they win \$$1\$ and advance to round 3. However, if they fail to answer the question, they are eliminated from the game. This means round 3 will have between \$k\$ and \$k + m\$ candidates, depending on how many can answer their questions.
Round 3 consists of \$m\$ more contests that are similar to round 1. In each contest, the participants have to accomplish a certain task. Unlike round 1, only one candidate receives a prize, but all candidates get to participate in the next contest. Each contests pay twice as much as the contest before it; the first one pays \$$2\$ and the last one \$$2^m\$.
Note that since all prizes are powers of two, knowing how much prize money a candidate earned means we know if they advanced to round 3 and which of the contests of round 3 they won.
Assume you're watching the game show and round 1 is already over, so you know which \$k\$ candidates have already reached round 3 and which \$m\$ candidates are still stuck in round 2. In how many ways can the remaining prize money be distributed?
Once we know which of the second round's \$m\$ candidates have advanced to round 3, it's easy to calculate the possible outcomes for this specific scenario. If \$j\$ candidates advance, there are \$k + j\$ total candidates in round 3, and thus \$k + j\$ possible outcomes for each contest. With \$m\$ individual contests in round 3, this makes \$(k + j)^m\$ outcomes for all \$m\$ contests.
Now, \$j\$ can take any value between \$0\$ and \$m\$, depending on which candidates answer correctly in round 2. For each fix value of \$j\$, there are \$\binom{m}{j}\$ different combinations of \$j\$ candidates that could have advanced to round 3. If we call the total number of possible outcomes for \$k\$ round 3 candidates and \$m\$ round 2 candidates \$g(m, k)\$, we get the following formula.
$$g(m,k) = \sum\_{j=0}^m \binom mj (j+k)^m$$
If we fix \$k = 1\$, we get the following special case, which constitutes our new approach to solve the original problem.
$$g(m,1) = \sum\_{j=0}^m \binom mj (j+1)^m = \sum\_{j=0}^m |s\_{m;j}| = \Sigma\_m $$
### A recursive formula
Now, assume that you fell asleep during the commercials after round 1, and woke up just in time to see who won the last contest of round 3 and thus the grand prize of \$2^m k$\$. You don't have any other information, not even how much prize money that candidate won in total. In how many ways can the remaining prize money be distributed?
If the winner was one of the \$m\$ candidates of round 2, we already now that they must have advanced to round \$3\$. Thus, we effectively have \$k + 1\$ candidates in round 3, but only \$m - 1\$ candidates in round 2. Since we know the winner of the last contest, there are only \$m - 1\$ contests with uncertain outcomes, so there are \$g(m - 1, k + 1)\$ possible outcomes.
If the winner is one of the \$k\$ candidates that skipped round 2, the calculation becomes slightly trickier. As before, there are only \$m - 1\$ rounds left, but now we still have \$k\$ candidates in round 3 and \$m\$ candidates in round 2. Since the number of round 2 candidates and the number of round 3 contests are different, the possible outcomes cannot be calculated with a simple invocation of \$g\$. However, after the first round 2 candidate has answered – rightly or wrongly – the number of round 2 candidates once again matches the \$m - 1\$ round 3 contests. If the candidate advances, there are \$k + 1\$ round 3 candidates and thus \$g(m - 1, k + 1)\$ possible outcomes; if the candidate is eliminated, the number of round 3 candidates remains at \$k\$ and there are \$g(m - 1, k)\$ possible outcomes. Since the candidate either advances or not, there are \$g(m - 1, k + 1) + g(m - 1, k)\$ possible outcomes combining these two cases.
Now, if we add the potential outcomes for all \$k + m\$ candidates that could have won the grand prize, the result must match \$g(m, k)\$. There are \$m\$ round 2 contestants that lead to \$g(m - 1, k + 1)\$ potential outcomes each, and \$k\$ round 3 contestants that lead to \$g(m - 1, k + 1) + g(m - 1, k)\$ ones. Summing up, we get the following identity.
\begin{align\*}
g(m,k) &= m \cdot g(m-1,k+1) + k \cdot (g(m-1,k+1)+g(m-1,k)) \\
&= (m+k) \cdot g(m-1,k+1) + k \cdot g(m-1,k)
\end{align\*}
Together with the base case
$$g(0,k)=1$$
these two formulae characterize the function \$g\$ completely.
### A golfy implementation
While
```
g=lambda m,k=1:0**m or(m+k)*g(m-1,k+1)+k*g(m-1,k)
```
(49 bytes, `0**m` yields **1** once **m** drops to **0**) or even
```
g=lambda m,k=1:m<1 or(m+k)*g(m-1,k+1)+k*g(m-1,k)
```
(48 bytes, returns *True* instead of **1**) would be valid solutions, there are still bytes to be saved.
If we define a function **f** that takes the number **n** of round 1 candidates instead of the number **m** of round 2 candidates as first argument, i.e.,
$$f(n,k)=g(n-k,k)$$
we get the recursive formula
\begin{align\*}
f(n,k) &= g(n-k,k)\\
&= ((n-k)+k) \cdot g((n-k)-1,k+1)+k\cdot g((n-k)-1,k) \\
&= n \cdot f((n-k-1)+(k+1),k+1)+k \cdot f((n-k-1)+k,k) \\
&= n \cdot f(n,k+1) + k \cdot f(n-1,k)
\end{align\*}
with base case
$$f(k,k)=g(k-k,k)=g(0,k)=1$$
Finally, we have
$$f(n,1)=g(n-1,1)=\Sigma\_{n-1}$$
so the Python implementation
```
f=lambda n,k=1:k/n or n*f(n,k+1)+k*f(n-1,k)
```
(`k/n` yields **1** once \$n = k\$) solves the task at hand with 1-based indexing.
[Answer]
# Mathematica, ~~33~~ 32 bytes
Saved one byte thanks to [JungHwan Min](https://codegolf.stackexchange.com/users/60043/junghwan-min).
```
Binomial[#,r=0~Range~#].(r+1)^#&
```
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 10 bytes
```
Ý©¹c®>¹m*O
```
Uses the **CP-1252** encoding. [Try it online!](https://tio.run/nexus/05ab1e#@3947qGVh3YmH1pnd2hnrpb///@WAA "05AB1E – TIO Nexus")
[Answer]
# Pyth - ~~13~~ 12 bytes
Just implements the formula without the `(-1)^k` part.
```
sm*.cQd^hdQh
```
[Test Suite](http://pyth.herokuapp.com/?code=sm%2a.cQd%5EhdQh&test_suite=1&test_suite_input=0%0A1%0A2%0A3%0A9&debug=0).
[Answer]
# [APL (Dyalog Extended)](https://github.com/abrudz/dyalog-apl-extended), ~~27~~ 16 bytes
```
1+(⍳!⊢)+.×⊢*⍨1+⍳
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT9dNrShJzUtJTflfbaitYfiobbLGo65Fio96VxjoPOrdrPmod6umtt7h6UBaCyhoqA0UBLJruao18CvUQVIKNFkDyFEEasBjIDZVIDvgykCitf@BymCqwOYgKfif9qhtwqPevkddzY961zzq3XJovfGjtomP@qYGBzkDyRAPz@D/aQqGXGkKRkBsDMQmQGwKAA "APL (Dyalog Extended) – Try It Online")
Formula taken from caird coinheringaahing.
-11 bytes from Bubbler (conversion to tacit form.)
## Explanation
```
1+(⍳!⊢)+.×⊢*⍨1+⍳ 
             1+⍳ 1 + range 1 - n
          ⊢*⍨    to the power n
  (⍳!⊢)          binomial coefficients of n
       +.×       inner(dot) product of the two
1+               + 1
```
[Answer]
## R, 36 bytes
```
sum(choose(n<-scan(),0:n)*(0:n+1)^n)
```
R's vectorization comes in handy here when applying the formula.
[Answer]
# [MATL](https://github.com/lmendo/MATL), 12 bytes
```
t:XnG:QG^*sQ
```
Input is 0-based.
[Try it online!](https://tio.run/nexus/matl#@19iFZHnbhXoHqdVHPj/vyUA "MATL – TIO Nexus")
### Explanation
Consider input `5` as an example.
```
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
```
[Answer]
# [J](http://jsoftware.com/), 19 bytes
```
+/@((!{:)*>:^{:)@i.
```
Uses one-based indexing.
[Try it online!](https://tio.run/nexus/j#@5@mYGuloK3voKGhWG2lqWVnFQekHDL1uLhSkzPyFTR09NKUDDQV7KwUMvUUDA0q/v8HAA)
## Explanation
```
+/@((!{:)*>:^{:)@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
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~8~~ 7 bytes
```
cŻḋŻ‘*Ɗ
```
[Try it online!](https://tio.run/##y0rNyan8/z/56O6HO7qP7n7UMEPrWNf///9NAQ "Jelly – Try It Online")
This is a trivial modification of [user80092's answer](https://codegolf.stackexchange.com/a/163186/66833), but given that the user has deleted their account, this seems like an acceptable solution
## How it works
```
cŻḋŻ‘*Ɗ - Main link. Argument: n (integer)        e.g.   5
 Ż      - Range from 0 to n                              [0, 1, 2, 3, 4, 5]
c       - Binomial coefficient                           [1, 5, 10, 10, 5, 1]
      Ɗ - Last three links as a monad:
   Ż    -   Generate the range from 0 to n...            [0, 1, 2, 3, 4, 5]
    ‘   -   Increment each                               [1, 2, 3, 4, 5, 6]
     *  -   Raise to the power of n                      [1, 32, 243, 1024, 3125, 7776]
  ḋ     - Dot-product                                    36232
```
[Answer]
# Maxima, 39 bytes
```
f(n):=sum(binomial(n,k)*(k+1)^n,k,0,n);
```
[Answer]
# PARI/GP, 35 bytes
```
n->sum(k=0,n,binomial(n,k)*(k+1)^n)
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 9 bytes
```
cR×R‘*ƊS‘
```
[Try it online!](https://tio.run/##y0rNyan8/z856PD0oEcNM7SOdQUDqf///5sCAA "Jelly – Try It Online")
## How it works
```
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
```
[Answer]
# Axiom, 39 bytes
```
f(n)==sum(binomial(n,i)*(i+1)^n,i=0..n)
```
test code and results
```
(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]]
```
]