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

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.

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) ->
*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;


• Very interesting, thank you very much, Marko. But I still a few confusing for your the answer!!What is the $A_1^r$ and $A_2,..$? The interval$[a,b]$ manes blocks with elements between a and b?Moreover, with your result, I think it is not the hard extent of this problem for cases $A$ and block mixed(multi-set), $A$ be a set and block mixed,... Also, I rarely confused for obtained you OPG!!HOw calculated? May you introduce a good reference about it for study? – d.y Aug 18 '17 at 7:50
• In your Completed answer the $\rho_{k, a,b}(n)$ means the number of partitions of positive integer $n$ into $k$ parts which each parts are between $a$ and $b$? – d.y Oct 5 '17 at 22:22
• That is correct. Thanks for pointing it out, the partition function at the last paragraph does not have $k$ in the subscript. The meaning should be clear. – Marko Riedel Oct 5 '17 at 22:49

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.

• @ Marko Riedel, Thank you.I am a bit confused to calculate generation function. How did you calculate it? What is the means of $$\mathfrak{P}_{=k}(\mathfrak{P}_{a\le\cdot\le b}(\mathcal{Z}))$$? – d.y Aug 9 '17 at 15:33
• There is this documentation at Wikipedia. – Marko Riedel Aug 9 '17 at 16:50
• I would like to extend this problem for Mixed partitions. Consider $A=\{1,\cdots,1,2,\cdots,n\}$ be a multiset which multiplicity of one is r. Is it possible use of this generation function for this case? – d.y Aug 11 '17 at 11:33