From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Permutation Problem!! Date: 2 Sep 1995 01:12:08 GMT In article <425tho$4le@cantua.canterbury.ac.nz>, Robert van Nobelen wrote: >I'm trying to find a general formulas for the number of ways N ordered >whole numbers, each no greater than N, add up to N^2-N. (In the examples he makes it clear he means _non-negative_ integers, with repeats of the summands permissible and order of the summands relevant). Imagine the numbers to be counting the balls in N bins. You've got to place some balls into each bin in such a way that the total count be N^2-N. You don't want more than N in any bin. Very well, start with N in each bin (total: N^2) and remove N balls (from any bins. Because of the constraints you gave us, I don't even have to worry about what would happen if I tried to remove more balls from any one bin than I started with.) Therefore, the patterns are in one-to-one correspondence with the "removal instructions", each of which may be represented by a picture showing a circle "o" for each ball to remove, surrounded by the walls "|" separating the bins. For example, (when N=5) you can remove 3 balls by removing 1 ball from bin 2, 2 balls from each of bins 4 and 5, and no balls from the others: | | o | | o o | o o | This represents the presentation 5 + 4 + 5 + 3 + 3 = 5^2-5. To enumerate all arrangements, you need to think about the number of ways of arranging N "o" 's and N+1 "|"'s in a line, starting and ending with a "|". The way to do this is to think about (N + N-1) slots, of which N-1 are to be filled with "|"'s. There are (N+N-1) choose N-1 ways to do this. So the number you want is (2N - 1) choose (N-1). For example, when N=4, this gives 7 choose 3 = 7*6*5/3*2*1 = 35, in agreement with your observation. This is a classic combinatorial argument. dave