The number of the partition of the set $A$ into $k$ bounded blocks.

Question

Let $A=\{1,2,\cdots,n\}$ be a set. We want to partitions of this set into $k$ non-empty unlabelled subsets $B_1,B_2,\cdots ,B_k$ such that cardinality of each $B_i$ between positive integers $a$ and $b$, that means $a\leq |B_i|\leq b$.

Let $D_{a,b}(n,k)$ be the number of partitions of the set $A$ into $k$ non-empty unlabelled subsets $B_1,B_2,\cdots ,B_k$ which $a\leq |B_i|\leq b$.

How can calculate the number of such partitions?

I try obtained the recurrence relation for $D_{a,b}(n,k)$ with the definition of Stirling numbers of the second kind but I couldn't.

Very thanks for any help and comment.

Answer 1

Additional answer in response to new query by OP asking for the same statistic for a multiset on $n$ different elements with multiplicity $r$ of the first element. Call this $E_{a,b,r}(n,k).$

As observed by OP in a personal communication we can get a simple closed form if the restriction on the multisets having at least $a$ and at most $b$ elements is lifted. With $p_k(n)$ counting partitions and $c_k(n)$ counting weak compositons we get from first principles on classifying by the number $m$ of instances of the element with multiplicity $r$ that are in a set by themselves

$$\sum_{m=0}^{r} \sum_{m_1=0}^{k-1} p_{m_1}(m) {n-1\brace k-m_1} c_{k-m_1}(r-m).$$

Here we use the convention that $p_0(0) = 1.$ Now the number of weak compositions is given by

$$c_k(n) = [z^n] \prod_{m=1}^k \frac{1}{1-z} = [z^n] \frac{1}{(1-z)^k} = {n+k-1\choose k-1}$$

and we obtain

$$\sum_{m=0}^{r} \sum_{m_1=0}^{k-1} p_{m_1}(m) {n-1\brace k-m_1} {k+r-m-m_1-1\choose k-m_1-1}.$$

Completed answer. We can actually give a closed from even for $[a,b]$ not being set to the simple $[1,n].$ Introduce $p_{k, a, b}(n)$ counting the number of partitions of $n$ into $k$ parts from the range $a$ to $b.$ This is easily computed using $p_{k,b}(n)$ the partitions with parts of size at most $b$, which has a simple recurrence, and we then have $p_{k,a,b}(n) = p_{k, b - a + 1}(n - (a - 1) k).$

Furthermore introduce the marked generating function

$$F_{k, b}(z) = \frac{1}{k!} \left(\sum_{q=1}^b B_q \frac{z^q}{q!}\right)^k.$$

Let the evaluation rule $B_q^*$ be given by

$$B_q = [[a\le q\le b]] \times (1+w+w^2+\cdots+w^{b-q}) \\ + [[1\le q\lt a]] \times (w^{a-q}+\cdots+w^{b-q}) \\ = w^{\max(a-q, 0)}+\cdots+w^{b-q}.$$

We have a mixed generating function with $z^q/q!$ counting a set drawn from the $n-1$ distinguishable values and $w^p$ giving the number of copies of the element with multiplicity $r$ attached to this set. This yields the closed form

$${\large (n-1)! \sum_{m=0}^{r} \sum_{m_1=0}^{k-1} p_{m_1,a,b}(m) [z^{n-1}] [w^{r-m}] \left. F_{k-m_1, b}(z) \right|_{B_q^*}.}$$

The above formula is implemented below and produces useable results where enumeration does not succeed. An alternate version proceeds from the observation that

$$F_{k,b}(z) = \frac{1}{k} \left(\sum_{q=1}^b B_q \frac{z^q}{q!}\right) F_{k-1,b}(z).$$

This gives a simple recurrence in four variables for the coefficient $[z^\alpha] [w^\beta] F_{k,b}(z)$ that may be memoized and which has also been implemented below. Study indicates that this method is the fastest yet.

with(combinat);

paux :=
proc(n, k, b)
option remember;
    if n = 0 and k = 0 then return 1 fi;
    if n <= 0 or k <= 0 or n < k then return 0 fi;

    if b = 0  then return 0 fi;

    if n = k then return 1 fi;
    if k = 1 then
        if n <= b then
            return 1
        else
            return 0;
        fi;
    fi;

    paux(n-1, k-1, b) + paux(n-k, k, b-1)
end;

p := (n, k, a, b) -> paux(n-(a-1)*k, k, b-a+1);

F := (k, b) -> 1/k!*add(B[q]*z^q/q!, q=1..b)^k;


EX :=
proc(n, k, a, b, r)
option remember;
local curF, m, m1, res, Bsubs;

    if n = 1 then
        return p(r, k, a, b);
    fi;

    Bsubs :=
    [seq(B[q]=add(w^l, l=max(a-q, 0)..b-q), q=1..b)];

    res := 0;

    for m1 from 0 to k-1 do
        curF := coeftayl(subs(Bsubs,  F(k-m1, b)),
                         z=0, n-1);

        for m from 0 to r do
            res := res +
            (n-1)!*p(m, m1, a, b)*
            coeff(curF, w, r-m);
        od;
    od;

    res;
