Counting Set Partitions with Constraints 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.
 A: 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.
$$
A: 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;

