## klimenkov 2 years ago How many natural solutions does this equation have? $x_1+x_2+\ldots+x_N=n$

$N$

2. experimentX

is N<n ??

3. klimenkov

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

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

5. klimenkov

@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

|dw:1350212084534:dw|

7. asnaseer

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

8. experimentX

|dw:1350212197575:dw|

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

10. klimenkov

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

11. experimentX

|dw:1350212336061:dw|

12. asnaseer

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

@Jonask zero is not a natural number.

17. experimentX

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

18. asnaseer

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

19. klimenkov

20. asnaseer

ok - that makes more sense now

21. klimenkov

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

23. experimentX

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

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

27. klimenkov

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

28. experimentX

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

29. estudier

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

30. experimentX

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

31. klimenkov

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

32. klimenkov

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

33. estudier

Ah, backwards ...duh!:-)

34. experimentX

35. experimentX

is that correct?

36. asnaseer

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

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

38. sauravshakya

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

39. klimenkov

40. asnaseer

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

That was only for n>5

42. estudier

Binomial coefficient, is it?

43. sauravshakya

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

44. asnaseer

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

45. estudier

N-1,n-1

46. experimentX

$\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

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

48. experimentX

@sauravshakya kind ov

49. asnaseer

that is for n>N+2

50. klimenkov

51. estudier

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

52. asnaseer

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

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

54. klimenkov

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

55. asnaseer

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

56. klimenkov

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

57. asnaseer

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

58. asnaseer

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

59. klimenkov
60. experimentX

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

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

62. asnaseer

Oh I see - thanks for clarifying.

63. estudier

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

64. experimentX

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

65. klimenkov

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

66. experimentX

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

67. estudier

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

68. klimenkov

Shame on me. Somebody clear my Smartscore...

69. asnaseer

:)

70. experimentX

71. klimenkov

@experimentX was right since the very beginning.

72. asnaseer

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

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

74. klimenkov

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

75. asnaseer

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

76. klimenkov

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

77. estudier

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

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

79. experimentX

thanks estudier for sharing!!

80. estudier

yw:-)

81. asnaseer

I also extends my thanks to estudier. :)