6
$\begingroup$

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.

$\endgroup$
7
  • 6
    $\begingroup$ Do you agree with 1,3,10,55,196,2730,10032 ? Not in OEIS. $\endgroup$ May 7, 2012 at 12:08
  • 1
    $\begingroup$ It seems more natural if we define $\tilde{s}(n)$ to be the number of solutions to $$1=k_1 +\frac{k_2}{2}+\cdots+\frac{k_n}{n}.$$ This more closely mimics the partition problem which is the number of solutions to $$1=k_n+\frac{n-1}{n}k_{n-1}+\dots + \frac{2}{n}k_2+\frac{1}{n}k_1.$$ If $n=p$ is prime, then $\tilde{s}(n)=1+\tilde{s}(n-1)$ $\endgroup$ May 7, 2012 at 14:46
  • 1
    $\begingroup$ By weakening your original condition, you seem to be adding a huge number of spurious solutions. This seems to make the problem more difficult, and even a complete solution to the new problem wouldn't say much about the original. If you are interested in the original problem, I think you should turn around. Of course, you may find the second problem of restricted partitions more interesting. By the way, the partitions of $n$ into $k$ parts which are at least $m$ correspond with the partitions of $n−km$ into at most $k$ parts. $\endgroup$ May 7, 2012 at 14:47
  • 1
    $\begingroup$ @Dougals, yes now actually, I am finding the second problem of restricted partitions more interesting than the one I started with. $\endgroup$ May 8, 2012 at 4:36
  • $\begingroup$ It appears that the $k_1$ term might be unnecessary. If we define $s(n,m)$ to be the number of solutions to $$\frac{k_2}{2}+\frac{k_3}{3}+...\frac{k_n}{n}=m $$ then $s(n)=\sum_{i=0}^n s(n,i).$ $\endgroup$ May 8, 2012 at 5:48

3 Answers 3

8
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Added this sequence as oeis.org/A208480 $\endgroup$ May 7, 2012 at 23:58
  • 1
    $\begingroup$ Thanks! What is the generating function or did you use brute force calculation method. $\endgroup$ May 8, 2012 at 4:34
  • 1
    $\begingroup$ I used dynamic programming to get my counts. This sequence however is closely related to oeis.org/A020473 which has almost four hundred terms computed. Perhaps the same approach may help computing terms of the current sequence. $\endgroup$ May 8, 2012 at 11:10
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.