3
$\begingroup$

How many different ways can a number $n \in N$ be expressed as a sum of $k$ different positive numbers?

$\endgroup$
  • $\begingroup$ How is this problem different than finding the "number of partitions of $n$ into $m$ distinct parts"? (see A008289) Answers here seem to use advanced tools compared to formulas on OEIS. $\endgroup$ – lbeziaud Oct 3 '17 at 19:29
2
$\begingroup$

We show how to establish a recurrene for the number $Q(n,k)$ of partitions of $n$ into $k$ different parts where order is not important. (If it were and with all parts distinct we could just multiply by $k!.$) Using the Polya Enumeration Theorem (PET) we get for the answer that it is given by

$$[z^n] Z(P_k)\left(\frac{z}{1-z}\right)$$

where $Z(P_k)$ is the cycle index of the unlabled set operator $\mathfrak{P}_{=k}$ with OGF

$$G(w) = \exp\left(a_1 w - a_2 \frac{w^2}{2} + a_3 \frac{w^3}{3} - \right) \\ = \exp\left(\sum_{l\ge 1} a_l (-1)^{l-1} \frac{w^l}{l}\right).$$

Differentiating we obtain

$$G'(w) = G(w) \left(\sum_{l\ge 1} a_l (-1)^{l-1} w^{l-1}\right).$$

Extracting coefficients on [w^k] we find

$$(k+1) Z(P_{k+1}) = \sum_{q=0}^k [w^{k-q}] G(w) [w^q] \sum_{l\ge 1} a_l (-1)^{l-1} w^{l-1} \\ = \sum_{q=0}^k Z(P_{k-q}) a_{q+1} (-1)^q = \sum_{q=1}^{k+1} Z(P_{k+1-q}) a_{q} (-1)^{q-1}.$$

We get the recurrence

$$Z(P_k) = \frac{1}{k} \sum_{q=1}^{k} Z(P_{k-q}) a_{q} (-1)^{q-1}$$

with $Z(P_0) = 1.$ This yields for the present case that the substituted cycle index

$$L_k(z) = Z(P_k)\left(\frac{z}{1-z}\right)$$

has recurrence

$$L_k(z) = \frac{1}{k} \sum_{q=1}^{k} L_{k-q}(z) \frac{z^q}{1-z^q} (-1)^{q-1}.$$

Extracting the coefficient on $[z^n]$ we obtain

$$Q_{n,k} = \frac{1}{k} \sum_{q=1}^{k} [z^n] L_{k-q}(z) \frac{z^q}{1-z^q} (-1)^{q-1} \\ = \frac{1}{k} \sum_{q=1}^{k} [z^{n-q}] L_{k-q}(z) \frac{1}{1-z^q} (-1)^{q-1} \\ = \frac{1}{k} \sum_{q=1}^{k} (-1)^{q-1} \sum_{p=0}^{\lfloor n/q\rfloor - 1} Q_{n-(p+1)q, k-q}.$$

The boundary conditions here are $Q_{0,0} = 1$ and $Q_{n,0} = Q_{0,k} = 0$ and $Q_{n,1} = 1.$ There is a non-essential boundary condition which is that $Q_{n,k} = 0$ when $n \lt \frac{1}{2} k(k+1).$

Observe that we can obtain an alternate form of the recurrence by writing

$$\frac{1}{k} \sum_{q=1}^{k} (-1)^{q-1} \sum_{p=1}^{\lfloor n/q\rfloor} Q_{n-pq, k-q}$$

which is

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{k} \sum_{m=1}^n \sum_{q|m\wedge q\le k} (-1)^{q-1} Q_{n-m, k-q}.}$$

This yields the following Maple routine:

with(numtheory);

Q :=
proc(n, k)
    option remember;

    if n=0 and k=0 then return 1 fi;
    if n=0 or k=0  then return 0 fi;

    if k=1 then return 1 fi;

    if n < 1/2*k*(k+1) then return 0 fi;

    1/k*add((-1)^(q-1)*
            add(Q(n-(p+1)*q, k-q), p=0..floor(n/q)-1),
            q=1..k);
end;


QX :=
proc(n, k)
    option remember;

    if k < 0 then return 0 fi;

    if n=0 and k=0 then return 1 fi;
    if n=0 or k=0  then return 0 fi;

    if k=1 then return 1 fi;

    if n < 1/2*k*(k+1) then return 0 fi;

    1/k*add(add((-1)^(q-1)*Q(n-m, k-q), q in divisors(m)),
            m=1..n);
end;


A := n -> add(Q(n,k), k=1..floor(sqrt(2*n)));
AX := n -> add(QX(n,k), k=1..floor(sqrt(2*n)));

This will produce the following sequence for the number of partitions into any number of distinct parts:

$$1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 38, 46, \\ 54, 64, 76, 89, 104, 122, 142, 165, 192, 222, 256, 296,\ldots $$

which points us to OEIS A000009 where these data are confirmed. We get the following sequence for partitions into seven distinct parts starting at $n=-1 + 1/2\times 7\times 8 = 27:$

$$0, 1, 1, 2, 3, 5, 7, 11, 15, 21, 28, 38, 49, 65, 82, 105, 131, \\ 164, 201, 248, 300, 364, 436, 522, 618, 733, 860, 1009,\ldots$$

which points to OEIS A008636 which again confirms the data and lists additional references.

Addendum. Starting from the generating function (first principles) we extract coefficients for an efficient recurrence for strict partitions into any number of parts:

$$P(x) = \prod_{q\ge 1} (1+x^q)$$

Differentiatinng we get

$$P'(x) = P(x) \sum_{q\ge 1} \frac{qx^{q-1}}{1+x^q}$$

and on extracting coefficients we find

$$(n+1) P_{n+1} = \sum_{m=0}^n P_{n-m} [x^m] \sum_{q\ge 1} \frac{qx^{q-1}}{1+x^q} \\ = \sum_{m=0}^n P_{n-m} \sum_{q\ge 1} q [x^{m+1-q}] \frac{1}{1+x^q} \\ = \sum_{m=0}^n P_{n-m} \sum_{q=1}^{m+1} q [x^{m+1-q}] \frac{1}{1+x^q} \\ = \sum_{m=0}^n P_{n-m} \sum_{q=0}^{m} (q+1) [x^{m-q}] \frac{1}{1+x^{q+1}} \\ = \sum_{q=0}^n (q+1) \sum_{m=q}^{n} P_{n-m} [x^{m-q}] \frac{1}{1+x^{q+1}}.$$

This implies $m-q = p(q+1)$ with $p\ge 0$ and where $m\le n$ or $p(q+1)+q \le n$ so that $p\le \lfloor (n+1)/(q+1)\rfloor -1$ and we obtain

$$\sum_{q=0}^n (q+1) \sum_{p=0}^{\lfloor (n+1)/(q+1)\rfloor -1} P_{n-p(q+1)-q} [x^{p(q+1)}] \frac{1}{1+x^{q+1}} \\ = \sum_{q=0}^n (q+1) \sum_{p=0}^{\lfloor (n+1)/(q+1)\rfloor -1} P_{n-p(q+1)-q} (-1)^{p} \\ = \sum_{q=0}^n (q+1) \sum_{p=1}^{\lfloor (n+1)/(q+1)\rfloor} P_{n-(p-1)(q+1)-q} (-1)^{p+1} \\ = \sum_{q=0}^n (q+1) \sum_{p=1}^{\lfloor (n+1)/(q+1)\rfloor} P_{n+1-p(q+1)} (-1)^{p+1} \\ = \sum_{q=1}^{n+1} q \sum_{p=1}^{\lfloor (n+1)/q\rfloor} P_{n+1-pq} (-1)^{p+1}.$$

This is

$$\sum_{k=1}^{n+1} P_{n+1-k} \sum_{p|k} \frac{k}{p} (-1)^{p+1} = \sum_{k=1}^{n+1} P_{n+1-k} \sum_{p|k} p (-1)^{k/p+1}.$$

This finally yields a linear recurrence which is

