Tag Info

New answers tagged

0

An alternate method would be to use symmetry: We have $\dbinom{29}{5}$ solutions in total, and the number of solutions where $x_1+x_2+x_3=x_4+x_5+x_6$ is given by $\dbinom{14}{2}\dbinom{14}{2}$, since then $x_1+x_2+x_3=12=x_4+x_5+x_6$. By symmetry, half of the remaining solutions will have $x_1+x_2+x_3>x_4+x_5+x_6$, so this gives ...


0

I would not bother with generating functions here. You know that $t_1$ can be any integer in $[13,24]$. For each of those values there are $$\binom{t_1+3-1}{3-1}=\binom{t_1+2}2$$ solutions to $x_1+x_2+x_3=t_1$ in non-negative integers, and similarly $$\binom{24-t_1+2}2=\binom{26-t_1}2$$ solutions to $x_4+x_5+x_6=24-t_1$ in non-negative integers. The ...


1

Something that you might find helpful are Blaschke products. If a sequence of numbers $|z_n| < 1$ satisfy the condition $\sum_{n=0}(1-|z_n|) < \infty$ then there is a function analytic in the disc for which $f(z_n)=0$. In particular, the Blaschke product is such a function $$B(z)=\prod_{n=0}^\infty \frac{|z_n|}{z_n} \frac{z_n - z}{1-\bar{z_n}z}.$$ In ...


3

Hint Prove that $\displaystyle \prod_{\nu\geqslant 0}(1+x^{2^{\nu}})=\frac{1}{1-x}=1+x+x^2+x^3+\cdots.$ Note that this proves existence and uniqueness.


1

