2
$\begingroup$

Given a set $S$ containing all possible permutations of a vector $v = (1, 2, 3, ..., n-1, n)$, find the size of the set $P$, where $P$ is defined as the set of possible component-wise sums obtained by adding $k$ elements of $S$ together. Each element in $P$ is a sum of $k$ vectors from $S$, i.e. $P=\sum_{i=1}^kS$. I'm wondering if there is a nice looking formula for $|P|$ as a function of $n$ and $k$.

Edit: the main reason why I'm considering this is the following. Imagine $n$ players play a game. Each round, they get ranked (without ties). The best player gets $n$ points, the second best $n-1$, etc... and the last one only gets $1$. These points gets added to the scoreboard, which starts at $0$ for each player. I want to know how many possible scoreboards there are after $k$ rounds.

Improve this question
$\endgroup$
8
  • $\begingroup$ I was pretty tired, wanted to say component-wise $\endgroup$
    – Talesseed
    Jun 16 at 8:58
  • 2
    $\begingroup$ I can't find a table in OEIS, but for $k=2$ there's A175176 with the suggestion that $n=11, k=2$ is unknown. $\endgroup$
    – Peter Taylor
    Jun 16 at 10:32
  • 3
    $\begingroup$ As far as I know, counting/describing vectors representable as the sum of two permutations is an open problem, which I have heard Alex Postnikov discuss. You can see him discuss it starting around the 57 minute of youtube.com/watch?v=thn16ncB4Js. $\endgroup$
    – Sam Hopkins
    Jun 16 at 19:15
  • $\begingroup$ Thanks a lot for the references! $\endgroup$
    – Talesseed
    Jun 17 at 15:00
  • 1
    $\begingroup$ @Talesseed: It's a brute force although a bit optimized. Eg. it starts with computing sequences corresponding to oeis.org/A019589 and then sums up their rearrangements. I don't think it's feasible going above $n=14$ this way. $\endgroup$
    – Max Alekseyev
    Jun 19 at 17:17

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.