Question

a+b+c+d=n

For integers 0 and greater, how many solutions are there for a given n?

Answer 1

I'm new here

Answer 2

but..

Answer 3

I would like to understand how to do this.

Answer 4

With \(n\) stars and \(3\) bars, there will be \(\dbinom{n+3}{3}\) solutions

Answer 5

Nice, I never learned the stars and bars way, so I had to find a different way to the answer. :P

Answer 6

I'd love to see how you work it w/o stars and bars...

Answer 7

I realized that if I took all the possible numbers and multiplied geometric series together like this, we'd have coefficients out front that count the number of ways to get that sum.
\[x^a x^b x^c x^d = x^{a+b+c+d}\]

So to do that, I'm basically saying \(f(n)\) is my answer:

\[\sum_{n=0}^\infty f(n)x^n = \left( \sum_{n=0}^\infty x^n \right)^4\]

I didn't really know how to multiply that out, seemed difficult but I figured this out pretty quick:

\[ \left( \frac{1}{1-x} \right)^k = \frac{1}{(k-1)!} \frac{d^{k-1}}{dx^{k-1}}\left( \frac{1}{1-x} \right)\]

So that turned this into a pretty straightforward problem, since the derivatives of polynomials is simple:

\[\sum_{n=0}^\infty f(n)x^n = \frac{1}{3!} \frac{d^{3}}{dx^{3}}\left( \sum_{n=0}^\infty x^n \right) = \sum_{n=0}^\infty \frac{(n+3)(n+2)(n+1)}{6} x^n\]

\[f(n) = \frac{(n+3)(n+2)(n+1)}{6} = \binom{n+3}{3}\]

So pretty fun, I'm gonna try to read up on stars and bars and see if it's similar in any way to this.

Answer 8

I'm not gonna lie, I'm actually pretty confused by the stars and bars method, I think I drank too much coffee and can't focus on the words right now haha so I'll have to learn that way some other time I think.

Answer 9

Your method can be used to work these type of problems with constraints too

Answer 10

For example,

Find the integer solutions to \(a + b + c + d = n\)

where
\(-2\le a\lt 5\)
\(3\le b\lt 7\)
\(0\le c,d\)

Answer 11

I didn't think of that bu now that you've got me thinking, if we have fixed constants r and s, how many solutions are there to:

\(ar+bs=n\)

Just amounts to replacing x with \(x^r\) and \(x^s \)in the generating function

Answer 12

Would that equation have solutions only if \(\gcd(r,s)\mid n\) ?

Answer 13

I don't know, I don't think so, I am not sure so I'll just state it as clearly as I can:

r,s, and n are constant integers (let's say greater than or equal to 0 for now, not sure if this applies in the negative case) then I'm asking how many ways can I choose a and b to make this true:

\[ar+bs=n\]

Answer 14

\[(1+x^r + x^{2r}+\cdots )(1+x^s + x^{2s}+\cdots )\]

The exponents add up to \(n\) only when \(\gcd(r,s)\mid n\) right ?

Answer 15

so the equation \(ar+bs=n\) need not have solutions for arbitrary \(r,s,n\)

Answer 16

Yeah, that last thing you said is true, the gcd statement is confusing me. But yes, there's nothing wrong with having 0 coefficient since there would be 0 ways of making some combinations yes, like r=3, s=5, n= 2 for instance

Answer 17

It is a diophantine equation, it can have infinite "nonnegative" solutions too

Answer 18

r = 3, x = -5, n = 2

Answer 19

It can't infinite solutions, at least in the way I've phrased it here since n is fixed, it's a finite number. So if you're only adding up positive numbers you'll eventually get "too big", well hre's the generating function anyways:

\[\left( \sum_{a=0}^\infty x^{ar} \right) \left( \sum_{b=0}^\infty x^{bs} \right) = \sum_{n=0}^\infty f(n) x^n \]

Answer 20

right, solutions will be finite if \(r\) and \(s\) are nonnegative

Answer 21

I just haven't really thought about it before so I'm thinking about what negative exponents will do right now trying to figure stuff out.

Answer 22

This is weird, I am not sure what is going on with this:

\[\sum_{n=0}^\infty x^{-n} = \frac{1}{1-x^{-1}} = -x \frac{1}{1-x} = -x \sum_{n=0}^\infty x^n \]

Answer 23

\(\dfrac{1}{x}\lt 1 \implies x \gt 1\)

so only one of the series is convergent

Answer 24

Heh, I wonder if that matters for formal power series though. Convergence is not necessary to use formal power series, so I wonder if this can still get useful results.

Answer 25

aren't we messing with below kindof stuff ?
\[\dfrac{1}{1-2} = \sum\limits_{n=0}^{\infty}2^n\]

Answer 26

\[\sum_{n=0}^\infty 2^{-n} = \frac{1}{1-2^{-1}} = -2 \frac{1}{1-2} = -2 \sum_{n=0}^\infty 2^n\]

Answer 27

im not feeling comfortable haha

Answer 28

Hahaha well that's not true I am sure, but if you have some function attached I think it might make sense. We're no really concerned with "what's x?". I never even used x when I solved the original problem I asked, I pretty much just used it as a vehicle to combine my terms in the way I want, at no point did its convergence really matter.