# Number of ways of writing N as sum of K positive natural numbers not more than W

My problem is similar to this

where i want to count number of ways where Order also matters. ( Restricted Composition instead of Restricted Partition).

Ex, n = 6, k =4, w = 3

Partitions: {2,2,1,1},{ 3,1,1,1}

Compositions: {2,2,1,1}, {2,1,2,1}, {2,1,1,2}, {1,2,1,2}, {1,1,2,2}, { 3,1,1,1}, {1,3,1,1}, {1,1,3,1}, {1,1,1,3}

I only need the number of such compositions.

Without restriction of W, Compositions can be counted as C(n-1,k-1) where C is Binomial coefficient by Stars and bars(combinatorics)

• You're looking for a numerical procedure to compute this in the software Mathematica? Commented May 7, 2017 at 17:36
• I think you omitted {1, 2, 2, 1}, yes? Commented May 7, 2017 at 17:49

This should be snappy:

SeriesCoefficient[t^#2 ((1 - t^#3)/(1 - t))^#2, {t, 0, #1}] &[n, k, m]

• Serves me right for not checking. Somehow I thought it would be slower than numerical integration on large n. Commented May 7, 2017 at 19:18
count[n_Integer, k_Integer, w_Integer] := Round@Im[
NIntegrate[
((x^(w + 1) - x)/(x - 1))^k/x^(n + 1), {x, 1/2, I, -1, -I, 1/2},
AccuracyGoal -> 5] / (2 Pi)];

count[6, 4, 3]
(*  10  *)

• Hi Michael E2; I do not know if this spectral analysis(?) approach can beat ciao's generating function but maybe for very large arguments. Anyway, I am getting an error of Im::argx: Im called with 2 arguments; 1 argument is expected. Commented May 7, 2017 at 19:57
• @bobbym Thanks. It was a mis-edit. I don't think it can't beat ciao's. I can speed it up a lot using x -> Exp[I t] and the trapezoidal rule. But for large values, you have to use large precision, and it slows down. It's actually a little faster than ciao's on small n, the reverse from what I expected. Commented May 7, 2017 at 20:03

A brute force approach:

f = Length[Join @@ Permutations /@ IntegerPartitions[#, {#2}, Range[#3]]] &;

f[6, 4, 3]


10

This has been covered by Uspensky in 1937 and he derived a series for this type problem. It is the fastest solution offered so far...(at least for the ranges I have looked at)

f[n_, k_, w_] := Sum[(-1)^i Binomial[k, i] Binomial[n - w*i - 1, k - 1], {i, 0, Floor[(n - k)/w]}]


For instance: for 100 integers that range from 1 to 1500 and must total to 25670:

AbsoluteTiming[f[25670, 100, 1500]]

(*{0.000331, \
2310773552971529511480321469112211316602961980009960692591725669202229\
3594981786745574228902895854419542372285795408010179071658412373062901\
6920021324630966393685711202000706652165362791220168581912905087746493\
6620786384841917330531789256398516365026521725791640201477713841376100\
0}*)


It might be a good idea to answer the OP's question...

AbsoluteTiming[f[6, 4, 3]]

{0.000075, 10}