end;

T := (n,k,r) -> EX(n, k, 1, n+r-1, r);

TABLEDATA :=
(mx, r) -> seq(seq(T(n, k, r), k=1..n+r-1), n=1..mx);

FCF :=
proc(alpha, beta, k, a, b)
option remember;
local res, q;

    if alpha < 1 or beta < 0 then return 0 fi;

    if k = 1 then
        if max(a-alpha, 0) <= beta and
        beta <= b-alpha then
            return 1/alpha!
        fi;
        return 0;
    fi;

    res := 0;

    for q to a-1 do
        res := res +
        add(`if`(alpha-q>0 and beta-qq>=0,
                 FCF(alpha-q, beta-qq, k-1, a, b), 0),
            qq=a-q..b-q)/k/q!;
    od;

    for q from a to b do
        res := res +
        add(`if`(alpha-q>0 and beta-qq>=0,
                 FCF(alpha-q, beta-qq, k-1, a, b), 0),
            qq=0..b-q)/k/q!;
    od;

    res;
end;

EX2 :=
(n, k, a, b, r) ->
`if`(n=1, p(r,k,a,b),
     (n-1)!*add(add(p(m, m1, a, b)*FCF(n-1, r-m, k-m1, a, b),
                    m1=0..k-1), m=0..r));

ST2 := (n, k) ->  EX2(n, k, 1, n, 1);

EX1N := (n, k, r) ->
add(add(p(m,m1,1,r)*stirling2(n-1,k-m1)
        *binomial(k+r-m-m1-1, k-m1-1), m1=0..k-1),
    m=0..r);

T2 := (n,k,r) -> EX2(n, k, 1, n+r-1, r);

TABLEDATA2 :=
(mx, r) -> seq(seq(T2(n, k, r), k=1..n+r-1), n=1..mx);

VERIF :=
proc(mx, r)
local lA, lB;

    lA := [TABLEDATA(mx, r)];
    lB := [TABLEDATA2(mx, r)];

    {seq(lA[p]-lB[p], p=1..nops(lA))};
end;

Answer 2

Supposing that we are trying to generalize Stirling numbers here we get the combinatorial class

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SET}_{=k}(\textsc{SET}_{a\le\cdot\le b}(\mathcal{Z}))$$

which yields the generating function

$$G(z) = \frac{1}{k!} \left(\sum_{q=a}^b \frac{z^q}{q!}\right)^k.$$

Differentiate to obtain

$$G'(z) = \frac{1}{(k-1)!} \left(\sum_{q=a}^b \frac{z^q}{q!}\right)^{k-1} \sum_{p=a-1}^{b-1} \frac{z^p}{p!}.$$

Extracting coefficients we find

$$D_{a,b}(n+1,k) = n! [z^n] \sum_{p=a-1}^{b-1} \frac{z^p}{p!} \frac{1}{(k-1)!} \left(\sum_{q=a}^b \frac{z^q}{q!}\right)^{k-1} \\ = n! \sum_{p=a-1}^{b-1} \frac{1}{p!} [z^{n-p}] \frac{1}{(k-1)!} \left(\sum_{q=a}^b \frac{z^q}{q!}\right)^{k-1} \\ = n! \sum_{p=a-1}^{b-1} \frac{1}{p!} \frac{1}{(n-p)!} D_{a,b}(n-p, k-1) \\ = \sum_{p=a-1}^{b-1} {n\choose p} D_{a,b}(n-p, k-1).$$

The base cases here are $D_{a,b}(n, k) = 0$ if $n\lt 1$ or $k=0$ and $D_{a,b}(n, 1) = [[a\le n\le b]]$ where we have used an Iverson bracket.

These were verified using enumeration, coefficient extraction from $G(z)$, and the recurrence. We also checked that $D_{1,n}(n,k)$ does indeed produce Stirling numbers. (Use the standard recurrence which exploits differentiation in a different way if you need regular Stirling numbers only.) This was the code.

with(combinat);

ENUM :=
proc(n, k, a, b)
local res, part, mset, inrange, psize;

    res := 0;

    part := firstpart(n);

    while type(part, list) do
        inrange := select(p -> a <= p and p <= b, part);
        psize := nops(part);

        if nops(inrange) = psize and k = psize then
            mset := convert(part, `multiset`);
            res := res +
            n!/mul(p!, p in part)
            /mul(q[2]!, q in mset);
        fi;

        part := nextpart(part);
    od;


    res;
end;

GCF := (n, k, a, b)
-> n!*coeftayl(add(z^q/q!, q=a..b)^k/k!, z=0, n);

DX :=
proc(n, k, a, b)
option remember;

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

    add(binomial(n-1, p)*DX(n-1-p, k-1, a, b), p=a-1..b-1);
end;

ST2 := (n, k) -> DX(n, k, 1, n);

Remark. These data are available at the OEIS, consult e.g. sequences A059022, A059023, A059024, and A059025.