The
Rational Argumentator
Free Tools for Rational Education
Combinatorics Practice Problems and Solutions
Partitions of Integers: Practice Problems and Solutions
This section is part of Mr. Stolyarov's Combinatorics Problems and Solutions.
Problem 5a (Source: Brualdi, Richard A. Introductory Combinatorics. First Edition. 1977): "A partition of a positive integer n is a representation of n as the sum of positive integers. The order of the integers in the sum is not taken into account. For instance, 6 = 3 + 3, 6 = 6, and 6 = 1 + 1 + 2 + 2 are partitions of 6. Let pn equal the number of partitions of n. Define p0 = 1."
"Show that pn equals the number of partitions of the multiset S = {n∙a} into unordered multisets whose number is not specified."
Solution 5a by Mr. Stolyarov. We consider some partition of n where n = b1 + b2 + ... + bk.
Such a partition corresponds to a partition of S = {n∙a} into the following k subsets:
{b1∙a},{b2∙a},..., {bk∙a}.
Likewise, any partition of S = {n∙a} into the m subsets
{c1∙a},{c2∙a},..., {cm∙a} will correspond to a partition of n where n = c1 + c2 + ... + cm.
So there is a one-to-one correspondence between partitions of S = {n∙a} into unordered multisets and partitions of n. So pn = the number of partitions of S = {n∙a} into unordered multisets. Q. E. D.
Problem 5b (Source:Brualdi, Richard A. Introductory Combinatorics. First Edition. 1977): "Show that pn equals the number of solutions to the equation n = 1x1 + 2x2 + ... + nxn in the nonnegative integers x1, x2, ... , xn."
Solution 5b by Mr. Stolyarov. A partition of n can contain some nonzero quantity of any of the numbers 1 through n but no nonzero quantity of any of the numbers greater than n. For any particular partition, the value of x1 is how many 1's are contained in the partition (at most n), the value of x2 is how many 2's are contained in the partition (at most n/2),..., the value of xn is how many n's are contained in the partition (at most 1). So any solution of the given equation in nonnegative integers (x1, x2,..., xn) is equivalent to a partition with x1 1's, x2 2's,..., and xn n's. Thus, the number of solutions to the given equation in nonnegative integers is equal to the number of partitions of n = pn. Q. E. D.
Gennady Stolyarov II (G. Stolyarov II) is an actuary, science-fiction novelist, independent philosophical essayist, poet, amateur mathematician, composer, and Editor-in-Chief of The Rational Argumentator, a magazine championing the principles of reason, rights, and progress.
In December 2013, Mr. Stolyarov published Death is Wrong, an ambitious children’s book on life extension illustrated by his wife Wendy. Death is Wrong can be found on Amazon in paperback and Kindle formats.
Mr. Stolyarov has contributed articles to the Institute for Ethics and Emerging Technologies (IEET), The Wave Chronicle, Le Quebecois Libre, Brighter Brains Institute, Immortal Life, Enter Stage Right, Rebirth of Reason, The Liberal Institute, and the Ludwig von Mises Institute. Mr. Stolyarov also published his articles on Associated Content (subsequently the Yahoo! Contributor Network) from 2007 until its closure in 2014, in an effort to assist the spread of rational ideas. He held the highest Clout Level (10) possible on the Yahoo! Contributor Network and was one of its Page View Millionaires, with over 3.1 million views.
Mr. Stolyarov holds the professional insurance designations of Associate of the Society of Actuaries (ASA), Associate of the Casualty Actuarial Society (ACAS), Member of the American Academy of Actuaries (MAAA), Chartered Property Casualty Underwriter (CPCU), Associate in Reinsurance (ARe), Associate in Regulation and Compliance (ARC), Associate in Personal Insurance (API), Associate in Insurance Services (AIS), Accredited Insurance Examiner (AIE), and Associate in Insurance Accounting and Finance (AIAF).
Mr. Stolyarov has written a science fiction novel, Eden against the Colossus, a philosophical treatise, A Rational Cosmology, a play, Implied Consent, and a free self-help treatise, The Best Self-Help is Free. You can watch his YouTube Videos. Mr. Stolyarov can be contacted at gennadystolyarovii@yahoo.com.
Click here to return to the index of Free Tools for Rational Education.
Learn about Mr. Stolyarov's novel, Eden against the Colossus, here.Read Mr. Stolyarov's comprehensive treatise, A Rational Cosmology, explicating such terms as the universe, matter, space, time, sound, light, life, consciousness, and volition, here.