Counting Set Partitions with Constraints

Question

I'm trying to count set partitions under the following constraints:

• The number of partitions on $n$ elements where the largest cell(s) have exactly $k$ elements
• All cells have at least two elements

Starting here, I'm able to get the number of partitions where the maximum size cell size is exactly $k$ for values of $k \geq \lfloor n/2\rfloor$.

Then, for values of $k < \lfloor n/2 \rfloor$, I'm trying to add up Stirling numbers:

$$ \sum \limits_{i=\frac {n-k}{2}+1}^\frac {n}{k} {n \brace i} - f(n, i) $$

where $f(n, i)$ is some function that calculates the number of partitions of $n$ elements into $i$ cells that have at least one cell of size 1.

My thought on the upper limit is that, if you divide up a set into $\frac {n} k$ cells and get rid of anything with size 1, then all cells have to be size $k$ (plus one additional cell for any remainder). Similarly, the low end is where you have one (or two) cells of size $k$ and the rest of them are size $2$.

Where I'm really stuck is getting rid of the partitions that have cells of size $1$. I think I'm headed in the right direction with the approach described above, but any help is appreciated.

Answer 1

Let $B^{\gamma,\mu }_n$ represent the number of partitions where cells have atleast $\gamma$ elements and the size of the largest cell is exactly $\mu$. So the answer to your question would be $B^{2,k}_n$.

Choose an arbitrary element $v$ from the set. Suppose $v$ is in a cell of size $k$ where $\gamma \leq k < \mu$. First we specify $v$'s cell in $n-1 \choose k-1$ ways. Then we partition the remaining elements in $B^{\gamma,\mu}_{n-k}$ ways. Thus we have

$$ \sum_{k=\gamma}^{\mu-1} {n-1 \choose k-1} \, B^{\gamma,\mu}_{n-k} $$

partitions. Now we have to be careful when $k=\mu$. Since $v$'s cell has $\mu$ elements, we do not need to satisfy the first constraint when we partition the remaining elements. Therefore, they can be partitioned in $B^{\gamma,\gamma}_{n-\mu} + B^{\gamma,\gamma+1}_{n-\mu} + \ ... + \, B^{\gamma,\mu}_{n-\mu}$ ways. So our final recurrence is:

$$ B^{\gamma,\mu}_{n} = \sum_{k=\gamma}^{\mu-1} {n-1 \choose k-1} \, B^{\gamma,\mu}_{n-k} + \sum_{j=\gamma}^\mu {n-1 \choose \mu-1} \, B^{\gamma,j}_{n-\mu} $$

With base cases

$$ B^{\gamma,\mu}_{n} = \left\{ \begin{array}{ll} 0 & : \;\;\; n<\mu \\ 1 & : \;\;\; n = \mu \\ \end{array} \right. $$

Answer 2

I believe that it is quite instructive to examine this problem using generating functions and combinatorial classes as presented in Analytic Combinatorics by Flajolet and Sedgewick.

Using the notation from the accepted answer we have for partitions of cell size at least $\gamma$ and the maximum element exactly $\mu$ the combinatorial class

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SET}(\textsc{SET}_{=\gamma}(\mathcal{Z})) \times \textsc{SET}(\textsc{SET}_{=\gamma+1}(\mathcal{Z})) \times \textsc{SET}(\textsc{SET}_{=\gamma+2}(\mathcal{Z})) \\ \times \textsc{SET}(\textsc{SET}_{=\gamma+3}(\mathcal{Z})) \times \cdots \times \textsc{SET}(\textsc{SET}_{=\mu-1}(\mathcal{Z})) \times \textsc{SET}_{\ge 1}(\textsc{SET}_{=\mu}(\mathcal{Z})).$$

This immediately produces the generating function which is $$G(z) = \left(\exp\left(\frac{z^\mu}{\mu!}\right)-1\right) \prod_{q=\gamma}^{\mu-1} \exp\left(\frac{z^q}{q!}\right).$$

This is (here we recognize the class $\textsc{SET}( \textsc{SET}_{\gamma\le\cdot\le\mu-1}(\mathcal{Z}))$)

$$G(z) = \left(\exp\left(\frac{z^\mu}{\mu!}\right)-1\right) \exp\left(\sum_{q=\gamma}^{\mu-1} \frac{z^q}{q!}\right).$$

We can extract an closed formula from this, getting $$n! [z^n] G(z) = n! \sum_{k=1}^{\lfloor n/\mu \rfloor} \frac{1}{(\mu!)^k k!} [z^{n-k\mu}] \exp\left(\sum_{q=\gamma}^{\mu-1} \frac{z^q}{q!}\right).$$

Now let $\lambda\vdash_\gamma^{\mu-1} (n-k\mu)$ be a partition of $n-k\mu$ with parts at least $\gamma$ and at most $\mu-1$ and let the multiplicities of $\lambda$ be denoted by $1^{f_1} 2^{f_2} 3^{f_3} \ldots$ to obtain

$$n! \sum_{k=1}^{\lfloor n/\mu \rfloor} \frac{1}{(\mu!)^k k!} \sum_{\lambda\vdash_\gamma^{\mu-1} (n-k\mu)} \prod_{q=\gamma}^{\mu-1} \frac{1}{(q!)^{f_q} (f_q)!}.$$

Observe that this formula produces the same values as the recurrence from the accepted answer, as can be verified using the following Maple code:

with(combinat);

B :=
proc(g, m, n)
    option remember;

    if n < m then return 0 fi;
    if n = m then return 1 fi;

    add(binomial(n-1,k-1)*B(g, m, n-k), k=g..m-1)
    + add(binomial(n-1, m-1)*B(g, j, n-m), j=g..m);
end;

G :=
proc(g, m, n)
    option remember;
    local gf;

    gf := (exp(z^m/m!)-1)
    *exp(add(z^q/q!, q=g..m-1));

    n!*coeftayl(gf, z=0, n);
end;

Q :=
proc(g, m, n)
    option remember;
    local p, k, res, interm, f;

    res := 0;

    for k to floor(n/m) do
        interm := 0;

        p := firstpart(n-m*k);
        while type(p, list) do
            if min(p) >= g and max(p) <= m-1 then
                f := convert(p, 'multiset');
                interm := interm +
                1/mul((ff[1]!)^ff[2]*ff[2]!, ff in f);
            fi;

            p := nextpart(p);
        od;

        res := res + interm/(m!)^k/k!;
    od;

    n!*res;
end;