# [seqfan] Re: Do we have this?

israel at math.ubc.ca israel at math.ubc.ca
Thu Jul 7 23:29:28 CEST 2016

```I pressed "send" too soon: a(n)/n! is A003436. Note Andrew Howroyd's
comment "Number of perfect matchings in the complement of C_{2n} where
C_{2n} is the cycle graph on 2n vertices".

Cheers,
Robert

On Jul 7 2016, israel at math.ubc.ca wrote:

>I'm pretty sure it should be 744, not 696, for 8 perople.  And I get 35160
>for 10.
>
> Let a(n) be the number of ways to distribute tests for 2n people. The 2n
> people originally form the vertices of a cycle graph. At the k'th stage,
> we take two non-adjacent vertices, assign the two copies of version k to
> those, and delete those vertices. After the first stage, each stage will
> have some disjoint collection of path graphs. Start by assigning the two
> copies of the first test version to two non-adjacent people, and deleting
> those people. This breaks up the cycle graph into two intervals. Continue
> assigning copies of each test version. At each stage the remaining people
> form some collection of interval graphs: we take, in all possible ways,
> two non-adjacent vertices to assign the next version of the test, remove
> those vertices, and calculate recursively. My Maple code is as follows.
>
>L:= proc(G) option remember;
># G is a list of integers, representing lengths of path graphs
># k = sum(G)/2 exam versions still to distribute
># wlog G is nondecreasing
>local i,j,ki,kj,nG,tot,Gp;
>nG:= nops(G);
>tot:= 0;
>for i from 1 to nG do
>  for j from i to nG do
># take an elt of list i and of list j.
>     if i=j then # same list, need non-adjacent
>       for ki from 1 to G[i]-2 do
>         for kj from ki+2 to G[i] do
>            Gp:= sort(subs(0=NULL,subsop(i=(ki-1,kj-ki-1,G[i]-kj),G)));
>            tot:= tot + procname(Gp);
>         od
>       od
>     else # different lists
>       for ki from 1 to G[i] do
>         for kj from 1 to G[j] do
>            Gp:=
>sort(subs(0=NULL,subsop(i=(ki-1,G[i]-ki),j=(kj-1,G[j]-kj),G)));
>            tot:= tot + procname(Gp);
>         od
>       od
>     fi
>   od
>od;
>tot
>end proc;
>L([]) := 1;
>
>F:= proc(n)
># this gives the number for the cycle graph C_{2n}
>
>seq(F(n),n=1..10);
>
>0, 2, 24, 744, 35160, 2394720, 222712560, 27154350720, 4205374225920,
>806700010233600
>
>It seems not to be in OEIS yet.
>
>Cheers,
>Robert
>
>
>On Jul 7 2016, Frank Adams-Watters wrote:
>
>>
>>
>>
>>
>> (You have to register with them to see their answer; but see below, I'm
>> sure that their answer is not correct.)
>>
>> There is an obvious sequence for, the same problem for 2n people. If I
>> 0, 2, 24, 696, which is not in the database. (The n! term comes from
>> permuting the tests without changing the pattern in which they are
>> handed out.) Looking only at 2, 24, 696 gives A030438 as the only match;
>> while this seems similar, I don't think it is actually the correct
>> sequence.
>>
>> The search dividing out the n! factor gives too many matches to look
>> through.
>>
>> The linked site claims the next term is 1048580, but this can't be
>> correct; it is not a multiple of 5!.
>>
>> So first, is my 29 correct? Second, is this sequence in the database? If
>> not, can someone compute a few terms?
>>
>>
>>
>>--
>>Seqfan Mailing list - http://list.seqfan.eu/
>>
>>
>
>--
>Seqfan Mailing list - http://list.seqfan.eu/
>
>
```