If you consider some symetry, you can show that (n+1)n*n*n|a(n). Pick and fix an arbitrary set S of order n+1. It is easy to see that any given cycle can defined by the transition of sets of order n+1 to other sets of order n+1(Although not all are allowable because some may involve repeating sets of length n). There are (n+1)n transitions from S to the next set, and then n^2 for the next transition. Although after that the symetry breaks down because the third set may share n or n-1 elements with the first set. Interestingly enough none of this precludes there being a(n)=0 for some n, because this merely begins a construction procedure which may end in possible cycles. If the conjecture is false it would seem likely that a(n) could be approximated by some analytic function only when it doens't equal 0. There are (2n+1 choose n)-1 of these transitions. So, we can get an upper bound of (n+1)n*n^(2(2n+1 choose n)-4) for n>=2. Although, the possibility easily exists that a(n)=0 for various values of n, I would guess from looking at the construction I would guess that the non-zero values of a(n) are around 2^((7 C 3)/k) where is some constant. Example: For n=3 (7 C 3)-1=34. So, 108|a(3), and a(3)<2*3^64. If there is any nice way of calculating a(3), I would conjecture there is some other symetry which would mean it is only divisible by pretty small primes. Notation: S(k,l):= Shares k elements with l T(k,l,m):= k allowable transitions to step l, via the equivalence class of m T():=No transformations possible Working with {1,2,3,4,5,6,7} 1) {1,2,3,4} T(3*2,2,{1,2,3}) 2) {1,2,3,5} S(3,1) T(2*2,3,{1,2,5}) 3) {1,2,5,6} S(2,1) S(3,2) T(1,4.1a,{1,2,6}) T(1,4.1b,{1,2,6}) T(1,4.1c,{1,2,6}) T(2,4.2,{2,5,6}) We could continue, but it starts getting really messy. The basic idea is that a set is equivalent if its elements are in the same previous sets. We then calculate the number of ways it can follow that path, and then at the end we sum up the product of all the paths. A computer program could be written using recursion, by writing a function that inputs the previous sets of order n+1, and previous sets of order n, then it finds the symetries, and calls itself for each of them. int levels(sets nplus1Sets,sets nSets,int numNplus1Sets) { foreach(for each element of nplus1Sets.lastSet()) { tempSet=nplus1Sets.lastSet()-element if(tempSet is not in nSets) { find all permissible equivalences of additions to tempSet and then recursively call this function } } } Gershon Bialer ----- Original Message ----- From: "N. J. A. Sloane" <njas@research.att.com> To: <math-fun@mailman.xmission.com> Sent: Saturday, January 17, 2004 12:23 PM Subject: [math-fun] Midlevels Conjecture
I posted this question to the seq-fan mailing list yesterday. I got some replies, which are mentioned below.
In Peter Winkler's very nice new book "Math Puzzles" he mentions an unsolved problem, which is related to a possibly new sequence:
a(n) = number of ways to cycle through all the subsets of size n and n+1 of a set of size 2n+1 by adding or deleting one element at a time
The conjecture is that a(n) is always > 0.
a(1) is 2, because the two cycles are
1 13 3 23 2 12 1 ...
and its reverse.
Yesterday Edwin Clark <eclark@math.usf.edu> wrote to say:
a(n) = 2b(n) where b(n) is the number of Hamiltonian cycles in the so-called bipartite Kneser graph H(2n+1,n) whose vertices are the subsets of size n and n+1 of a set of size 2n+1. A is adjacent to B iff one set is contained in the other.
Using the Hamiltonian cycle finder in the program Groups & Graphs, I got b(2) = 24.
Then when I tried the case n = 3, I got the reply: "Too much output. Logging of Hamiltonian cycles is being terminated. 10382 cycles were found so far."
So all I can say is b(3) >=10382.
So all I know at the moment is that the sequences a(n) and b(n) begin
2, 48, >=20764 1, 24, >=10382
Also, Peter Winkler says:
I'm delighted to see this sequence in your sights. My old colleague Bob Roth (laker@mathcs.emory.edu) once computed some terms, you might ask him if he still has the results after 25 years or so!
So far I have not heard back from Bob Roth.
Can anyone supply more terms?
Neil
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun