# Tag Info

## New answers tagged generating-functions

0

You want sequences, so you have to use exponential generating functions (the positions label your digits). Assuming there are "infinite" of each digit available to simplify, you have: Even number of 1 (or 2): $1 + \frac{z^2}{2!} + \frac{z^4}{4!} + \dotsb = \frac{\mathrm{e}^z - \mathrm{e}^{-z}}{2}$ At least one 3: $\frac{z}{1!} + \frac{z^2}{2!} + ... 0 Use a generating function for the dice. Normal dice have faces with 1 to 6 dots, so they are represented by the polynomial:$\begin{align} D(z) &= z + z^2 + z^3 + z^4 + z^5 + z^6 \\ &= z \frac{1 - z^6}{1 - z} \end{align}$Throwing two dice gives the distribution:$\begin{align} D^2(z) &= z^2 + 2 z^3 + 3 z^4 + 4 z^5 + 5 z^6 + 6 z^7 ...

0

The operators $x_i D_{x_i}$ for $i \ne j$ conmute, so you should start by seeing what happens with $(x_1 D_{x_1})^F f$. I bet Leibnitz' rule helps cutting down the verbiage, and gives a clue on the terms you mention.

2

Note that if $\sum_kA_kz^k=A(z)$, then $$\left(\sum_{n\le k}A_n\right)z^k=A(z)(1+z+z^2+\cdots)=\frac{A(z)}{1-z}\;.$$ Thus you have $$\sum_{k\in\mathbb{N}_0}\left(\sum_{n\leq k}(A_n B_k+A_k B_n)-A_k B_k\right)z^k=\frac{A(z)}{1-z}\star B(z)+A(z)\star \frac{B(z)}{1-z}-A(z)\star B(z)\;,$$ where $\star$ denotes the Hadamard product given by ...

0

