3

Is there any general formula for the following problem? (Repetition of numbers is allowed).

How many ways can $n$ numbers be chosen, each of which is between $1$ and $m$, such that the sum of the $n$ numbers equals $k$?

amWhy
  • 209,954
Goku95
  • 41
  • Look at "generalized partitions" – Peter Dec 01 '16 at 21:56
  • @Peter are u talking about generalized partitions of graphs? – Goku95 Dec 01 '16 at 21:59
  • 2
    Graphs are unrelated. An easy way to see the answer if you have calculator software handy is to look at the coefficient of $x^k$ in the expansion of $(x+x^2+x^3+\dots+x^m)^n$ – JMoravitz Dec 01 '16 at 22:00
  • No, partitions are sets of numbers summing up to a given number, for example the partitions of $5$ are $5=4+1=3+2=3+1+1=2+2+1=2+1+1+1=1+1+1+1+1$ – Peter Dec 01 '16 at 22:00
  • @JMoravitz This is sufficient to determine the number of (generalized) partitions ? – Peter Dec 01 '16 at 22:02
  • So, a question I would have is whether you allow order of the numbers to matter, or if the numbers must all be in descending order. If order of numbers matter, in addition to the partitions @Peter mentions you would also have each of the above in their alternate orderings, $1+4, 2+3, 1+3+1, 1+1+3,\dots$ as well – JMoravitz Dec 01 '16 at 22:02
  • 1
    @Peter the generating function I mention would indeed count the number of integer solutions to $x_1+x_2+\dots+x_n = k$ where $1\leq x_i\leq m$ for all $i$., noting that in my interpretation, $(3,1,1)$ is considered a different outcome than $(1,3,1)$ – JMoravitz Dec 01 '16 at 22:03
  • @JMoravitz OK, I understand. – Peter Dec 01 '16 at 22:04
  • then for n=4 ,m=5, k=10, what should be the answer? – Goku95 Dec 01 '16 at 22:05
  • @Goku95 The coefficient of $x^{10}$ in $(x+x^2+x^3+x^4+x^5)^4$ – JMoravitz Dec 01 '16 at 22:08
  • Somewhat related, where $m$ is $9$ (and lower limit is $0$): http://math.stackexchange.com/questions/2007216/how-many-different-possible-permutations-are-there-with-k-digits-that-add-up-to/2007311#2007311 – Joffan Dec 01 '16 at 23:36

0 Answers0