2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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;

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – d.y Aug 18 '17 at 7:50
  • $\begingroup$ 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$? $\endgroup$ – d.y Oct 5 '17 at 22:22
  • $\begingroup$ 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. $\endgroup$ – Marko Riedel Oct 5 '17 at 22:49
2
$\begingroup$

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

$$\mathfrak{P}_{=k}(\mathfrak{P}_{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.

$\endgroup$
  • $\begingroup$ @ 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}))$$? $\endgroup$ – d.y Aug 9 '17 at 15:33
  • $\begingroup$ There is this documentation at Wikipedia. $\endgroup$ – Marko Riedel Aug 9 '17 at 16:50
  • $\begingroup$ 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? $\endgroup$ – d.y Aug 11 '17 at 11:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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