What's the number of ways we can write $n\in\mathbb{N}$ as:

$n=d_1+2d_2+3d_3+\ldots+n\cdot d_n$, where $d_i$ is either $0$ or $1$?

By number of ways I mean how many different sets $\{d_1,\ldots,d_n\}$ are there. For example, $2=0+2\cdot 1$, and that's the only one way ($d_1=0, d_2=1$).

I noticed that if $d_n=1$, then $d_1,\ldots,d_{n-1}$ must be zero or if $d_n=0$ and $d_{n-1}=1$, then $d_1$ must be 1 and $d_2,\ldots,d_{m-2}$ must be zero. But that does not help much and I'd really appreciate some help. Maybe there is some technique that is applicable to this problem?

  • 4
    $\begingroup$ Unless I'm missing something, you're essentially asking for number of ways to partition $n$ into distinct parts. Google "partitions into distinct parts." $\endgroup$ – B. Goddard Nov 26 '16 at 19:49
  • $\begingroup$ $n\ne n$. Use two variables. $\endgroup$ – Martín-Blas Pérez Pinilla Nov 26 '16 at 19:53
  • $\begingroup$ As @B.Goddard said, this is the number of partitions of $n$ into distinct parts. The sequence of these values is [OEIS A000009](oeis.org/A000009); at the link you’ll find a fairly substantial collection of references, asymptotics, generating functions, etc. $\endgroup$ – Brian M. Scott Nov 26 '16 at 19:54
  • $\begingroup$ @Martín-BlasPérezPinilla clarified - if the author disagrees hopefully they will update further, if they can find the edit link (always a challenge for new users). $\endgroup$ – Joffan Nov 26 '16 at 20:34

Your Answer

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

Browse other questions tagged or ask your own question.