Problem: count the number of distinct ways to write number X as the sum of numbers {a, b, c...} with replacement. For instance, there are 3 ways to write 11:2+2+72+2+2+2+32+3+3+3What's the name of this problem?

Question

Problem: count the number of distinct ways to write number X as the sum of numbers {a, b, c...} with replacement. For instance, there are 3 ways to write 11:2+2+72+2+2+2+32+3+3+3What&#039;s the name of this problem?

ululatonh · Accepted Answer

With replacement, the answer is that the number       s    n   of ways has generating function      ∑    n        s    n        x    n    =  (  1  +      x    a    +      x          2      a        +  .  .  .  )  (  1  +      x    b    +      x          2      b        +  .  .  .  )  (  1  +      x    c    +      x          2      c        +  .  .  .  )  .  .  .or equivalently      1          (      1      −              x        a            )      (      1      −              x        b            )      (      1      −              x        c            )      .      .      .        .This is because choosing a term from each factor corresponds to choosing how many times you use each number you can use. For example, with the choices   {  1  ,  2  ,  5  ,  10  ,  25  }, this is the problem of counting the number of possible ways to make change for a certain amount of money.The generating function can be converted into an explicit formula when the set of possibilities is finite, but it is messy in the general case and not really worth caring about. It leads to a straightforward asymptotic which I could explain if you are interested.

zaiskaladu · Accepted Answer

If you are indeed looking at prime partitions, this is a very complicated problem. The usual counting generating series approach will unfortunately not yield too much without additional powerful analytic techniques.Let   p  (  n  ) denote the number of ways to write a positive integer   n as a sum of prime numbers. Because of the irregularity in the distribution of prime numbers, it has long been believed that it is not possible to obtain an asymptotic formula for   p  (  n  ). (Of course, this depends on what one means by an asymptotic formula.) In this paper, the author obtains a formula for   p  (  n  ) in the form  p  (  n  )  =  M  (  n  )  (  1  +  O  (      n          −      1              /            5        )  )    (  n  →  ∞  )  ,where   M  (  n  ) is a smooth function whose definition involves the generating function of   p  (  n  ). Moreover, using the same analytic method, the author obtains the following remarkable result:  p  (  n  +  1  )  −  p  (  n  )  ∼            π      p      (      n      )              3      n      log      ⁡      n

Problem: count the number of distinct ways to write number X as the sum of numbers {a, b, c...} with replacement. For instance, there are 3 ways to write 11: 2+2+7, 2+2+2+2+3, 2+3+3+3, What's the name of this problem?

Answered question

Answer & Explanation

New Questions in Precalculus