$$\bbox[5px,border:2px solid #00A000]{ P_n = \frac{1}{n} \sum_{k=1}^{n} P_{n-k} \sum_{p|k} p (-1)^{k/p+1}}$$

where $P_0 = 1.$

Now for the inner sum its Dirichlet series is evidently given by

$$-\zeta(s-1) \sum_{n\ge 1} \frac{(-1)^n}{n^s} = -\zeta(s-1) \left(\frac{2}{2^s}-1\right)\zeta(s).$$

Multiplication by $\zeta(s)$ is summing over the divisors in terms of Dirichlet series so we need to examine the product of the first two terms. We get that for $n$ even the term $1/n^s$ appears twice, first paired with $-2\times n/2$ and second with $n$ for a contribution of zero. For $n$ odd the term appears just once paired with $n$, for a contribution of $n.$ Hence the inner sum is the sum of the odd divisors of $k$ and we get

$$\bbox[5px,border:2px solid #00A000]{ P_n = \frac{1}{n} \sum_{k=1}^{n} P_{n-k} \sum_{p|k\wedge p\;\text{odd}} p.}$$

$\endgroup$
  • $\begingroup$ Do you have an upper bound for $Q_{n, k}$? $\endgroup$ – Frank Vega Dec 31 '16 at 3:07
  • $\begingroup$ Good question. The OEIS entry has the asymptotics. $\endgroup$ – Marko Riedel Dec 31 '16 at 4:14
  • $\begingroup$ I found the asymptotics for the sum of the number of partitions of $n$ into at most $k$ parts in the OEIS entry. But, I need the asymptotics for the sum of the number of partitions of $n$ into exactly $k$ distinct parts. I post that question in: $\endgroup$ – Frank Vega Dec 31 '16 at 4:37
  • $\begingroup$ math.stackexchange.com/questions/2078090/… $\endgroup$ – Frank Vega Dec 31 '16 at 4:38
0
$\begingroup$

Number of integer partitions of a number n, denoted by p(n), is much harder to find and no easy formula available.

This wiki page gives various algorithms for finding p(n)

Approximate value for p(n) can be found using Hardy-Ramanujan Asymptotic Partition Formula $p(n) \approx \dfrac{1}{4n\sqrt{3}}e^\left(\pi \sqrt{\dfrac{2n}{3}}\right)$

This tool generates number of integer partitions online and is very useful

This link is also is related to this.

$\endgroup$
  • 1
    $\begingroup$ Is it not also required that a particular integer appear in the partition only once? $\endgroup$ – DJohnM Dec 31 '16 at 0:58
  • $\begingroup$ a particular integer can appear more than one time. for example, one of the integer partitions of $3$ can be $1,1,1$ $\endgroup$ – Kiran Dec 31 '16 at 1:06
  • $\begingroup$ Though interesting, this fails to answer the question, which specifically asks for each integer to appear at most once. $\endgroup$ – goblin Dec 31 '16 at 2:38
  • $\begingroup$ @goblin, i believe, the question was edited after I answered and when I answered, the word 'different' was not there. Not sure though and I cannot verify now. $\endgroup$ – Kiran Dec 31 '16 at 15:14
  • 1
    $\begingroup$ @Kiran, fair enough. Just one of the flaws in the website design, I suppose $\endgroup$ – goblin Jan 1 '17 at 2:16
0
$\begingroup$

As noted by Marko Riedel we can limit the analysis to $Q(n,k)$ = number of partitions of $n$ into $k$ distinct parts, where order is not important.
That is to say: Number of strictly increasing sequences, of $k$ terms, with sum = $n$, or
(changing parameters notation for better clearness) $$ \begin{gathered} Q(s,q) = \text{No}\text{.}\,\text{of}\,\text{sol}\text{.}\,\text{of}\left\{ \begin{gathered} 0 < x_{\,1} < x_{\,2} < \cdots < x_{\,\,q} \hfill \\ \sum\limits_{1 \leqslant \,j\, \leqslant \,q} {x_{\,j} = s} \hfill \\ \end{gathered} \right.\quad = \hfill \\ = \text{No}\text{.}\,\text{of}\,\text{sol}\text{.}\,\text{of}\left\{ \begin{gathered} 0 < y_{\,j} \left( { \leqslant s} \right)\quad \left| {\;1 \leqslant j \leqslant q} \right. \hfill \\ \sum\limits_{1 \leqslant \,j\, \leqslant \,q} {j\;y_{\,j} } = s \hfill \\ \end{gathered} \right.\quad = \hfill \\ = \text{No}\text{.}\,\text{of}\,\text{sol}\text{.}\,\text{of}\left\{ \begin{gathered} 0 \leqslant z_{\,j} \left( { < s} \right)\quad \left| {\;1 \leqslant j \leqslant q} \right. \hfill \\ \sum\limits_{1 \leqslant \,j\, \leqslant \,q} {j\;z_{\,j} } = s - \frac{{q\left( {q + 1} \right)}} {2} \hfill \\ \end{gathered} \right. \hfill \\ \end{gathered} \tag{1} $$ where the 2nd step comes from taking $y_{j}=x_{q-j+1}-x_{q-j} \; | \; x_0=0$.
We define Q to be non null only for positive value of the parameters, and to be $=1$ for the empty word $s=0,\;q=0$. $$ Q(s < 0,q) = 0\quad Q(s,q < 0) = 0\quad Q(0,q) = [q = 0] $$ (the square brackets indicating the Iverson Bracket)
so that it corresponds to the double generating function $$ G(x,y) = \sum\limits_{\begin{subarray}{l} 0 \leqslant \,q \\ 0 \leqslant \,s\, \end{subarray}} {Q(s,q)\;x^{\,s} \;y^{\,q} } = \prod\limits_{1 \leqslant \,k} {\left( {1 + y\,x^{\,k} } \right)} \tag{2} $$ From the second relation in (1) it is easy to deduce the recurrence $$ Q(s,\;q) = \sum\limits_{1 \leqslant \,j\,\,\left( {\, \leqslant \,\,\left\lfloor {s/q} \right\rfloor \,\, \leqslant \,\,s\,} \right)} {Q(s - q\,j,\;q - 1)} + \left[ {s = 0} \right]\left[ {q = 0} \right] \tag{3} $$

$\endgroup$

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.