2
$\begingroup$

Let's $N$ be a positive integer and $P$ - set of all possible partitions of the $N$, where $p = (a_1,a_2,...,a_n)$ with $a_1\le a_2 \le ... \le a_n$ and $a_1+a_2+...+a_n = N$. Let's $A$ be the number of partitions $p \in P: \dfrac{\max\{p\}}{\min\{p\}}<2$. How do I find the $A$?

Input: $N \in \Bbb N$. Output: $A$ - the number of partitions $p \in P: \dfrac{\max\{p\}}{\min\{p\}}<2$.

I think that this problem can be solved by a dynamic-based algorithm, but I didn't figure it out. Thanks in advance for your reply.

$\endgroup$
3
  • $\begingroup$ Okay, so maybe you need to correct your notation first; I think: $P$ is the set of all possible partitions of $N$ (instead of $\{P\}$) with elements $p = (a_1, a_2, …, a_n)$ with $a_1 ≤ a_2 ≤ … ≤ a_n$ and $a_1 + … + a_n = N$ – that is $p$ is a finite sequence (and not a set $p_k = \{a_1, a_2, …, a_n\}$ (and what’s $k$ here anyway?)) –, and then you look for $$A = \#\{p ∈ P; \frac{\max p}{\min p} < 2\}.$$ $\endgroup$
    – k.stm
    Commented Sep 14, 2017 at 17:23
  • 2
    $\begingroup$ Yes it can be solved with dynamic programming: if you compute for each $(n, k)$ the number $S(n, k)$ of partitions of $n$ with smallest part at least $k$ (which itself you can compute with dynamic programming), then the answer you want given input $N$ is $1 + \sum_{1 \le a \lt N} S(N - a, \lceil a/2 \rceil)$. (In other words: if the largest part in the partition of $N$ is $a$, then for the rest of the partition you need to find a partition of the remaining $N - a$, with smallest part at least $\lceil a / 2 \rceil$.) $\endgroup$
    – ShreevatsaR
    Commented Sep 14, 2017 at 17:26
  • $\begingroup$ @k.stm You're right, notation was quite unclear. I corrected it as you said, now it seems better $\endgroup$
    – Pathbreaker
    Commented Sep 14, 2017 at 17:40

1 Answer 1

Reset to default
3
$\begingroup$

Ends up this $A(n)$ sequence is very interesting: it gives the coefficients of the 5th order mock theta function $\chi_1(q)$ from Ramanujan's "lost" notebook. See the Online Encyclopedia of Integer Sequences link http://oeis.org/A053263 for the generating function, equivalent partition interpretations, references, etc.

$\endgroup$
3
  • $\begingroup$ How did you know that????? $\endgroup$
    – marty cohen
    Commented Sep 29, 2017 at 3:36
  • 1
    $\begingroup$ Oh, I just saw it... HA! I computed how many such partitions there were for small $n$ (by hand) and looked up the sequence in the OEIS. $\endgroup$
    – Brian Hopkins
    Commented Sep 29, 2017 at 3:54
  • $\begingroup$ Yep - that's what it's for. $\endgroup$
    – marty cohen
    Commented Sep 29, 2017 at 3:56

You must log in to answer this question.

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