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

# | User | Rating |
---|---|---|

1 | tourist | 3843 |

2 | jiangly | 3705 |

3 | Benq | 3628 |

4 | orzdevinwang | 3571 |

5 | Geothermal | 3569 |

5 | cnnfls_csy | 3569 |

7 | jqdai0815 | 3530 |

8 | ecnerwala | 3499 |

9 | gyh20 | 3447 |

10 | Rebelz | 3409 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 171 |

2 | adamant | 163 |

2 | awoo | 163 |

4 | TheScrasse | 157 |

5 | nor | 153 |

6 | maroonrk | 152 |

6 | -is-this-fft- | 152 |

8 | Petr | 145 |

9 | orz | 144 |

9 | pajenegod | 144 |

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

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/17/2024 23:30:01 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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.

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.

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

Note that this problem can be solved indirectly using Combinatorics. Suppose that you have a positive integer

nthat you would like to partition as the summation ofknumbers, wherek≥ 1. An equivalent problem is to count the number of distinct (n+k- 1) bit strings that contain exactlynzeros andk- 1 ones. Theknumbers are simply the lengths ofkzero segments whose total length isnand are separated byk- 1 ones in such bit strings.The answer should be . When any of the

knumbers should be strictly positive, the count should exclude the cases when the length of some segment is zero, i.e. when ann+k- 1 bit string contains two consecutive ones or when either the first bit or the last bit is one.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