Suppose i have an $n-$elements array. I want to count number of permutations for which element $a_i$ allowed to appear in range $i-k, \dots, i+k,$ so $2k+1$ positions available after permutation has happenned.

I got a rough bound $n$ elements at most $2k+1$ positions for every one. Thus, the bound is $n^{2k+1}.$ And this is an upper bound, but i need lower one as well. The best is exact formula.

EDIT: A lower bound is $(k!)^{n/k}.$

  • 1
    $\begingroup$ You should have a look at oeis.org/A002524 which deals especially with the case $k=1$ but also discusses and has links to material on the general case. Maybe you could follow up on what you find there, and then come back here to post an answer summarizing what you've learned. $\endgroup$ – Gerry Myerson Nov 10 '14 at 11:40
  • 1
    $\begingroup$ Had a chance to check that link? $\endgroup$ – Gerry Myerson Nov 11 '14 at 11:49
  • 1
    $\begingroup$ @GerryMyerson, sorry, for my particular problem exact answer wasn't necessary, and doc about n-case not so simple for me to read it fast. $\endgroup$ – Yola Nov 11 '14 at 19:33
  • 2
    $\begingroup$ OK. When you get a chance, then, I hope you'll write something up and post it as an answer. $\endgroup$ – Gerry Myerson Nov 12 '14 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.