Questions tagged [generating-functions]

Generating functions are formed by making a series $\sum_{n\geq 0} a_n x^n$ out of a sequence $a_n$. They are used to count objects in enumerative combinatorics.

3,862 questions
Filter by
Sorted by
Tagged with
32 views

Expected Number of Rolls Until the sequence 6,6,5?

I've seen the recursive expected value approach to solving this problem but I am interested in how to solve this from a generating function perspective. Let E be the expected number of rolls, and X ...
20 views

51 views

21 views

Connection between generating functions with special polynomials

I was learning special function (ODE II course) where I encounter various kind of special polynomials like Legendre, Bessel's, Hermite and Laguerre. And many of their properties (specially recursive ...
36 views

Is it possible to find the value of a polynomial from the generating function?

Suppose I've to find $H_4(0),$ where $H$ represents the Hermite polynomial. I've only been provided with the following relation : $$e^{-t^2+2tx}=\sum_n H_n(x)\frac{t^n}{n!}$$ My first step is to ...
102 views

Is there a closed form for $\sum_{k=0}^n \binom{n}{k}^2p^k(1-p)^{n-k}$?

I have come accross the following sum \begin{align} s_n=\sum_{k=0}^n \binom{n}{k}^2p^k(1-p)^{n-k}. \end{align} Can we obtain some closed-form expression with respect to $p$ for this summation? I found ...
37 views

73 views

How to solve $x(x-1)(x-2)(x-3)(x-4)(x-5)....(x-999)$? [closed]

How to solve $x(x-1)(x-2)(x-3)(x-4)(x-5)....(x-999)$? I'm calculating the probability of $1000$ multicast group having different address. Multicast address space is $2^{28}$. So I tried to calculate ...
92 views

Understaing Concept of Generating function.

I can easily understand the generating function of sequence such as $a_n = n+1$ or something, but cannot understand generating function for some object. There are 2 examples (with photos): What does &...
54 views

Show that $\sum_{k=1}^n \binom{n}{k}k^2=n^2\cdot \:2^{n-2}+n\cdot \:2^{n-2}$.

Let $n$ be a positive integer. Show that $\sum_{k=1}^n \binom{n}{k}k^2=n^2\cdot \:2^{n-2}+n\cdot \:2^{n-2}$. I have that $$(1+x)^n = \sum_{k=0}^n {n \choose k} x^k$$ and I'm wondering if I can use ...
68 views

34 views

Consider $5$ dice with six sides, three of which are labeled $1$ and three of which are labeled $2$. How many ways are there to get a sum of $9$?

Consider $5$ dice, each with six sides, three of which are labeled $1$ and three of which are labeled $2$. How many ways are there to get a sum of $9$ from rolling these five dice? I'm learning about ...
65 views

Alternating sum of binomials divided by a polynomial of the index

I'm working with a sequence of $k$ by $k$ matrices $M^n$ whose entries satisfy $$M^n_{ij} = \binom{j-1}{i-1} \sum_{l=0}^{j-i} \binom{j-i}{l} (-1)^{l} (\frac{1}{i+l})^n, \quad n \in \mathbb{N}$$ I've ...
67 views

Solve generating function for $a_n$

I am not sure how to solve questions like this. I am aware of both recurrence relations and generating functions and how two of these concepts work, but I find it hard to combine them. I would really ...
76 views

Find the coefficient of $x^n$ in $(x^2 +x^3 +x^4 +\cdots)^5$

I have got stuck on this question, though I realise that I have probably got really close to an answer. This is how I approached it: \begin{align*}f(x) &= (x^2+x^3+x^4+\cdots)^5\\ &= x^{10}(1 +...
11 views

Solving recurrence of functions with changing input.

I'm trying to solve the following recurrence relation: $$Z_n(h) = Z_{n-1}(h+k) + Z_{n-1}(h-k),$$ with $Z_1(h)$ some given function. I was thinking about all kinds of techniques to solve this, but ...
77 views

Finding a closed-form formula to a recurrence with summation of past terms

I'm trying to find a closed form formula for the following recurrence problem but I'm having some difficulty: \begin{align} g(n) &= -\frac{1}{n+1} - \sum_{i=1}^{n} \frac{1}{n+1}g(i) \\ &= \...
35 views

Recurrence relations in the generating function of binary partitions

Let $b(n)$ denote the number of binary partitions of $n$, that is, the number of partitions of $n$ as the sum of powers of $2$. Define \begin{equation*} F(x) = \sum_{n=0}^\infty b(n)x^n = \prod_{n=0}^\...
217 views

Coefficient extraction

I want to show: \begin{equation*} [z^n]\frac{1}{(1-z)^{\alpha + 1}} \log \frac{1}{1-z} = \binom{n + \alpha }{n} (H_{n+\alpha} - H_{\alpha}). \end{equation*} where $[z^n]$ means the $n$-th ...
41 views

22 views

49 views

Number of different suits among some randomly chosen cards

A standard deck of cards has 4 suits, with 13 cards per suit. 2 different colored decks (red and blue) are shuffled together to form a single 104-card deck. Red suits are distinct from blue suits. ...
98 views

Showing the formal identity $(1-x+x^2)(1-x^2+x^4)(1-x^4+x^8)\cdots =\frac{1}{1+x+x^2}$

How to show this formal identity (or you can assume $|x|<1$)? $$(1-x+x^2)(1-x^2+x^4)(1-x^4+x^8)\cdots =\frac{1}{1+x+x^2}$$ I can show that the latter is $$=1-x+x^3-x^4+x^6-x^7+\cdots$$ but how to ...
I'm trying to solve following problem, and I got stuck. Let be $[n]=\{1,...,n\}$. Def. A partition $\pi$ of $[n]$ is called non-crossing, if $a$ and $b$ belong to one block and $x$ and $y$ to another, ...