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.
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
KEYWORD
nonn,more
AUTHOR
Adam A. Arfaoui, May 11 2022
STATUS
approved