A353922 Number of distinct pairs of partially ordered sets and legal permutations on labeled directed acyclic graphs (DAGs) with n nodes.

1, 1, 4, 48, 1368, 76560, 7163280

Offset

0,3

Comments

The number of labeled DAGs with n nodes is given by A003024. For each distinct DAG, the direction of all edges may be viewed as a partial ordering (poset) on the set of 1:n nodes. Considering only those posets which are acyclic gives rise to forbidden sequences on the set of n! possible permutations. Conversely, legal sequences exist which conform to the partial ordering. A353922 is the total number of legal sequences that traverse all nodes exactly once on each labeled DAG of degree n.

Links

Table of n, a(n) for n=0..6.

Example

For n = 2 the a(2) = 4 solutions are
(~) -> {1,2}|{2,1} = 2! = 2
(1<2) -> {1,2} = 1
(2<1) -> {2,1} = 1
(1<2,2<1) -> not DAG = 0
a(2) = 2 + 1 + 1 + 0 = 4.
For n = 3 the a(3) = 48 solutions are
(~) -> {1,2,3}|{1,3,2}|{2,1,3}|{2,3,1}|{3,1,2}|{3,2,1} = 3! = 6
(1<2) -> {1,2,3}|{1,3,2}|{3,1,2} = 3
(1<3) -> {1,2,3}|{1,3,2}|{2,1,3} = 3
(2<3) -> {1,2,3}|{2,1,3}|{2,3,1} = 3
(2<1) -> {2,1,3}|{2,3,1}|{3,2,1}  = 3
(3<1) -> {2,3,1}|{3,1,2}|{3,2,1}  = 3
(3<2) -> {1,3,2}|{3,1,2}|{3,2,1}  = 3
(1<2, 1<3) -> {1,2,3}|{1,3,2} = 2
(1<2, 2<3) -> {1,2,3} = 1
(1<2, 2<1) ->  not DAG = 0
(1<2, 3<1) -> {3,1,2} = 1
(1<2, 3<2) -> {1,3,2}|{3,1,2} = 2
(1<3, 2<3) -> {1,2,3}|{2,1,3} = 2
(1<3, 2<1) -> {2,1,3} = 1
(1<3, 3<1) -> not DAG = 0
(1<3, 3<2) -> {1,3,2} = 1
(2<3, 2<1) -> {2,1,3}|{2,3,1} = 2
(2<3, 3<1) -> {2,3,1} = 1
(2<3, 3<2) -> not DAG = 0
(2<1, 3<1) -> {2,3,1}|{3,2,1} = 2
(2<1, 3<2) -> {3,2,1} = 1
(3<1, 3<2) -> {3,1,2}|{3,2,1} = 2
(1<2, 1<3, 2<3) -> {1,2,3} = 1
(1<2, 1<3, 2<1) -> not DAG = 0
(1<2, 1<3, 3<1) -> not DAG = 0
(1<2, 1<3, 3<2) -> {1,3,2} = 1
(1<2, 2<3, 2<1) -> not DAG = 0
(1<2, 2<3, 3<1) -> not DAG = 0
(1<2, 2<3, 3<2) -> not DAG = 0
(1<2, 2<1, 3<1) -> not DAG = 0
(1<2, 2<1, 3<2) -> not DAG = 0
(1<2, 3<1, 3<2) -> {3,1,2} = 1
(1<3, 2<3, 2<1) -> {2,1,3} = 1
(1<3, 2<3, 3<1) -> not DAG = 0
(1<3, 2<3, 3<2) -> not DAG = 0
(1<3, 2<1, 3<1) -> not DAG = 0
(1<3, 2<1, 3<2) -> not DAG = 0
(1<3, 3<1, 3<2) -> not DAG = 0
(2<3, 2<1, 3<1) -> {2,3,1} = 1
(2<3, 2<1, 3<2) -> not DAG = 0
(2<3, 3<1, 3<2) -> not DAG = 0
(2<1, 3<1, 3<2) -> {3,2,1} = 1
a(3) = 6+3+3+3+3+3+3+2+1+0+1+2+2+1+0+1+2+1+0+2+1+2+1+0+0+1+0+0+0+0+0+1+1+0+0+0+0+0+1+0+0+1 = 48

Prog

(MATLAB)
function a = A353922(n)
NPosets = n*(n-1);
AllPosets = [nchoosek(1:n, 2); flip(nchoosek(1:n, 2), 2)];
store = uint32(zeros(2^(n*(n-1)/2)*factorial(n), 1));
store(1) = factorial(n);
iter = 2;
for i = 1:n
    choices = nchoosek(1:NPosets, i);
    for j = 1:size(choices, 1)
        Poset = uint32(AllPosets(choices(j, :), :));
        G = digraph(Poset(:, 1), Poset(:, 2));
        if ~isdag(G)
            continue
        end
        Available = 1:n;
        Sequence = uint32(zeros(1, n));
        Candidates = setdiff(Available, Poset(:, 2));
        Out = FindAllEnds(Available, Candidates, Poset, 0, Sequence);
        store(iter) = size(Out, 1);
        iter = iter+1;
    end
end
store(iter:end) = [];
a = sum(store(:));
end
function Out = FindAllEnds(Available, Candidates, Poset, iter, Sequence)
iter = iter+1;
Out = [];
if ~isempty(Available)
    for i = 1:length(Candidates)
        S = Candidates(i);
        A = setdiff(Available, S);
        P = Poset(Poset(:, 1)~=S, :);
        C = setdiff(A, P(:, 2));
        Seq = Sequence;
        Seq(iter) = S;
        O = FindAllEnds(A, C, P, iter, Seq);
        Out = [Out; O];
    end
else
    Out = Sequence;
end
end

Crossrefs

Sequence in context: A191952 A013145 A013150 * A332865 A346949 A011266

Adjacent sequences: A353919 A353920 A353921 * A353923 A353924 A353925

Keyword

nonn,more

Author

Adam A. Arfaoui, May 11 2022

Status

approved