6
$\begingroup$

Consider a partition $$n=n_1+n_2+\cdots+n_k$$ such that each number $1,\cdots, n$ can be obtained by adding some of the numbers $n_1,n_2,\cdots,n_k$. For example, $$9=4+3+1+1,$$

and every number $1,2,\cdots,9$ be ca written as a sum of some of the numbers $4,3,1,1$. This other partition $$9=6+1+1+1$$ fails the desired property, as $4$ (and $5$) cannot be given by any sum of $6,1,1,1$.

Question: Can we charaterize which partitions of an arbitrary $n$ have this property? We clearly need at least one $1$ among $n_1,n_2,\cdots,n_k$, and intuitively we need many small numbers $n_i$. But I can't see much beyond this. Any idea or reference will be appreciated.

$\endgroup$
  • $\begingroup$ If at least half of the number are 1's, you can do it. But the condition is certainly not necessary. $\endgroup$ – MathChat Jan 26 '17 at 6:03
  • 1
    $\begingroup$ I once studied this problem and found a constructive partition method. Here is the brief. We are given a positive integer $n$. STEP ONE: if $n$ is an even number, partition it into $A=\frac{n}{2}$ and $B=\frac{n}{2}$; otherwise, partition it into $A=\frac{n+1}{2}$ and $B=\frac{n-1}{2}$. STEP TWO: re-partition $B$ into $A_1$ and $B_1$. STEP THREE: re-partition $B_1$......Until we get $1$. I didn't prove this method always works but I believe it is valid. $\endgroup$ – apprenant Jan 26 '17 at 6:04
  • $\begingroup$ EXAMPLE: $13 \rightarrow (7,6) \rightarrow (7,3,3) \rightarrow (7,3,2,1)$. May it be helpful. $\endgroup$ – apprenant Jan 26 '17 at 6:06
  • $\begingroup$ @apprenant. This method looks interesting. BTW, is this problem well known? $\endgroup$ – ALEXIS Jan 26 '17 at 6:14
  • $\begingroup$ You can work up the other way, too, by powers of two, e.g $13 \to 1,2,4,6$ $\endgroup$ – Joffan Jan 26 '17 at 6:17
1
$\begingroup$

Let $\lambda$ be a partition of $n$. The required condition is that $\lambda$ contain partitions $\lambda_i$ of each $1 \le i < n$. Clearly if $\lambda$ contains a partition of $j$ then it also contains a partition of $(n - j)$, being the multiset difference $\lambda - \lambda_j$.

Therefore the first thing to notice is that $\lambda$ cannot contain any element $a > \lceil \frac{n}{2} \rceil$, for if it did then $\{a\}$ cannot be part of a partition of $\lceil \frac{n}{2} \rceil$ and $\lambda - \{a\}$ is a partition of $(n - a) < (n - \lceil \frac{n}{2} \rceil) < \lceil \frac{n}{2} \rceil$ cannot contain a partition of $\lceil \frac{n}{2} \rceil$.

Now, suppose that the largest element of $\lambda$ is $m$. It is certainly sufficient that $\lambda - \{m\}$ should satisfy the corresponding condition of providing partitions for each $1 \le i < (n - m)$. Proof: $\lambda - \{m\}$ is a partition of $(n - m)$ and provides partitions for each smaller natural number, so it remains to construct partitions $\lambda_i$ for $(n - m) < i < n$. We can do this by taking partitions from $\lambda - \{m\}$ for $(n - 2m) < j < n - m$ and then adding $\{m\}$ to each one. This can only fail if $j < 0$, which can only happen if $(n - 2m) < -1$. Since $m \le \lceil \frac{n}{2} \rceil$ we have $n - 2m \ge n - 2\lceil \frac{n}{2} \rceil$, which is $0$ if $n$ is even and $-1$ if $n$ is odd, so all cases are covered.

The interesting question is whether it's necessary that $\lambda - \{m\}$ should satisfy the same condition. Clearly it must contain partitions of $1 \le i < m$, since $\{m\}$ doesn't participate in them. And by the simple principle of taking complements in $\lambda$ it's clear that for each $m \le i < n$ the remnant $\lambda - \{m\}$ must either contain partitions of $(i - m)$ and $n - i$; or $i$ and $n - m - i$. Is that sufficient?

My intuition is that it's necessary, and testing on small examples (up to $n = 30$) supports that, but I haven't proved it.

In the Online Encyclopedia of Integer Sequences it's A126796 and a comment claims the characterisation

A partition is complete iff each part is no more than 1 more than the sum of all smaller parts. (This includes the smallest part, which thus must be 1.) - Franklin T. Adams-Watters, Mar 22 2007

$\endgroup$
1
$\begingroup$

This is just a quick and dirty list of the first examples, for $n$ up to $10$. Feel free to edit, extend, or amend.

$$1\\1+1\\ 1+1+1\quad1+2\\ 1+1+1+1\quad1+1+2\\ 1^5\quad1+1+1+2\quad1+2+2\quad1+1+3\\ 1^6\quad1^4+2\quad1^2+2+2\quad1^3+3\quad1+2+3\\ 1^7\quad1^5+2\quad1^3+2+2\quad1+2^3\quad1^4+3\quad1^2+2+3\quad1^3+4\quad1+2+4\\ 1^8\quad1^6+2\quad1^4+2+2\quad1^2+2+2+2\quad1^5+3\quad1^3+2+3\quad1^2+3+3\quad1+2+2+3\quad1^4+4\quad1+1+2+4\\ 1^9\quad1^7+2\quad1^5+2+2\quad1^3+2^3\quad1+2^4\quad1^6+3\quad1^4+2+3\quad1^2+2+2+3\quad1^3+3+3\quad1+2+3+3\quad1^5+4\quad1^3+2+4\quad1+2+2+4\quad1+1+3+4\quad1^4+5\quad1^2+2+5\\ 1^{10}\quad1^8+2\quad1^6+2^2\quad1^4+2^3\quad1^2+2^4\quad1^7+3\quad1^5+2+3\quad1^3+2^2+3\quad1+2^3+3\quad1^4+3^2\quad1^2+2+3^2\quad1^6+4\quad1^4+2+4\quad1^2+2^2+4\quad1^3+3+4\quad1+2+3+4\quad1^5+5\quad1^3+2+5\quad1+2^2+5\quad1+1+3+5$$

I hope the meaning of the superscript notation is clear, and I hope someone will check that I didn't make any mistakes or overlook anything. The list so far gives the sequence

$$1,1,2,2,4,5,8,10,16,20,\ldots$$

which (after correcting a pair of mistakes in the original posting here) Peter Taylor found in the OEIS.

$\endgroup$
  • $\begingroup$ I get 1, 1, 1, 2, 2, 4, 5, 8, 10, 16, 20, 31, 39, 55, 71, 100, 125, 173, 218, 291 starting at index 0. A126796 $\endgroup$ – Peter Taylor Jan 26 '17 at 17:07
  • $\begingroup$ @PeterTaylor, thank you! I see now what I missed: $7=1^3+4$ and $10=1+1+3+5$. Darn! I swear, I checked and double checked all my counts. I guess I needed to triple check.... $\endgroup$ – Barry Cipra Jan 26 '17 at 19:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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