Path: utzoo!attcan!utgpu!news-server.csri.toronto.edu!rutgers!sun-barr!cs.utexas.edu!usc!wuarchive!uunet!brunix!wcn
From: wcn@cs.brown.edu (Wen-Chun Ni)
Newsgroups: comp.theory
Subject: Re:partitioning problem
Message-ID: <58269@brunix.UUCP>
Date: 2 Dec 90 17:10:36 GMT
Sender: news@brunix.UUCP
Reply-To: wcn@cs.brown.edu (Wen-Chun Ni)
Organization: Brown University Department of Computer Science
Lines: 42


I originally sent the following solution to the person asking
the question. But I think it is necessary to let the public
know what it is.

------------------ Solution



If I do not misinterpret your problem, the problem is in fact
easier than the original one. No recurrence is required, and
the answer is k^n/k!.

From generating function, n!S(n,k) is the coefficient of x^n in
	(exp(x)-1)^k/k!,
but the function of your answer is 
	(exp(x))^k/k!.
You may refer to Liu's introductory book for such interpretations.
You can also get just k^n if you consider the groups are labelled,
but the generating function is another story.

Somebody (I deleted it from my file) answered this question by posing 
an incorret answer: sum(for i=1 to k) S(n,i). 
	 



  Wen-Chun Ni: Department of Computer Science   
	       Brown University,               (H) (401) 2723615
	       Providence, RI 02912            (O) (401) 8637668
  ________________________________________________________________

      *   *                    I'm quite sure if God were asked
     *   *      *              to draw up a programme of the world
    **   ***  ***              he had created, he could never do it.
   * *   *      *                           
  *  *   ********                  -- Mahler to Alma, 15th Dec 1901
     *     *  *                 
     *     *  *                     in description of 2nd Symphony
     *    *   *  *                                  "Resurrection."
     *   *    ****
  ________________________________________________________________


Brought to you by Super Global Mega Corp .com