A simple looking problem in partitions that became increasingly complex - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T15:12:43Z http://mathoverflow.net/feeds/question/96204 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/96204/a-simple-looking-problem-in-partitions-that-became-increasingly-complex A simple looking problem in partitions that became increasingly complex Nilotpal Sinha 2012-05-07T11:27:46Z 2012-05-09T10:25:01Z <p>I began with problem which looked simple in the beginning but became increasingly complex as I dug deeper. </p> <p><strong>Main questions</strong>: Find the number of solutions $s(n)$ of the equation $$n = \frac{k_1}{1} + \frac{k_2}{2} + \ldots + \frac{k_n}{n}$$ where $k_i \ge 0$ is a non-negative integer. This is my main questions. After tying different approaches, the one that I found most optimistic is as follows. But soon even this turned out to be devil (as we shall see why). </p> <p>Let $l_n$ be the LCM of the first $n$ natural numbers We know that $\log l_n =\psi(n)$. Multiplying both sides by $l_n$ we obtain $$n l_n = \frac{k_1 l_n}{1} + \frac{k_2 l_n}{2} + \ldots + \frac{k_n l_n}{n}$$</p> <p>Each term on the RHS is a positive integer thus our question is equivalent to finding the number of partitions of $nl_n$ in which each part satisfy some criteria.</p> <p><strong>Criteria 1</strong>: How small can a part be? Assume that there is a solution with $k_n = 1$ then the smallest term in the above sum will be the $n$-th term which is $l_n / n$. Hence each term in our partition is $\ge l_n/n$.</p> <p><strong>Criteria 2</strong>: How many prime factors can each part contain? If my calculation is correct then for $n \ge 2, 2 \le r \le n$, the minimum number of prime factors that $l_n /r$ can contain is $\pi(n)-1$. With these two selection criterion we have:</p> <p><strong>$s(n) \le$ No. of partitions of $n l_n$ into at most $n$ parts such that each part is greater than $l_n / n$ and has at least $\pi(n) - 1$ different prime factors.</strong></p> <p>May be we can narrow down further by adding sharper selection criterions but I thought it was already complicated enough for the time being. The asymptotics of the number of partitions of $n$ into $k$ parts $p(n,k)$ is well known, but I have not found in literature any asymptotics for the number of partitions of $n$ into $k$ parts such that each part is at least $m$, let alone the case when each part has a certain minimum number of prime factors. I am looking for any suggestions, reference materials that would help in these intermediate questions that would ultimately help in answering the main question.</p> http://mathoverflow.net/questions/96204/a-simple-looking-problem-in-partitions-that-became-increasingly-complex/96228#96228 Answer by Max Alekseyev for A simple looking problem in partitions that became increasingly complex Max Alekseyev 2012-05-07T15:22:46Z 2012-05-07T15:22:46Z <p>I've got the following counts (which agrees with Brendan's):</p> <p>1: 1</p> <p>2: 3</p> <p>3: 10</p> <p>4: 55</p> <p>5: 196</p> <p>6: 2730</p> <p>7: 10032</p> <p>8: 108999</p> <p>9: 973258</p> <p>10: 20780331</p> <p>11: 79309308</p> <p>12: 2614200602</p> <p>13: 10073335754</p> <p>14: 288845706742</p> <p>15: 11805287917646</p> <p>16: 254331289285523</p> http://mathoverflow.net/questions/96204/a-simple-looking-problem-in-partitions-that-became-increasingly-complex/96271#96271 Answer by William J. Keith for A simple looking problem in partitions that became increasingly complex William J. Keith 2012-05-07T22:31:33Z 2012-05-07T22:31:33Z <p>This may or may not be useful to you; I didn't get a complete answer from it.</p> <p>If you multiply the original equation by $n!$ on both sides, you get $$n \cdot n! = k_1 n! + k_2 \frac{n!}{2} + \dots + k_n \frac{n!}{n} .$$</p> <p>In the factorial-base expansion $n = a_1 1! + a_2 2! + a_3 3! + \dots$, this is then partitioning $00\dots0n$ into parts $00\dots0001 = (n-1)! = \frac{n!}{n}$ , $00\dots0011 = (n-1)!+(n-2)! = \frac{n!}{n-1}$ , $00\dots0221 = \frac{n!}{n-3}$ , $00\dots6631$ , ... , $00\dots000\frac{n}{2}$ , $00\dots00001 = n!$.</p> <p>The leading digits obey the obvious distribution, starting with $0\dots x1$, then $0\dots x2$, with the $x$ increasing at increasing rates. Now, partition problems don't necessarily behave well under small changes in the allowed parts, but if you can prove some sort of well-behavedness in the vicinity of these summands -- say, just taking the $0\dots x j$ parts -- perhaps poking at the factorial-base expansion will give you some sense of the asymptotics?</p> <p>(Interestingly, the very largest parts converge to a constant form with trailing zeros, but only about log of them have frozen at any $n$.)</p> http://mathoverflow.net/questions/96204/a-simple-looking-problem-in-partitions-that-became-increasingly-complex/96424#96424 Answer by Aaron Meyerowitz for A simple looking problem in partitions that became increasingly complex Aaron Meyerowitz 2012-05-09T10:25:01Z 2012-05-09T10:25:01Z <p>I am impressed by the counts found by Max. Here are some comments which are perhaps already included in his dynamic program. For any non-negative integer $m$ let $f(m,n)$ be the number of solutions to $m = \frac{k_1}{1} + \frac{k_2}{2} + \ldots + \frac{k_n}{n}$ with the $k_i$ non-negative integers. We could actually consider $f(u,n)$ for rational $u$ but won't pay much attention to that general case. The numbers requested are the diagonal of the table of $f(m,n)$ for $m,n$ integers. The obvious generating function procedure for $\sum f(u,n)x^u$ is effective, at least for a while; To calculate the values of $f(u,n)$ $u \le U$ form the product $$\prod_{d=1}^n\frac{1}{1-x^{\frac{1}{d}}}$$ and truncate at $x^U.$ In practice this would be done one factor at a time (computing all the $f(u,s)$ for $s \lt n$ along the way.) If desired, all terms with $x$ to an exponent greater than $U$ can be truncated before going on. The coefficient of $x^u$ is $f(u,n)$. Of course $f(u,n)$ for fixed $n$ is given by some polynomial function depending on the denominator of $u.$ </p> <p>A more efficient modification is to treat seperately all groups of $j$ fractions $\frac{1}{j}.$ Call the sum of these the $w$-<strong>part</strong> and the remainder the $v$-<strong>part</strong>.If we have a given expansion $u = \frac{k_1}{1} + \frac{k_2}{2} + \ldots + \frac{k_n}{n}$ let $k_d=dq_d+r_d$ with $0 \le r_d \lt d$ then $u=w+v$ where $v = \frac{r_2}{2} + \ldots + \frac{r_n}{n}$ will be a number less than $n$ with the same fractional part as $u$ while $w=\frac{q_1}{1} + \frac{2q_2}{2} + \ldots + \frac{nq_n}{n}$ will be an integer expressed as a sum of units. The number of ways to get a fixed integer $w$ is $\binom{w+n-1}{n-1}$ because this is just the number of ways to put $w$ identical balls into $n$ boxes (a ball in box $j$ denotes a pack of $j$ fractions $\frac{1}{j}$.) Here is an analysis of this process carried out for a few steps.</p> <p>For an integer $n \ge 0$, </p> <ul> <li><p>$f(n+\frac{y}{2},2)=n+1$ for $y=0,1$. </p></li> <li><p>$f(n+\frac{y}{6},3)=\binom{n+2}{2}$ for $y=0,2,3,4,5$ but $f(n+\frac{1}{6},3)=f((n-1)+\frac{7}{6})=\binom{n+1}{2}$ This is because the $v$ part is less than $1$ with the exception of $\frac{1}{2}+\frac{2}{3}=\frac{7}{6}$ </p></li> <li><p>$f(n+\frac{y}{12},4)=\binom{n+2}{3}+\binom{n+3}{3}=\frac{(n+1)(n+2)(2n+3)}{6}$ for $y=0,3,4,7,8,11$ This is the sum of the squares up to $(n+1)^2$ so a <em>square-pyramidal</em> number. The other possibilities are $2\binom{n+2}{3}$ for $y=1,2,5$ and $2\binom{n+3}{3}$ for $y=6,9,10$.</p></li> <li><p>$f(n,5)=\binom{n+3}{4}+\binom{n+4}{4}=\frac{(n+2)^2((n+2)^2-1)}{12}$ these are <a href="http://oeis.org/A002415" rel="nofollow">four-dimensional pyramidal numbers</a> . Note that the expansion looks like the previous case. This is because the $v$ part can not use anything of the form $\frac{r}{5}$ . This only becomes possible at $n=10$ with $\frac{2}{5}+\frac{1}{10}=\frac{1}{5}+\frac{3}{10}=\frac{5}{10}=\frac{1}{2}$ as well as four ways to get $1$ and two ways to get $\frac{3}{2}$ </p></li> <li><p>$f(n,6)=4\binom{n+3}{5}+7\binom{n+4}{5}+\binom{n+5}{5}.$ The $7$ in the middle comes from the five cases $\frac{1}{2}+\frac{2}{4}=\frac{1}{2}+\frac{3}{6}=\frac{2}{4}+\frac{3}{6}=\frac{1}{2}+\frac{1}{3}+\frac{1}{6}=\frac{2}{4}+\frac{1}{3}+\frac{1}{6}=1$ along with $\frac{1}{3}+\frac{4}{6}=\frac{2}{3}+\frac{2}{6}=1$ . This <a href="http://oeis.org/A086689" rel="nofollow">appears</a> without much comment in OEIS.</p></li> <li><p>$f(n,7)=4\binom{n+4}{6}+7\binom{n+5}{6}+\binom{n+6}{6}$ The coefficients are as in the previous case because there can be no contribution of $\frac{r}{7}$ to the $v$ part until $n=14.$ This sequence of numbers $1,14,81,308,910,2268,4998,10032,\cdots$ does not appear in the OEIS at this moment.</p></li> </ul>