Definition:
The complexity of a surjection $\{1,\ldots,n+k\}\rightarrow \{1,\ldots,n\}$ is defined in the following way. First think of this map as the tuple $(f(1),\ldots,f(n+k))$. For two numbers $1\le i<j\le n$ first delete all entries in this tuple that are not $i$ or $j$ and afterwards eliminate all repititions of $i$ and $j$, i.e. whenever a number appears several times in a row, delete all but one of those repititions. Define $c_{i,j}$ as the length of the new tuple minus 1.
The complexity of $f$ is the maximum of $c_{i,j}$ over all choices of $i,j$.
Example: The complexity of $(1,2,1,3,1,2)$ is three, and it is obtained at the choices $i=1,j=2$:
Deleting all non 1,2's in $(1,2,1,3,1,2)$ yields $(1,2,1,1,2)$. There is ony one repitition and removing it means we have to delete one $1$, which gives $(1,2,1,2)$.
Question: For given numbers $n,k,c$ what is the number of surjections $\{1,\ldots,n+k\}\rightarrow \{1,\ldots,n\}$ of complexity $\le c$?
Motivation:(Feel free to ignore it) This notion of complexity was defined in Multivariable cochains and little n-cubes by McClure and Smith.
For example one can form a chain complex, where $C^{k}$ is the free $R$-module on the surjections as above. The differential sends a surjection/tuple to an alternating sum (lets ignore signs here) of the tuples obtained by trying to delete each entry (if the result is not surjective anymore, just ignore it).
Further note that this complex is really a free chain complex over $R[\Sigma_n]$, the symmetric group acts by postcomposing with bijections.
Thus the notion of complexity really gives a filtration of this chain complex by subcomplexes. Usually this could be used to compute the homology of this complex, however it is a free resolution of $R$ as an $R\Sigma$-module and thus its homology is not very interesting. The fact that everything dies, might be, if one has a good understanding of the differentials.
Anyway we can also tensor it with $R$ over $R[\Sigma_n]$ and we still have a filtered complex, which gives us a spectral sequence converging to $H_*(\Sigma_n,R)$, which might at least have some potential to be interesting.
This question seems to be the first step in figuring out what the $E_1$-page is.
