|
[Home] [Puzzles & Projects] [Delphi Techniques] [Math Topics] [Library] [Utilities] |
| Most positive integers can be written as the sum of positive integers in several ways. The elements or "parts" of such a sum for an integer n are called a partition of N. Partitions of N can contain as few as a single part {N}, or as many as N parts {1,1,1,.....1}. The normal representation of a partition is as a set of integers which sum to N, without the "+" signs. For example 5 may be partitioned in 7 ways. {5}, {4,1}, {3,2}, {3,1,1}, {2,2,1}, {2,,1,1,1}, {1,1,1,1,1}. Note that the order on the elements of a partition are not significant - they are typically written in colexicographical (reverse dictionary) order, also called standard form (SF). There are two common forms of the function which returns the number of partitions for a given integer: P(N) represents the total number of partitions of N. The other, P(N,k) or Pk(N), represents the number of partitions of N that contain K elements. Clearly P(N)=sum(Pk(N), k=1 to N). The program available here can generate all partitions or those of a specified size for numbers from 1 to 100. Actually, for P(N) grows quite rapidly, P(100)= exceeds 190 million, so it is not feasible to list partitions for large numbers. The program will stop computing after a specified number up to 1,000 are displayed. I would like to be able to display the partition of a particular rank, say the one millionth partition of 100, but haven't quite figured out how to do it yet. This page was motivated to help solve problem #103 in the Project Euler set of programming challenges: "Find the set, A, of 7 positive integers with the following characteristics:
A challenge indeed!
|
[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 2000-2011, Gary Darby
All rights reserved.
|
