Counting number of occurences Let $1\leq k\leq n$. We find all finite sequences of positive integers with sum $n$. Suppose that the term $k$ occurs a total of $T(n, k)$ times in all these sequences. 

Find $T(n, k)$.

As an example to make things more clear: $T(3,1)=5$, $T(3,2)=2$ and $T(3,3)=1$
This on base of the sums $1+1+1=3$, $1+2=3$, $2+1=3$ and $3=3$.
In this I'm pretty sure we can do this by choosing $r$ $x$'s and letting them be equal to $k$ individually, in groups of $2$ and so on. We can then sum it over $r$. But I'm unable to write a solution and obtain an expression for $T(n,k)$. 
Thanks in advance!
 A: The number $T(n,k)$ can be calculated from the following recurrence relation:
$$T(n, k)=2^{n-k-1}+\sum_{i=1}^{n}T(n-i, k)\tag{1}$$
...with the following "boundary" conditions:
$$T(k, k)=1$$
$$T(n, k)=0 \quad\text{for} \quad n<k$$
Proof: 
To evaluate $T(n, k)$ we need all sequences with sum equal to $n$. That sum can either start with $k$ or not. In how many sequencies will $k$ appear as a starting one? Obviously, the number of such sequencies is equal to the number of sequencies with the sum equal to $n-r$. 
If you have $p$ members of the sequence, it's like splitting a group of $n-r$ elements with $p-1$ dividers. And you can put those dividers in $n-r-1$ different places. So the number of sequencies with $p$ terms is:
$$\binom{n-r-1}{p-1}$$. 
The total number of sequencies starting with $r$ is therefore:
$$\sum_{p=1}^{n-r}\binom{n-r-1}{p-1}=2^{n-r-1}\tag{2}$$
On top of that we should add a number of appearances of $k$ in all shorter sequences. Shorter sequencies are defined by picking the first number of the sequence, say $i$, between 1 and $n$ and counting the number of appearances of $k$ in a sequence with sum $n-i$. That number of appearances is given with the following sum:
$$\sum_{i=1}^{n}T(n-i, k)\tag{3}$$
Add (2) and (3) and you get (1).
A little play with Mathematica:
t[n_, k_] := Sum[t[n - i, k], {i, 1, n}] + 2^(n - k - 1)
t[n_, k_] := 1 /; n == k
t[n_, k_] := 0 /; n < k

$$
\begin{matrix}
k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
n=1 & 1 \\
n=2 & 2 & 1 \\
n=3 & 5 & 2 & 1 \\
n=4 & 12 & 5 & 2 & 1 \\
n=5 & 28 & 12 & 5 & 2 & 1 \\
n=6 & 64 & 28 & 12 & 5 & 2 & 1 \\
n=7 & 144 & 64 & 28 & 12 & 5 & 2 & 1 \\
n=8 & 320 & 144 & 64 & 28 & 12 & 5 & 2 & 1 \\
n=9 & 704 & 320 & 144 & 64 & 28 & 12 & 5 & 2 & 1 \\
n=10 & 1536 & 704 & 320 & 144 & 64 & 28 & 12 & 5 & 2 & 1 \\
\end{matrix}
$$
The sequence 1, 2, 5, 12, 28, 64, 144, 320, 704, 1536... is also described in OEIS A045623 as "Number of 1's in all compositions of n+1". 
OEIS also states that for $n>1$:
$$T(n,1)=(n+2)\times2^{n-3}$$
$$$$
A: With $q$ the length of the sequence and $k$ marked with $u$ we get the
generating function
$$G(z, u) = \sum_{q\ge 0} (z+z^2+\cdots+uz^k+\cdots)^q
\\ = \sum_{q\ge 0} z^q (1+z+\cdots+uz^{k-1}+\cdots)^q
\\ = \sum_{q\ge 0} z^q \left(\frac{1}{1-z} + (u-1)z^{k-1}\right)^q
\\ = \frac{1}{1-z(1/(1-z)+(u-1)z^{k-1})}
\\ = \frac{1-z}{1-z-z(1+(u-1)(1-z)z^{k-1})}.$$
The desired quantity is given by
$$[z^n] \left.
\frac{\partial}{\partial u} G(z, u)\right|_{u=1}
\\ = [z^n] \left. \frac{1-z}{(1-z-z(1+(u-1)(1-z)z^{k-1}))^2}
(z (1-z) z^{k-1})\right|_{u=1}
\\ = [z^n] \frac{1-z}{(1-2z)^2} (z (1-z) z^{k-1})
\\ = [z^n] \frac{1-2z+z^2}{(1-2z)^2} z^k
= [z^{n-k}] \frac{1-2z+z^2}{(1-2z)^2}.$$
We thus have for $k=n$ the value one, corresponding to the composition
$n=n$, for $k=n-1$ the value
$$[z^1] \frac{1-2z+z^2}{(1-2z)^2} = 4 - 2 = 2$$
corresponding to  the compositions  $1 +  (n-1) = (n-1)  + 1$  and for
$k\le n-2$
$$(n-k+1) \times 2^{n-k} - (n-k) \times 2^{n-k}
+ (n-k-1) \times 2^{n-k-2}
\\ = 2^{n-k} + (n-k-1) \times 2^{n-k-2}.$$
for a closed form of
$$\bbox[5px,border:2px solid #00A000]{
2^{n-k-2} (n-k+3).}$$
We clearly obtain zero when $k\gt n.$
