7
$\begingroup$

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)

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

4 Answers 4

7
$\begingroup$

This should be snappy:

SeriesCoefficient[t^#2 ((1 - t^#3)/(1 - t))^#2, {t, 0, #1}] &[n, k, m]
$\endgroup$
1
  • $\begingroup$ Serves me right for not checking. Somehow I thought it would be slower than numerical integration on large n. $\endgroup$
    – Michael E2
    Commented May 7, 2017 at 19:18
5
$\begingroup$
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  *)
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – bobbym
    Commented May 7, 2017 at 19:57
  • $\begingroup$ @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. $\endgroup$
    – Michael E2
    Commented May 7, 2017 at 20:03
3
$\begingroup$

A brute force approach:

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

f[6, 4, 3]

10

$\endgroup$
3
$\begingroup$

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}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.