After correcting the typos, we have $$\begin{align*} A(z)&=2+z\sum_{n\ge 1}a_{n-1}z^{n-1}+z\sum_{n\ge 1}2^{n-1}z^{n-1}\\ &=2+z\sum_{n\ge 0}a_nz^n+z\sum_{n\ge 0}2^nz^n\\ &=2+zA(z)+z\sum_{n\ge 0}2^nz^n\;, \end{align*}$$ since $A(z)=\sum_{n\ge 0}a_nz^n$. Now just subtract $zA(z)$ from both sides to get $$(1-z)A(z)=A(z)-zA(z)=2+z\sum_{n\ge ...


1

Note: The formulation of the problem seems to be incorrect. Nevertheless here's a hint for a 6-sided die. The generating function for tossing one die once is $x^1+x^2+\ldots+x^6$, the exponent of $x$ indicating the result of the throw. Let's denote with $A(x)$ the generating function for tossing $r$ dice. We observe, applying the formula for finite ...


2

We need $k\geq3$. The number of words of length $k$ with exactly one $A$ are $\binom{k}{1}25^{k-1}$ (choose the position for the $A$ and count all possibilities for the letters in the other positions). the generating function of this sequence is ...


1

The coefficient of $x^n$ is called the Hilbert polynomial. It can be calculated, see the book R. Stanley, Enumerative combinatorics. Vol. 1., Cambridge Studies in Advanced Mathematics. 49. Cambridge: Cambridge University Press. (1999). See the Theorem 4.1.1 and Proposition 4.1.1 of the book. Related sofware see here I sure those calculation can be ...


1

Continuing mickep's answer, these are, indeed, the Legendre Polynomials $$ \sum_{k=0}^m (-1)^k{m\choose k}^2 \bigl[\tfrac{1}{2}(1+\cos2\theta)\bigr]^{m-k}\bigl[\tfrac{1}{2}(1-\cos2\theta)\bigr]^k = P_m(\cos(2\theta)) $$


2

We use the binomial theorem, to see that $$ (z\cos\theta+w\sin\theta)^m = \sum_{k=0}^m {m\choose k}z^{m-k}\cos^{m-k}\theta \,w^k\sin^k\theta $$ and $$ (-z\sin\theta+w\cos\theta)^m=\sum_{k=0}^m {m\choose k}(-z)^k\sin^k\theta\,w^{m-k}\cos^{m-k}\theta. $$ Written this way, I think it is clear that when we multiply these factors together, the coefficient in ...


0

For $a_0+a_1n+a_2n^2+a_3n^3+\cdots$ in the numerator, where $a_i$s are given constants, we need to express it as $b_0+b_1n+b_2n(n-1)+b_3n(n-1)(n-2)+\cdots$ where $b_i$s are arbitrary constants $a_0+a_1n+a_2n^2+a_3n^3+\cdots=b_0+b_1n+b_2n(n-1)+b_3n(n-1)(n-2)+\cdots$ Set $n=0,1,2\cdots$ in the above identity to express $b_i$s in terms of $a_i$s ...


1

To determine if a sequence goes on forever, you can use ellipses such as in {$\cdots-2, -1, 0, 1, 2\cdots$} showing that they do that, like you did. It can also be identified by when something says "all integers", "all even numbers greater than $-5$", "all numbers divisible by $10$", etc. The word "all" identifies that any of those sequences goes on ...


2

What you want is to count the number of surjective functions from a set of size $15$ to a set of size $5$. The number of ways to do this is ${15 \brace 5}\times 5!$. where $15 \brace 5$ is the Stirling coefficient of the second kind. Why? every surjection induces a partition of the domain (the set of books that go to child $1$, the set of books that go to ...


2

Suppose that: $$ f(z) = \sum_{n\geq 0}\frac{a_n}{n!}z^n,\qquad g(z)=\sum_{n\geq 0}\frac{b_n}{n!}z^n. $$ Then: $$ [z^m]g(z)e^z = \sum_{n=0}^{m}\frac{b_n}{n!}\cdot\frac{1}{(m-n)!}=\frac{a_m}{m!}=[z^m]f(z) $$ so $f(z)=e^z g(z)$, from which $g(z)=e^{-z} g(z)$. Since: $$ e^{-z}=\sum_{n\geq 0}\frac{(-1)^n}{n!}z^n,$$ it follows that: $$ ...


1

It's not going to be particularly pretty, but the standard way (as is done with the Fibonacci sequence, for example) is to let $$ 2x^2 - x + 1 = (x - \alpha) (x - \beta) $$ for complex $\alpha, \beta$ (it will probably save you work to name them $\alpha$ and $\beta$ rather than giving them explicitly with the quadratic formula). Then solve the partial ...


1

Consider a tree of that form with final vertex $n+1$, there are two cases. Case $1$ is when vertex $(n+1)$ is connected to vertex $0$. In this case we classify all the trees according to how many vertices are in the same external block as vertex $n+1$ (an external block is a path between consecutive external vertices. Notice that if we delete all of the ...


2

No, $(1)$ has the coefficients for $a_r=r+1$. Remember, $a_r$ is the coefficient of $x^r$. Here, for instance, $(1)$ has a constant term of $1$, so the coefficient of $x^0$ is $1$, not $0$, and similarly for every other term.


1

$x$ itself is a power series $$0+x+0x^2+0x^3+\dots$$, so $$x+e^x=1+2x+\frac{1}{2!}x^2+\frac{1}{3!}x^3+\dots.$$


1

The sequence generated by $e^x$ is $$ (1,1,\frac{1}{2!},\frac{1}{3!},\frac{1}{4!},\ldots), $$ and the sequence for $x$ is just $$ (0,1,0,0,\ldots), $$ and thus the sequence generated by the sum, $x+e^x$, is just the sum of the sequences, $$ (1,2,\frac{1}{2!},\frac{1}{3!},\frac{1}{4!},\ldots). $$ I assume that you mean by "the sequence generated by $f(x)$", ...


15

There are many reasons. Here are some: Closed forms facilitate calculations with generating functions. Certain combinatorial operations correspond to simple operations on the generating functions such as addition and multiplication, and these are facilitated by working with closed forms. Proving identities. Continuing the previous bullet, manipulations of ...


2

There are $n!$ ways to arrange $n$ books on a shelf, so the EGF of the number arrangements of a single shelf containing $w$ or more books is $$w! \frac{1}{w!} z^w + (w+1)! \frac{1}{(w+1)!} x^ {w+1} + (w+2)! \frac{1}{(w+2)!} x^ {w+2} + \dots = \frac{z^w}{1-z}$$ The bookcase is simply a sequence of $k$ shelves, so the EGF for the number of ways books can be ...


1

I may be pointing out the obvious, but... Set $y=2x$. Then $$ 1+y+\frac{y^2}{2!}+\frac{y^3}{3!}+\dots = 1+2x+\frac{(2x)^2}{2!}+\frac{2x^3}{3!}+\dots = 1+2x+\frac{2^2}{2!}x^2+\frac{2^3}{3!}x^3+\dots $$ Set $z=2^x$. Then, $$ 1+z+\frac{z^2}{2}+\frac{z^3}{3!}+\dots = 1+2^x+\frac{2^{2x}}{2!}+\frac{2^{3x}}{3!}+\dots $$ It is possible to use $2^x=e^{x\log 2}$ to ...


0

Read generatingfunctionology by Wilf: http://www.math.upenn.edu/~wilf/DownldGF.html It's a free download and has lots of good stuff about (what else?) generating functions.


0

By way of enrichment, here is the species specification for this problem: $$\mathfrak{P}(\mathcal{Z}) \times \mathfrak{S}_{=n}(\mathfrak{S}(\mathcal{Z})).$$ The first term represents the set of values that are exempted from being distributed into the $n$ boxes and the rest describes ordered partitions being distributed into $n$ slots. These ordered ...


0

Suppose we are trying to evaluate $$\sum_{k=0}^n {2n-k\choose k} (-1)^k 4^{n-k}.$$ Introduce the integral representation $${2n-k\choose k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+1}} (1+z)^{2n-k} \; dz.$$ This gives for the sum the integral $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z} \sum_{k=0}^n \frac{(-1)^k 4^{n-k}}{z^k ...


0

Here is some enrichment material to complete this calculation. I assume you are working with labeled trees since you mention an exponential generating function. First note that these planted trees correspond to ordinary rooted trees with an extra node attached at the root. The species equation here is $$\mathcal{T} = \mathcal{Z} ...


0

Suppose we are trying to evaluate $$\sum_{k=0}^n {n\choose k} (n-k)^n (-1)^k.$$ Observe that $$(n-k)^n = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp((n-k)z) \; dz.$$ This gives for the sum the integral $$\frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \sum_{k=0}^n {n\choose k} (-1)^k \exp((n-k)z) \; dz \\ = \frac{n!}{2\pi i} ...


0

Here is some enrichment material to complete this calculation. First note that these planted plane trees correspond to ordinary plane trees with an extra node attached at the root. The species equation for these enumerating by the internal nodes (i.e. excluding the node where the tree is planted) is $$\mathcal{T} = \mathcal{Z}\times ...


0

Suppose we are trying to evaluate $$\sum_{k=0}^n k {n\choose k}^2.$$ Note that $$k{n\choose k} = \frac{n!}{(k-1)! (n-k)!} = n \frac{(n-1)!}{(k-1)! (n-k)!} = n{n-1 \choose k-1}.$$ This means the sum is in fact $$n\sum_{k=1}^n {n\choose k} {n-1\choose k-1}.$$ Introduce the integral representation $${n-1\choose k-1} = \frac{1}{2\pi i} \int_{|z|=\epsilon} ...


0

We can solve this one using species which possibly qualifies as a combinatorial proof. First, observe that 2-regular graphs are sets of undirected cycles, which is the species $$\mathfrak{P}( \mathfrak{D}_{=3}(\mathcal{Z}) + \mathfrak{D}_{=4}(\mathcal{Z}) + \mathfrak{D}_{=5}(\mathcal{Z}) + \cdots).$$ This gives the generating function $$G(z) = ...


1

If you wrote the first term on the LHS as $\frac{u(x) - u_0 - u_1 x }{x^2}$ and the second as $ \frac{8(u(x) -u_0)}{x}$ and then did the algebra, that should be fine. Don't forget expand the fraction on the RHS.


1

With this type of problem Lagrange inversion is the preferred approach. Suppose we seek to extract coefficients from $$Q(z) = \frac{1}{2} \left(\frac{1}{\sqrt{1-4z}}-1\right) \left(\frac{1-\sqrt{1-4z}}{2z}-1\right).$$ The closed form for the coefficients is $$[z^n] Q(z) = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{2} ...


2

I’ll try to explain the general proceeding of solving recursions with generating functions using this example. Write $u = \sum_{n=0}^∞ u_nX^n$ as well as $I = \sum_{n=0}^∞ X^n$. Observe that $I = \frac{1}{1 - X}$ ( – this is because $(1-X)I = \sum_{n=0}^∞ X^n - \sum_{n=1}^∞ X^n = 1$). $I[2X] = \frac{1}{1 - 2X}$ (– which follows from the above for $I[2X] ...


2

You know $f(0) = 0$, so you want $g(0) = 0$. Note that $f(t) = t + t^2 (1 + t/2 + \ldots) = t + t^2 + t^3/2 + \ldots$. Plug in $t = g(x) = a_1 x + a_2 x_2 + a_3 x^3 + \ldots$.


0

The way is first to solve the generating function $x^2-4x+4=0$ and get the solutions $x_1=x_2=2$. So, the general form of the sequence is $u_n=\alpha\cdot2^n+\beta\cdot n 2^n$. By the initial settings, $u_0=1,\,u_1=0$, we get $\alpha=1,\,\beta=-1$. Then, $u_n=(1-n)2^n$.


2

Do you know the concept of generating functions? Just solve the equation for $ u_{n+2}$. Then you are ready to go. Edit: My proceeding would have been to define $$ A(x) = \sum\limits_{n = 0}^\infty u_n x^n $$ Now you set in the starting values of $ u_n $ and write: $$ A(x) = u_o + u_1 \cdot x + \sum\limits_{n = 2}^\infty (4u_{n-1} - 4u_{n-2})x^n $$ ...


0

Start from the bivariate generating function of the Eulerian numbers: $$G(z, u) = \frac{u-1}{u-\exp((u-1)z)}.$$ This gives for $A_n(2)$ by substitution the generating function $$\frac{1}{2-\exp(z)} = \frac{1}{1-(\exp(z)-1)}.$$ But ordered set partitions are the species $$\mathfrak{S}(\mathfrak{P}_{\ge 1}(\mathcal{Z}))$$ which means they have generating ...


0

$$(1+t+\cdots+t^5)^6=1+\dots+at^{12}+\dots+t^{30}$$ $$t^6(1+t+\cdots+t^5)^6=t^6(1+\dots+at^{12}+\dots+t^{30})=t^6+\dots+at^{12+6}+\dots+t^{36}$$


0

Note for pgf the general differentiation rule for m th derivative( repeated derivative m times), when s = 1 is given by g^m (1) = E( X(X - 1) ......... ( X - m + 1)) and so it follows g^2(1) = n(n - 1 )p^2 for the Binomial R.V. X


0

Observing that $$\begin{align} g'(1) &=\Bbb E(X)\\ g''(1)&= \Bbb E(X(X − 1)) \end{align} $$ so you have $$ \begin{align} g''(1)+g'(1)-[g'(1)]^2 &=\Bbb E(X(X − 1))+\Bbb E(X)-[\Bbb E(X)]^2\\ &= \Bbb E(X^2) -\Bbb E(X)+\Bbb E(X)-[\Bbb E(X)]^2\\ &= \Bbb E(X^2) -[\Bbb E(X)]^2\\ n(n-1)p^2+np-(np)^2&=\mathrm{Var}(X)=npq \end{align} $$


0

\begin{align*} \operatorname{Var}(X)&=\mathbb{E}[X^2]-\mathbb{E}[X]^2\\ &= \mathbb{E}[X(X-1)]+\mathbb{E}[X]-\mathbb{E}[X]^2 & \text{linearity}\\ &= n(n-1)p^2 + np - (np)^2 & \mathbb{E}[X]=np\\ &= np[(n-1)p + 1 - np]\\ &= np(1-p)\\ &= npq \end{align*}


2

After n visits to cities, we are in a state (a, b, c, d), where a is how often the last city was visited, and b, c, d is how often we visited the other cities. a+b+c+d will equal n. a, b, c, d are all 4 or less. We may assume that b, c, d are arranged in descending order (for example 2, 3, 2, 0). In the first move, there are four ways to enter state (1, ...


-1

The number of ways to get $n$ in one throw of the dice is the coefficient of $n$ in $t+t^2+t^3+t^4+t^5+t^6$, in other words it is one for $n=1,2,3,4,5,6$. The probability to get, say, seven, in two throws of the dice is the value of the $t^7$ term in $(t+t^2+t^3+t^4+t^5+t^6)^2$. This is just a "coincidence" in that the number of ways to combine works out to ...


1

When you expand $(1+t+\dots+t^5)^6$, you get some polynomial of degree $30$, which we can write as $\sum_{n=0}^{30} a_n t^n$ for some $\{ a_n \}_{n=0}^{30}$. When you multiply it by $t^6$ you get a polynomial of degree $36$, specifically $\sum_{n=0}^{30} a_n t^{n+6}$. The coefficient of $t^{18}$ here is $a_m$ where $m+6=18$, that is, $m=12$. So the ...


2

the first one, you'll note, has $t^6$ glommed onto the beginning of its generating function; remove that, and you go from the coefficient of $t^{18}$ to that of $t^{18-6}=t^{12}$.


3

The number of such functions is $${10 \brace 4}\cdot 7\cdot 6\cdot 5\cdot 4$$ where ${10 \brace 4}$ a Stirling number of the second kind, counting in how many ways it is possible to partition a $10$ elements set into four nonempty subsets. Inclusion-exclusion principle gives: $${n \brace k}=\frac{1}{k!}\sum_{i=0}^{k}(-1)^i\binom{k}{i}(k-i)^n $$ and the EGF ...



Top 50 recent answers are included