cp's OEIS Frontend

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.

%I A322751 #23 Jan 14 2024 11:52:14
%S A322751 1,0,4,80,4704,436992,58897920,10880501760,2640513576960,
%T A322751 814928486400000,311763576754667520,144816978675459686400,
%U A322751 80294888451877031116800,52385405443881146567884800,39727727942688305214337843200,34656123210118214086941474816000
%N 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.
%C A322751 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:
%C A322751 1. Each vertex has an out-degree and in-degree of 1.
%C A322751 2. No edge connects vertices that are paired.
%C A322751 3. Starting with any pair, following the edges of paired vertices connects all vertices.
%C A322751 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.
%C A322751 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?
%H A322751 Andrew Howroyd, <a href="/A322751/b322751.txt">Table of n, a(n) for n = 0..100</a>
%F A322751 E.g.f.: 1 + log(B(x)) where B(x) is the e.g.f. of A000316. - _Andrew Howroyd_, Jan 13 2024
%e A322751 For n = 1, there is one pair; a(1) = 0 since requirements 1 and 2 can't be satisfied.
%e A322751 For n = 2, there are two pairs; a(2) = 4 graphs given by these edge destinations:
%e A322751     ((2, 3), (1, 0))
%e A322751     ((2, 3), (0, 1))
%e A322751     ((3, 2), (1, 0))
%e A322751     ((3, 2), (0, 1)).
%o A322751 (Python)
%o A322751 from itertools import permutations as perm
%o A322751 def num_connected_by_pairs(assigned, here=0, seen=None):
%o A322751     seen = (seen, set())[seen is None]
%o A322751     for proposed in [(here - 1, here), (here, here + 1)][(here % 2) == 0]:
%o A322751         if proposed not in seen:
%o A322751             seen.add(proposed)
%o A322751             num_connected_by_pairs(assigned, assigned[proposed], seen)
%o A322751     return len(seen)
%o A322751 def valid(assigned, pairs):
%o A322751     self_give = [assigned[i] == i for i in range(len(assigned))]
%o A322751     same_pair = [assigned[i] == i + 1 or assigned[i+1] == i for i in range(0, 2*pairs, 2)]
%o A322751     if pairs == 0 or True in self_give + same_pair:
%o A322751         return False
%o A322751     num_connected = [num_connected_by_pairs(assigned, here) for here in range(2, 2*pairs, 2)]
%o A322751     return min(num_connected) == 2*pairs
%o A322751 print([len([x for x in perm(range(2*pairs)) if valid(x, pairs)]) for pairs in range(0, 6)])
%o A322751 (PARI) \\ Here B(n) gives A003471 as vector.
%o A322751 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}
%o A322751 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
%Y A322751 A322750 does not allow reciprocal connections.
%Y A322751 A010050 is the number of graphs (2n)!.
%Y A322751 Cf. A000316, A003471.
%K A322751 nonn
%O A322751 0,3
%A A322751 _Russell Y. Webb_, Dec 25 2018
%E A322751 a(0) changed to 1 and a(8) onwards from _Andrew Howroyd_, Jan 13 2024