For example ultrafilter, you overcount by the cases where there are more than 2 sets of consecutive numbers.
Eureka! That’s it! My sum shouldn’t be a sum at all - it should be an alternate “+”, “-” jobbie.
Ooh, I need to think about this.
But now I’m going home.
pan
Yeah, I agree here. From 1 to 20, there are 20 pairs {i,i+1}. Dividing by 2 eliminates half of the pairs, all of which are invalid:
{ (1,2) (2,3) (3,4) (4,5) (5,6) (6,7) (7,8) (8,9) (9,10)
(11,12) (12,13) (13,14) (14,15) (15,16) (16,17) (17,18) (18,19) (19,20) (20,1) }
If you took order into account (1,2 different from 2,1) you would be left with 40 invalid pairs, not 20.
I didn’t go home. Instead I put the numbers back into Excel, using my revised formula and with (-1)[sup]k-1[/sup] in the formula as well.
You get 4.2519 x 10[sup]16[/sup] acceptable combinations with no consecutive numbers.
In other words 34.95% of the permutations do NOT have any consecutive numbers.
There. ::bows::
pan
:: applauds ::
I don’t suppose there’s anyway to state that as a function of <n>?
In case you’re interested, here is the table of numbers:
i Contribution towards sum
1 1.28047E+17
2 -6.75806E+16
3 2.3852E+16
4 -6.33568E+15
5 1.35161E+15
6 -2.41359E+14
7 3.71322E+13
8 -5.02832E+12
9 6.09493E+11
10 -67044257280
11 6772147200
12 -634888800
13 55814400
14 -4651200
15 372096
16 -29070
17 2280
18 -190
19 20
sum 7.91261E+16
total permutations 1.21645E+17
"good" permutations 4.2519E+16
% good permutations 34.95%
pan
Well, muttrox, you have the sum above, which is a function of n. You can establish the result for any n by producing an Excel table as I do above.
I’m certain however that there is an elegant way to state that sum as a simple function of n. But I’m blowed if I can think of it off the top of my head. And it’s definitely home time now!
pan
What I did made a lot more sense this morning. kabbes is right, that I overcount instances that have more than two numbers in a row.
I’ll run that formula through Maple tonight and see what it comes back with.
“Brute-Force Man” is here, just to toss out some numbers for differently-sized rings of N beads. Assuming that clockwise and counter-clockwise arrangements are the same (otherwise multiply the below numbers by 2), and that rotations don’t matter (multiply by N), my crunch-and-count program spat this out (N less than 5 doesn’t ever work, of course):
For N=5, there’s 1 good arrangment of beads out of 12 possible (~8%)
N=6: 5 good out of 60 (~8%)
N=7: 33 out of 360 (~9%)
N=8: 245 out of 2,520 (~9%)
N=9: 2,053 out of 20,160 (~10%)
N=10: 19,137 out of 181,440 (~10%)
N=11: 196,705 out of 1,814,400 (~10%)
N=12: 2,212,037 out of 19,958,400 (~11%)
N=13: 27,029,085 out of 239,500,800 (~11%)
N=14: 356,723,177 out of 3,113,510,400 (~11%)
That’s what come out so far. My surfing the Web while the program is running can’t be helping. My non-optimized code took about just a few seconds to do everything from N=5 to N=12, but then took almost a minute to add N=13. N=14 took a further 10 minutes or so. I’m not going to wait around for 15, but I’ll let the program keep chugging on it when I leave work. Probably pop out sometime late this afternoon.
N=20? In-my-head calculations make me think this would take over 5,000 years, so I doubt that answer will be forthcoming on this computer.
kabbes wrote:
Brute-Force Man begs to differ. The other method being “list all the combinations that meet the specs and count 'em.” Hmmm. 5,000 years? Okay, I’ll agree with you for large values of N. 
At least, I hope we’d get the same answers for the smaller values of N above… Oh, and while the percentages above are rising with N, they’d better hurry the heck up in order to reach your ~35% at N=20.
“I will not use work time to write code to check this… I will not use work time to write code to check this… I will not…”
This is kabbes corrected formula. Let’s call this f(n). I stuck this into Maple, and it spit back the following:
G denotes the gamma function, and GI denotes the incomplete gamma function. A google search would turn up pages that explain those better than I can–suffice it to say that G(n) = (n-1)! when n is an integer.
At first, I felt kinda bad about using a computer algebra system to do this, but since I’ve never had much experience putting sums into closed form, I figured I had to. Upon seeing the incomplete gamma function in there, I didn’t feel so bad anymore.
Now here’s the thing: n*e[sup]-1[/sup]*GI(n,-1) is positive for n = 1, 2, 3, 4, and 5. And (n-1)! is the number of possible permutations. Either I made a mistake typing in the formula, or kabbes has overcounted something. For those who know such things, here’s the Maple code I entered:
I used the same approach kabbes did (principle of inclusion-exclusion), but I get a different sum:
(-1)[sup]n[/sup] * C(20,n) * (19-n)!
where the sum is from n=0 to 20 (here I’m defining (-1)! = 1).
A couple of notes I should make for clarity–I am allowing two consecutive numbers to appear if they are out of order; for example, (4,5) is not allowed, but (5,4) is allowed. I’m also not allowing (20,1), but I am allowing (1,20).
I’m not precisely sure at which step the discrepancy between mine and kabbes answers occurs, but here’s my reasoning:
Let N(a[sub]i[/sub]) be the number of circles not including (i,i+1). Let N(a[sub]i[/sub]a[sub]j[/sub]) be the number of circles not including (i,i+1), and not including (j,j+1). And so forth.
Similarly, Let N(a’[sub]i[/sub]) be the number of circles including (i,i+1). Let N(a’[sub]i[/sub]a’[sub]j[/sub]) be the number of circles including (i,i+1), and including (j,j+1). And so forth.
The principle of inclusion-exclusion:
N(a[sub]1[/sub]…a[sub]n[/sub]) =
N - SUM[N(a’[sub]i[/sub])] + SUM[N(a’[sub]i[/sub]a’[sub]j[/sub])] - SUM[N(a’[sub]i[/sub]a’[sub]j[/sub]a’[sub]k[/sub])] + … + (-1)[sup]n[/sup]N(a’[sub]1[/sub]…a’[sub]n[/sub])
(The sum in each case is over all values of i,j,k,… such that no two are equal. For example, the third sum is over all C(20,3) combinations of three distinct a’[sub]i[/sub] 's out of the full 20).
Now N(some set of n distinct a’[sub]i[/sub]s in here) = (19-n)! Now look at the sum corresponding to that single term, and we see that we will sum up a total of C(20,n) of the (19-n)! 's. Throw in the (-1)[sup]n[/sup] to make it alternating, and that’s where I got the sum above.
Anyway, I hope that made sense, and I hope I committed no typos. However, there’s no way I’m going to do that sum by hand, and at the moment I have no software that will do it for me, but I should have a chance to do that later. If someone would like to do it for me in the meantime, I would be grateful.
I just noticed one omission I made in the principle of inclusion-exclusion, and that’s that N = total number of possible arrangements of beads = 19!
Cabbage: I ran your sum through Maple, and failed to get it in closed form. It may have had something to do with the fact that Maple doesn’t like (-1)!, and I don’t feel up to rewriting in terms of the gamma function.
kabbes: I think I may have used the wrong formula. To make things easy on me, could you just write out exactly what you’re summing?
Cabbage wrote:
The assumption that both pairs, (4,5) and (5,4), should be disallowed appears to have come in with the 8th post in this thread, by muttrox:
This makes sense to me because, since we’ve got something circular, it could be “read back” counter-clockwise, and all those (5,4) pairs you’re allowing would be (4,5) pairs, and thus invalid. curwin hasn’t made any sort of correction to this method of considering the question in the OP, so I dunno if it makes a difference to him/her.
If we assume that muttrox is correctly interpreting the OP, then 5 beads is the smallest number that yields possible answers. If the first bead we pick is 1, then the second bead can only be 3 or 4. If we pick 3, then the 5 is forced next, followed by the 2, and finally the 4 (call this the 1-3-5-2-4 solution). If the second bead we pick is the 4, then the 2 is forced, followed by the 5, and then the 3, giving us 1-4-2-5-3, which is just the 1-3-5-2-4 solution read counter-clockwise from the 1.
If we pick a different starting bead, the same solutions pop up, just “rotated” (if we start at 3, our only choices are the 5 or the 1, and the remaining beads are all forced).
Given these considerations, if rotations and CW/CCW “orientations” are to be counted differently, then there are indeed N! possibilites. If we disallow rotations only, we cut it to (N-1)!. If we disallow both rotations and orientation, it’s down to (N-1)!/2, which is what I used in my number-crunching, above.
Anyway, if “decreasing neighbors” (5,4) are allowed, then 3 beads becomes the minimum. 1-3-2 works, but only when “read” clockwise. CCW, it becomes 1-2-3, which is obviously “wrong” (no matter how you interpret the OP). Actually, I guess 2 beads is the minimum, since 2-1 is allowed under those rules. (And 1 bead is obviously a very special case we can ignore no matter what the rules.)
So, perhaps you and kabbes are simply operating under different assumptions. Perhaps dropping back to a simpler example to get the equations worked out with numbers closer to everyday life would help (8! is only 40,320, for example)?
I’ll readily admit that the equations and notations kabbes used made my eyes cross, but going back and forcing myself, along with ultrafilter’s help (having posted the “corrected version”), it’s pretty obvious (now, to me) that their little-n is the same as my capital-N, or the number of beads. What happens when n=5?
or, 24 minus the sum of
[
k=2: 120/2*-1 = -60
k=3: 120/61 = 20
k=4: 120/12-1 = -10
]
which is -50.
24 - (-50) is 74, which is clearly far off from any answer I would expect. 1 is what I got under my assumptions. Calling CCW different from CW would give us 2 (still following muttrox’s “either higher or lower isn’t allowed” assumption. Throwing in rotations as different, as well, would give us 10 valid solutions (out of a complete 5! - or 120 - total possibilities).
Under your assumptions, what do we get?
1: 1-3-2-5-4
2: 1-3-5-2-4
3: 1-3-5-4-2
4: 1-4-2-5-3
5: 1-4-3-5-2
6: 1-5-2-4-3
7: 1-5-3-2-4
8: 1-5-4-3-2
8 possibilities. If we throw in the rotations, we’re up to 40. And we can’t multiply by two because six of these solutions become invalid if read CCW.
Either way, 74 seems to be a bizarre result. But, because I’ll admit that my high-school education (up to 2 semesters of calculus) is a long way behind me, and I don’t do this kind of thing for a living (or even as a hobby[sup]*[/sup]), I’m willing to bet that I’ve misapplied the formulas kabbes and ultrafilter provided, or screwed up the arithmetic somewhere. But given the two different apparent assumptions in this thread so far, I can only see the following possible solutions when the number of beads is 5:
a) 1 out of 12 total permutations (muttrox, no rotations, CW=CCW)
b) 2 out of 24 (muttrox, no rotations, CW!=CCW)
c) 5 out of 60 (muttrox, with rotations, CW=CCW)
d) 8 out of 24 (Cabbage, no rotations)
e) 10 out of 120 (muttrox, with rotations, CW!=CCW)
f) 40 out of 120 (Cabbage, with rotations)
On re-reading the posts, I think I can honestly say I’m not sure what assumptions kabbes was working under…
[sup]*[/sup]I do enjoy playing with these kinds of problems, but not so much I’d call it a ‘hobby’. My enjoyment comes primarily as “Brute-Force Man”-style stuff - kind of. Once I get a computer program that pops out what appear to be correct answers (which seems simple, in this case), the fun comes in trying to get that program to do so faster, by doing things like unlooping loops, eliminating recursion, pre-calculating values, etc., or just dumping the first brute-force method for another if a better idea comes along.
AAAARGH! I typed out a whole bloody reply with subscripts and things and then pressed escape! NYARGH! Still, here we go again. If I’m a bit short this time, you know why.
[/quote]
I think I was unclear:
Now my sum, using the same notation, is:
19! - SUM[(-1)[sup]n+1[/sup] * C(20,n) * (20-n-1)!]
where the sum goes from 1 to 20.
Now since 19! = C(20,0) * 19!
and since 20 - 1 = 19
and since (-1)[sup]n+1[/sup] = - (-1)[sup]n[/sup]
I can rewrite my sum as:
SUM((-1)[sup]n[/sup] * C(20,n) * (19-n)!)
where the sum goes from 0 to 20.
So Cabbage, we don’t have different formulae at all! As numerical “proof”, I put your equations into Excel. I got the following:
n (-1)^n C(20,n) (19-n)! Contribution to sum
0 1 1 1.21645E+17 1.21645E+17
1 -1 20 6.40237E+15 -1.28047E+17
2 1 190 3.55687E+14 6.75806E+16
3 -1 1140 2.09228E+13 -2.3852E+16
4 1 4845 1.30767E+12 6.33568E+15
5 -1 15504 87178291200 -1.35161E+15
6 1 38760 6227020800 2.41359E+14
7 -1 77520 479001600 -3.71322E+13
8 1 125970 39916800 5.02832E+12
9 -1 167960 3628800 -6.09493E+11
10 1 184756 362880 67044257280
11 -1 167960 40320 -6772147200
12 1 125970 5040 634888800
13 -1 77520 720 -55814400
14 1 38760 120 4651200
15 -1 15504 24 -372096
16 1 4845 6 29070
17 -1 1140 2 -2280
18 1 190 1 190
19 -1 20 1 -20
20 1 1 1 1
TOTAL: 4.2519E+16
Note: same answer!
Ultrafilter - does this help you? Good work on the GLIM by the way. The e[sup]-1[/sup] term is consistent with some playing around I did last night. More of that below.
DaveW - or “Brute Force Man” (yergh ;)) - as you say, Cabbage and I are assuming differently to you. To my mind “consecutive” means strictly “i, i+1” but I’m not going to argue over it - both interpretations are reasonable. I’m not going to redo the maths though! That’s left as an exercise for the reader.
Ultrafilter - note this is why my solution has results for k < 5 - “3,2,1” is perfectly acceptable under my interpretation.
[/quote]
Now - I was playing with this last night trying to get a better formula (a task ultrafilter has shown was fruitless, despite my instinct. Incomplete gamma?!).
I did though consider what would happen if we weren’t dealing with a circle, but with a straight line instead. In this case, permutations would be k! rather than (k-1)!
The sum reworks to:
SUM((-1)[sup]n[/sup] * C(20,n) * (20-n)!)
= SUM((-1)[sup]n[/sup] * [20!/((20-n)! * n!)] * (20-n)!)
= 20! * SUM((-1)[sup]n[/sup] * 1/n!)
which approximates (since 20 is “large”) to
20! * e[sup]-1[/sup]
In general, for any large enough k, the result will be approximately k! * e[sup]-1[/sup]
Personally, I find this rather neat.
pan
[fixed coding]
[Edited by DrMatrix on 08-22-2001 at 04:40 AM]
Wow. You math guys have really been going at it. Quite cool.
As to the 4,5 - 5, 4 issue. Here’s the origin of the question:
I’m terrible at these kinds of games. I have no patience. My wife on the other hand, is quite good at them. I noticed she had solved the game by placing all the beads in order (btw, that means that 20 was followed by 1, since it is a circle.) I knew that I could never do the puzzle myself, but I could (and did) play around with it enough so that there were not even two consecutive numbers. And that got me thinking about the OP.
Now since I think that it doesn’t matter if the solution to the puzzle is clockwise or counter-clockwise (maybe that actually makes it two games), then neither 4-5 or 5-4 would work.
kabbes:
Cool! The notation on this board definitely does make it hard to read mathematics, but I see that our answers agree after all, which is always good. I just got home a little bit ago and plugged in my sum into Maple and got the same answer as you did (as you just mentioned). If there’s any precision freaks out there, the answer I got was actually 42,519,034,050,101,745 out of a possible 121,645,100,408,832,000, exactly. By the way, if you’re at all curious from the above stuff early on in the thread, I do have a math degree, and I picked Cabbage as my name here since that’s actually my real name (surname). Cool coincidence!
curwin:
I see now that my interpretation wasn’t quite what you intended, as far as whether the numbers have to be in order ((4,5) versus (5,4), for example). I’ll try to get around to that later today (or the following evening) if I have time (which I’m not certain of), and if no one else does it first. Considering it very briefly, I don’t think it’ll be very much more involved than what kabbes and I just did, but I do see one or two areas that could potentially end up being tricky, so I can’t be sure offhand.
Oh, by the way, about getting this sum into a closed form; I think ultrafilter was misinterpreting your sum, so I checked my sum with Maple to see what kind of form it would give me. Now, I am by no means a Maple expert, just basically know how to do the essentials, and I’m not familiar with all the notations it uses. Well…er…here’s what it gave me, cut and pasted:
(-1)^n+(n-1)!(GAMMA(1-n)+nGAMMA(-n,1))-sum((-1)^kbinomial(n,k)(n-1-k)!,k = n … n)+signum(exp(IPin))*infinity
I don’t even know what the hell that means. “…*infinity”??? I think maybe we ought to just be satisfied with the sum.
Here’s something else interesting I just came across. Consider the interpretation kabbes and I just used (where, for example, (5,4) and (1,20) are acceptable, and (4,5) and (20,1) are unacceptable). Say instead of 20 numbers we’re dealing with a circle of n consecutive numbers. Call the number of acceptable permutations (under kabbes and my interpretation) g[sub]n[/sub].
Also, let d[sub]n[/sub] be the number of derangements of the first n positive integers. A derangement is a permutation in which no integer appears in its natural position–so for example (2,3,1) is a derangement, but (3,2,1) is not, since the 2 appears in the 2nd position.
Now we have the following interesting relation:
g[sub]n[/sub] + g[sub]n+1[/sub] = d[sub]n[/sub]
Also interesting (and well known) is that
lim d[sub]n[/sub] / n! = 1/e
as n goes to infinity.
Might want to try the command “simplify(%)”, which takes the last result and attempts to simplify it. I’d do it myself, but the computer I have Maple on is going to lose internet access sometime this afternoon.