0
$\begingroup$

I am trying to find number of solutions to $2a+b\leq n$ for $a,b\geq 0$ given some $n\geq 0$.

Anyone have ideas? Maybe stars and bars? Thank you!

$\endgroup$
1
$\begingroup$

Generating function approach

It's the $n$th coefficient of the expansion of $$\frac{1}{(1-x)^2}\cdot \frac{1}{1-x^2}\tag{1}$$

Multiplying numerator and denominator by $(1+x)^2$ and you get:

$$\frac{(1+x)^2}{(1-x^2)^3} = (1+x)^2\sum_{k=0}^{\infty}\binom{k+2}{2}x^{2k}$$

So if $n=2m$ is even, then the coefficient of $x^{n}$ is $\binom{m+2}{2}+\binom{m}{2}$, and if $n=2m+1$ is odd, then the coefficient of $x^n$ is $2\binom{m+2}{2}$.

This can be written as: $$\left\lfloor \frac{(n+2)^2}{4}\right\rfloor$$

Or:

$$\frac{2n^2+8n+7}{8}+\frac{(-1)^n}{8}\tag{2}$$

You could also get this formula by doing partial fractions to write (1) as:

$$\frac{a}{(1-x)^3}+\frac{b}{(1-x)^2}+\frac{c}{1-x}+\frac{d}{1+x}$$

and then get the formula $a\binom{n+2}{2}+b\binom{n+1}{1}+c+d(-1)^n$.

Wolfram Alpha gives me $a=1/2,b=1/4,c=1/8,d=1/8$.

Formula (2) indicates a recursion:

$$a_{n+4}=2a_{n+3}-2a_{n+1}+a_n$$

Not sure if you can find a nice counting argument for that recursion.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Makes sense to me. Thank you! $\endgroup$ – Ryan Stodola Jan 16 '17 at 20:51
0
$\begingroup$

$a$ can be anything be anything between $0$ and $\lfloor n/2 \rfloor$ (inclusive;) and $b$ can be anything from $0$ to $n - 2a$.

So there are $\sum_{a=0}^{\lfloor n/2 \rfloor}\sum_{b= 0}^{n-2a}1$ solutions.

$\sum_{a=0}^{\lfloor n/2 \rfloor}\sum_{b= 0}^{n-2a}1=$

$\sum_{a=0}^{\lfloor n/2 \rfloor}(n - 2a + 1)=$

$(\lfloor n/2 \rfloor + 1)n + (\lfloor n/2 \rfloor + 1) - 2\sum_{a=0}^{\lfloor n/2 \rfloor}a=$

$(\lfloor n/2 \rfloor + 1)n + (\lfloor n/2 \rfloor + 1) -2\frac{\lfloor n/2 \rfloor (\lfloor n/2 \rfloor + 1)}2=$

$(\lfloor n/2 \rfloor + 1)(n - \lfloor n/2 \rfloor + 1)=$

$(\lfloor n/2 \rfloor + 1)(\lceil n/2 \rceil + 1)$

If $n$ is even this is $(n/2 + 1)^2$.

If $n$ is odd this is $(n/2 + 1/2)(n/2 + 1/2 + 1) = \frac{(n + 1)(n+3)}4$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You use $k$ when I think you mean $a$, and it should start at $a=0$. And $b$ can be anything from $0$ to $n-2a$. So it should be $$\sum_{a=0}^{\lfloor n/2\rfloor} (n-2a+1)=(n+1)(\lfloor n/2\rfloor+1)-\lfloor n/2\rfloor(\lfloor n/2\rfloor +1)=(\lfloor n/2\rfloor+1)(\lceil n/2\rceil +1)$$ $\endgroup$ – Thomas Andrews Jan 17 '17 at 14:36
  • $\begingroup$ Oh, I thought (probably incorrectly) that b and a had to be positive. and I did mean a. Well, actually I meant k and I meant to replace the a with a k because .... I was typing in a hurry and I was thinking of a as fixed and k can be the variables to represent the different fixed values of a.... Moral: Don't do math when your favorite tv show is just about to start. $\endgroup$ – fleablood Jan 17 '17 at 16:42
  • $\begingroup$ Um why $\sum (n-2a +1)$ rather than $\sum (n-2a)$? $\endgroup$ – fleablood Jan 17 '17 at 16:58
  • $\begingroup$ Because the number of values $b$ with $0\leq b\leq m$ is $m+1$. Same mistake - $b$ is allowed to be $0$. @fleablood $\endgroup$ – Thomas Andrews Jan 17 '17 at 17:13
  • $\begingroup$ b is allowed to be 0 (if n is even) but b = n-2a; not b = n-2a +1 and .... argh! $\endgroup$ – fleablood Jan 17 '17 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.