# Tag Info

## New answers tagged generating-functions

0

Suppose we seek to evaluate $$\sum_{q=0}^{n+1} (-1)^{n-q} 4^q {n+q+1\choose 2q} = (-1)^n \sum_{q=0}^{n+1} (-1)^{q} 4^q {n+q+1\choose n+1-q}.$$ We use the integral $${n+q+1\choose n+1-q} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n+q+1}}{z^{n-q+2}} \; dz.$$ This has the property that it is zero when $q\gt n+1$ so we may extend $q$ to infinity to ...

0

Some things can be said about this, you should take a look at the book "$\underline{\text{Enumeration of finite groups}}$" by Blackburn, Neumann and Venkataraman. In this book, if for any $n$, $\mu(n)$ denotes $max(\alpha_i)$ where : $$n=\prod_{i=1}^rp_i^{\alpha_i}$$ Then you have the following upper bound proven by Laszlo Piber proven in 1991 : ...

-1

Here is the bivariate generating function for the number of length n valid arrangements that have exactly k white cards: $-((1 + x)/(-1 + x + x y + x^2 y))$. I solved this system of equations: sol = Solve[{a[x, y] == y x a[x, y] + y x b[x, y], b[x, y] == 1 + x + x b[x, y] + 2 x a[x, y]}, {a[x, y], b[x, y]}] // Flatten /. y -> 1 The generating ...

2

If $G(x) = \sum_{j=0}^\infty a_n x^n$, I get \eqalign{ a_{4k} &= 3 a_{2k} + 2 a_k\cr a_{4k+1} &= 2 a_{2k} + 3 a_k\cr a_{4k+2} &= 3 a_{2k+1} + 2 a_k\cr a_{4k+3} &= 2 a_{2k+1} + 3 a_k\cr} In particular, $a_{2^m} = 3 a_{2^{m-1}} + 2 a_{2^{m-2}}$, and with $a_1 = 1$ and $a_2 = 3$, this implies $$... 1 You have a minor issue with the expression for g_Y:$$g_Y(t)=\frac{q(qt-1)}{p^2+qt-1}$$Then$$P\{Y=k\}=\frac{g_Y^{(k)}(0)}{k!}=(-1)^{k+1}\frac{(q-1)^2}{(q-2)^{k+1}} \text{, }k=0,1,\dots2 (The notations are slightly changed here) We may use a directed graph for such pattern avoiding problems. Write the matrix as \begin{align*} A = \left(\begin{array}{r|rrr} & W & G & R \\ \hline W & w & g & r \\ G & w & g & 0 \\ R & w & 0 & r \\ \end{array}\right) \end{align*} W,G,R are the states to ... 1 Rewrite the generating function G(x) as \begin{align*} G(x) &= \frac{1}{\left(1-x\right)^2\left(1-x^5\right)\left(1-x^{10}\right)}\\ &= \frac{\left(1+x+x^2+x^3+x^4\right)^2\left(1+x^5\right)^3}{\left(1-x^{10}\right)^4}\\ &= \left(1+x+x^2+x^3+x^4\right)^2\left(1+x^5\right)^3\sum_k \binom{k+3}{3} x^{10\, k} \end{align*} Now, ... 0 So the generating function expansion can be truncated to:  (1+x+x^2+\cdots +x^{100})^2. (1+x^5+x^{10}+\cdots +x^{100}). (1+x^{10}+x^{20}+\cdots + x^{100}) You're then looking for the coefficient of x^{100}. The first two terms (for the 1 dollar coins and the 1 dollar bills) become 1+2x+3x^2+\cdots +101x^{100} plus higher powers. Only the powers that ... 0 Perhaps this will help. First suppose you only have one symbol, so there's only one string of each length. The exponential generating function which counts these is\sum_{n\ge0}\frac{x^n}{n!}=e^x.$$Now suppose you have a binary string, so there are two symbols 0 and 1. Say you want to know how many strings there are with k zeros and n-k ones. ... -1 Write G(x)=R_1(x)+R_2(x)+R_4(x)+R_8(x)+R_{16}(x)+\dots, where$$ R_{2^k}(x):=x^{2^k}f_k(x), $$for some f_k(x) with deg(f_k)<2^k. From G(x)=x+G(x^2)p(x)+G(x^4)q(x) it follows that R_1(x)=x and$$ R_2(x)+R_4(x)+R_8(x)+R_{16}(x)+\dots  =p(x)(R_1(x^2)+R_2(x^2)+R_4(x^2)+R_8(x^2)+R_{16}(x^2)+\dots)  ...

