A simple looking problem in partitions that became increasingly complex - MathOverflow

A simple looking problem in partitions that became increasingly complex

2012-05-07T11:27:46Z

I began with problem which looked simple in the beginning but became increasingly complex as I dug deeper.

Main questions: 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).

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} $$

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.

Criteria 1: 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$.

Criteria 2: 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:

$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.

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.

Answer by Max Alekseyev for A simple looking problem in partitions that became increasingly complex

2012-05-07T15:22:46Z

I've got the following counts (which agrees with Brendan's):

1: 1

2: 3

3: 10

4: 55

5: 196

6: 2730

7: 10032

8: 108999

9: 973258

10: 20780331

11: 79309308

12: 2614200602

13: 10073335754

14: 288845706742

15: 11805287917646

16: 254331289285523

Answer by William J. Keith for A simple looking problem in partitions that became increasingly complex

2012-05-07T22:31:33Z

This may or may not be useful to you; I didn't get a complete answer from it.

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} .$$

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!$.

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?

(Interestingly, the very largest parts converge to a constant form with trailing zeros, but only about log of them have frozen at any $n$.)

Answer by Aaron Meyerowitz for A simple looking problem in partitions that became increasingly complex

2012-05-09T10:25:01Z

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.$

A more efficient modification is to treat seperately all groups of $j$ fractions $\frac{1}{j}.$ Call the sum of these the $w$-part and the remainder the $v$-part.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.

For an integer $n \ge 0$,

$f(n+\frac{y}{2},2)=n+1$ for $y=0,1$.
$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}$
$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 square-pyramidal 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$.
$f(n,5)=\binom{n+3}{4}+\binom{n+4}{4}=\frac{(n+2)^2((n+2)^2-1)}{12}$ these are four-dimensional pyramidal numbers . 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}$
$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 appears without much comment in OEIS.
$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.