Bertie

Been away for a few days, but to continue ... .

Melody, N is the number of computers, k the number of peripherals, not the other way round.

To repeat what I said earlier,

if N>k (more computers than peripherals), there is no possible connection setup. A peripheral can be connected to just a single computer, so there are not enough peripherals to go round. In this case the formula returns a value of zero. A proof of this is in the next post.

If N=k then it's simply one peripheral to one computer. There are N! ways of doing this. The formula produces this value.

If N<k, (more peripherals than computers), two or more peripherals will be connected to one or more computers. There will be many ways of doing this and the formula (apparently) produces the number of possibles connection setups. I still don't have a proof of this, but I do have a verification for the 19,23 case. I shall post that later.

3*5*7*...*(2k-1)

= 2*3*4*5*6*7*...*(2k-2)*(2k-1) / (2*4*6*...*(2k-2))

= (2k-1)! / (2^(k-1)*1*2*3*...*(k-1))

= (2k-1)! / (2^(k-1)*(k-1)!)

Worse than double counting, multiple counting.

To illustrate why this method is wrong, consider an even simpler situation. Suppose that you have just four people and you want to split them into pairs. How many ways ?

If you employ the method used for the eight person problem, I guess that you would say that the number would be 4C2*2C2 = 6.

However, if you call the people A,B,C,D, you can see that there are only three possible pairings (AB and CD), (AC and BD) and (AD and BC). The basic reason why the first answer is wrong is that each grouping has been counted twice. (AB and CD) and (CD and AB), for example, are being thought of as being two different pairings, meaning that that particular pairing has been counted twice, if that makes sense. The 4C2 = 6 contains AB, AC, AD, BC, BD and CD, but both AB and CD produce the same split into two pairs.

Try the eight into four groups of two again.

Hi Chris and Melody, hope you don't mind me joining the conversation.

I'm with Chris on this one, I think that the 10080 is correct, (I've gone through the calculation in a different way and arrived at the same answer).

So, here's a question for Melody. Forget about rotations and seat positions for the moment, suppose that I have eight people and that I'm going to split them into four groups of two. In how many ways can this be done ?

Let's see If we can get agreement on that to begin with.

Small changes $$\delta x$$ and $$\delta y$$ in the x,y co-ordinates will bring about a small change $$\delta z$$ in the z co-ordinate given by

$$\delta z \approx \frac{\partial z}{\partial x}\delta x+ \frac{\partial z}{\partial y}\delta y.$$

So, $$\delta z \approx 4x \delta x - 6y \delta y.$$

We need $$\delta z$$ to be negative, in which case we need $$\delta x$$ to be negative and $$\delta y$$ to be positive. So, the move needs to be into the second quadrant of the xy plane.

If then we move a small distance $$h$$ at an angle $$\theta$$ to the negative x-axis, $$\delta x = -h\cos \theta,$$ and $$\delta y = h \sin \theta,$$ so $$\delta z \approx -h(8\cos\theta+6\sin\theta).$$

This will be a maximum when $$\tan \theta = 3/4$$ from which it follows that a vector in the required direction will be $$-4\hat{\imath}+3\hat{\jmath}$$ and a unit vector will be that divided by 5.

It's a truly brilliant formula, I'd quite happily buy a drink for the person that constructed it. Like Nauseated I've tried to find out where it comes from but without success.

Back to the question, (the original one with 19 computers and 23 peripherals). It's badly worded. It's true that each computer should be connected to a peripheral and that each peripheral should be connected to a computer, but there's more to it than that. What it should also say is that any of the computers can be connected to several peripherals if need be, but each peripheral can be connected to only one computer.

An immediate consequence of that is if there are more computers than peripherals then no connection setup is possible, we run out of peripherals. Miraculously, in these cases, the formula produces a zero result. (I have a proof of that, I don't have the time to post it at the moment, but I shall do it tomorrow night or possibly Wednesday morning (UK), assuming that no-one else does so in the meantime). That also answers one of Melody's questions, if N>k then the result is zero.

If N=k the formula produces the expected result N!

If N<k, there will be an excess of peripherals over computers and in this case one or more of the computers have to be connected to more than one peripheral. The formula produces the number of (the most economical) possible setups

Consider a simple case of 3 computers and 5 peripherals, (before dealing with the 19,23 problem). The possible connection setups are (1) one of the computers is connected to three of the peripherals and the other two computers connected to one peripheral each, and (2) two of the computers are connected to two peripherals each and the third computer to the remaining peripheral. Do the arithmetic and you find that there are 150 possible connection setups and that this is also the result produced by the formula.

Have to go now.

It should be pointed out that the "cross partial derivatives" are not always equal, but usually they are !

Hi Melody

I don't have an answer to this question yet, other than taking Nauseated's formula on trust, but I can tell you why your logic is wrong.

For your 5,3 setup, there will be times when one or even two of the printers have no computer connected to them at all, (at odds with the requirement).

Consider one of your possibilities, one where each of the five computers is connected to a single printer. Those connections could be to just two, or even just one of the printers. Those possibilities have to be subtracted from your total. The problem is how to count them.

This is known as Haberdasher's Problem.  A web search will get you the solution.

A search on Mathematical Disections gets further more general info.

I really like Chris's answer to this question, using the graph plotter makes life so much easier.

Here's the 'on paper' method that we had to use before these sophisticated plotters were available.

Let

$$7\cos12t+6\sin12t\equiv R\cos(12t-\alpha)=R\cos12t\cos\alpha+R\sin12t\sin\alpha,$$

then

$$R\cos\alpha=7 \text{ and } R\sin\alpha=6.$$

Squaring and adding,       $$R^{2}=7^{2}+6^{2}=85, \text{ so }R=\sqrt{85}.$$

Dividing,                         $$\tan\alpha = 6/7, \text{ so }\alpha = 0.7086 \text{ rad}.$$

We have then                 $$7\cos12t+6\sin12t=\sqrt{85}\cos(12t-0.7086)>9.$$

The maximum for the cosine occurs when 12t - 0.7086 = 0, that is, when t = 0.0591 (4dp, but I kept greater accuracy for all decimal values during the calculation).

For equality with the 9,           $$12t - 0.7086 = \cos^{-1}(9/\sqrt{85}),\quad t=0.0773.$$

It follows that the wave is greater than 9 for the time span 2(0.0773 - 0.0591) = 0.0364.

Since the period of the wave is 2pi/12, the proportion of the time that the wave is greater than 9 is

0.0364/(pi/6) = 0.0696, that is, about 7% (agreeing with Chris).

As an alternative, the form    $$R\sin(12t+\beta)$$    could have been chosen rather than the cosine.