Wikipedia:Reference desk/Archives/Mathematics/2023 February 1

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

February 1

How many non-equal pairing schemes?

Imagine 2 identical sets of unique items (eg "a,b,c,d" "a,b,c,d"). How many different pairing schemes are there when no pair comprises identical items? With n=1 ("a" "a") it is 0 as the only pair is "aa". With n=2 ("a,b" "a,b") it is 1 (ab,ab). With n=3 ("a,b,c" "a,b,c") it is 1 (ab,ac,bc) and with n=4 ("a,b,c,d" "a,b,c,d") it is 6 (ab,ab,cd,cd) (ab,ac,bd,cd) (ab,ad,bc,cd) (ac,ac,bd,bd) (ac,ad,bc,bd) and (ad,ad,bc,bc). Is there a formula for this? -- SGBailey (talk) 11:23, 1 February 2023 (UTC)

This sounds like the number of Derangements, except you're counting a permutation and its inverse as the same thing. So off the top of my head it's (number of derangement + number of derangements of order 2)/2. The number of derangement of order 2 should be straightforward, 0 if n is odd and (n-1)(n-3)...(3)(1) if n is even. Another way to look at this is the number of Multigraphs (no loops) on n nodes with degree 2. --RDBury (talk) 14:38, 1 February 2023 (UTC)

With even n some derangements are self-inverse, so dividing by 2 gives an undercount. —Tamfang (talk) 18:24, 1 February 2023 (UTC)

It's more than just identifying a permutation with its inverse. Consider n=6, and a permutation consisting of two disjoint 3-cycles. Each 3-cycle is being identified with its inverse, which means 4 different permutations are being collapsed into 1.--2600:4040:7B33:6E00:7D1B:6AA6:5446:FA6B (talk) 18:32, 1 February 2023 (UTC)

This is sequence A002137 in the OEIS (see the last comment by Kellen Myers).  --Lambiam 18:49, 1 February 2023 (UTC)

I think it will satisfy this recurrence relation: $P_{n}=(n-1)!/2+\sum _{i=2}^{n-2}P_{n-i}*(i-1)!/2$. Here (n-1)!/2 counts the pairings coming from a single n-cycle, and otherwise you have an i-cycle containing the first element, and an (n-i)-pairing for the remaining elements.2600:4040:7B33:6E00:7D1B:6AA6:5446:FA6B (talk) 18:54, 1 February 2023 (UTC)

Taking $P_{1}=0,P_{2}=P_{3}=1,$ this formula results in $P_{4}=$ $3!/2+\sum _{i=2}^{2}P_{4-i}*(i-1)!/2=$ $6/2+P_{2}\times 1!/2=$ $7/2.$  --Lambiam 19:41, 1 February 2023 (UTC)

Right, it shouldn't be dividing by 2 for 2-cycles.2600:4040:7B33:6E00:7D1B:6AA6:5446:FA6B (talk) 20:20, 1 February 2023 (UTC)

Here is the corrected relation. Putting $P_{0}=1,P_{1}=0,$ we have, for $n\geq 2,$

$P_{n}=(n-1)P_{n-2}+\sum _{k=3}^{n}{\frac {(n-1)!}{2(n-k)!}}P_{n-k}.$

Defining $Q_{n}={\frac {P_{n}}{n!}},$ we obtain a simpler (but no longer integer-valued) recurrence relation:

$nQ_{n}=Q_{n-2}+{\frac {1}{2}}\sum _{k=3}^{n}Q_{n-k}.$

Further defining $S_{n}=\sum _{i=0}^{n}Q_{n}$ produces, for $n\geq 3,$

$S_{n}=S_{n-1}+{\frac {S_{n-2}}{n}}-{\frac {S_{n-3}}{2n}}.$

Next, using $T_{n}=n!S_{n}$ brings us back to integer terrain, with

$T_{n}=nT_{n-1}+(n-1)T_{n-2}-{\frac {(n-1)(n-2)}{2}}T_{n-3}.$

Then $P_{n}=T_{n}-nT_{n-1}.$ (This can probably be done in fewer steps.)  --Lambiam 23:46, 1 February 2023 (UTC)

This $T_{n}$ is sequence A345132 in the OEIS.  --Lambiam 09:20, 2 February 2023 (UTC)

I take the point about my formula being wrong with n=6. I'm pretty sure it's right for n<=5 though, so it's not undercounting anything, just overcounting ones with multiple cycles of length >2. For example for n=2, 3, 4 it gives (1+1)/2 = 1, (2+0)/2 = 1, (9+3)/2 = 6. For the correct formula, the OEIS gives the exponential generating function and it should be possible to generate a recursion from that in addition to deriving it independently; that kind of thing is usually included in the OEIS and I assume that whoever was working on the entry figured the e.g.f. was enough. I have a feeling that if there were a simple closed form expression the the OEIS would have it. --RDBury (talk) 23:58, 1 February 2023 (UTC)

Thank you all - this is far more complicated than I expected. -- SGBailey (talk) 06:44, 2 February 2023 (UTC)