0

I have the following recursion relation:

$d(m,k)=d(m-1,k) + d(m-1,k-1) + ... + d(m-1,k-\min(k+1,m)+1); \hspace{2cm} m=1,2,3,...; k=0,1,2,...,\binom{m}{2}.$

with the following conditions

$d(m,0) = 1, d(1,k) = 0 \text{ for } k>0.$

For $k \leq m-1,$ the recursion becomes

$d(m,k)=d(m,k-1)+d(m-1,k).$

How to get a closed form of $d(m,k)$ for any $k$?

sankha
  • 11
  • 2
  • How did this sequence arise & what have you tried with it so far? – πr8 Jan 26 '16 at 11:08
  • $d(m,k)$ is the number of permutations of $1,2,...,m$ with exactly $k$ discordant pairs. I've found upto $d(m,2)$, but don't have clue to find it for any $k.$ – sankha Jan 26 '16 at 11:20
  • Are you sure about the recursion for $k\le m-1$? On a sidenote, this offers some insight to the area you're looking at, if not an explicit formula. – πr8 Jan 26 '16 at 11:35
  • Thanks @πr8 . I'll look closely at the paper. I'm sure about the recursion for $k \leq m-1.$ – sankha Jan 26 '16 at 11:47

0 Answers0