0
$\begingroup$

I know that there is a formula where even 0 is treated as significant, but is there a formula where 1 and 0 cannot be parts?

Edit:The formula that I was referencing was (Excuse the presentation) $\frac{(n-1)!}{(k-1)!(n-k)!}$ This one discards the 0, but what I was looking for one that would discard 1 as well. Also, what I'm looking for is the compositions, not the partitions.

$\endgroup$
5
  • $\begingroup$ It sounds as though you're asking for the number of partitions of an $n$-element set into $k$ parts where each part has $2$ or more elements. Seems that the answer should be $a_n$ where $\sum_{n \geq 0} a_n \frac{x^n}{n!} = \frac{(e^x - 1 - x)^k}{k!}$, whence it's just a matter of working that out. $\endgroup$
    – Todd Trimble
    Oct 7, 2018 at 1:04
  • 1
    $\begingroup$ @bof Typo: you meant “$k$ nonnegative parts”, not $2k$. $\endgroup$ Oct 7, 2018 at 7:48
  • 3
    $\begingroup$ Calculating the number of ways to split $n-2k$ into $k$ non-negative parts can be done by a standard “stars and bars” argument, giving the result obtained below: $\binom{n-k-1}{k-1}$. $\endgroup$ Oct 7, 2018 at 8:03
  • $\begingroup$ @JeremyRickard Yes, of course. thanks. $\endgroup$
    – bof
    Oct 7, 2018 at 10:34
  • 2
    $\begingroup$ The number of compositions of $n$ into $k$ parts with each part $\ge2$ is the same as the number of compositions of $n-k$ into $k$ positive parts, or the number of compositions of $n-2k$ into $k$ nonnegative parts. $\endgroup$
    – bof
    Oct 7, 2018 at 10:38

1 Answer 1

1
$\begingroup$

Here how to obtain the generating function:

Give a compsotion of $n$ with $k$ summands the weight $x^n y^k$. The compositions of $n$ into $k$ parts with terms $\geq 2$ are then obtained as $Sequ(\mathbb{N}_{\geq 2})$, see for example 2.2.1. of https://arxiv.org/pdf/1409.2562.pdf. Thus the generating function is $\frac{1}{1-(x^2y+x^3y+....)}=\frac{1-x}{(1-x)-yx^2}$.

Now you can get a formula by expanding the function $\frac{1-x}{(1-x)-yx^2}$.

$\frac{1-x}{(1-(x+yx^2)}=(1-x) \sum\limits_{k=0}^{\infty}{(x+yx^2)^k}=(1-x) \sum\limits_{k=0}^{\infty}(x^k \sum\limits_{l=0}^{k} \binom{k}{l} (yx)^l)$. From this one should be able to order the terms together for the form $y^s x^t$ to arrive at the result $\binom{n-k-1}{k-1}$ as in the comment.

$\endgroup$
1
  • 1
    $\begingroup$ $\dots$ which is $\binom{n-k-1}{k-1}$. $\endgroup$ Oct 7, 2018 at 3:30

Not the answer you're looking for? Browse other questions tagged or ask your own question.