A328682 Array read by antidiagonals: T(n,r) is the number of connected r-regular loopless multigraphs on n unlabeled nodes.

1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 2, 1, 0, 0, 1, 0, 1, 0, 3, 0, 1, 0, 0, 1, 0, 1, 1, 4, 6, 6, 1, 0, 0, 1, 0, 1, 0, 6, 0, 19, 0, 1, 0, 0, 1, 0, 1, 1, 7, 15, 49, 50, 20, 1, 0, 0, 1, 0, 1, 0, 9, 0, 120, 0, 204, 0, 1, 0, 0, 1, 0, 1, 1, 11, 36, 263, 933, 1689, 832, 91, 1, 0, 0, 1, 0, 1, 0, 13, 0, 571, 0, 13303, 0, 4330, 0, 1, 0, 0, 1, 0, 1, 1, 15, 72, 1149, 12465, 90614, 252207, 187392, 25227, 509, 1, 0, 0

Offset

0,33

Comments

Initial terms computed using 'Nauty and Traces' (see the link).

T(0,r) = 1 because the "nodeless" graph has zero (therefore in this case all) nodes of degree r (for any r).

T(1,0) = 1 because only the empty graph on one node is 0-regular on 1 node.

T(1,r) = 0, for r>0: there's only one node and loops aren't allowed.

T(2,r) = 1, for r>0 since the only edges that are allowed are between the only two nodes.

T(3,r) = parity of r, for r>0. There are no such graphs of odd degree and for an even degree the only multigraph satisfying that condition is the regular triangular multigraph.

T(n,0) = 0, for n>1 because graphs having more than a node of degree zero are disconnected.

T(n,1) = 0, for n>2 since any connected graph with more than two nodes must have a node of degree greater than two.

T(n,2) = 1, for n>1: the only graphs satisfying that condition are the cyclic graphs of order n.

This sequence may be derived from A333330 by inverse Euler transform. - Andrew Howroyd, Mar 15 2020

Links

Andrew Howroyd, Table of n, a(n) for n = 0..350

Brendan McKay and Adolfo Piperno, Nauty and Traces

Formula

Column r is the inverse Euler transform of column r of A333330. - Andrew Howroyd, Mar 15 2020

Example

Square matrix T(n,r) begins:
========================================================
n\r | 0     1     2     3     4     5      6      7
----+---------------------------------------------------
  0 | 1,    1,    1,    1,    1,    1,     1,     1, ...
  1 | 1,    0,    0,    0,    0,    0,     0,     0, ...
  2 | 0,    1,    1,    1,    1,    1,     1,     1, ...
  3 | 0,    0,    1,    0,    1,    0,     1,     0, ...
  4 | 0,    0,    1,    2,    3,    4,     6,     7, ...
  5 | 0,    0,    1,    0,    6,    0,    15,     0, ...
  6 | 0,    0,    1,    6,   19,   49,   120,   263, ...
  7 | 0,    0,    1,    0,   50,    0,   933,     0, ...
  8 | 0,    0,    1,   20,  204, 1689, 13303, 90614, ...
  ...

Prog

# This program will execute the "else echo" line if the graph is nontrivial (first three columns, first two rows or both row and column indices are odd)
(nauty/shell)
for ((i=0; i<16; i++)); do
n=0
r=${i}
while ((n<=i)); do
if( (((r==0)) && ((n==0)) ) || ( ((r==0)) && ((n==1)) ) || ( ((r==1)) && ((n==2)) ) || ( ((r==2)) && !((n==1)) ) ); then
echo 1
elif( ((n==0)) || ((n==1)) || ((r==0)) || ((r==1)) || (! ((${r}%2 == 0)) && ! ((${n}%2 == 0)) || ( ((r==2)) && ((n==1)) )) ); then
echo 0
else echo $(./geng -c -d1 ${n} -q | ./multig -m${r} -r${r} -u 2>&1 | cut -d ' ' -f 7 | grep -v '^$');  fi;
((n++))
((r--))
done
done

Crossrefs

Rows n=3..9 are: A000035, A253186, A324221, A324218, A324217, A325474, A327604.

Columns r=3..8 are: A000421, A129417, A129419, A129421, A129423, A129425.

Cf. A289986 (main diagonal), A333330 (not necessarily connected), A333397.

Sequence in context: A363709 A246398 A051699 * A007920 A127587 A175832

Adjacent sequences: A328679 A328680 A328681 * A328683 A328684 A328685

Keyword

nonn,tabl,hard

Author

Natan Arie Consigli, Dec 17 2019

Status

approved