1

If you know the product theorem for exponential generating functions, the result is quite understandable. I will slightly paraphrase the version presented in Miklós Bóna, Introduction to Enumerative Combinatorics: Theorem. Denote by $f_n$ the number of ways to carry out a task on $[n]$, and denote by $g_n$ the number of ways to carry out another task on ...

0

I finally solved the question. When I was trying to do it I was so tired so I had a lot of mistakes that I overlooked. I have 2 big mistakes that I edited in the original question (mistake in red): 1) $(r-1)^k(-1)\color{red}{=}(1-r)^k\$yeah, is terrible, I know 2) $\sum f \color{red}{\Delta} g=\sum_{k\ge 0}(1-)^k\ \Delta ^k f\ \frac{E^k}{\Delta^k}g\$ I ...

1

Only the last calculation is somewhat wrong (see Hints below). Everything else is ok. Let's start from \begin{align*} \left[(x+z)^2-x^2\right]^k=z^k(2x+z)^k = \sum_{n \geq k} Y^{\Delta}(n,k,x)z^n\tag{1} \end{align*} Then we know from this paper by V. Kruchinin, that \begin{align*} Y^{\Delta}(n,k,x) = \frac{k!}{n!}B_{n,k}^{x^2}(x) \end{align*} ...

0

The finite state machine is correct. But note, the entries $a_{i,j}$ of the transition matrix $A=(a_{i,j})_{0\leq i,j\leq 2}$ count the number of possibilities to walk in one step from state $q_i$ to state $q_j$. Since we can go from $q_0$ to $q_0$ either via $a$ or $c$, we have two possibilities and therefore $$a_{1,1}=2$$ The same holds true for $a_{2,2}$ ...

3

The series can be cast into hypergeometric form and is given by \begin{align} \sum_{k=0}^\infty \binom{a}{k} \binom{b}{c-k} \binom{d-k}{e} = \binom{b}{c} \binom{d}{e} \, {}_{3}F_{2}(-a, -c, e-d; -d, b-c+1; 1) \end{align} Further reduction may be possible depending on the values of $\{a,b,c,d,e\}$. Proof of result \begin{align} S &= \sum_{k=0}^\infty ...

0

Yes, $L=\varnothing$. Thus, if $\ell(n)$ is the number of words of $L$ of length $n$, we have $\ell(n)=0$ for all $n\in\Bbb N$. Is this function $\ell$ a rational function?

2

You don’t actually need to know exactly to what he’s referring there, since the calculation that he needs is given in full detail at $(7)$. What he does there is a two-variable version of the following one-variable derivation of the relationship that he has in mind. Let $\langle a_k:k\in\Bbb N\rangle$ be a summable sequence with generating function $A(x)$, ...

4

Ok, I have to say, it is complicated but it works (see the final result before going through the whole calculus). You might want to have pages 52, 53 and 54 of this book : https://www.math.upenn.edu/~wilf/DownldGF.html in front of you. First set : $$G(x,z):=\sum_{n=0}^{\infty}a_n(x)z^n$$ Furthermore : ...

0

