Usu's blog

Number theory

By Usu, history, 6 years ago, In English

Hi! I encounter difficulties in understanding a well known fact in number theory. Given a number n, in how many ways can we write n as a sum of numbers? Exemple: 4 -> ( 4 ) ( 1 3 ) ( 2 2 ) ( 1 1 2 ) ( 1 1 1 1 ) Many thanks for those who can help me

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

The object is called partition.

The link is https://en.wikipedia.org/wiki/Partition_(number_theory), but Codeforces apparently dislikes the parentheses, so above is a hacky way to get there.

→ Reply
»
6 years ago, # |
← Rev. 14   Vote: I like it +3 Vote: I do not like it

Related: https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)

Stars and Bars

A similar question can be rephrased as: How many ways are there to distribute n stars into k bins (possibly empty), where stars are non-distinguishable, but unlike your question, the bins/variables are distinguishable (so order matters!). If n = 4, and you have say k = 4 'bins' to distribute each star, stars and bars will count the number of ways this can be done (the number of unique k-tuples that sum to n). When order does not matter and empty bins are disallowed (eg 1 + 0 + 0 + 3 = 3 + 0 + 0 + 1 = 1 + 0 + 3 + 0 etc are counted as the same, but would all be different in stars in bars), use partitions, provided in the comment above by Gassa.

Note that stars and bars can be extended to work for inequalities: How many ways to write n as a sum that is less than or equal to n using just k = 4 bins? Just add an extra bin (k = 5) where the stars count as 0.

→ Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Thank you, these helped me, especially 'stars and bars'

→ Reply
»
6 years ago, # |
← Rev. 12   Vote: I like it +5 Vote: I do not like it

Note that this problem can be solved indirectly using Combinatorics. Suppose that you have a positive integer n that you would like to partition as the summation of k numbers, where k ≥ 1. An equivalent problem is to count the number of distinct (n + k - 1) bit strings that contain exactly n zeros and k - 1 ones. The k numbers are simply the lengths of k zero segments whose total length is n and are separated by k - 1 ones in such bit strings.

The answer should be . When any of the k numbers should be strictly positive, the count should exclude the cases when the length of some segment is zero, i.e. when an n + k - 1 bit string contains two consecutive ones or when either the first bit or the last bit is one.

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

As already mentioned, this problem is popularly known as partition problem. It has a closed-formula, already mentioned by CodingKnight.

Here is one such problem you can solve.UVa: How do you add

→ Reply