1
$\begingroup$

I need to calculate in how many ways can I add the integers in the interval $[1,9]$ in groups of $P$ elements, so that they sum to $N$. The set of groups must not contain sums that have the same elements (in the sense that 1+1+3, 1+3+1, and 3+1+1 would all count as 1 variation).

We may call this a specific partition Q, so I'm trying to figure out:

$$Q_p(n) = ?$$

$Q$ can be defined as $0$ if $\frac{n}{p}<1$ or $\frac{n}{p}>9$, since we cannot generate a feasible solution.

For instance $Q_2(8) = 4$, because we can write 8 as the following sums: $(1+7, 2+6, 3+5, 4+4)$

The solution of $Q_3(8) = 5$ and the sums are: $(1+1+6,1+2+5,1+3+4,2+2+4,2+3+3)$

I've calculated programmatically the values up to 9, but I can't seem to figure out a pattern.

        1
       1 1
      1 1 1
     1 2 1 1
    1 2 2 1 1
   1 3 3 2 1 1
  1 3 4 3 2 1 1
 1 4 5 5 3 2 1 1
1 4 7 6 5 3 2 1 1

It is clear for me that:

$Q_1(N)=1$

$Q_2(N) = \lfloor N/2 \rfloor$ (only for N < 19, thanks Mike)

$Q_{N-1}(N)=1$

$Q_N(N)=1$

But I can't figure out either a generic way to represent all of them, nor even the central diagonals. Is this a known problem? Any help or hints highly appreciated

EDIT: this seems like a variation of the restricted part size or number of parts that can be solved recursively as (but will fail for N>10 because of the restriction interval): $$Q_p(n) = Q_p(n-p) + Q_{p-1}(n-1)$$

$\endgroup$
  • $\begingroup$ (1) You say "non-repeating," but allow $4+4$, can you clarify? (2) You say "ordered," but do not count $1+7$ distinct from $7+1$, can you clarify? (3) Are $p$ and $K$ the same thing? (4) Does $Q_2(N)=\lfloor N/2\rfloor$ hold for all $N$? Seems like $Q_2(19)$ should be zero; the largest possible sum with $2$ numbers is $9+9$. $\endgroup$ – Mike Earnest Jan 28 at 17:36
  • $\begingroup$ Hello @MikeEarnest, thank you for your remarks. I have edited my question to make sure they are all clear. I apologize for my wording, I come from a computer science background. Summing up: (1,2) repeated sequences are not allowed, so 1+7 and 7+1 count as 1. (3) yes, I renamed K to p. (4) you are absolutely correct, I missed that completely. I added the definition of when Q should be zero $\endgroup$ – luksfarris Jan 28 at 19:46
1
$\begingroup$

Letting $Q^m_p(n)$ be the number of partitions of $n$ with $p$ parts whose sizes are between $1$ and $m$, you want $Q^9_p(n)$. This can be computed via $$ Q^m_p(n) = Q^{m-1}_{p}(n-p)+Q^m_{p-1}(n-1). $$ This is a known problem. It is related to the Gaussian binomial coefficients. Specifically, $$ \sum_{n=p}^{mp}Q^{m}_{p}(n)q^n=q^p\binom{m+p-1}{p}_q. $$

$\endgroup$
  • $\begingroup$ Brilliant, seems I have some catching up to do. Thank you very much, Mike $\endgroup$ – luksfarris Jan 28 at 21:14

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.