performance tuning - Improving speed of code computing number of nonrepeating partitions

I need to answer the following for a number of parameters: How many ways can the integer $k$ be written as a sum of $n$ different integers ranging from $1$ to $m$?

My initial attempt was the following function:

NumberOfWays[k_, n_, m_] := 
  Count[Map[Length, 
    Map[DeleteDuplicates, 
     IntegerPartitions[k, {n}, Range[m]]]], 
   n];

This works, but becomes very slow as the parameters get big. I then thought I might do it using a generating function and attempted the following:

GenFuncy[m_] := Product[1 + y*x^j, {j, 1, m}];
NumberOfWays2[k_, n_, m_] := Coefficient[GenFuncy[m], x^k*y^n];

Again this works, but surprisingly (to me) it is even slower.

Is there any way I can speed these functions up, or maybe another faster way to do the calculation altogether?

Answer

This seems pretty quick, particularly on larger cases / larger k, e.g. 451, 29, 101 finishes in a few seconds on the loungebook.

N.B. - I have not tested this exhaustively, just thrown together from ideas...

If[Min[#3, #1 - Tr@Range@(#2 - 1)] < 0, 0, 
   SeriesCoefficient[QPochhammer[-x y, x, Min[#3, #1 - Tr@Range@(#2 - 1)]], 
                     {x , 0, #1}, {y, 0, #2}]] &[n, k, m]

UPDATE:

This seems to be very fast, particularly on larger cases. n.b.: posted with testing in progress, I'd like to prove correctness, but so far empirical testing matches prior methods, and appears faster than answers prior on large cases...

myDP[n_, k_, m_] := If[n < Binomial[k + 1, 2] || m < k, 0, 
                       SeriesCoefficient[QBinomial[m, k, q], {q, 0, n - Binomial[k + 1, 2]}]]

For a huge case of {n, k, m} = {5050, 100, 5050} this took a fraction of a second on the loungebook to return the result of 1 (for this case, there would be ~$2.74235\times 10^{68}$ partitions generated for any of the partition massaging methods like the OP's NumberOfWays, making use of these absurd for anything other than minimal cases.) The neat follow-up solution from KennyColnago took (unsure - aborted it after 5 minutes, monitoring progress indicated over an hour would be needed, figure 10X faster or so for both on a workstation...) for the same case - but I'd prefer to perhaps have his benchmark post extended with results on his hardware for a fair comparison.

Update 2: A further optimization, taking advantage of the symmetry of the gaussian polynomial:

myDPc[n_, k_, m_] := 
 Module[{mn = Binomial[k + 1, 2], mx = (k - k^2 + 2 k m)/2},
  If[mn <= n <= mx && m >= k,
     SeriesCoefficient[QBinomial[Min[n - Binomial[k, 2], m], k, q],
                       {q, 0, If[n > (mn + mx)/2, mx - n, n - mn]}],0]];

On an exhaustive search for all valid n for {k,m}={45,60} this was over 4X faster than myDP, and for large cases (e.g., {n,k,m}={18775, 50, 400} it was over 20,000X faster than myDP.

There's an additional optimization possible that might be advantageous when searching ranges of {n,k,m}: for any given {n,k,m}, by symmetry of the Q-Binomial, there's a dual of {n', k',m} where n' and k' are simple transformations of n and k that has precisely the same polynomial. Memoization on that can about double the performance for such searches.

Update 3 2015/08/20: Added an optimization (in edited myDPc above) for larger k, resulting in over 2 orders of magnitude performance boost to e.g. {n,k,m}={5100,100,5100} and about three orders of magnitude boost to {n,k,m}={12000,154,12000}.

I think I've run out of ideas...