New answers tagged

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