The problem states:
Find the number $f(n)$ of binary sequences $w = a_1a_2...a_k$ (where k is arbitrary) such that $a_1 = 1$, $a_k = 0$, and $inv(w) = n$ (where $inv(w)$ is the number of $i<j$ such that $w_i>w_j$).
For instance, $f(4) = 5$, corresponding to the sequences $10000$, $11110$, $10110$, $10010$, $1100$. How many of these sequences have exactly $j$ 1's.
So I actually have a solution to this problem. I use the fact that any such sequence, $w$, has $k-1 < inv(w)$. I then found upper bounds for $k$ using the fact that $inv(w) \leq 2k-4$. I then generate $ \sum q^{inv(w)}$ for all such $w$.
In general, the set of binary sequences of size $n$ has $A(n) = \sum q^{inv(w)} = \sum_{m=0}^{n} {n \choose m}_q$.
Based on the value of $k$ in our sequence $w$ we want a different coefficient of $q$ in the generating function. Simplifying gives $f(n) = \sum_{k=1}^{n} [q^{n-k}](A(k-1)$ and $f_j(n) = \sum_{k=1}^{n} [q^{n-k}]{k-1 \choose j}_q$. (where $[x^n](f(x))$ is the coefficient of $x^n$ in $f(x)$.
My question now is regarding how I can simplify my expressions for $f(n)$ and $f_j(n)$. Also, if there are any more elegant solutions, I would be glad to see them.
Each sequence $w$ containing $j$ ones can be converted into a sequence of $j$ positive integers $a_1\geq a_2,\geq\dots, \geq a_l$ such that $a_1+a_2+\dots+a_l=n$ (here $a_1$ is the number of inversions formed with the $i$'th $1$).
It is not hard to prove this function is a bijection between the binary sequences $w$ with $w_1=0$ and last term $0$ and the sums $w_1+w_2+\dots+w_l=0$ with $w_i\geq W_{i+1}$ and $w_l\geq 1$. These last are counted by the partition function.