Not really an answer, but an example of something that can be done. Take the generating function for central Delannoy numbers: \begin{align} D(z) = \sum_{n \ge 0} D_{n n} z^n = \frac{1}{\sqrt{1 - 6 z + z^2}} \end{align} This is a power, take logarithms and differentiate: \begin{align} \frac{D'(z)}{D(z)} &= - \frac{1}{2} \frac{-6 + 2 z}{1 - 6 z + ... 1 Shift indices to get: $$b_{n + 2} = 2 b_{n + 1} + b_n$$ Define the generating function: $$B(z) = \sum_{n \ge 0} b_n z^n$$ Multiply the recurrence byz^n$, sum over$n \ge 0$and recognize the resulting sums: $$\frac{B(z) - b_0 - b_1 z}{z^2} = 2 \frac{B(z) - b_0}{z} + B(z)$$ As partial fractions:$\begin{align} B(z) &= \frac{2z}{1 - 2 z ...

0

Define the generating functiom: $$A(z) = \sum_{n \ge 0} a_n z^n$$ Multiply the recurrence by $z^n$, sum over $n \ge 0$: \begin{align} \sum_{n \ge 0} a_{n + 1} z^n &= \sum_{n \ge 0} \sum_{0 \le k \le n} k a_{n - k} z^n \\ \frac{A(z) - a_0}{z} &= \left( \sum_{n \ge 0} n z^n \right) \left( \sum_{n \ge 0} a_n z^n \right) \\ \frac{A(z) - ... 0 The binomial coefficient hints at using an exponential generating function: $$\widehat{T}(z) = \sum_{n \ge 0} t(n) \frac{z^n}{n!}$$ Shift indices and reorganize: $$2^n t(n + 1) = 2^n + \sum_{0 \le i \le n} \binom{n}{i} t(i)$$ Multiply byz^n/n!$, sum over$n \ge 0, and recognize the resulting sums: $$\sum_{n \ge 0} t(n + 1) \frac{(2 z)^n}{n!} = ... 0 Most basic types, that arise often, are variants of:$$ (1 - z)^{-n} = \sum_{k \ge 0} (-1)^k \binom{-n}{k} z^k = \sum_{k \ge 0} \binom{k + n - 1}{n - 1} z^k 0 For this you'll require the sums up to fourth powers: \begin{align} \sum_{0 \le k \le n} k &= \frac{n (n + 1)}{2} \\ \sum_{0 \le k \le n} k^2 &= \frac{n (n + 1) (2 n + 1)}{6} \\ \sum_{0 \le k \le n} k^3 &= \frac{n^2 (n + 1)^2}{4} \\ \sum_{0 \le k \le n} n^4 &= \frac{n^2 (6 n^3 + 15 n^2 + 10 n - 1)}{30} \end{align} So you want: ... 2 Induction is easier, but to use generating functions let's assume that f(x)=\sum_{n=1}^\infty a_nx^n $$Then$$ \begin{align} \sum_{n=1}^\infty na_{n+1}x^n &=x\left(\frac{f(x)}x\right)'\\ &=f'(x)-\frac{f(x)}x \end{align} $$and$$ \begin{align} \sum_{n=1}^\infty(n+2)a_nx^n &=\frac1x\left(f(x)x^2\right)'\\ &=2f(x)+xf'(x) \end{align} $$... 0 This is a linear recurrence of the first order. So you can divide by the summing factor:$$ \prod_{1 \le k \le n} \frac{k + 2}{k} = \frac{(k + 2)!}{1 \cdot 2 \cdot k!} = \frac{(k + 1) (k + 2)}{2} $$Really any constant multiple of this will do, take (n + 1) (n + 2):$$ \frac{a_{n + 1}}{(n + 1) (n + 2)} - \frac{a_{n}}{n (n + 1)} = 0 $$This just ... 0 You have that:$$ (1 + z)^{50} = \sum_{n \ge 0} \binom{50}{n} z^n so that: \begin{align} z \frac{\mathrm{d}}{\mathrm{d} z} (1 + z)^{50} &= \sum_{n \ge 0} n \binom{50}{n} z^n \\ &= 50 z (1 + z)^{49} \end{align} which is the generating function you are looking for. 0 Yet another way is to start with: \sum_{0 \le k \le n} z^k = \frac{1 - z^{n + 1}}{1 - z} $$differentiate thrice:$$ \frac{\mathrm{d}}{\mathrm{d} z} \left( z \frac{\mathrm{d}}{\mathrm{d} z} \left( z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1 - z^{n + 1}}{1 - z} \right) \right) = \frac{1 + 4 z + z^2 - z^n ... 0 If you really want to get blown away, consider the following, taken from Aigner's "A Course in Enumeration" (Springer, 2007). Define: $$s_m(n) = \sum_{0 \le k < n} k^m$$ and it's exponential generating function: \begin{align} \widehat{S}_n(z) &= \sum_{m \ge 0} s_m(n) \frac{z^m}{m!} \\ &= \sum_{1 \le k \le n - 1} \sum_{m ...

1

Note that if $A(z) = \sum_{n \ge 0} a_n z^n$, then $$z \frac{\mathrm{d}}{\mathrm{d} z} A(z) = \sum_{n \ge 0} n a_n z^n$$ and also: $$\frac{A(z)}{1 - z} = \sum_{n \ge 0} \left( \sum_{0 \le k \le n} a_k \right) z^n$$ Starting with: $$\sum_{n \ge 0} z^n = \frac{1}{1 - z}$$ the generating function for the sum you want is: \begin{align} ... 1 Call your variablesa_i$, so that you want$a_1 + 3 a_2 + 3 a_3 = n$with$a_i \ge 0$integers. The values of$a_1$are represented by: $$1 + z + z^2 + \dotsb = \frac{1}{1 - z}$$ The values added by$a_2$and$a_3$are: $$z^3 + z^6 + \dotsb = \frac{z^3}{1 - z^3}$$ In all, you want the coeficient of$z^n$in:$\begin{align} [z^n] \frac{z^6}{(1 - z) ...

0

This is a solution form the book ''CHALLENGING MATHEMATICAL PROOLEMS WITH ELEMENTARY SOLUTIONS VOL 1'' by A. M. Yaglom and I. M. Yaglom : In making up $n$ cents out of 1-, 2-, and 3-cent stamps, we can use either no 3-cent stamps at all, or one 3-cent stamp, or 2 of them, etc., up to a maximum of $q = \left[n/3\right]$ of them. In the first case the $n$ ...

0

Epp's text on Discrete Mathematics is a very nice read. Johnsonbaugh is good as well, but is more technical and more geared towards computer scientists. Nicholas Loehr's text Bijective Combinatorics is a great read for the topics you listed, which fall in the realm of combinatorics. Loehr's text is rigorous and thorough, but it is also very well written and ...

0

Here are very complete notes and problem sets from Jacob Lurie's (Harvard) combinatorics course (Harvard). http://www.math.harvard.edu/~lurie/155.html

1

"generatingfunctionology" by Herbert S. Wilf and "A=B" by Marko Petkovsek, Herbert Wilf and Doron Zeilberger. These are available as free downloads at https://www.math.upenn.edu/~wilf/DownldGF.html and https://www.math.upenn.edu/~wilf/AeqB.html

1

This supplements R. Israel's answer. Given the continued fraction discussed in this post for $|q|<1$, $$\frac{1}{1-q} =\cfrac{1}{1+q-\cfrac{\color{brown}{2q(1+q^2)}}{1+q^3+\cfrac{q^2(1-q)(1-q^3)}{1+q^5-\cfrac{q^3(1+q^2)(1+q^4)}{1+q^7+\cfrac{q^4(1-q^3)(1-q^5)}{1+q^9-\ddots}}}}}$$ and using a little algebraic manipulation to transform the brown part to ...

2

Note: I agree with @Joriki's comment and I want to provide some reasoning why we don't expect to get a closed formula for OP's expression. We do so by translating the problem into a representation with polynomials and comparing it with the Vandermonde's Identity. While the polynomials in case of Vandermonde's identity can be easily transformed to a ...

2

(A partial answer.) This is a special case of a conjectured equality discussed in this MO post. Let $|q|<1$, then, \begin{aligned}U(q) &= \prod_{n=0}^\infty \frac{\big(1-a^2q^3(q^4)^n\big)\big(1-b^2q^3(q^4)^n\big)}{\big(1-a^2q(q^4)^n\big)\big(1-b^2q(q^4)^n\big)}\\ &= \dfrac{1} {1+ab-\dfrac{(a+bq)(b+aq)} {1+(ab)^3+\dfrac{(a-bq^2)(b-aq^2)q} ... 0 You have in generalG(\mathbf{z}) = G(z_1,\ldots,z_d)=\operatorname{E}\bigl (z_1^{X_1}\cdots z_d^{X_d}\bigr) = \sum_{x_1,\ldots,x_d=0}^{\infty}p(x_1,\ldots,x_d)z_1^{x_1}\cdots z_d^{x_d}$$So suppose for example$$P(\mathbf{X}=(0,0))=\frac45, \,P(\mathbf{X}=(1,0))=\frac35, \,P(\mathbf{X}=(0,1))=\frac25, \, P(\mathbf{X}=(1,1))=\frac15,$$then rather simply ... 3 The ordinary generating function for your recurrence is$$ g(x) = \dfrac{1+x^2}{1-x-x^3}$$Thus$$\sum_{n=0}^\infty (-1)^n a_n q^n = g(-q) = \frac{1+q^2}{1+q+q^3}\tag1$$If that is \phi(q), then indeed$$ \phi(1/q) = \dfrac{1/q^2+1}{1/q^3 + 1/q + 1} = \dfrac{q (1 + q^2)}{1+q^2 + q^3} = q \phi(q)$$Now let's try to get your continued fraction.$$ ...

0

Let $f(z)$ be the ordinary generating function and $\mathcal{L}$ be the Laplace transform. Then the EGF $g(z)$ has the form $$g(z)=\mathcal{L}^{-1}\left(\frac{1}{z} f(z)\Big |_{z=\frac{1}{z}}\right)$$

1

Let $f(z)$ be the ordinary generating function and $\mathcal{L}$ be the Laplace transform. Then the EGF $g(z)$ has the form $$g(z)=\mathcal{L}^{-1}\left(\frac{1}{z} f(z)\Big |_{z=\frac{1}{z}}\right)$$

0

You are looking for ($\dotsb$ at the end of a factor covers terms that don't affect the result): \begin{align} [z^{10}] (z + \dotsb + z^5) &(z^2 + \dotsb + z^6) (z^3 + \dotsb + z^9) \\ &= [z^{10 - 1 - 2 - 3}] (1 + \dotsb + z^4) (1 + \dotsb + z^4) (1 + \dotsb + z^6) \\ &= [z^6] \frac{(1 - z^5)^2 (1 - z^7)}{(1 - z)^3} \\ &= [z^6] (1 - 2 ... 0 General technique is to write your recurrence so there are no subtractions in indices: $$a_{n + 2} = a_{n + 1} + a_n$$ Multiply byz^n$, sum over$n \ge 0$: $$\sum_{n \ge 0} a_{n + 2} z^n = \sum_{n \ge 0} a_{n + 1} z^n + \sum_{n \ge 0} a_n z^n$$ Recogize some sums: $$\frac{A(z) - a_0 - a_1 z}{z^2} = \frac{A(z) - a_0}{z} + A(z)$$ ... 0 Define the generating function$A(z) = \sum_{n \ge 0} a_n z^n$. Take the recurrence, multiply by$z^n$, sum over$n \ge 0$: $$\sum_{n \ge 0} a_{n + 1} z^n - \sum_{n \ge 0} a_n z^n = \sum_{n \ge 0} n^2 z^n$$ Recognize some sums, note that:$\begin{align} \sum_{n \ge 0} z^n &= \frac{1}{1 - z} \\ \sum_{n \ge 0} n z^n &= z ...

0

Note that: $$\frac{1}{k (n - k)} = \frac{1}{k n} + \frac{1}{n (n - k)}$$ Thus your sum is: \begin{align} \sum_{1 \le k \le n - 1} \frac{1}{k (n - k)} &= \sum_{1 \le k \le n - 1} \frac{1}{k n} + \sum_{1 \le k \le n - 1} \frac{1}{n (n - k)} \\ &= \frac{1}{n} \sum_{1 \le k \le n - 1} \frac{1}{k} + \frac{1}{n} \sum_{1 \le k \le n ... 0 Define the generating function: $$G(z) = \sum_{n \ge 0} D(n) z^n$$ Take your recurrence written as: $$D(n + 2) = D(n + 1) + D(n) + 5 (n + 1)$$ Multiply byz^n$, sum over$n \ge 0$and recognize some sums: $$\frac{G(z) - D(0) - D(1) z}{z^2} = \frac{D(z) - D(0)}{z} + G(z) + \frac{5}{(1 - z)^2}$$ Solve for$G(z)$, split into partial fractions: ... 0 Let$a_r$be the number of ways of doing this with$r$objects. There are two cases - either there is an object in box one, or there is not. The first case is counted by$r3^{r-1}$and the second case by$3^r$. Hence $$a_r = r3^{r-1} + 3^r,$$ which is the same as what you had. No generating functions necessary :) 1 Too long for a comment: By investigating series of the form$S_a(x)=\displaystyle\sum_{n=0}^\infty{an\choose n}~x^n$, we notice that — in general — we get a$($generalized$)$hypergeometric function of argument$\dfrac{a^a}{(a-1)^{a-1}}~x$, which then naturally leads us to suspect that we should rather be inspecting the values of the same ... 0 A complete asymptotic solution to exactly this kind of recurrences is derived by Erdös et al "The Asymptotic Behavior of a Family of Sequences" Pacific Journal of Mathematics 126:2 (1987), pp 227-241. They use this exact recurrence as an example, and show that: $$a_n \sim \frac{12}{\log 432} n$$ 0 This is too long for a comment and I don't know if this is useful, but I tried to do it with Mathematica and it gave me:$\quad\quad\quad\quad\quad\quad$Which in TeXForm, yields: $$\frac{ \, _2F_1(-n,2 x-y;-n+x+1;-2) x!}{n! (x-n)!}$$ Where$_2F_1(a,b;c;d)$and Hypergeometric2F1 are this hypergeometric function. If you need a reference for ... 3 Let$C$be any contour in the complex plane surrounding the origin counter-clockwisely once. We have this little identity $$\frac{x^k}{k!} = \frac{1}{2\pi i}\int_C \frac{e^{xt}}{t^{k+1}} dt$$ Given an OGF$f(x) = \sum_{k=0}^\infty a_k x^k, we can "formally" construct the corresponding EGF as \begin{align} f_{\rm EGF}(x) \stackrel{def}{=} ... 1 Wilf's book "generatingfunctionology" explains why exponential generating functions are useful. Another view, much more mathematically demanding, is explained by Flajolet and Sedgewick's "Analytic Combinatorics", the approach is summarized by Wikipedia. 0 Roughly speaking, a "closed form" is a formula that requires less work than just doing the computation. This typically means not having summation signs or other "repeat for all..." structures. But in any case, you'd have to agree on some set of "elementary" functions, i.e., powers, factorials, binomial coefficients are normally considered such. 1 For the sequence \langle a_n \rangle the (ordinary) generating function is A(z) = \sum_{n \ge 0} a_n z^n (you get other flawors of generating functions by selecting some other sequence of functions instead of z^n to mark the positions). The point of generating functions is that they summarize the whole sequence in a single object (Wilf's ... 1 Let S= 1 + x + x^2 + x^3 + x^4 \quad I multiplying both sides by x xS=x + x^2 + x^3 + x^4+x^5 \quad II Subtracting II by I S(1-x)=1-x^5 Dividing the equation by (1-x) S=\frac{1-x^5}{1-x} 1 If you know that \dfrac{1}{1-x} = 1 + x + x^2 + \ldots, then you can use this fact after breaking up the fraction: \begin{align} \frac{1-x^5}{1-x} &= \frac{1}{1-x} - \frac{x^5}{1-x} \\ &= \frac{1}{1-x} - x^5\frac{1}{1-x} \\ &= (1 + x + x^2 + \ldots) - x^5(1 + x + x^2 + \ldots) \\ & = 1 + x + x^2 + x^3 + x^4 \end{align} $$This is ... 1 All this comes from the high school identity:$$a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+\dots+ab^{n-2}+b^{n-1})$$and setting a=1. 4 Think of 1+x+x^2+x^3+x^4 as a geometric series with common ratio x. The sum of the first n terms of a geometric series is given by$$S_n = \frac{a(1-r^n)}{1-r}$$where a is the first term and r the common ratio. Here a = 1, r = x, n = 5 so we get$$1+x+x^2+x^3+x^4=\frac{1-x^5}{1-x}$$1 \bf{My\; Solution::} Let$$\displaystyle S = 1+x+x^2+x^3+x^4\tag1$$Now Multiply both side by x\;, We Get$$x\cdot S = x+x^2+x^3+x^4+x^5\tag2$$Now (1)-(2)\;, We Get$$\displaystyle (1-x)\cdot S = 1-x^5\Rightarrow S = \frac{1-x^5}{1-x}$$3 (1 + x + x^2 + x^3 + x^4)(1-x)=(1 + x + x^2 + x^3 + x^4) - (x + x^2 + x^3 + x^4+x^5) = 1-x^5 6 Suppose that \sigma=\langle a_n:n\in\Bbb N\rangle is a sequence of real numbers. A function f:\Bbb N\to \Bbb R is a closed form for the n-th term of \sigma if f(n)=a_n for each n\in\Bbb N. (You can replace real with complex and \Bbb R with \Bbb C, if you like.) The ordinary generating function for \sigma is the function g:\Bbb R\to\Bbb ... 3 The generating function is a closed form of a power series that has (the closed form of) the terms of the sequence as its coefficients. Generating function for sequence having terms a_n:$$f(x) = \sum_{n=0}^{\infty} a_n x^n$5 Method 1 - Bilu-Hanrot-Voutier theorem on Lucas sequences. First some definitions, Lucas pair - A Lucas pair is a pair$(\alpha,\beta)$of algebraic integers such that$\alpha + \beta$and$\alpha\beta$are non-zero coprime rational integers and$\frac{\alpha}{\beta}\$ is not a root of unity. Lucas numbers - Given a Lucas pair, the corresponding sequence ...

Top 50 recent answers are included