Tag Info

New answers tagged

5

$$(1+x+\dots+x^5)^8=\left(\frac{1-x^6}{1-x}\right)^8=(1-x^6)^8(1-x)^{-8}$$ Using the binomial theoerem, $$ (1-x^6)^8=\sum_{k\ge0}(-1)^k\binom{8}{k}x^{6k} $$ and using the negative binomial theorem, $$ (1-x)^{-8}=\sum_{k\ge0}(-1)^k\binom{-8}{k}x^k=\sum_{k\ge0}\binom{8+k-1}{k}x^k $$ Thus, when we convolve the above two generating functions, the $x^{24}$ ...


0

$\bf{My\; Solution::}$ Let $S = 1+x+x^2+x^3+........+x^5......(1)$ Multiply both side by $x\;,$ We get $\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;xS = x+x^2+x^3+..............x^6........(2)$ Now Subtract $(1)$ and $(2)\;,$ we get $\Rightarrow \displaystyle S(1-x) = 1-x^6\Rightarrow S = \frac{(1-x^6)}{(1-x)}$ So we have to find Coeff. of ...


2

Set $z=te^{i\phi}$ then your generating function can be written as $$A(t)=\frac{1-t\cos(\phi)}{1-2t\cos(\phi)+t^2}=\frac{1-\frac{1}{2}(z+\bar{z})}{(z-1)(\bar{z}-1)}=\frac{(1-z)+(1-\bar{z})}{2(z-1)(\bar{z}-1)}=\frac{1}{2}(\frac{1}{1-z}+\frac{1}{1-\bar{z}})$$ For $|z|<1$ we have the following series expansion ...


0

HINT: $(e^{i n \theta})$ , $(e^{-i n \theta})$ or if you want, $(\cos(n \theta))$, $(\sin(n \theta))$ are solutions.


3

You hardly need any formulas at all, just focus on the $r_k$. Consider a valid configuration on board $C$. Either there is a rook on $S$ or there is no rook on $S$. If there is a rook on $S$, there cannot be any rook in the entire row or column containing $S$, so the remaining $k-1$ rooks are determined by the placement of $k-1$ rooks in $C_2$. On the ...


0

there are only two irreducible polynomials of degree $3$ in $F_{2^3}$. these are easy to construct as: $f=x^3 +x^2 +1$ and $g=x^3+x +1$. if $\alpha$ is a root of $f$ then the remaining two roots of $f$ are $\alpha^2$ and $(\alpha^2)^2$ (c.f. Frobenius automorphism). by simple algebra if $\alpha$ is a root of $f$ then $\alpha^{-1}$ is a root of $g$. from ...


1

$h(x)$ has been written as the product of $g(x)$ and $1/(1-x)$. The n-th term of the series for which the generating function is a product of two generating functions is the convolution product of the terms in the two factors. Because the factors in the sequence from $1/(1-x)$ are all 1, the convolution (sum) looks simply like a sum of terms generated by ...


1

You expand the generating function as 1+x+3*x^2+8*x^3+20*x^4+... and look the coefficients up in http://oeis.org/A001792 .


1

First one may reduce the generating function of B(t) to the generating function which keeps only each 4th term of b, say Bmod(t). Then c is the convolution product of the two sequences and therefore the generating function C(t) the product of the two generating functions A(t)*Bmod(t). Generating Bmod(t) could be done in 2 steps of dissecting the sequence b, ...


2

Note that $$ \sum_{n=0}^\infty \frac{F_n}{3^n}t^n = \sum_{n=0}^\infty F_n\left(\frac{t}{3}\right)^n = G(t/3) $$


0

You know that: $$\sum_{n=0}^{\infty}a_nt^n=A(t)$$ Derive both sides (left side term by term).You get: $$\sum_{n=0}^{\infty}na_nt^{n-1}=A'(t)$$ Now multiply both sides by $t$: $$\sum_{n=0}^{\infty}na_nt^{n}=tA'(t)$$


