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

Click For Summary
SUMMARY

The discussion centers on calculating the number of combinations of positive integers less than or equal to a given integer n that sum to n. For example, for n=3, the valid combinations are {3}, {2,1}, and {1,1,1}. For n=4, the combinations include {4}, {3,1}, {2,2}, {2,1,1}, and {1,1,1}. The problem relates to the concept of integer partitions in number theory, specifically referencing the Wikipedia page on partitions.

PREREQUISITES
  • Understanding of integer partitions in number theory
  • Basic combinatorial mathematics
  • Familiarity with positive integers and their properties
  • Knowledge of generating functions (optional for deeper insights)
NEXT STEPS
  • Study the concept of integer partitions in detail
  • Learn about generating functions and their application in combinatorics
  • Explore algorithms for calculating partitions, such as dynamic programming approaches
  • Investigate the relationship between partitions and combinatorial identities
USEFUL FOR

Mathematicians, computer scientists, and students interested in combinatorial mathematics and number theory.

mapkan
Messages
3
Reaction score
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
http://en.wikipedia.org/wiki/Partition_%28number_theory%29" .
 
Last edited by a moderator:
pmsrw3 said:
http://en.wikipedia.org/wiki/Partition_%28number_theory%29" .
Thank you very much!
Perfect!
 
Last edited by a moderator:

Similar threads

Graduate Number of unequal integers with sum S
  • · Replies 12 ·
Replies
12
Views
2K
High School Two interesting number theory tricks
  • · Replies 3 ·
Replies
3
Views
2K
Each integer n>11 can be written as the sum of two composite numbers?
  • · Replies 7 ·
Replies
7
Views
4K
Graduate Spin a dial that has a pointer to n regions
  • · Replies 10 ·
Replies
10
Views
5K
Undergrad Help with a difficult (?) regression
  • · Replies 7 ·
Replies
7
Views
2K
Graduate Is this product always greater than these sums?
  • · Replies 10 ·
Replies
10
Views
7K
Comp Sci Finding Cousins of Giuga Numbers: Can You Solve This Prime Number Puzzle?
  • · Replies 32 ·
2
Replies
32
Views
5K
Undergrad What Is the Probability of Rolling Pairs That Sum to Seven with n Dice?
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Can 1/4 of the total combinations match 6 numbers drawn from a set of 80?
  • · Replies 2 ·
Replies
2
Views
7K
Undergrad Find an explicit formula for this n-sum problem
  • · Replies 7 ·
Replies
7
Views
3K