[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