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