This is a continuation of an earlier counting question that Nauseated and Geno answered.

This formula is rare. I have yet to find it after searching several statistical and combinatorics sites. I am sure it is on the web somewhere. How do you search for a formula that does not have a name?

This formula was given to me years ago by a classmate. I am unsure if he found it in a publication or independently discovered it –he definitely had the math skills to do that. I wrote a Fortran program to test it. All the tests demonstrated (not proved) it distributes the counts such that N contains at least one (or more) k elements.

I’ll continue to look for the theory behind this formula, either on the web or by dissecting it. It looks very similar to the Binomial CDF that should give a starting point.

How do you know which number is N and which one is k. Should N be the smallest one, it was for your other example.

Yes, the (k) has to be equal to or greater than the (N). The (i) functions as the k in the binomial.

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.

Thanks Bertie,

I just want to look at this simlified scenario,

5 computers 3 printers.

Now it seems to me that the number of ways any computer can be net worked to printers is as follows:

any one printer+ any 2 printers+ all three printers = 3C1+3C2+3C3 = 3+3+1 = 7 ways

There are 5 computers so the number of ways is   $${{\mathtt{7}}}^{{\mathtt{5}}} = {\mathtt{16\,807}}$$

Ok so here every computer is connected to at least one printer BUT for some of these outcomes 1 or more computers are not connected to any printer.  So some of these outcomes are invalid.  The number is too big.

IS THAT STATEMENT CORRECT BERTIE?  Perhaps i see a glimmer of light.  :/

-------------------------------------------------------

What was your formula Nauseated? 

$$\displaystyle \sum \limits_{i=0}^{\textcolor[rgb]{1,0,0}{N-1}} *(-1)^i*\binom{N}{i}* (N-i)^k$$

The solution to this is found using this formula. k = number of computers and N = number of peripheral graphics devices.    N=3,    k=5

$$\displaystyle \sum \limits_{i=0}^{\textcolor[rgb]{1,0,0}{3-1}} *(-1)^i*\binom{3}{i}* (3-i)^5 \hspace{15pt}| \hspace{15pt} \Text {N=3 \; k=5} \\\$$                           k is the big one

I have a question for you too Nauseated :)

How do you know which number is N and which one is k.   Should N be the smallest one, it was for your other example.   If that is so then I have the 5 and 3 around the wrong way here.

PLUS Nauseated, I just realised that you used some LaTex that I didn't know. \binom{5}{i}  also \hspace {15}

Thanks for that - I will add it to our very disorganised LaTex thread.  :))

Thanks Nauseated:)

Sorry Bertie, somehow I overlooked giving you points - I have rectified this oversite now.  :)

I really appreciate you helping me improve my probability abilities :)

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.

I am still thinking about this formual

$$\displaystyle \sum \limits_{i=0}^{\textcolor[rgb]{1,0,0}{N-1}} *(-1)^i*\binom{N}{i}* (N-i)^k$$

So k could be computers and N peripherals where each peripheral is attached to exactly one computer but each computer can be attached to one or more peripherals.

So the number of computers (k) must be greater or equal to the number of peripherals (N)

If there are 5 computers and 3 peripherals then

$$\\\displaystyle \sum \limits_{i=0}^{\textcolor[rgb]{1,0,0}{3-1}} *(-1)^i*\binom{3}{i}* (3-i)^5 \\\\\\
=\binom{3}{0}*3^5\hspace{15pt}+(-1)^1*\binom{3}{1}*(3-1)^5
\hspace{15pt}+(-1)^2*\binom{3}{2}*(3-2)^5\\\\
=243\hspace{15pt}+-1*3*32\hspace{15pt}+3\\\\
=243-96+3\\\\
=150 ways$$

Mmm I wonder if that is correct?      (both the formula and my arithmetic)   

It is an odd formula.  That minus sign is really strange.   :/

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.

$$\\\displaystyle \sum^{N-1}_{\imath=0}(-1)^{\imath}\left(\begin{array}{c} N \\ \imath\end{array} \right)(N-\imath)^{k}.$$

The object of the exercise is to show that this is equal to zero if N>k and equal to N! if N=k.

Begin with

