Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

So, I guess divide it into six sections representing the difference between the numbers, so the first is $0\rightarrow n$, the second through fifth are $1\rightarrow n$ and the sixth is $0\rightarrow n$ again, and that becomes a generating function of $((1+x+x^2+\cdots+x^n)^2)((x^2+\cdots+x^n)^4)$. Does this make sense, and what coefficient represents what value of $n$?

share|improve this question
    
The answer shouldn't be in terms of n; you want a single fixed function f(x) such that the coefficient of x^n is the number you want (for n). Also, is this homework? –  Qiaochu Yuan Dec 4 '10 at 18:55
    
Er, maybe that series is infinite –  Tony B Dec 4 '10 at 19:00
    
So it's really $x^8/(1-x)^6$, though this is actually off-by-one and should be $x^9/(1-x)^6$ (consider that the first non-zero combination is $1,3,5,7,9$). –  Yuval Filmus Dec 4 '10 at 19:24
    
You've got the right idea with dividing it into six sections, and your answer is almost the same as the book's. But do you really need that n in there? –  Qiaochu Yuan Dec 4 '10 at 19:28

2 Answers 2

up vote 0 down vote accepted

Let $f_{k,n}$ be the number of ways to select $k$ integers in $\{ 1, 2, ... n \}$ such that no two are consecutive. There are two ways to do this: either the largest one is not $n$, and then you choose $k$ integers in $\{ 1, 2, ... n-1 \}$, or the largest one is $n$, and then you choose $k-1$ integers in $\{ 1, 2, ... n-2 \}$. This gives

$$f_{k,n} = f_{k,n-1} + f_{k-1, n-2}.$$

The generating function you want is $\sum_{n \ge 0} f_{5,n} x^n$, but I think it will be easier to find the bivariate generating function $\sum_{n,k \ge 0} f_{k, n} y^k x^n$ first. Do you know how to do this from a recursion?

share|improve this answer
    
I'm fairly sure this isn't what the question is asking me to do, as none of what you said makes any sense to me. The answer at the back of the book is (1+x+x^2+...)(x+x^2+...)^4(1+x+x^2+...). –  Tony B Dec 4 '10 at 19:15
    
Ah, I see. I'm using a more general method, but I guess the book's method is simpler for this problem. Do you understand how the answer at the back of the book works? –  Qiaochu Yuan Dec 4 '10 at 19:19
    
Not exactly, which is my main problem. Its similar to the answer I came up with. –  Tony B Dec 4 '10 at 19:21

I don't understand why this question is asked in the language of generating functions. The easy way to solve the problem is to take any subset $\{a,b,c,d,e\}$ of $\{1,\dots,n-4\}$, and choose the subset $\{a,b+1,c+2,d+3,e+4\}$. In particular, there are $\binom{n-4}{5}$ ways to do this. We can recover the generating function using basic generating function knowledge:

$$\sum_{n\geq 0} \binom{n-4}{5}x^n =\sum_{n\geq 0} \binom{n-9+5}{5}x^n=x^9\sum_{n\geq 0} \binom{n-9+5}{5}x^{n-9}$$ Changing indices and recognizing the form of the generating function, we have $$=x^9\sum_{N\geq -9} \binom{N+5}{5}x^N=\frac{x^9}{(1-x)^6}.$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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