[seqfan] Re: Do we have this?

[Rob Pratt]

The problem description doesn’t specify that there are exactly two copies of each version of the test.  For example, isn’t alternating versions 1 and 2 a legal distribution of tests, without using versions 3, 4, or 5?

-----Original Message-----
From: SeqFan [mailto:seqfan-bounces at list.seqfan.eu] On Behalf Of israel at math.ubc.ca
Sent: Thursday, July 07, 2016 5:29 PM
To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
Subject: [seqfan] Re: Do we have this?

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_sou
>> rce=facebook&utm_campaign=adv_fb_posts_07062016&utm_content=qq_ch_lin
>> ear_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/
>
>

--
Seqfan Mailing list - http://list.seqfan.eu/