$$(x-y)^{N}=\left(\begin{array}{c} N \\ 0 \end{array} \right)x^{N}-\left(\begin{array}{c} N \\ 1 \end{array} \right)x^{N-1}y+\left(\begin{array}{c} N \\ 2 \end{array} \right)x^{N-2}y^{2}- \dots (-1)^{N}\left(\begin{array}{c} N \\ N \end{array} \right)y^{N}=\displaystyle \sum^{N-1}_{\imath=0}(-1)^{\imath}\left(\begin{array}{c} N \\ \imath\end{array} \right)x^{N-\imath}y^{\imath}$$

Differentiating this wrt x,

$$N(x-y)^{N-1}=\displaystyle \sum^{N-1}_{\imath=0}(-1)^{\imath}\left(\begin{array}{c} N \\ \imath\end{array} \right)(N-\imath)x^{N-\imath-1}y^{\imath}..............(1)$$

and substituting x =  y = 1,

$$0=\displaystyle \sum^{N-1}_{\imath=0}(-1)^{\imath}\left(\begin{array}{c} N \\ \imath\end{array} \right)(N-\imath)$$                 This proves the result for k = 1.

Multiplying (1) by x and differentiating again,

$$N(x-y)^{N-1}+N(N-1)x(x-y)^{N-2}=\displaystyle \sum^{N-1}_{\imath=0}(-1)^{\imath}\left(\begin{array}{c} N \\ \imath\end{array} \right)(N-\imath)^{2}x^{N-\imath-1}y^{\imath}..............(2)$$

and substituting x = y = 1,

$$0=\displaystyle \sum^{N-1}_{\imath=0}(-1)^{\imath}\left(\begin{array}{c} N \\ \imath\end{array} \right)(N-\imath)^{2}$$ which is the result for k=2.

Proceeding in this way, (multiply by x, differentiate wrt x and substitute x = y = 1), gets the results for k = 3 ,4,...,  until we arrive at k = N. For that, we find

$$\text{ (a whole load of terms, each containing the factor (x-y))} +N!x=\displaystyle \sum^{N-1}_{\imath=0}(-1)^{\imath}\left(\begin{array}{c} N \\ \imath\end{array} \right)(N-\imath)^{N}x^{N-\imath-1}y^{\imath}$$

And now, putting x = y = 1,

$$N!=\displaystyle \sum^{N-1}_{\imath=0}(-1)^{\imath}\left(\begin{array}{c} N \\ \imath\end{array} \right)(N-\imath)^{N}$$ which is the N=k result.

Here's a verification of the original 19 computer 23 peripheral problem.

The 19 computers are each going to have a peripheral assigned to them, the remaining 4 peripherals can be assigned as (1) all 4 to a single computer, (2) 2 to one computer and 2 to another, (3) 3 to one computer and 1 to another, (4) 2 to one computer and the other 2 to a computer each, (5) each one of the 4 to a single computer.

The number of connection setups for each of these is as follows.

(1) 23C5*19! = 33649*19!

(2) 23C3*20C3*19! / 2! = 1009470*19!

(3) 23C4*19C2*19! = 1514205*19!

(4) 23C3*20C2*18C2*19! / 2! = 25741485*19!

(5) 23C2*21C2*19C2*17C2*19! / 4! = 51482970*19!

Add those together and you get 79781779*19! = 9,705,062,517,250,244,272,128,000 which is the original answer as stated.

I've confirmed that this is the number given by the formula, (but I still don't know how it does it). Maybe later ?

Thanks Bertie,

This is another that I would like to spend more time on as well. :)

So here is about this question. My professor explain me this question is put on practice assignments although the book do not show how to do them. The question and answer is given to maybe find students that have a understanding of advanced maths. They do not expect that most will show the proper workings how to find a solution for the question.

When a student does show proper workings then the professors will consider maybe this student is very excellent at maths and give him or her more tests and special instruction. Though I tell them where I find the answer they still give me the test and they find out I am not very excellent at maths. When the score for the test came to my professor’s attention, he make a big joke and said Bertie and Nauseated made a good score but I did not. Bertie and Nauseated I thought might like to know. Hahahaha

Thank you for all your help!

Thanks Squareroot,

I am sure that Bertie and Nauseated will both be very pleased about your professor's assessment as well as pleased about your acknowledgement of their skill and your 'thank you' .