## klimenkov Group Title How many natural solutions does this equation have? $x_1+x_2+\ldots+x_N=n$ one year ago one year ago

$N$

2. experimentX Group Title

is N<n ??

3. klimenkov Group Title

Very interesting answer, because doesn't depend on $$n$$.

is that a linear equation,$x+y+z=b$ how many solutions

5. klimenkov Group Title

@experimentX actually you can think that N≤n, and there are no solutions if N>n. But the final formula will consider it.

6. experimentX Group Title

|dw:1350212084534:dw|

7. asnaseer Group Title

if $$x_i$$ represents ANY real number, then there are an infinite number of solutions

8. experimentX Group Title

|dw:1350212197575:dw|

the problem is the difference between the solution of the equation and the solution set

10. klimenkov Group Title

@asnaseer I wrote in the statement of the problem that xi are natural.

11. experimentX Group Title

|dw:1350212336061:dw|

12. asnaseer Group Title

ah! ok - thanks for pointing that out.

|dw:1350180042769:dw|slution set implies tha t there are infinite solutions to the numbers $x _{1}+x _{2}=2$

(0,2) (2,0)\ (1,1)

i only see 3 positive ones

16. klimenkov Group Title

@Jonask zero is not a natural number.

17. experimentX Group Title

is it ?? $\binom {n+N-1}{n-N}$

18. asnaseer Group Title

@klimenkov are you saying that you know what the answer is and that it does NOT depend on n?

19. klimenkov Group Title

20. asnaseer Group Title

ok - that makes more sense now

21. klimenkov Group Title

@experimentX use your method to find the number of solutions for $$x_1=2$$.

23. experimentX Group Title

for n=N there should be 1 solutions. for n=N+1 there should be N solutions.

no constants (coeffecient)$\left[\begin{matrix}1& ...1\\ & \end{matrix}\right]=$

the coeffecient matrix

26. experimentX Group Title

n = N+2, $N + N(N-1)/2$

27. klimenkov Group Title

@experimentX for $$n=N+2$$ that is not right.

28. experimentX Group Title

huh .. isn't it $\binom{N}{1} + \binom{N}{2}$

29. estudier Group Title

"there are no solutions if N>n" x_1 + x_2 = 3 (answer 1 +2) Am I missing something?

30. experimentX Group Title

another un/lucky guess$\left(\begin{matrix}n-1 \\ n-N\end{matrix}\right)$

31. klimenkov Group Title

@experimentX very close, but not right. Hope you will get it!

32. klimenkov Group Title

@estudier in your case N=2, n=3 N<n.

33. estudier Group Title

Ah, backwards ...duh!:-)

34. experimentX Group Title

35. experimentX Group Title

is that correct?

36. asnaseer Group Title

After playing around with this for a while I /think/ the Fibonacci sequence is involved in the answer - or am I wildly off?

37. sauravshakya Group Title

N=n --->1 N=n-1-->1 N=n-2--->2 N=n-3--->3

38. sauravshakya Group Title

N=1 --->1 N=n/2 if n is even and (n-1)/2 if n is odd

39. klimenkov Group Title

40. asnaseer Group Title

I am getting something along the lines of:$1+F(x)$where x is some function of n and N and F(x) is the x'th Fibonacci number

41. sauravshakya Group Title

That was only for n>5

42. estudier Group Title

Binomial coefficient, is it?

43. sauravshakya Group Title

@experimentX and @estudier I think question is related to the necklace question... right?

44. asnaseer Group Title

is it:$1+F(N-n-2)$

45. estudier Group Title

N-1,n-1

46. experimentX Group Title

$\binom{n-1}{N-1} = \left(\begin{matrix}N+2-1 \\ N-1\end{matrix}\right) = \binom{N+1}{N-1} = {(N+1)N \over 2}$ both seems to be equal here on this particular case. $\binom{N}{1} + \binom{N}{2} = N + {N(N-1) \over 2} = {N(N+1) \over 2}$

47. asnaseer Group Title

sorry, that should be:$1+F(n-N-2)$

48. experimentX Group Title

@sauravshakya kind ov

49. asnaseer Group Title

that is for n>N+2

50. klimenkov Group Title

51. estudier Group Title

Stars and Bars ex 0 -> (N-1 n-1)

52. asnaseer Group Title

Wait - I made a small mistake, I believe it should be:$1+F(n-N)$And no problem @klimenkov - please take your time to check - this is a very interesting problem. :)

53. sauravshakya Group Title

@klimenkov I know there must be a pattern but I dont think it is Fibonacci

54. klimenkov Group Title

I know the answer and it doesn't equal to Fibonacci number +1. Write the way you think @asnaseer

55. asnaseer Group Title

These were my thoughts: |dw:1350214566420:dw|

56. klimenkov Group Title

My English is not too good. But I think @estudier should be given Best response.

57. asnaseer Group Title

Looking at this again, it looks more like:$F(n-N)+F(n-N-1)+...+F(1)$

58. asnaseer Group Title

@estudier I did not understand what you meant by: Stars and Bars ex 0 -> (N-1 n-1)

59. klimenkov Group Title
60. experimentX Group Title

for n=6 and N=3, the answer is 10 ... this seems to work out http://www.wolframalpha.com/input/?i=Binomial[n%2B2%2C+n-1]+where+n%3D3

61. estudier Group Title

Stars and Bars is combinatorics speak for putting N objects into n bins so that all bins contain at least one object.

62. asnaseer Group Title

Oh I see - thanks for clarifying.

63. estudier Group Title

The idea of linking binomial coefficient with Fibonacci is interesting....

64. experimentX Group Title

shouldn't this be like this (N-1 n-1) -> (n-1 N-1) ??

65. klimenkov Group Title

@experimentX yes. The answer is $$\left(\begin{matrix}n-1 \\ N-1\end{matrix}\right)$$. Who will prove it?

66. experimentX Group Title

that and this are equivalent $\left(\begin{matrix}n-1 \\ n-N\end{matrix}\right)$

67. estudier Group Title

Can we use k and n, I am getting very confused:-)

68. klimenkov Group Title

Shame on me. Somebody clear my Smartscore...

69. asnaseer Group Title

:)

70. experimentX Group Title

71. klimenkov Group Title

@experimentX was right since the very beginning.

72. asnaseer Group Title

I don't understand how this can be correct. Take the n=5 and we will get:$\frac{4!}{(4-N)!(N-1)!}$then we get: N=1, Ans=4 N=2, Ans=12 Or have a misread the solution?

73. estudier Group Title

For positive n, k the number of different n-tuples (ex 0) with sum k is (k-1,n-1)

74. klimenkov Group Title

@asnaseer $\left(\begin{matrix}5-1 \\ N-1\end{matrix}\right)=\frac{ 4! }{ (5-N)!(N-1)! }$

75. asnaseer Group Title

D'oh! Now I think its time for someone to take my smartscore away! :)

76. klimenkov Group Title

Did anyone get this? Why does this formula give the right result?

77. estudier Group Title

Maybe an example helps to see it Seven identical coins between three people (k=7, n = 3) so (6,2) is 15 possible ways

78. estudier Group Title

There is a proof on page 12 of http://www.ma.utexas.edu/users/geir/teaching/m390c/lecturenotes.pdf

79. experimentX Group Title

thanks estudier for sharing!!

80. estudier Group Title

yw:-)

81. asnaseer Group Title

I also extends my thanks to estudier. :)