Number of triple of sequences

Question

I was thinking about the following problem:

There is a set [n], and $l>0$. How many different triples $(s_1, s_2, s_3)$ there are with following properties:

1. $s_1, s_2$ and $s_3$ are sequences all with lenght $l$ over [n] such that at each position any number from [n] can be chosen (so, for $l = 4$, and n =4, $s_1 = 1,1,2,3 $ is one such sequence, some elements from [n] might be unselected).

2. considering $s_i, 1\leq i \leq 3 $ as the sets, no letters exist in common for all $s_i,$ i.e, $$\bigcap_{i=1}^3 s_i = \emptyset.$$

I solved the problem with $s_1$ and $s_2$ by using formula of inclusion-exclusion. I am wondering if there are som other principle of solving this problem with the number of three sequences and try to use it here the same, but I stucked in hard derivations.

Thanks for any help!

PS. I am also interesting in a general problem: when there are $m$ sequences. There are some principle of solving such things considering these problems as the table problems. If someone is familiar with literature (or some papers) which can be of help, please share me the info.

Answer 1

It would appear that inclusion-exclusion is the best approach here, with nodes $P\subseteq [n]$ of the poset being used representing configurations where the elements of $P$ are common to all $m$ sequences, plus possibly additional values from $[n]$. With $p=|P|$ we get

$$\sum_{p=0}^n {n\choose p} (-1)^p (l! [z^l] (\exp(z)-1)^p \exp(z)^{n-p})^m$$

Here we have used the labeled combinatorial class

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SEQ}_{=p}(\textsc{SET}_{\ge 1}(\mathcal{Z})) \textsc{SEQ}_{=n-p}(\textsc{SET}(\mathcal{Z}))$$

which also appeared at this MSE link, which is very similar to the present question.

For the inner term we find using basically the same computation

$$l!\times p!\times [z^l] \frac{(\exp(z)-1)^p}{p!} \exp(z)^{n-p} \\ = l!\times p!\times \sum_{q=0}^l [z^q] \frac{(\exp(z)-1)^p}{p!} [z^{l-q}] \exp(z)^{n-p} \\ = l!\times p!\times \sum_{q=p}^l [z^q] \frac{(\exp(z)-1)^p}{p!} [z^{l-q}] \exp(z)^{n-p} \\ = l!\times p!\times \sum_{q=p}^l \frac{1}{q!} {q\brace p} \frac{(n-p)^{l-q}}{(l-q)!}$$

We thus obtain the closed form

$$\bbox[5px,border:2px solid #00A000]{ \sum_{p=0}^n {n\choose p} (-1)^p \left(p! \sum_{q=p}^l {l\choose q} {q\brace p} (n-p)^{l-q}\right)^m.}$$

There is also some Maple code to consult where this formula may be verified by enumeration.

with(combinat);

ENUM :=
proc(n, l, m)
option remember;
local count, recurse;

    count := 0;

    recurse :=
    proc(sofar, mult, pos)
    local part, psize, vset, mset, multnxt;

        if pos > m then
            if `intersect`(op(sofar)) = {} then
                count := count + mult;
            fi;

            return;
        fi;

        part := firstpart(l);

        while type(part, `list`) do
            psize := nops(part);

            if n >= psize  then
                mset := convert(part, `multiset`);

                vset := firstcomb(n, psize);

                multnxt := mult*l!/mul(q!, q in part)
                *psize!/mul(q[2]!, q in mset);

                while type(vset, `set`) do
                    recurse([op(sofar), vset],
                            multnxt, pos+1);
                    vset := nextcomb(vset, n);
                od;
            fi;

            part := nextpart(part);
        od;
    end;


    recurse([], 1, 1);

    count;
end;


X := (n, l, m) ->
add(binomial(n,p)*(-1)^p
    *(p! * add(binomial(l, q) * stirling2(q, p)
               * (n-p)^(l-q), q=p..l))^m,
    p=0..n);