OFFSET
0,3
COMMENTS
The sequence is the number of unique arrangements of directed graphs connecting 2*n vertices, where vertices occur in pairs, and meeting the following requirements:
1. Each vertex has an out-degree and in-degree of 1.
2. No edge connects vertices that are paired.
3. Starting with any pair, following the edges of paired vertices connects all vertices.
The requirements were chosen to yield a nice gift exchange between a set of couples. Acknowledgement to the additional members of the initial, inspirational gift exchange group: Cat, Brad, Kim, Ada, Graham, Nolan, and Leah.
The fraction of graphs meeting the requirements is approximately 0.12. Starting with n=2, the fractions are (0.166666667, 0.111111111, 0.116666667, 0.12042328, 0.122959756, 0.124807468). Is there a way to compute the percentage of graphs satisfying the condition in the limit as n approaches infinity?
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..100
FORMULA
E.g.f.: 1 + log(B(x)) where B(x) is the e.g.f. of A000316. - Andrew Howroyd, Jan 13 2024
EXAMPLE
For n = 1, there is one pair; a(1) = 0 since requirements 1 and 2 can't be satisfied.
For n = 2, there are two pairs; a(2) = 4 graphs given by these edge destinations:
((2, 3), (1, 0))
((2, 3), (0, 1))
((3, 2), (1, 0))
((3, 2), (0, 1)).
PROG
(Python)
from itertools import permutations as perm
def num_connected_by_pairs(assigned, here=0, seen=None):
seen = (seen, set())[seen is None]
for proposed in [(here - 1, here), (here, here + 1)][(here % 2) == 0]:
if proposed not in seen:
seen.add(proposed)
num_connected_by_pairs(assigned, assigned[proposed], seen)
return len(seen)
def valid(assigned, pairs):
self_give = [assigned[i] == i for i in range(len(assigned))]
same_pair = [assigned[i] == i + 1 or assigned[i+1] == i for i in range(0, 2*pairs, 2)]
if pairs == 0 or True in self_give + same_pair:
return False
num_connected = [num_connected_by_pairs(assigned, here) for here in range(2, 2*pairs, 2)]
return min(num_connected) == 2*pairs
print([len([x for x in perm(range(2*pairs)) if valid(x, pairs)]) for pairs in range(0, 6)])
(PARI) \\ Here B(n) gives A003471 as vector.
B(n)={my(v=vector(n+1)); v[1]=1; for(n=4, n, my(m = 2-n%2); v[n+1] = v[n]*(n-1) + 2*(n-m)*v[n-2*m+1]); v}
seq(n)={my(v=B(2*n)); Vec(serlaplace(1+log(sum(k=0, n, v[1+2*k]*x^k/k!, O(x*x^n)))))} \\ Andrew Howroyd, Jan 13 2024
CROSSREFS
KEYWORD
nonn
AUTHOR
Russell Y. Webb, Dec 25 2018
EXTENSIONS
a(0) changed to 1 and a(8) onwards from Andrew Howroyd, Jan 13 2024
STATUS
approved