[seqfan] Re: Do we have this?

[israel at math.ubc.ca]

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}
>n*add(L(sort([i,2*n-i-2])),i=1..2*n-3) end proc;
>
>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:
>
>>  
>>  
>>  
>> https://brilliant.org/practice/linear-recurrence-relations-level-4-5-challenges/?problem=are-you-ready-for-brimo&utm_medium=social&utm_source=facebook&utm_campaign=adv_fb_posts_07062016&utm_content=qq_ch_linear_recurrence_l45
>>
>> (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 
>> haven't made a mistake, this should start with 0*1!, 1*2!, 4*3!, 29*4! = 
>> 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?
>>
>>Franklin T. Adams-Watters
>>
>>
>>--
>>Seqfan Mailing list - http://list.seqfan.eu/
>>
>>
>
>--
>Seqfan Mailing list - http://list.seqfan.eu/
>
>