Number of combinations of integers \leq n which sum to n

In summary, the "stars and bars" formula is a way to calculate the number of combinations of integers that sum to n. It is derived from the concept of dividing objects into groups and can be used for any values of n and r, as long as they are non-negative integers. Other methods for calculating this number include using generating functions and dynamic programming. The concept can be applied in various real-world applications, such as probability and statistics, and computer science.
  • #1
mapkan
3
0
Hi all,
I'm new to the forum, this is my problem:

given a positive integer n, i want to find how many combinations of integers smaller than n but larger than 0 sum to n. E.g.

n=3:
{3},{2,1},{1,1,1}

n=4:
{4},{3,1},{2,2},{2,1,1},{1,1,1}

it might just be that I'm tired, but I've been thinking about this for a while.

Thank you very much!
 
Physics news on Phys.org
  • #2
http://en.wikipedia.org/wiki/Partition_%28number_theory%29" .
 
Last edited by a moderator:
  • #3
pmsrw3 said:
http://en.wikipedia.org/wiki/Partition_%28number_theory%29" .
Thank you very much!
Perfect!
 
Last edited by a moderator:

Related to Number of combinations of integers \leq n which sum to n

1. What is the formula for calculating the number of combinations of integers that sum to n?

The formula for calculating the number of combinations of integers that sum to n is known as the "stars and bars" formula. It is expressed as (n + r - 1) choose (r - 1), where n is the total sum and r is the number of integers being combined.

2. How is the "stars and bars" formula derived?

The "stars and bars" formula is derived from the concept of dividing n objects into r groups. By placing (r - 1) dividers, or "bars", among the n objects, we can create r groups of objects. The number of ways to arrange these objects and dividers is equivalent to the number of combinations of integers that sum to n.

3. Can the "stars and bars" formula be used for any value of n and r?

Yes, the "stars and bars" formula can be used for any value of n and r. However, it is important to note that the formula only works for non-negative integers. Additionally, if n is a large number, it may be more practical to use a computer program to calculate the number of combinations.

4. Are there any other methods for calculating the number of combinations of integers that sum to n?

Yes, there are other methods for calculating the number of combinations of integers that sum to n. One method is through the use of generating functions, which involves expressing a series of numbers as a polynomial. Another method is through the use of dynamic programming, which involves breaking down a problem into smaller subproblems and storing the solutions in a table for efficient computation.

5. Can the number of combinations of integers that sum to n be used in real-world applications?

Yes, the concept of the number of combinations of integers that sum to n can be used in various real-world applications. For example, it can be used in probability and statistics to calculate the likelihood of certain outcomes. It can also be used in computer science for optimization problems, such as finding the most efficient way to pack items into a container.

Similar threads

A Number of unequal integers with sum S
    • Set Theory, Logic, Probability, Statistics
Replies
12
Views
1K
Each integer n>11 can be written as the sum of two composite numbers?
    • Calculus and Beyond Homework Help
Replies
7
Views
2K
Proof That 6 Divides Any Integer N
    • Precalculus Mathematics Homework Help
Replies
3
Views
1K
Can I use recursion/induction to show that N <= x < N+1 for x real
    • Math Proof Training and Practice
Replies
10
Views
2K
I Stuck on the probability of rolling 'p' with 'n' s-sided dice
    • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
Comp Sci Finding Cousins of Giuga Numbers: Can You Solve This Prime Number Puzzle?
    • Engineering and Comp Sci Homework Help
Replies
32
Views
3K
I Find an explicit formula for this n-sum problem
    • General Math
Replies
7
Views
2K
I Help with a difficult (?) regression
    • Set Theory, Logic, Probability, Statistics
Replies
7
Views
1K
Spin a dial that has a pointer to n regions
    • Set Theory, Logic, Probability, Statistics
Replies
10
Views
4K
Sum of combinations from k to n
    • Set Theory, Logic, Probability, Statistics
Replies
4
Views
3K

Hot Threads

Recent Insights

Back
Top