|
%I #27 Jul 07 2022 02:26:39
%S 1,1,4,48,1368,76560,7163280
%N Number of distinct pairs of partially ordered sets and legal permutations on labeled directed acyclic graphs (DAGs) with n nodes.
%C 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.
%e For n = 2 the a(2) = 4 solutions are
%e (~) -> {1,2}|{2,1} = 2! = 2
%e (1<2) -> {1,2} = 1
%e (2<1) -> {2,1} = 1
%e (1<2,2<1) -> not DAG = 0
%e a(2) = 2 + 1 + 1 + 0 = 4.
%e For n = 3 the a(3) = 48 solutions are
%e (~) -> {1,2,3}|{1,3,2}|{2,1,3}|{2,3,1}|{3,1,2}|{3,2,1} = 3! = 6
%e (1<2) -> {1,2,3}|{1,3,2}|{3,1,2} = 3
%e (1<3) -> {1,2,3}|{1,3,2}|{2,1,3} = 3
%e (2<3) -> {1,2,3}|{2,1,3}|{2,3,1} = 3
%e (2<1) -> {2,1,3}|{2,3,1}|{3,2,1} = 3
%e (3<1) -> {2,3,1}|{3,1,2}|{3,2,1} = 3
%e (3<2) -> {1,3,2}|{3,1,2}|{3,2,1} = 3
%e (1<2, 1<3) -> {1,2,3}|{1,3,2} = 2
%e (1<2, 2<3) -> {1,2,3} = 1
%e (1<2, 2<1) -> not DAG = 0
%e (1<2, 3<1) -> {3,1,2} = 1
%e (1<2, 3<2) -> {1,3,2}|{3,1,2} = 2
%e (1<3, 2<3) -> {1,2,3}|{2,1,3} = 2
%e (1<3, 2<1) -> {2,1,3} = 1
%e (1<3, 3<1) -> not DAG = 0
%e (1<3, 3<2) -> {1,3,2} = 1
%e (2<3, 2<1) -> {2,1,3}|{2,3,1} = 2
%e (2<3, 3<1) -> {2,3,1} = 1
%e (2<3, 3<2) -> not DAG = 0
%e (2<1, 3<1) -> {2,3,1}|{3,2,1} = 2
%e (2<1, 3<2) -> {3,2,1} = 1
%e (3<1, 3<2) -> {3,1,2}|{3,2,1} = 2
%e (1<2, 1<3, 2<3) -> {1,2,3} = 1
%e (1<2, 1<3, 2<1) -> not DAG = 0
%e (1<2, 1<3, 3<1) -> not DAG = 0
%e (1<2, 1<3, 3<2) -> {1,3,2} = 1
%e (1<2, 2<3, 2<1) -> not DAG = 0
%e (1<2, 2<3, 3<1) -> not DAG = 0
%e (1<2, 2<3, 3<2) -> not DAG = 0
%e (1<2, 2<1, 3<1) -> not DAG = 0
%e (1<2, 2<1, 3<2) -> not DAG = 0
%e (1<2, 3<1, 3<2) -> {3,1,2} = 1
%e (1<3, 2<3, 2<1) -> {2,1,3} = 1
%e (1<3, 2<3, 3<1) -> not DAG = 0
%e (1<3, 2<3, 3<2) -> not DAG = 0
%e (1<3, 2<1, 3<1) -> not DAG = 0
%e (1<3, 2<1, 3<2) -> not DAG = 0
%e (1<3, 3<1, 3<2) -> not DAG = 0
%e (2<3, 2<1, 3<1) -> {2,3,1} = 1
%e (2<3, 2<1, 3<2) -> not DAG = 0
%e (2<3, 3<1, 3<2) -> not DAG = 0
%e (2<1, 3<1, 3<2) -> {3,2,1} = 1
%e 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
%o (MATLAB)
%o function a = A353922(n)
%o NPosets = n*(n-1);
%o AllPosets = [nchoosek(1:n,2); flip(nchoosek(1:n,2),2)];
%o store = uint32(zeros(2^(n*(n-1)/2)*factorial(n),1));
%o store(1) = factorial(n);
%o iter = 2;
%o for i = 1:n
%o choices = nchoosek(1:NPosets,i);
%o for j = 1:size(choices,1)
%o Poset = uint32(AllPosets(choices(j,:),:));
%o G = digraph(Poset(:,1),Poset(:,2));
%o if ~isdag(G)
%o continue
%o end
%o Available = 1:n;
%o Sequence = uint32(zeros(1,n));
%o Candidates = setdiff(Available,Poset(:,2));
%o Out = FindAllEnds(Available,Candidates,Poset,0,Sequence);
%o store(iter) = size(Out,1);
%o iter = iter+1;
%o end
%o end
%o store(iter:end) = [];
%o a = sum(store(:));
%o end
%o function Out = FindAllEnds(Available,Candidates,Poset,iter,Sequence)
%o iter = iter+1;
%o Out = [];
%o if ~isempty(Available)
%o for i = 1:length(Candidates)
%o S = Candidates(i);
%o A = setdiff(Available,S);
%o P = Poset(Poset(:,1)~=S,:);
%o C = setdiff(A,P(:,2));
%o Seq = Sequence;
%o Seq(iter) = S;
%o O = FindAllEnds(A,C,P,iter,Seq);
%o Out = [Out; O];
%o end
%o else
%o Out = Sequence;
%o end
%o end
%K nonn,more
%O 0,3
%A _Adam A. Arfaoui_, May 11 2022
|
