Just to confirm, are you interested in how to compute it for specific values of n,k, or looking for a general formula? You can obviously use Fast Fourier Transform to extract the coefficients for fixed $n,k$.

I see, thank you. The property I need is that $\Pr[B_1=k_1, ..., B_n=k_n]\geq \Pr[R_1=k_1, ..., R_n=k_n] - O(1/n)$ (and I wrongly assumed that perhaps the the variational distance between them goes to zero as $n\to +\infty$ that justifies the inequality). Perhaps I can use something else here such as negative association of the permutation distribution to get the above inequality. Any ideas? (Or should I post this as a separate question?)

Thanks I accepted it (I previously upvoted it)

I see I misunderstood their proof. They were actually doing what you're doing (but it's not as clear as your writing). Thank you!

Thanks for the answer. I'm still a bit confused how independence implies $S_n^\ast$ equals $S_n$ in distribution? (I just learned about coupling recently, so this might be an obvious question).

The condition $a_i \in \Re$ will likely make this not in $P$. Restricting $a_i \in \Re_{+}$, there might be some hope with greedy-like algorithms.

@SeanEberhard Ahh, not so interesting after all :).

@TimothyChow yes you're right, edited.

@MaxAlekseyev Few typos, fixed now.