The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A322751 Number of directed graphs of 2*n vertices each having an in-degree and out-degree of 1 such that the graph specifies a pairwise connected gift exchange. 1
 0, 0, 4, 80, 4704, 436992, 58897920, 10880501760 (list; graph; refs; listen; history; text; internal format)
 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 Table of n, a(n) for n=0..7. EXAMPLE For n = 0, there are no pairs; a(0) = 0 since no edges exist. 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)]) CROSSREFS A322750 does not allow reciprocal connections. A010050 is the number of graphs (2n)!. Sequence in context: A013007 A013008 A013180 * A000316 A012106 A156103 Adjacent sequences: A322748 A322749 A322750 * A322752 A322753 A322754 KEYWORD nonn,more AUTHOR Russell Y. Webb, Dec 25 2018 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 8 18:04 EDT 2023. Contains 363165 sequences. (Running on oeis4.)