A320579 - OEIS

%I #21 Oct 18 2018 09:46:29

%S 1,2,1,7,3,1,26,18,4,1,115,111,27,5,1,592,771,186,37,6,1,3532,5906,

%T 1459,274,48,7,1,24212,49982,12643,2253,378,60,8,1,188869,466314,

%U 120252,20228,3230,499,73,9,1

%N Triangle read by rows: T(n,k) is the number of disconnected permutation graphs on n vertices with domination number k, with 2 <= k <= n.

%H Theresa Baren, Michael Cory, Mia Friedberg, Peter Gardner, James Hammer, Joshua Harrington, Daniel McGinnis, Riley Waechter, Tony W. H. Wong, <a href="https://arxiv.org/abs/1810.03409">On the Domination Number of Permutation Graphs and an Application to Strong Fixed Points</a>, arXiv:1810.03409 [math.CO], 2018.

%F T(n,k) = A320578(n,k) - A320583(n,k).

%e Triangle begins:

%e     1;

%e     2,   1;

%e     7,   3,   1;

%e    26,  18,   4,  1;

%e   115, 111,  27,  5,  1;

%e   592, 771, 186, 37,  6,  1;

%e   ...

%o (Python)

%o import networkx as nx

%o import math

%o def permutation(lst):

%o     if len(lst) == 0:

%o         return []

%o     if len(lst) == 1:

%o         return [lst]

%o     l = []

%o     for i in range(len(lst)):

%o         m = lst[i]

%o         remLst = lst[:i] + lst[i + 1:]

%o         for p in permutation(remLst):

%o             l.append([m] + p)

%o     return l

%o def generatePermsOfSizeN(n):

%o     lst = []

%o     for i in range(n):

%o         lst.append(i+1)

%o     return permutation(lst)

%o def powersetHelper(A):

%o     if A == []:

%o         return [[]]

%o     a = A[0]

%o     incomplete_pset = powersetHelper(A[1:])

%o     rest = []

%o     for set in incomplete_pset:

%o         rest.append([a] + set)

%o     return rest + incomplete_pset

%o def powerset(A):

%o     ps = powersetHelper(A)

%o     ps.sort(key = len)

%o     return ps

%o     print(ps)

%o def countdisDomNumbersOnN(n):

%o     lst=[]

%o     l=[]

%o     perms = generatePermsOfSizeN(n)

%o     for i in range(n):

%o         lst.append(i+1)

%o     ps = powerset(lst)

%o     dic={}

%o     for perm in perms:

%o         tempGraph = nx.Graph()

%o         tempGraph.add_nodes_from(perm)

%o         for i in range(len(perm)):

%o             for k in range(i+1, len(perm)):

%o                 if perm[k] < perm[i]:

%o                     tempGraph.add_edge(perm[i], perm[k])

%o         if nx.is_connected(tempGraph)==False:

%o             for p in ps:

%o                 if nx.is_dominating_set(tempGraph,p):

%o                     dom = len(p)

%o                     if dom in dic:

%o                         dic[dom] += 1

%o                         break

%o                     else:

%o                         dic[dom] = 1

%o                         break

%o     return dic

%Y CF. A320578, A320583.

%K nonn,tabl,hard,more

%O 2,2

%A _James Hammer_, _Daniel A. McGinnis_, Oct 15 2018