# Tagged Questions

89 views

54 views

### Simplifying a generating function in two variables with two binomial coefficients

I'm trying to to make the below expression simpler, and it would be great if it could be expressed as something like $(x+y)^k$. $$\sum_{i=0}^k\binom{n+1}i\binom{m+1}{k-i}x^iy^{k-i}$$ The number ...
52 views

### Solving a recurrence (with the form of a convolution) involving binomial coefficients

While dealing with a problem related to intersection of hyperplanes I have come across the following recurrence to obtain the values of $K_{j}$ \begin{array}{cccccccccc} 1 & = & ...
70 views

### Extracting a coefficient from a generating function

Background: I am working on an exercise relating to Skolem $k-$subsets with index $k$ in Goulden and Jackson's Combinatorial Enumeration text and they broke it down to finding the coefficient of $x^n$ ...
53 views

### How to simplify $F(x)=\sum_{n}^{\infty}\sum_{k}^{\infty}{n-k-1\choose k}x^n$?

This generating function is equivalent to $$\sum_{n}^{\infty}F_n x^n=\dfrac{x}{1-x-x^2}$$ where $F_n$ is a fibonacci number. To show this, I need to simplify the above generating function with ...
47 views

### Number of nodes with an even number of children in an ordered tree (AKA Plane Planted Tree)

I am looking for verification for my attempt at the solution. I have found that my answer disagrees with an answer I found here: Extract Coefficients From A Function Problem at hand: For a plane ...
255 views

### Prove that $\exp(\log(\frac{1}{1-x})) = \frac{1}{1-x}$

I am trying to prove this directly by comparing the coefficients in the two series rather than using formal calculus. Here is what I have so far, but I think I made a mistake: \begin{align*} ...
59 views

### $\sum_{k=1}^{n}\dfrac{(-1)^{k+1}}{k}{n\choose k}=\sum_{k=1}^n\dfrac{1}{k}$

If $n$ is a positive integer, then the above identity holds. I tried to solve this question using generating function. $$A(x)=\sum_n\left(\sum_{k=1}^n\dfrac{1}{k}\right)x^n=-\dfrac{\log(1-x)}{1-x}$$ ...
43 views

### Generating functions of form $\sum_{n=0}^\infty a_n x^{kn}$

Let's consider generating function $$F(x) = (1+x)^r = \sum_{n=0} \binom{r}{n} x^n$$ And another generating function $$G(x) = (1+x^2)^r = \sum_{n=0} \binom{r}{n}x^{2n}$$ Please note those 2 functions ...
65 views

### Finding the coefficient of a generating function

Given $f(x) = x^4\left(\frac{1-x^6}{1-x}\right)^4 = (x+x^2+x^3+x^4+x^5+x^6)^4$. This is the generating function $f(x)$ of $a_n$, which is the number of ways to get $n$ as the sum of the upper faces of ...
130 views

### Prove an equation about binomial coefficients

Could we prove: $\sum_{k} \binom{2k}{k}\binom{n+k}{m+2k} \frac{(-1)^k}{k+1} = \binom{n-1}{m-1}$ when $m,n \in N$
100 views

### Finding the Coefficient of X^9 in (1+x^3+X^8)^10

This is solved by the following approach e1 takes values 0 3 8 e2 takes values 0 3 8 .. .. .. . and finally it is said that we get 9 when we take ai=3.And the answer become 10c3. Can someone ...
190 views

354 views

### Combinatorial Interpretation of Fractional Binomial Coefficients

My question is a bit imprecise - but I hope you like it. I even strongly think it has a proper answer. The binomial coefficient $\binom{\frac{1}{2}}{n}$ is strongly related to Catalan numbers - the ...
216 views

### Calculating a binomial sum

I came across this excercise in an old exam (in discrete math), and I don't know how to approach it: $$\sum_{k=0}^{10}\left(\frac{1}{2}\right)^k\left(-1\right)^k\binom{10}{k}$$ I know the answer is ...
104 views

### Generating Functions and the Negative Binom

I'm reading from 3 different sets of notes on generating functions and having a little trouble integrating their approaches. First, I'm used to working with the following definitions: ...
214 views

Initially, I have the following problem: find $$\sum_{k=0}^{n+1}(−1)^{n−k}4^k{n+k+1 \choose 2k}.$$ I thought, if I found the function $g_n(x) = \sum_{k=0}^{n}{n+k \choose 2k}x^k$, the answer would be ...
88 views

### Is there a simple expression for this generating function that is almost like the binomial formula?

This is a curiosity I when looking at the binomial theorem. Say you have an ordinary generating function $\displaystyle\sum_{n,m\geq 0}\binom{n}{m}x^ny^m$. This looks kind of like ...
153 views

### On a formula that relates 2-regular graphs on $n$ vertices and permutations of $n$ elements with no fixed points or cycles of length 2

Let $g_n=$ number of 2-regular graphs on $n$ vertices Let $c_n=$ permutations of $n$ with no fixed points or cycles of length 2 By a computation with the exponential generating function I think that ...
190 views

### Evaluating an expression using snake oil and convolutions gives different answers

I have to evaluate this expression $\sum \limits_{k=0}^n(-1)^k\binom{n}{k}\binom{m+n-k}{n-k}$ using snake oil and convolutions. The problem is that I got two different results, could you help me to ...
248 views

### Evaluating an expression using snake oil

I have to evaluate this expression: $\sum_k\binom{n}{k}\binom{2k}{k}(-2)^{-k}$, (In the original question we had $\sum_k\binom{n}{k}\binom{2k}{k}(-2)^{k}$) this is what I have done: ...
195 views

### Evaluating the sum $\sum\limits_k \ k\binom{n}{k}^2$ using generating functions

I have to evaluate this expression $\sum\limits_k \ k\binom{n}{k}^2$ using generating function. Could you help me please? Also with some hints.
218 views

### Two series relations, each one implies the other - from Andrews' partition book

That's my first question here, and i was encouraged to post because my question in MathOverflow (HERE) was beautifully and fast answered. But my questions in not at research level... As i said there, ...
286 views

### Expanding the generating function of the Fibonacci numbers to find a cute formula

$F_0=1$, $F_1=1$, $F_n=F_{n-1}+F_{n-2}$. The generating function is $-\frac{1}{x^2+x-1}$. I have to expand it to prove that $F_n=\sum_k\binom{k}{n-k}$. Could you help me please?
718 views

### Combinatorial proof for two identities [duplicate]

Does exist a combinatorial proof for the following two identities ? $\sum_{k = 0}^{n} \binom{x+k}{k} = \binom{x+n+1}{n}$ $\sum_{k = 0}^{n} k\binom{n}{k} = n2^{n-1}$ I know how to derive the ...
321 views

### Construction of generating function from identity

I am trying to solve identity involving binomials and fibbonaci numbers by using generating functions: \sum_{k=0}^n{n \choose k}{n+k\choose k}f_{k+1}=\sum_{k=0}^n{n \choose k}{n+k\choose ...
272 views

### Two generating functions involving binomial coefficients

Are any of you familiar with the closed form solutions for $\sum_{k=0}^{n} k C(n,k) x^k$ and $\sum_{k=0}^{n} k^2 C(n,k) x^k$ where $0 < x < 1$? Thanks!
I've got the following finite sum: $s_{n}=\sum\limits_{k=0}^{n}\binom{n}{k}^2p^k$ (esp. if $p$ is a function of $n$, like $p=\frac1{n}$), which can be rewritten as ...