[seqfan] Re: Do we have this?

Rob Pratt Rob.Pratt at sas.com
Fri Jul 8 00:04:53 CEST 2016

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".


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:=
>            tot:= tot + procname(Gp);
>         od
>       od
>     fi
>   od
>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;
>0, 2, 24, 744, 35160, 2394720, 222712560, 27154350720, 4205374225920,
>It seems not to be in OEIS yet.
>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/

More information about the SeqFan mailing list