# math question

**URL:** <https://boards.straightdope.com/t/math-question/77167>\
**Category:** Factual Questions\
**Created:** [August 20, 2001, 4:27pm UTC](https://boards.straightdope.com/t/math-question/77167 "2001-08-20T16:27:37Z")\
**Posts on this page:** 20\
**Page:** 3

<div class="post-metadata">

**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\
**Post date:** [August 22, 2001, 3:07pm UTC](https://boards.straightdope.com/t/math-question/77167/41 "2001-08-22T15:07:20Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [August 22, 2001, 3:10pm UTC](https://boards.straightdope.com/t/math-question/77167/42 "2001-08-22T15:10:06Z")

</div>

> [@](#):
>
> \*Originally posted by Cabbage \*  
> \*\*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. 🙂

---

<div class="post-metadata">

**Author:** ![DaveW](https://avatars.discourse-cdn.com/v4/letter/d/9d8465/32.png) [@DaveW](https://boards.straightdope.com/u/DaveW)\
**Post date:** [August 22, 2001, 3:17pm UTC](https://boards.straightdope.com/t/math-question/77167/43 "2001-08-22T15:17:06Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\
**Post date:** [August 22, 2001, 3:38pm UTC](https://boards.straightdope.com/t/math-question/77167/44 "2001-08-22T15:38:32Z")

</div>

**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!]

---

<div class="post-metadata">

**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\
**Post date:** [August 22, 2001, 3:42pm UTC](https://boards.straightdope.com/t/math-question/77167/45 "2001-08-22T15:42:29Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![muttrox](https://avatars.discourse-cdn.com/v4/letter/m/a8b319/32.png) [@muttrox](https://boards.straightdope.com/u/muttrox)\
**Post date:** [August 22, 2001, 3:53pm UTC](https://boards.straightdope.com/t/math-question/77167/46 "2001-08-22T15:53:33Z")

</div>

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](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.

---

<div class="post-metadata">

**Author:** ![DaveW](https://avatars.discourse-cdn.com/v4/letter/d/9d8465/32.png) [@DaveW](https://boards.straightdope.com/u/DaveW)\
**Post date:** [August 22, 2001, 5:30pm UTC](https://boards.straightdope.com/t/math-question/77167/47 "2001-08-22T17:30:01Z")

</div>

_ **Cabbage explains things** _

Thanks!

So, when **kabbes** wrote:

> [@](#):
>
> Now my sum, using the same notation, is:
> 
> 19! - SUM[(-1)n+1 \* C(20,n) \* (20-n-1)!]
> 
> where the sum goes from 1 to 20.

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: 1_5_6, or 30  
n=2: -1_10_2, or -20  
n=3: 1_10_1, or 10  
n=4: -1_5_1 (assuming that 0! is 1), or -5  
n=5: 1_1_1, 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? 🙂

---

<div class="post-metadata">

**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\
**Post date:** [August 22, 2001, 7:10pm UTC](https://boards.straightdope.com/t/math-question/77167/48 "2001-08-22T19:10:40Z")

</div>

**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.

---

<div class="post-metadata">

**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\
**Post date:** [August 23, 2001, 4:55am UTC](https://boards.straightdope.com/t/math-question/77167/49 "2001-08-23T04:55:48Z")

</div>

> [@](#):
>
> (-1)^n+(n-1)!_(GAMMA(1-n)+n_GAMMA(-n,1))-sum((-1)^k_binomial(n,k)_(n-1-k)!,k = n … n)+signum(exp(I_Pi_n))\*infinity

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

```auto

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.

---

<div class="post-metadata">

**Author:** ![astro](https://avatars.discourse-cdn.com/v4/letter/a/9dc877/32.png) [@astro](https://boards.straightdope.com/u/astro)\
**Post date:** [August 23, 2001, 5:25am UTC](https://boards.straightdope.com/t/math-question/77167/50 "2001-08-23T05:25:24Z")

</div>

> [@](#):
>
> \*Originally posted by Chronos \*  
> \*\*
> 
> > [@](#):
> >
> > (-1)^n+(n-1)!_(GAMMA(1-n)+n_GAMMA(-n,1))-sum((-1)^k_binomial(n,k)_(n-1-k)!,k = n … n)+signum(exp(I_Pi_n))\*infinity
> 
> 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
> 
> ```auto
> 
> 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.

---

<div class="post-metadata">

**Author:** ![kabbes](https://avatars.discourse-cdn.com/v4/letter/k/e99b99/32.png) [@kabbes](https://boards.straightdope.com/u/kabbes)\
**Post date:** [August 24, 2001, 8:09am UTC](https://boards.straightdope.com/t/math-question/77167/51 "2001-08-24T08:09:18Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Richard](https://avatars.discourse-cdn.com/v4/letter/r/f0a364/32.png) [@Richard](https://boards.straightdope.com/u/Richard)\
**Post date:** [August 24, 2001, 1:59pm UTC](https://boards.straightdope.com/t/math-question/77167/52 "2001-08-24T13:59:47Z")

</div>

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)^k_binomial(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)(2_a(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.

---

<div class="post-metadata">

**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\
**Post date:** [August 24, 2001, 2:44pm UTC](https://boards.straightdope.com/t/math-question/77167/53 "2001-08-24T14:44:57Z")

</div>

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:

1. If you remove the number n, you get a proper n-1 circle. These are easy to account for.

2. 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!

---

<div class="post-metadata">

**Author:** ![DaveW](https://avatars.discourse-cdn.com/v4/letter/d/9d8465/32.png) [@DaveW](https://boards.straightdope.com/u/DaveW)\
**Post date:** [August 24, 2001, 3:24pm UTC](https://boards.straightdope.com/t/math-question/77167/54 "2001-08-24T15:24:57Z")

</div>

**kabbes** wrote:

> [@](#):
>
> 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

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.

---

<div class="post-metadata">

**Author:** ![RTFirefly](https://avatars.discourse-cdn.com/v4/letter/r/c77e96/32.png) [@RTFirefly](https://boards.straightdope.com/u/RTFirefly)\
**Post date:** [August 24, 2001, 5:25pm UTC](https://boards.straightdope.com/t/math-question/77167/55 "2001-08-24T17:25:14Z")

</div>

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]\*\*).

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [August 24, 2001, 6:30pm UTC](https://boards.straightdope.com/t/math-question/77167/56 "2001-08-24T18:30:36Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![RTFirefly](https://avatars.discourse-cdn.com/v4/letter/r/c77e96/32.png) [@RTFirefly](https://boards.straightdope.com/u/RTFirefly)\
**Post date:** [August 24, 2001, 6:41pm UTC](https://boards.straightdope.com/t/math-question/77167/57 "2001-08-24T18:41:55Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![RTFirefly](https://avatars.discourse-cdn.com/v4/letter/r/c77e96/32.png) [@RTFirefly](https://boards.straightdope.com/u/RTFirefly)\
**Post date:** [August 24, 2001, 7:00pm UTC](https://boards.straightdope.com/t/math-question/77167/58 "2001-08-24T19:00:35Z")

</div>

**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.

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [August 24, 2001, 7:04pm UTC](https://boards.straightdope.com/t/math-question/77167/59 "2001-08-24T19:04:23Z")

</div>

> [@](#):
>
> \*Originally posted by RTFirefly \*  
> \*\ ***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.

---

<div class="post-metadata">

**Author:** ![DaveW](https://avatars.discourse-cdn.com/v4/letter/d/9d8465/32.png) [@DaveW](https://boards.straightdope.com/u/DaveW)\
**Post date:** [August 24, 2001, 7:16pm UTC](https://boards.straightdope.com/t/math-question/77167/60 "2001-08-24T19:16:19Z")

</div>

**RTFrefly** wrote:

> [@](#):
>
> 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?

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]

[Previous page](https://boards.straightdope.com/t/math-question/77167.md?page=2)

[Next page](https://boards.straightdope.com/t/math-question/77167.md?page=4)