A320583 - OEIS

%I #18 Oct 18 2018 08:59:21

%S 1,1,3,10,3,43,28,223,236,2,1364,1842,62,9643,18433,1015,2,77545,

%T 181568,14146,84,699954,1938199,189077,2093,2

%N Irregular triangle read by rows: T(n,k) is the number of connected permutation graphs on n vertices with domination number k, with 1 <= k <= floor(n/2).

%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,n/2) = 2 for even n. See Theorem 4.5 in the link by Theresa Baren, et al.

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

%F T(n,1) = A320578(n,1).

%e Triangle begins:

%e     1;

%e     1;

%e     3;

%e    10,   3;

%e    43,  28;

%e   223, 236,  2;

%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 countcnctdDomNumbersOnN(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)==True:

%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, A320579.

%K nonn,hard,tabf,more

%O 1,3

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