I agree with the comment by Aulo. The sequence is all 5's. The generating function is 5/(1 - x). If we are determined to find a "complicated solution to a simple problem" then we can solve the differential equation: DSolve[{2 x y'[x] - 10 x/(1 - x)^2 + 5/(1 - x) == y[x], y[0] == 5}, y[x], x]. Mathematica gives: y[x] -> (-5 - Sqrt[x] C[1] + x^(3/2) ...

1

Note $$P_{n}-5=2n(P_{n-1}-5)$$ let $P_{n}-5=a_{n}$.then we have $$a_{n}=2na_{n-1}\Longrightarrow \dfrac{a_{n}}{a_{n-1}}=2n$$ then easy to find $$a_{n}=\prod_{i=2}^{n}\dfrac{a_{i}}{a_{i-1}}\cdot a_{1}=5\cdot 2^n\cdot n!$$

0

You've got the wrong Taylor series. $$\log\left(\frac{1}{1-z}\right)=\sum_{n=1}^\infty \frac{z^n}{n}$$ for $|z|<1$. Setting $z=qt$ gives you $P(X=n)=\frac{q^n}{n}$. Note that this is not a probability function for all $q$, because you'd need $g_X(1)=1$, that is $\log\left(\frac{1}{1-q}\right) = 1$, which means you can only have one specific ...

1

Method 1: Given $P_{n}=2nP_{n-1}-10n+5$ and $P_{0}=5$ then \begin{align} \sum_{n=0}^{\infty} P_{n+1} \, t^{n} &= 2 \, \sum_{n=0}^{\infty} (n+1) \, P_{n} \, t^{n} - 10 \, \sum_{n=0}^{\infty} n \, t^{n} - 5 \, \sum_{n=0}^{\infty} t^{n} \\ \sum_{n=1}^{\infty} P_{n} \, t^{n-1} &= 2 \, \frac{d}{dt} \, \sum_{n=0}^{\infty} P_{n} \, t^{n+1} - 10 ...

1

I believe you are searching for a complicated solution to a simple problem. If $P_n=5$, then $$P_{n+1} = 5 - 10n +10n = 5$$ By recursion, as the starting value is $5$ then each of the following terms is also equal to $5$.

0

Let $F(z) = \sum\limits_{n \geq 0} \binom{2n}{n}z^n$. Then we can use what Thomas wrote in the comments: \begin{align*} F(z)^2 = F(z)\cdot F(z) &= \left( \sum\limits_{n \geq 0} \binom{2n}{n}z^n\right) \left( \sum\limits_{n \geq 0} \binom{2n}{n}z^n \right)\\ &= \sum\limits_{n \geq 0} \left(\sum\limits_{k = 0}^n \binom{2k}{k}\binom{2n - 2k}{n - k} ...

4

You can just look at the Taylor expansion of the function. Without going into analysis too much, here some fact it the general realm of problems you deal with here: For $|\,x\,|<1$, you have the geometric series $\dfrac{1}{1-x}=\sum_{n=0}^\infty x^n,$ and it comes in handy to know that if you have another function given by a series ...

5

The basic identity you should know is the geometric series (Wikipedia link): $$\frac{1}{1-x}=\sum_{n=0}^\infty x^n\quad \text{ (for }|x|<1)$$ Therefore $$\frac{1}{(1-x)^2}=\frac{d}{dx}\left(\frac{1}{1-x}\right)=\frac{d}{dx}\left(\sum_{n=0}^\infty x^n\right)=\sum_{n=0}^\infty nx^{n-1}=\sum_{n=1}^\infty nx^{n-1}$$ Therefore \begin{align*} ... 2 The exponential generating for the number of ways to partition [n] into a single pair is \frac{x^2}{2!}, since there is one way when n=2 and 0 otherwise. Thus, the exponential generating function for the number of ways to partition [n] into pairs ise^{x^2/2}=\sum_{n\ge 0}\frac{x^{2n}}{2^nn!}=\sum_{n\ge ...

0

You don't have to use the binomial theorem. Since $f(x)=(1-2x)^{19}$ is a polynomial, it is equal to its Taylor series, that is, $$f(x) = \sum_{k=0}^\infty \frac{f^{(k)}(0)}{k!}x^k.$$ It's clear that for $0\leqslant k\leqslant 19$, $$f^{(k)}(x) = (-2)^k(19)_k(1-2x)^{19-k},$$ where $(n)_k$ denotes the falling factorial: $$(n)_k = n(n-1)\cdots(n-k+1).$$ So ...

1

You have to use the binomial theorem: $(a+b)^n=\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k$ In this case you have $a=1$, $b=-2X$ and $n=19$ Therefore the term which will have $X^{12}$, is the term in which $k=12$, therefore, for this $k$, we have that $[X^{12}]=\binom{19}{12} 1^{19-12}(-2)^{12}=\binom{19}{12} (-2)^{12}$ Here $[X^{12}]$ is the coefficient of ...

2

In your Attempt 1 you should replace the $\sum$ by a $\prod$: One can select $n$ nominees from the list of $2n$ people in ${2n\choose n}$ ways. Order the chosen nominees alphabetically. The first nominee can choose his two voters in ${2n\choose 2}$ ways, then the second nominee can choose his two voters among the $2n-2$ left over voters in ${2n-2}$ ways, and ...

0

Following Hennings comment. Let $f_n$ be the sequences of length $n$ with symbols $\{1,2,3\}$ starting in $1$, ending in $2$ or $3$ and not containing repeated terms. By inspection $f(3)=2,f(4)=6$. We now find a recursion for $f_{n+2}$, we classisfy the sequences of length $n+2$ in two kinds. First kind: Those with second to last character equal to $2$ ...

1

Hint: How many sequences of symbols from $\{1,2,3\}$ of length $n$ are there such that a symbol is never repeated, and the first and last symbols are different? How many are there where the first and last symbol are equal? Write down two mutual recurrences.

2

Relating that polynomial to your own example, we can understand $(1+x^5+x^9)^{100}$ as follows: There are $9$ each of $100$ kinds of objects. The ordinary enumerator for selecting none or five or all nine of the objects of that kind is $(1+x^5+x^9)^{100}$. Here's another interpretation: Consider three-sided dice whose faces have $0$, $5$, or $9$ ...

2

If your question was counting the number of ways of distributing $n$ indistinguishable balls among $m$ distinguishable bins so each bin had $0$ or $2$ balls, the answer would be the coefficient of $x^n$ in the expansion of $(1+x^2)^m$. If you let $m=1$, you are left with looking at one bin and the generating function $(1+x^2)$. There is one way of ...

2

Let us call : $Fib(x)$ the generating function associated to the Fibonacci number $(F_k)$. We know that : $$Fib(x)=\frac{x}{1-x-x^2}$$ Now if we want to make appear something like a serie with only the $F_{2k+1}$ it seems like a good idea to compute : $$Fib(x)-Fib(-x)=2\sum_{k=0}^{\infty}F_{2k+1}x^{2k+1}$$ ...

0

$\def\zz{\mathbb{Z}}$Let $G_n = F_{2n+1}$ for all $n \in \zz$. $F_{2n+1} = F_{2n} + F_{2n-1} = 2 F_{2n-1} + F_{2n-2} = 3 F_{2n-1} - F_{2n-3}$. Thus $(R^2-3R+1)(G) = 0$ where $R$ is the right-shift operator. If you want the generating function for just the positive index part of the sequence, you get extra leftovers due to the initial conditions.

0

Use the fact that $F_{2n+1}=F_{2n-1}+\sum_{k=1}^nF_{2k-1}=2F_{2n-1}+\sum_{k=1}^{n-1}F_{2k-1}$, and prove it by induction on $n$. Let $f(n)$ be the number of block fountains with a base of $n$ coins, and assume that $f(k)=F_{2k-1}$ for $k\le n$. Now start with a base of $n+1$ coins. If the second row has no coin in the first available slot, you have ...

1

This is just another approach to the problem, not sure if it gets anywhere. If the limit of $b_n$ is $f(b,c)$, then we have (in an appropriate range) $$f(b+c,bc)=f(b,c).$$ Assuming that $c$ is small, it is plausible that this $f$ will be given by a convergent power series in $c$, so (since $f(b,0)=b$) $$f(b,c) = b + \sum_{k>0} a_k(b)c^k.$$ Then the ...

0

Your generating function is correct. Here is the Mathematica code for the Taylor series expansion about x=0 of your g.f.: nn = 20; CoefficientList[Series[((1 - x^4)/(1 - x))^2/(1 - x)^2, {x, 0, nn}], x]. It returns: 1, 4, 10, 20, 33, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208,224, 240, 256, 272, 288,... You can see the terms are increasing by 16 ...

0

Let's take it from the point where we ask for the coefficient of $x^{12}$ in: $$(1 + x^2 + x^4 + ... + x^{18} + x^{20})^2(1 + x^2 + x^4 + ... + x^{20} + x^{22})^3$$ [Note, however, that a factor of $\binom{5}{2}=10$ is already left out of the calculation at this point, which would account for varying positions of the two odd summands $x_i$. See the ...

0

I am assuming that the desired relation is $(1+x+x^2+x^3)^2(\frac{1}{(1-x)^2}) =\sum_{n=0}^{\infty} a_n$. Then $\begin{array}\\ \sum_{n=0}^{\infty} a_n &=(1+x+x^2+x^3)^2(\frac{1}{(1-x)^2})\\ &=(\frac{1-x^4}{1-x})^2(\frac{1}{(1-x)^2})\\ &=\frac{(1-x^4)^2}{(1-x)^4}\\ &=(1-x^4)^2(1-x)^{-4}\\ &=(1-x^4)^2\sum_{n=0}^{\infty} ... 2 Let the numbers be$2a + 1, 2b + 1, 2c, 2d, 2e$, where$a, b, c, d, e$are natural. Note that this makes the odd numbers greater than or equal to$3$, and the even numbers greater than or equal to$2$. Then you have$2a + 1 + 2b + 1 + 2c + 2d + 2e = 24 \rightarrow a + b + c + d + e = 11$. You can solve this with a standard stars-and-bars approach. 1 Here's the calculation of$[z^n]: \begin{align*} [z^n]\frac{(-z)^k}{x^k(x+z)^k}&=[z^n]\frac{(-z)^k}{x^{2k}\left(1+\frac{z}{x}\right)^k}\\ &=\frac{(-1)^k}{x^{2k}}[z^n]\frac{z^k}{\left(1+\frac{z}{x}\right)^k}\\ &=\frac{(-1)^k}{x^{2k}}[z^{n-k}]\frac{1}{\left(1+\frac{z}{k}\right)^k}\tag{1}\\ ... 1 You can construct the partitions in a systematic way: take the partitions ofn-1$, and form two new sets: in blue, by appending$1$, in green by adding$1$to the last element. $$1\to(1)$$ $$2\to(1,1),(2)$$ $$3\to(1,1,1),(2,1),(1,2),(3)$$ ... 1 Think about $$(x+x^2+x^3+\cdots)(x+x^2+x^3+\cdots)\cdots\underbrace{(x+x^2+x^3+\cdots)}_{m-\text{th term}}$$ Coefficient of$x$in the above expression is the number of ways we can add up$m$natural numbers to$n$respecting the order. So the generating function is ... 1 Hint:$c_n = 2^{n-1}$for$n>0$. 10 Hint: Try to understand why $$P(x)=\frac{1}{\prod_{n=1}^{\infty}\left(1-x^n\right)},$$ and what are the corresponding expressions for$Q(x)$and$R(x). Spoiler: 1 By making use of \begin{align} F_{n} = \frac{\alpha^{n} - \beta^{n}}{\alpha - \beta} \end{align} where2 \alpha = 1+ \sqrt{5}$and$2 \beta = 1 - \sqrt{5}, then \begin{align} \sum_{n=0}^{\infty} F_{2n} \, x^{2n} &= \frac{1}{\alpha - \beta} \, \left( \frac{1}{1-\alpha^{2} x^{2}} - \frac{1}{1 - \beta^{2} x^{2}} \right) = \frac{F_{2} \, x^{2}}{1 - L_{2} ... 3 Repeating Slade's hint, for every generating functionF$, it is the case that $$F_{\mathrm{even}}(x) = \frac{F(x) + F(-x)}{2}.$$ Similarly, we have $$F_{\mathrm{odd}}(x) = \frac{F(x) - F(-x)}{2}.$$ Even more generally, for any$k$and$m$we can consider $$F_{m,k} = \frac{1}{m} \sum_{t=0}^m \omega^{kt} F(\omega^{-t} x),$$ where$\omegais a primitive ... 1 Hint: It is pretty easy to see that $$u_n=\left\lfloor\frac n2\right\rfloor+1$$ This will be a useful series here \begin{align} \frac1{(1-x)^2} &=\frac{\mathrm{d}}{\mathrm{d}x}\frac1{1-x}\\ &=\frac{\mathrm{d}}{\mathrm{d}x}\left(1+x+x^2+x^3+\dots\,\right)\\[6pt] &=1+2x+3x^2+\dots \end{align} Thus,\$ \begin{align} U(x) ...

Top 50 recent answers are included