# Tag Info

## New answers tagged generating-functions

1

\begin{align}G_Y(s)&=\Bbb E[s^{Y}]\\&=\Bbb E\left[\Bbb E\left[s^Y\mid N\right]\right]=\Bbb E\left[\Bbb E\left[s^{X_i}s^{X_2}\cdots s^{X_N}\right]\right]\\&=\Bbb E\left[\Bbb E\left[s^{X_1}\right]\Bbb E[s^{X_2}]\cdots \Bbb E[s^{X_n}]\right]=\Bbb E\left[G_X(s)^N\right]=G_N\left(G_X\left(s\right)\right)\end{align} and \Bbb E[Y]=\Bbb E\left[\Bbb ... 1 Hint: Maybe the following representation of indices is helpful \begin{align*} \sum_{k=1}^{M}\sum_{r=1}^{k}b_{r,k}=\sum_{1\leq r\leq k\leq M}b_{r,k}=\sum_{r=1}^{M}\sum_{k=r}^Mb_{r,k} \end{align*} 0 First of all your approach is fine and the generating function G(z) is correct. As verification we consider a slightly different approach in the same spirit as it can be found in chapter 5 in Analysis of Algorithms. Then we look at the coefficients of G(z) Generating function G(z): We can find in section Bitstrings of chapter 5 a ... 22 Here is my solution: If a=\sum_{j\geq 0} a_j b^j, then u_b(a) = \frac{1}{2}\sum_j (1-(-1)^{a_j}) because 1-(-1)^m=\begin{cases} 0 & 2\mid m\\ 2 & 2\nmid m\end{cases}. Note that a_j is the digit directly left of the decimal point in the b-adic expansion of ab^{-j}, i.e. a_j = \lfloor ab^{-j} \rfloor \mod b. Now if b is even we can ... 0 Another way. Note that for any sequence a_n, with A(z) = \sum_{n \ge 0} a_n \frac{z^n}{n!} \begin{align} z \frac{\mathrm{d}}{\mathrm{d} z} A(z) &=z \sum_{n \ge 0} a_n \frac{z^{n - 1}}{(n - 1)!} \\ &= \sum_{n \ge 0} n a_n \frac{z^n}{n!} \end{align} Thus you get what you want by doing the above twice to \mathrm{e}^z: \begin{align} z ... 0 One more method you can look at this is, we know\frac{1}{1-x}=\sum_{x=0}^\infty x^n$$So applying operator xD where D is derivative w.r.t x on it, we have$$ \frac{x}{(1-x)^2} = \sum_{x=0}^{\infty} n x^n$$Now if raise both side to k, then we have$$ \frac{x^k}{(1-x)^{2k}}= \sum_{n_1+n_2+\ldots+n_k=n}n_1n_2\ldots n_k$$This is the generating function ... 0 Assuming that c is a positive integer, Solve the homogeneous recurrence first: T(n)=aT(n-1), which yields the general solution T(n)=\alpha a^n In the case that a\neq 1, next assume that \beta_0+\beta_1n+\beta_2n^2+\dots+\beta_cn^c = T(n) and plug that in place of T(n) and T(n-1). In the case that a=1, instead assume that ... 0 I'm quite, quite far from an expert but I do have a specific literature reference to contribute: the whole section 2.4 Power series, analytic theory in the book generatingfunctionology by Herbert S. Wilf. The second edition (1994) is downloadable (there is a third edition but not on the web) and this is how the author introduces the topic in the section: ... 1 Let C_n be the triangular board of side length n with squares in positions (i,j) for i \le j, so C_3 is as shown in the question. Given a non-attacking placement of k-rooks on C_n, there is a corresponding function f : \{1,2,\ldots,n,n+1\} \rightarrow \{2,\ldots,n,n+1\} \cup \{ \star\} defined by$$f(i) = \begin{cases} j+1 &\text{if ...

7

A generating function solution. For every $S\subset\{1,2,\ldots,2015\}$ we will write $\Sigma S=\sum_{k\in S}k$. Let $$f(a,x) = \prod_{k=1}^{2015} (1+a^kx) = \sum_{S\subset\{1,\ldots,2015\}} a^{\Sigma S} x^{|S|}.$$ Take the average this function over putting $5$th complex roots of unity for $a$. Let $\omega=e^{2\pi i/5}$; then $$\frac15\sum_{j=0}^4 ... 1 I do not think your first example is correct. We have between 1 and 4 red balls, exactly 2 balls, and at most 2 yellow balls. You have an extra 1 in two of your expressions (I am not sure why).$$[x^7](x+x^2+x^3+x^4)(x^2)(1+x+x^2) = 2$$Your answer to the dice question is exactly correct. You can make it a little more compact ... 4 This is a straightforward application of the Polya Enumeration Theorem. We treat the problem of subsets with n elements of the set \{1,2,\ldots, q\} whose sum is divisible by k. Suppose Z(P_n) is the cycle index of the set operator \mathfrak{P}_{=n} given by the recurrence by Lovasz which is$$Z(P_n) = \frac{1}{n} \sum_{l=1}^n ...

1

Hint. I would set $$\epsilon:=x-1$$ then, as $\epsilon \to 0$, use the binomial theorem to get $$x^N=(1+\epsilon)^N=1+N\epsilon+\frac{1}{2} N(N-1)\:\epsilon^2+\frac{1}{6} N(N-1)(N-2)\:\epsilon^3+o(\epsilon^3). \tag1$$ Inserting $(1)$ in your identity gives the sought result. In fact, by applying $\left\lbrace (1+\epsilon)D_\epsilon \right\rbrace^2$ to ...

1

The answer is $\frac{1}{5}\binom{2015}{n}$. For each subset of $n$ elements (not necessarily with sum multiple of $5$) consider the set of the $2015$ translations of the $n$-set. In other words, if we have $\{a_1,a_2\dots a_n\}$ Consider the family of sets of the form $\{r(a_1+k),r(a_2+k),\dots r(a_3+k)\}$ with $k\in\{0,1,\dots 2015\}$, and where $r(m)$ is ...

2

Process 1: Start with $1-2x-x^2$. Now, the given, from the problem, is that \begin{align} 1-2x-x^2 &= (1- a x)(1 - b x) \\ &= 1 -(a+b) x + ab x^2. \end{align} Equating coefficients leads to $a + b = 2$ and $ab = -1$. Using this information leads to \begin{align} a - \frac{1}{a} &= 2 \\ a^2 - 2 a - 1 &= 0 \\ a &= 1 \pm \sqrt{2}. ...

2

Elaborating on what Wojowu has mentioned, $$a_n^2=a_{n-1}\cdot a_{n-2}$$ $$a_n^2\cdot a_{n-1}=a_{n-1}^2\cdot a_{n-2}$$ That is, $a_n^2\cdot a_{n-1}=$ constant is invariant. Hence $$a_n^2\cdot a_{n-1}=a_{n-1}^2\cdot a_{n-2}= \ldots = a_1^2a_0 = 4$$ or, $$a_n^2=\frac{4}{a_{n-1}}=\frac{4}{\frac{2}{\sqrt{a_{n-2}}}}=2\sqrt{a_{n-2}}$$ or, ...

3

Squaring both sides, $a_n^2=a_{n-1}a_{n-2}$. Then, $2\log(a_n)=\log(a_{n-1})+\log(a_{n-2})$. Set $b_n=\log(a_n)$. Thus $2b_n=b_{n-1}+b_{n-2}$ with $b_0=0$ and $b_1=\log2$. Can you coninue?

2

This may be treated by the Egorychev method. Suppose we are given the OGF $f(z)$ of an interesting sequence and want to extract the generating function of the first $n$ terms. Thus we wish to compute $$g(w) = \sum_{k=0}^n w^k [z^k] f(z) = \sum_{k\ge 0} [[0\le k\le n]] w^k [z^k] f(z).$$ Introduce the Iverson bracket $$[[0\le k\le n]] = ... 3 Rewrite \frac{(2n)!}{(r!)^2((n-r)!)^2} = \binom{2n}{n}\binom{n}{r}\binom{n}{n-r}.$$\therefore \sum_{r=0}^{n}\frac{(2n)!}{(r!)^2((n-r)!)^2}= \sum_{r=0}^{n}\binom{2n}{n}\binom{n}{r}\binom{n}{n-r} = \binom{2n}{n}\sum_{r=0}^{n}\binom{n}{r}\binom{n}{n-r}$$Now, \sum_{r=0}^{n}\binom{n}{r}\binom{n}{n-r} is just choosing n objects out of total 2n objects. ... 1 Inspired by Ross's answer, we'll prove that there is a bijection between equivalence classes of such sequences and subsets of \{0,\ldots, 3n+2\} with size n+1. We will first define an equivalence relation \sim on \{0,\ldots, 3n+3\} by saying two sets are equivalent if they are cyclic shifts of each other, i.e. A\sim B if B = A + j \mod 3n+4 for ... 1 It seems there are \frac 1{2\cdot 2015+1}{3\cdot 2015 \choose 2015} such sequences. I modeled the recurrence in Excel, finding 3,12,55,273,1428,7752 such sequences starting at m=1. Looking up in OEIS finds A001764 I don't have a proof that this is correct, but it certainly seems one could make a stars and bars argument. 1 If P_{n,k} is the amount of sequences of a_0,\ldots, a_n such that a_n = k and for any m we have 0\leq a_m \leq 3m then:$$P_{n,k} = \begin{cases} 0 &\text{if } k < n\\ 1 & \text{if } k = n\\ \displaystyle\sum_{i=0}^{k-n} P_{n-1,n-1+i} & \text{if } n < k \leq 3n\\ 0 & \text{if } k > 3n \end{cases}$$The amount of ... 0 One easy case is when the recurrence is linear with constant coefficients and the inhomogeneity is a polynomial. In this case a particular solution is also a polynomial. Most of the time, it is a polynomial of the same degree as the inhomogeneity. For example:$$T(n)=-2T(n-1)-T(n-2)+n. If you assume $T(n)=an+b$ then the equation becomes ...

4

The formula given in the book is actually correct. It is easy to calculate "by hand" that the coefficient of $n=2$ in the formal power series of $\log \sum_{n=0}^\infty n! x^n$ is $\frac32$. The probability that two uniformly random elements of $S_2$ generate a transitive subgroup is $\frac34 = \frac{1}{2!} \frac{3}{2}$, whereas your modification would give ...

Top 50 recent answers are included