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?

Zack Chase 2022-09-25 Answered
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?
You can still ask an expert for help

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (2)

ululatonh
Answered 2022-09-26 Author has 4 answers
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.
Did you like this example?
Subscribe for all access
zaiskaladu
Answered 2022-09-27 Author has 2 answers
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
Did you like this example?
Subscribe for all access

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2021-09-08

A restaurant offers a $12 dinner special with seven appetizer options, 12 choices for an entree, and 6 choices for a dessert. How many different meals are available when you select an appetizer, an entree,and a dessert?

asked 2021-09-09
In a fuel economy study, each of 3 race cars is tested using 5 different brands of gasoline at 7 test sites located in different regions of the country. If 2 drivers are used in the study, and test runs are made once under each distinct set of conditions, how many test runs are needed?
asked 2022-06-22
These are two problems I have to solve and I just need you to check if my solution is correct.
First: I have 10 red balls and 3 blue balls. What is the probability of picking 1 red ball and 3 blue balls?
My solution: 10/13 * 3/12 * 2/11 * 1/10 = 1/286
Or should it be 10/13 * 3/12 * 3/11 *3/10 = 9/572?
Second: They have 16 different postcards in the shop. How many possibilities do we have if we want to choose 6 different ones?
My solution: 16 * 15 * 14 * 13 * 12 * 11 = 5765760
asked 2022-07-01
In a box there are 16 ice-creams: 6 lemon flavor,4 mint flavor and 6 strawberry flavor.When we extract two ice-creams,what's the probability of getting two different flavors,given that at least one is strawberry flavor.
That's my solution :
P ( A ) = "Different flavors" = ( 16 2 ) 16 !
P ( B c ) = "At least one is strawberry flavor" = 1 ( 10 2 ) 16 !
We want P ( A | B c ) using conditional probability, where I go wrong?
asked 2022-09-17
The non-iterative method for calculating graycode depends on Log2N bytes, to store position information for the next bit in the iteration sequence.
Specifically, the goal is to know the next bit to change without having to look at the current code.However, for the 3 bit gray code, there's a iteration sequence 0,1,2,1,0,1,2,1 that can be represented with a much simpler function - maintain "0,1,2,1" in a register and rotate each time (as an example of a more general permutation).To reduce the necessary state, this could be kept in two positions, starting 0,1 and a constant function of "xor, permute" applied: 0,3 => 1,0 => 2,1 => 3,2 => 0,3 (the bit to change being the first, and 3 handled as 1 since only 0,1,2 are valid)
Is it possible for graycodes to exist for higher values of N, such that the iteration function can be calculated with just a permutation operation?
asked 2022-10-02
Why a complete graph has n ( n 1 ) 2 edges?
asked 2022-11-05
There are 5 different boxes and 7 different balls.All the balls are to be distributed in the 5 boxes placed in a row so that any box can recieve any number of balls.

New questions