Thanks for the suggestion, but I can’t get it to do anything; all it gives me are error messages that I can’t make sense of, like “negative factorial” (there weren’t any negative factorials in my input, only in the output I posted above), and “division by zero” (there was no division by zero). I give up on that, I really have doubts there’s going to be a nice closed form for it.
Oh well. If you’re feeling up to it, you could replace all your factorials with gamma’s, but I won’t be upset if you don’t. 
Okay, so what’s wrong with the way I’m working ultrafilter’s post of the corrected formula?
(n - 1)! - SUM[sub]k=2[/sub][sup]k = n-1/sup*(-1)[sup]k-1[/sup]
The first iteration of the summation, when k=2, is always a large negative number: -(n!/2) The second iteration is a positive number 1/3rd that size. Then a negative n!/24 gets added, etc. In other words, this sum never appears to go positive, but, as n gets larger, appears to converge somwhere between -(n!/3) and -(n!/2). If it’s always negative, the full formula will always spit out a number greater than (n-1)!, since we’re subtracting a negative, and will always be larger than the total number of possibilities allowed no matter what the rules?
I already wrote out my by-hand analysis when n=5, and even included a mistake (I know quite well that 4!=24, not 12, but ran with that glitch anyway - I didn’t realize it until this morning). Corrected, I get 69 for an answer, when there are only 24 permutations of 5 beads.
Of course, now that I see ultrafilter saying “I think I used the wrong formula,” perhaps all this is just completely off-base. I can’t follow the math in the latest posts, simply because I don’t know what that C function [as in C(20,n)] is defined to be. (If someone could point me in the right direction there, that’d be a help.)
All I’m doing, of course, is coming at the problem from a different angle. If these formulas the real math whizzes here (I’m just an algorithm guy, curwin) are posting are anywhere near correct, then matching up what the formulas spit out for a situation in which the result can easily be checked by hand seems to me to be essential as evidence that the gigantic 17-digit monsters we can’t check by a different method are okay, too.
DaveW:
I believe you (along with ultrafilter and me) missed kabbes correction to his formula at 12:41PM on 8/21 (actually, though, I think that sum should be from 1 to 20 instead of 19, and don’t forget the (-1)^(n+1))
Anyway, I think mine and kabbes sums do actually differ a tiny bit (by exactly one), since he sums from 0 to 19 (basically) and I sum from 0 to 20.
C(n,k) is a binomial coefficient, often read as “n choose k”. Given n distinct objects, it’s the number of different ways you can select exactly k of them:
C(n,k) = n! / [(n-k)! * k!]
[/quote]
Anyway, I think mine and kabbes sums do actually differ a tiny bit (by exactly one), since he sums from 0 to 19 (basically) and I sum from 0 to 20.
[/quote]
I take that back, I believe I see where he changed that to a sum from 0 to 20.
Just to further demonstrate that my seat-of-the-pants factorization method was BS, I got the prime factors of the number that the Cabbage bro’s seem to agree on as correct.
(calculator at http://www.btinternet.com/~se16/js/factor.htm)
42519034050101745 --> 2.2.2.2.19.139.1006224773999
…which has a 19 in ther but not much else worth knowing!
And to double check, I also factored the “total possible” number they gave.
121645100408832000 --> 2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.3.3.3.3.3.3.3.3.5.5.5.7.7.11.13.17.19
…which seems dead on.
Cabbage explains things
Thanks!
So, when kabbes wrote:
Does this mean that the general form would then be (using b to represent the number of beads):
(b-1)! - SUM[sub]n=1[/sub][sup]n=b[/sup][(-1)[sup]n+1[/sup] * C(b,n) * (b-n-1)!]
Assuming that it is, then given that
C(n,k) = n! / [(n-k)! * k!]
(thanks for that, too) then when b is 5, we get the following in the summation, right?:
n=1: 156, or 30
n=2: -1102, or -20
n=3: 1101, or 10
n=4: -151 (assuming that 0! is 1), or -5
n=5: 111, or 1
Summed: 16. 24 [(5-1)!] minus 16 is 8, which is exactly the same number I got brute-forcing up all the possibilities last night.
I feel better now. Thanks again.
So, where’s the formula for the no-(5,4)-pairs version? We’ve already got 10 data points, can’t we just fit a curve to them?
DaveW:
Yep, that’s the general form all right.
As for the version where we don’t allow consecutive pairs in either order, I looked at that earlier today. As I expected, there are some tricky parts to them (if we try using the princ. of inc-exc as before), and I don’t see any nice way around them at this point.
Here’s the problem. Before, in the early version (using my earlier notation) that we just did, it was easy to compute the N(a[sub]i[/sub]'a[sub]j[/sub]‘a[sub]k[/sub]’) type stuff–it fell into a nice orderly pattern, dependent only on the number of a’s in the parentheses.
If we try a similar extension for the case curwin had in mind, say, let
N(b[sub]i[/sub]) be the number of circles not including (i+1,i), and let
N(b[sub]i[/sub]’) be the number of circles including (i+1,i), then things can start getting a little messier.
For example, what’s N(a[sub]i[/sub]‘b[sub]k[/sub]’)? Well, that depends highly on how close i and k are. Sometimes it will be zero, other times it will behave nicely, just like it did when we were only dealing with the a’s. Separating (counting) the two cases just seems to be a pain, particularly when you start throwing more a’s and b’s in there. I think it can be done, and there may very well be a nice solution to it with this approach (or at least some other approach, I should think), but I haven’t really given it much more additional thought. I’ll post here if I end up going any further with it.
The problem here, Cabbage, is that Maple is thinking too generally. Unless told otherwise, it assumes that everything in an equation is a general complex scalar. Try putting the lines
assume(n,integer);
assume(n,real);
assume(n,positive);
just above your formula, and re-evaluate it-- That usually eliminates the need for it to put signum-type stuff in the answer.
It looks like that pesky infinity is just a limit of some sort (of a sum or such), and so it’s not a big no-no.
Excuse me young man! You’re supposed to be doing your homework! Anymore of this self distraction and it’s back on the Ritilin for you.
Just wanted to say that I’ve been away from the boards for a few days, during which time I tried to solve the alternate form of the problem.I ran into the same problems as Cabbage however.
This is not particularly my area of expertise and I’m rather worried that I’m not going to be able to solve this one without putting in more time than I am willing to spare. I’ll keep plugging away in spare moments though.
In the meantime I’d suggest that DaveW’s brute force method looked as though it was heading towards a limit of about 12%. Sounds about right to me
pan
My son is a Ph. D. student in Operations Research. He likes to play with this kind of problems, so I sent it to him. Here is his reply:
Interpretation 1: exclude (n, 1) and (i, i + 1) for i = 1 to n - 1.
I generated the good permutations exhaustively for small n and submitted the first few terms to the Encyclopedia of Integer Sequences, which gave me the following.
ID Number: A000757 (Formerly M4521 and N1915)
Sequence: 1,0,0,1,1,8,36,229,1625,13208,120288,1214673,13469897, 162744944,2128047988,29943053061,451123462673,7245940789072,
123604151490592,2231697509543361
Name: Cyclic permutations of [ n ] with no i->i+1 (mod n)
References S. M. Jacob, The enumeration of the Latin rectangle of depth three…,
Proc. London Math. Soc., 31 (1928), 329-336.
R. P. Stanley, Space Programs Summary. Jet Propulsion Laboratory, California Institute of Technology, Pasadena, California, Vol. 37-40-4 (1966), pp. 208-214.
R. P. Stanley, Enumerative Combinatorics I, Chap. 2, Exercise 8, p. 88.
Formula: a(n)=(-1)^n + sum((-1)^kbinomial(n,k)(n-k-1)!,k=0…n-1); e.g.f. = exp(-x)(1-ln(1-x)); a(n) = (n-3)a(n-1) + (n-2)(2a(n-2) + a(n-3)).
Keywords: nonn,easy,nice
Offset: 0
Author(s): njas
Extension: Better description from Len Smiley (smiley@math.uaa.alaska.edu)
So Cabbage’s inclusion-exclusion argument appears to be correct.
Interpretation 2: exclude (1, n), (n, 1), and both (i, i + 1) and (i + 1, i) for i = 1 to n - 1. Consider reflected arrangements to be equivalent (else multiply counts by 2).
ID Number: A002816 (Formerly M3102 and N1257)
Sequence: 0,0,1,3,23,177,1553,14963,157931
Name: Polygons formed from n points on circle, no 2 adjacent.
References P. Poulet, Reply to Query 4750, Permutations,
L’Interm’{e}diaire des Math’{e}maticiens, 26 (1919), 117-121.
Keywords: nonn,nice,more
Offset: 3
Author(s): njas
The absence of an explicit or recursive formula or generating function in the entry above supports the fact that Interpretation 2 makes things harder. This was my original interpretation of the problem, but
inclusion-exclusion would be very messy, and I don’t see any other way to do it. In graph-theoretic terms, we are counting Hamiltonian cycles in the graph K_n \ C_n, where K_n is the complete graph on n vertices and C_n is the cycle graph on n vertices. I have seen an inclusion-exclusion formula for the number of perfect matchings on K_n \ C_n (with n necessarily even), though.
I’m not sure I’ll spend any more time on this, but I thought I’d toss out what I did try and see if anyone can do anything with it.
I gave up on inclusion-exclusion a while ago and started playing around with recurrence relations; I’m not sure if it’d be any easier that way, 'cause I got stick trying that, too, but here’s where I got:
Let s[sub]n[/sub] be the number of proper n circles (i.e., acceptable permutations of 1,…,n on a circle, as curwin defined it), and let’s try and find a recurrence relation for it. If you take a proper n circle, there are two cases:
-
If you remove the number n, you get a proper n-1 circle. These are easy to account for.
-
If you remove n, you don’t get a proper n-1 circle. This can happen one of two ways:
a. Removing n results in two consecutive numbers getting squeezed together in the new circle, and/or
b. (1,n-1) or (n-1,1) is in the proper n circle, so that when n is removed, they suddenly become a flaw in the new n-1 circle.
Cases where (2b and not 2a) occur are easy to take care of as I recall, it’s only 2a that causes problems. If anyone has any insights on 2a, post away!
kabbes wrote:
Yesterday, I happened to have a moment to check that computer. It had hung to the point of only being resurrectable via power off/on. Yuck. But, my brute-force program had added N=15 to the list before that time. Total number of good curwin-style combinations for N=15 is a little above 5 billion, 50 million, IIRC. This is about 11.6% of the 43,589,145,600 total possible.
You guys have been doing combinatorics all week, and I missed it, durnitall!!
I’m heartened by the fact that kabbes, Cabbage, & Co. have so far left one good unsolved problem on the table. I’ll have to take a crack at it this weekend, if one or another of my compatriots doesn’t beat me to it. And Richard, your son came up with a nice way of visualizing the problem (counting the Hamilton cycles on K[sub]n[/sub]**C[sub]n[/sub]**).
I’m not that familiar with graph notation. What does K[sub]n[/sub]*C[sub]n[/sub]* mean? I know that K[sub]n[/sub] is the complete graph on n vertices and C[sub]n[/sub] is the cycle on n vertices, but I’ve not seen the / before.
Going back to your 8/21, 3:51pm post:
For N=5, I get 1 good arrangement.
For N=6, I get 3.
Does your program tell you what the good arrangements are? For N=6 (using beads=0,1,2,3,4,5) I get, in ‘dictionary’ order:
A: 024153
B: 025314
C: 031524
D: 035142
E: 041352
F: 042513
and that’s all. And D,E,F are the same Hamilton cycles as A,B,C, traversed in reverse order. (Or D,E,F are CCW versions of CW sequences A,B,C.)
If you can tell me if I’m missing something, I’d appreciate it. It appears to me that there’s only one Hamilton cycle on K[sub]6[/sub]\C[sub]6[/sub], and numbering the vertices and rotating turns it into 3 of them.
ultrafilter - the \ loosely translates into ‘minus the edges of’. So K[sub]n[/sub]\C[sub]n[/sub] is the complete graph on n vertices, with the edges of the n-cycle removed.
Right, the difference operator. Sorry, I’ve been looking at quotient groups lately, and so I was thinking it was some kind of quotient operator.
RTFrefly wrote:
Not anymore, it doesn’t, because I verified a slew of them, and, not wanting to fill my hard drive with sequences, I turned that feature off. Actually, keeping track of the order was slowing me down, too.
Anyway, I didn’t get 3 for N=6, I got 5. By your list, I should have gotten 3. And I can tell exactly what my problem was, even without having the stupid code in front of me (it’s an hour’s drive away). Oh, my cheeks are pink! I’m sure I forgot to compare the value of bead n to bead 1!!! Crappola.
[super hero voice]
Brute-Force Man isn’t always correct on his first attempt!
[/super hero voice]