1

Hello I am a 15 year old taking gcse maths and further maths and computer science. I need to know about partition of numbers for an algorithm that i am working on. However, partition is degree level maths and not something that i understand at all. I would really appreciate if someone could explain it to me in a easier to understand way. Want i want to achieve is where the input is a number between 1 and 200 and i want to output the number of possible shapes it can form. For example i want to make a hypothetical staircase where each step must be lower than the one above it and at least 2 steps must be made. For example, if the number inputted is 3 then the output should be 1 because it can only form one shape, 2 in the first step and one in the second.

However if 5 was inputted then it should output 2 because it can form 4 in the first column and 1 in the second column but can also form 3 in the first column and 2 in the second column.

Finlay Marsh
  • 21
  • There are several ways to define a partition of a number. Please edit your question to provide more information: the actual algorithm input and output specification, or an example, or both. – Ethan Bolker Mar 28 '17 at 23:19
  • I think you are looking for the number of ways to partition a number into distinct parts. This is not an easy problem. Here are two links: https://en.wikipedia.org/wiki/Partition_(number_theory)#Odd_parts_and_distinct_parts, https://oeis.org/A000009 – Ethan Bolker Mar 28 '17 at 23:42
  • Yes partitions are good, maybe you want to read about compositions too, later: https://en.wikipedia.org/wiki/Composition_(combinatorics) – mathreadler Mar 29 '17 at 07:41

0 Answers0