login
A353922
Number of distinct pairs of partially ordered sets and legal permutations on labeled directed acyclic graphs (DAGs) with n nodes.
1
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.
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
KEYWORD
nonn,more
AUTHOR
Adam A. Arfaoui, May 11 2022
STATUS
approved