# Calculating all non repeating ordered partitions in an interval

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)$$

• (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$. Jan 28 '19 at 17:36
• 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 Jan 28 '19 at 19:46

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.$$