2

The author factorised the denominator. $$\left(1-y\right)\left(1-\left(\frac{y}{1-y}\right)x\right) = 1-y-yx = 1-y(1+x)$$ The coefficient of $x^k$ is unaffected by factoring out a function of $y$.


1

Derivative of $h(x)$ seems to go something like $$h^{(n)}(0)=(-1)^n(\alpha)_n A^{\frac{1}{\gamma}-\alpha}+(-B)^n\left({\frac{1}{\gamma}-\alpha}\right)_n A^{\frac{1}{\gamma}-\alpha-n}$$ And for $f(x)$ we have $$f^{(n)}(0)=(-1)^n A^{-(\frac{1}{\gamma}-\alpha)-1}$$ So the sum will be $$\sum_{k=1}^{n}\binom{n}{k}\left((-1)^{n-k}(\alpha)_{n-k} ...


2

Note: I've posted a detailed answer to the question of the OP which also clarifies your question. First of all: You did not misunderstand the multiset construction and the function $P_1(z)$ is actually the generating function for the partitions of two-colored, odd integers $>1$. Two hints: Observe that the number of partitions of ...


1

Note: This is really a nice question since it provides a good opportunity to consider similar but different concepts in a non-trivial but manageable way! But first some clarification: The example with $n=9$ in the question above giving a result of $10$ means the number of different compositions of $9$ is $10$. Later on a generating function for ...


1

Pitman gave a wonderful solution. Talking about "Joyal point of view" one could give up those vertebrates and talking only about functions and labeled trees. And in case we haven't rooted trees there'll be $n^2$ functions for each tree. Otherwise, if the problem concerns labeled rooted trees, then we'll have $n$ functions associated to every such tree. ...


1

In the broadest sense, no, there cannot be such a procedure. Let's assume it were decidable whether there is a maximal $m$ such that $a_m = 0$. Then we could take a generic enumeration of all Turing Machines and define a generating function $A(z)$ via $a_m = 0$ if the $m$th machine $M_m $ halts on input $M_m$, and $1$ otherwise. Now if we could decide ...


0

$$f(x) = x^4\left(\frac{1-x^6}{1-x}\right)^4 = (x+x^2+x^3+x^4+x^5+x^6)^4=x^4(1+x+^2+x^3+x^4+x^5)^4=\\ =x^4\left(\sum_{k=0}^{5}x^k\right)^4=x^4\left(\frac{1-x^6}{1-x}\right)^4=x^4(1-x^6)^4(1-x)^{-4}=\\=x^4\sum_{j=0}^{4}(-1)^j\binom{4}{j}x^{6j}\sum_{h=0}^{\infty}(-1)^h\binom{-4}{h}x^h$$ Note that $(-n)!=(-n)(-n-1)(-n-2)\cdots=\infty$, and ...


2

It has no meaning - that's simply the definition. The generating function of a sequence $a_n$ is the function $f(x) = \sum_{k=0}^\infty a_kx^k$ (for values of $x$ where that makes sense, i.e. where the infinite sum converges). The point about generating functions is that they can sometimes give you information about the sequence that generated them. For ...


3

We can prove this using a close relative of the labelled tree function that is known from combinatorics. This will provide a closed form of the exponential generating function of the four terms that are involved. The species of labelled trees has the specification $$\mathcal{T} = \mathcal{Z} \times \mathfrak{P}(\mathcal{T})$$ which gives the ...


0

Check out [Leighton's version] of the Akra-Bazzi theorem. Consider a recurrence of the form: $$ T(z) = g(z) + \sum_{1 \le k \le n} a_k T(b_k z + h_k(z)) $$ fo $z \ge z_0$, $a_k$ and $b_k$ constants, with the restrictions: There are enough base cases For all $k$, $a_k > 0$ and $0 < b_k < 1$ There is a constant $c$ such that $g(z) = O(z^c)$ when $z ...


1

Given $n$, let $f_n$ denote the required number of block arrangements. If we consider the possibilities for the first block for such arrangements, we see that, since the first block can be red or blue and have length one of $3$, $5$, $7$, etc, \begin{eqnarray*} f_n &=& 2(f_{n-3} + f_{n-5} + f_{n-7} + \cdots + f_k) \\ && \\ && ...


1

Assuming you are meaning partitions, the generating function you are looking for is $$ P_{odd,redblue}(z) = \prod_{n=1}^{\infty} \frac{1}{1-2z^{2n+1}}. $$ I don't know yet if the function has a nicer form or what the properties of the function are. How to get there: You should first be familiar with the multiset construction, from Flajolet's book Analytic ...


2

From the Jacobi-Anger expansion: $$e^{ix\cos\theta}=\sum_{n\in\mathbb{Z}}i^n J_n(x)\, e^{i n\theta}\tag{1}$$ it follows that: $$e^{i(x\cos\theta-m\theta)}=\sum_{n\in\mathbb{Z}}i^n J_n(x) e^{i (n-m)\theta}=i^m\sum_{n\in\mathbb{Z}}i^n J_{n+m}(x)e^{in\theta}$$ so, mapping $\theta$ into $\frac{\pi}{2}-\theta$ then into $-\theta$: $$e^{ix\sin\theta} = ...


0

We are computing the product $(1+1+t)(1+1+t)(1+1+t)$, which we do by selecting one term from each factor in all $27$ possible ways, then summing the result. Interpret the three factors as the $x$, $y$, and $z$ coordinates. We select the first $1$ if we want that coordinate to be 0, the other if we want it to be $1$. And we select the $t$ if we allow it to ...


0

The $(d+1)$-cube is the Cartesian product of the $d$-cube and the 1-cube aka the unit interval. Your obeservation is a reflection of the fact the "face generating function" of a Caresian product the product of the generating functions of its factors. So for the $d$-cube the generating function is $(t+2)^d$. This is not a complete proof, because I have not ...


4

I think you have a few misconceptions running around here. First of all, it is not true that "$\frac{1}{1-x}$ generates $\sum x^n$." Rather, for $ |x| < 1$ we have that $$ \sum_{i =0}^{\infty} x^i = \frac{1}{1-x}, $$ whereas for every $x \in \mathbb{C}$ $$ \sum_{i =0}^{n} x^i = \frac{1-x^{n+1}}{1-x}. $$ Note that, if $|x| < 1$ and we let $n \to ...


5

A generating function is a formal power series. The set of formal power series forms a ring and in this ring $1-x$ has an inverse, which is $1+x+x^2+\cdots$.


1

The generating function for partitions where no odd number appears more than once is $$\prod_{k\ge 1} \frac{1}{1-z^{2k}} \prod_{k\ge 0} (1+z^{2k+1}).$$ The number of partitions containing no element of $A$ is $$\prod_{k\ge 1} \frac{1}{1-z^k} \prod_{k\ge 0} (1-z^{4k+2}).$$ Re-write this as $$\prod_{k\ge 1} \frac{1}{1-z^{2k}} \prod_{k\ge 0} ...


1

There are several graphs possible with three edges: A 3-matching. A union of a 1-path and a 2-path. A 3-path. A 3-star (three edges incident to the same vertex). A triangle. Denote by $N(i)$ the number of occurrences of graphs of type $i$ in your graph. We have $$ \begin{align*} \binom{q}{3} &= N(1) + N(2) + N(3) + N(4) + N(5) \\ -(q-2) \sum_i ...


1

Here's another variation of the theme using Egorychevs formal residual calculus for power series. Note: This powerful technique is based upon Cauchys residue theorem and was introduced by G.P. Egorychev (Integral Representation and the Computation of Combinatorial Sums) to compute binomial identies. We use only two aspects of this theory: Let ...



Top 50 recent answers are included