6
$\begingroup$

For the sequence of unique partitions of integer $n$: $n, \\ (n-1)+1,\\ (n-2)+2,\ (n-2)+1+1,\\ (n-3)+3,\ (n-3)+2+1,(n-3)+1+1+1,\\ (n-4)+4,\ (n-4)+3+1,\ (n-4)+2+2,\ (n-4)+2+1+1,\ (n-4)+1+1+1+1,\\ ...etc.$

the sequence of the number of items in each partition is: $1,2,2,3,2,3,4,2,3,3,4,5,2,3,3,4,4,5,6,2,3,3,4,3,4,....etc.$

What's the $nth$ term of this sequence? Does a closed form expression for it exist? My guess is not, but I can't prove it. The need for one arises from the generating function for a permutation of a set of objects in a set of containers.

$\endgroup$
4
  • 1
    $\begingroup$ Really struggling to make sense of this question. Partitions are usually written with addition, not subtraction, e.g. partitions of $4$ are $4$, $3+1$, $2+2$, $2+1+1$, $1+1+1+1$. I don't understand how $n-1$ is a partition of $n$, nor $n-2$, $n-1-1$ etc. Perhaps you could clarify? $\endgroup$
    – N. Shales
    Commented Apr 22, 2017 at 0:34
  • 1
    $\begingroup$ @N Shales Apologies, don't know what I was thinking. I had meant to write these in the form (n-2)+2, etc. It's fixed now. $\endgroup$
    – Jeff Strom
    Commented Apr 22, 2017 at 1:11
  • $\begingroup$ Why do we need consider $n, n-1, n-2$ etc. instead of just looking at the partitions $1, 2, 1+1, 3, 2+1, ...$? Note that some of these will not be partitions for small values of $n$ - e.g., $(n-3, 3) = (1,3)$ is not a partition for $n = 4$ since partitions are usually defined as decreasing tuples. $\endgroup$ Commented Apr 22, 2017 at 1:30
  • $\begingroup$ @Jair Taylor my reason for writing the sequence of partitions this way is that it directly relates to a problem I'm working on. I'm certain there are many other ways to write this, this way is clearest for what I'm trying to do (which is count the number of values used in each partition of $n$, starting from $n$ and ending at $n \ = \ 1 + 1 + 1 + ..$). $\endgroup$
    – Jeff Strom
    Commented Apr 22, 2017 at 1:43

1 Answer 1

2
$\begingroup$

Always try OEIS (Online Encyclopedia of Integer Sequences). If you subtract one from your sequence you get

$0, 1, 1, 2, 1, 2, 3, 1, 2, 2, 3, 4, \ldots$

This is sequence A036043 in OEIS. "Irregular triangle read by rows: row n (n >= 0) gives number of parts in all partitions of n (in Abramowitz and Stegun order)." I doubt there is any kind of nice formula.

The Abramowitz and Stegun order on partitions is apparently the one you are using.

$\endgroup$
4
  • $\begingroup$ Thanks for the reference (I could swear I searched the OEIS and didn't find anything before). Is there a generating function for the nth term of the sequence, though? $\endgroup$
    – Jeff Strom
    Commented Apr 22, 2017 at 2:34
  • 1
    $\begingroup$ Hmm, I doubt it, since the gf would have to somehow encode this particular ordering of partitions and that's not the kind of thing that generating functions are usually good for. $\endgroup$ Commented Apr 22, 2017 at 2:53
  • 1
    $\begingroup$ Enumeration of partitions is generally hard (there's no simple formula even for the number of partitions of $n$) $\endgroup$ Commented Apr 22, 2017 at 2:55
  • $\begingroup$ That's precisely what I was thinking in the original question statement. Glad (or maybe I should say "not glad") to see that my instinct was correct. So far I've got a shortcut method of calculation for finding the order of sequence terms, but it's messy. Hope someone (a better mathematician) can figure this out at some point. $\endgroup$
    – Jeff Strom
    Commented Apr 22, 2017 at 2:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .