[seqfan] Re: Do we have this?

israel at math.ubc.ca israel at math.ubc.ca
Thu Jul 7 23:26:24 CEST 2016


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/
>
>


More information about the SeqFan mailing list