A322751 - OEIS

%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