Number of permutations whose sum makes n. How many ways are there to make n by summing non-null natural numbers ?
Let N(n) be that number of ways.


*

*For n=1, there is N(1)=1 way, namely: "1"  

*For n=2, there are N(2)=2 ways, namely: "2" and "1+1"  

*For n=3, N(3)=3 : "3", "2+1", "1+1+1" ("1+2" isn't different from "2+1", as the order doesn't matter)  

*For n=4, N(4)=5 : "4", "3+1", "2+2", "2+1+1", "1+1+1+1"  

*For n=5, N(5)=7 : "5", "4+1", "3+2", "3+1+1", "2+2+1", "2+1+1+1", "1+1+1+1+1"  

*For n=6, N(6)=11  

*For n=7, N(7)=15  

*For n=8, N(8)=22
The above values had been determined by writing all the possibilities.
The below values were computed in a spreadsheet, based on a method*.
N(9)=30
N(10)=42
N(11)=56
N(12)=77
N(13)=101
N(14)=135
N(15)=176  

*method:
Let's apply the method to n=5.
The possibilities can be put in 5 groups:


*

*the one starting by 5: 1 possibility no more, no less.
"5"  

*the one starting by 4, then, there's 5-4=1 remaining so 1 possibility, because N(1)=1.
"4+1"  

*those starting by 3, then, there's 5-3=2 remaining so 2 possibilities, because N(2)=1.
"3+2", "3+1+1"  

*those starting by 2, then, there's 5-2=3 remaining but only 2 possibilities, because the possibilities can't include numbers greater than 2, as we've already counted them (since $3 > {5\over 2}$).
"2+2+1", "2+1+1+1"  

*the one starting by 1: always 1.
"1+1+1+1+1"


Eventually, N(5)=1+N(1)+N(2)+2+1
But where does the "2" comes from ?
p and n being non-null natural numbers, let L be defined by:


*

*if $p<n$
$$ L(p,n)=\sum\limits_{i=1}^p L(i,n-i)$$

*if $p≥n$
$$ L(p,n)=N(n)$$


Notice: $L(1,n)=1$, as $L(1,n)=L(1,n-1)=L(1,n-2)=...=L(1,1)=N(1)=1$
Then, 2 $= L(2,5-2)$
So $$N(n) = 1+\sum\limits_{i=1}^{floor({n\over2})} N(i) + \sum\limits_{i=1}^{ceil({n\over2}-1)} L(i,n-i)$$
What can also be written: $$N(n) = 1+\sum\limits_{i=1}^{floor({n\over2})} N(i) + L(ceil({n\over2}-1),n)$$
That's what I could find until now. But the number of calculations increase exponentially with n.
 A: That's the partition function, and it isn't very easy to calculate.
This might be rather sad to read, so I thought the following results might cheer you up:

If we allow for ordered partitions: That is the number of integer solutions for $k=1$ to $k=n$ of $a_1+\dots+a_k=n$ then we have that is equal to $2^{n-1}$ this result can be obtained by drawing $n$ points in a horizontal line we show an example for $n=9$
$* * * * * * * * *$ Then we observe we could make a cut in between any pair of points: here is an example  of cutting between $4$ and $5$ and $7 $ and $8$:
$****|***|** $ this corresponds to the ordered partition $4,3,2$. Since there are $n-1$ spaces between the stars and we can chose whether we want to cut or not at each space there are $2^{n-1}$ ordered partitions

It is also simple to count the ordered partitions of $n$ into exactly $k$ elements, we can do this by using the stars and bars method. Suppose we want partition $11$ into $4$ ordered parts. Then first of all we know each part will be at least $1$, so this is the same as partitioning $7$ into $4$ non-negative parts. We can do this using the same diagrams as before. To partition $7$ into $4$ parts we will neded $3$ bars and $7$ stars so the diagram will look like this: $*** |**|*|*$ and there are $10$ places and $3$ bars to place. In general the ordered partitions of $n$ into $k$ elements is $\binom{n-1}{k-1}$.

Finally we can also count the unordered partitions of numbers smaller $kn$ into $n$ pieces or less of size $k$ or less. For any given non-ordered partition. Place the largest parts to the right and order them from biggest to smallest. For example: if $k=6$ and $n=5$ an example will be the following:

notice each of these give you a path from $(0,0)$ to $(n,k)$ therefore the number of non-order partitions for numbers smaller than or equal to $nk$ and with $n$ parts or less is $\binom{n+k}{k}$
