Tag Info

New answers tagged

2

Suppose we have a sequence of values of length $k$ where the values are any non-negative integer. This is has the combinatorial specification $$\mathfrak{S}_{=k}\left(\sum_{q\ge 0} \mathcal{Z}^q\right).$$ This gives the generating function $$\frac{1}{(1-z)^k}.$$ On the other hand all such sequences can be obtained by stars-and-bars combining $n$ elements ...


2

It is quite easy to show by induction (or through other combinatorial arguments) that: $$ \sum_{n=0}^{N}\binom{n+k-1}{k-1}=\binom{N+k}{k},$$ hence if $$ f_k(x) = \sum_{n\geq 0}\binom{n+k-1}{k-1}x^n $$ it follows that $$ f_{k+1}(x) = \frac{f_k(x)}{1-x}=\frac{1}{(1-x)^{k+1}},$$ since if $$ f(z) = \sum_{n\geq 0} a_n z^n $$ we have: $$ ...


0

The following solution is supposed to be the simplest one. Let's consider a complex number $a$ such that $a^{4}=1$. So, denote $S_{n}=\sum_{s=0}{\binom{i}{m}}$. We know its generating function $A(s)=(1+s)^{m}$. So, the generating function for the sequence over all $i=4q, q\in \mathbb{Z}$ would look like this ...


0

Given the desired backward equations, the definitions of these generating functions appear to be slightly incorrect. Given a certain intermediate cell at time $\tau$, there will be, at any future time $t\ge \tau$, a certain number $I_1(t,\tau)$ of intermediate cells and $M_1(t,\tau)$ of malignant cells that descend from it via the intermediate cell dividing ...


0

Let's answer this question (even if it's not a very useful answer), the answer discuss the part how many information we can get from $G(z)$ We can use sets instead of sequences, given a set $A$ of sets $I$ such that :$|A|=m$ and $\forall I\in A |I|=n$ (The question imposes $n=m$ but the answer will be more general) we define: $$G_A(z)=\sum_{I\in ...


1

We have, if $\left|x\right|<1$ ...


3

Consider that, by the discrete Fourier transform: $$ 4\cdot\mathbb{1}_{n\equiv 0\pmod{4}} = 1^n+(-1)^n+i^n+(-i)^n \tag{1}$$ hence: $$ \mathbb{1}_{n\equiv 2\pmod{4}} = \frac{1}{4}\left(1^n + (-1)^n - (-i)^n - i^n\right)\tag{2} $$ and: $$\begin{eqnarray*} \sum_{n\equiv 2\pmod{4}}\binom{m}{n} &=& ...


2

Note: The following answer is divided in three steps. We start with a short Overview Step 1: A convenient representation We transform OPs expression by doing some index shifting and by adding one summand to both sides which considerably simplifies the RHS of OPs expression. We show OPs expression is equivalent to \begin{align*} ...


1

These are just a few with the generating functions or expansions. 1) Matthias Schork 2) Robert A. Sulanke 3) Sen-Peng Eu 4) Toufik Mansour 5) Ira M. Gessel 6) Eva Y. P. Deng


1

Square the Binet formula to get $$F_n^2=\frac{\phi^{2n}-2(-1)^n+\phi^{-2n}}{5},$$where $\phi=(1+\sqrt5)/2$. Now the series splits into three geometric series, where the common ratios are respectively $\phi^2s$, $-s$, and $\phi^{-2}s$.


3

Here is one approach that requires some technique but very little intuition: To begin with, we write down a recurrence relation. We have $a_{n+1}/a_n = (4n+1)/(n+1)$, or $(n+1)a_{n+1} = (4n+1)a_n$. Define $a_0 = 1$ for consistency. Since I posted this answer, the question was changed/merged to define $a_0 = 0$. The effect is to subtract $1$ from the ...


0

This is called generalized Binomial coefficient. Just expand $(1-4x)^{-\frac{1}{4}} = \sum_{k=0}^{\infty} \binom{-\frac{1}{4}}{k} (-4x)^k$ and apply the binomial expansion rule to the coefficient, this result will pop out. EDIT: the coefficient you have can be rewritten (after mulitplying by $(2n)!!$) as $ \frac{1}{2^n} \binom{2n}{n} $ EDIT 2: To get the ...


1

What you are looking for is a row in the table of Mahonian numbers. Here they are: Sloane's A008302. That link gives you lots and lots of other links and references, and it includes a recurrence for calculating them (which I added a couple of years ago). Here, $T(1,)$ represents $1$ and $T(2,)$ represents $(1+x)$, etc. $$T(1, 1) = 1,\qquad T(1, k\neq 1) = ...


2

This product gives the Poincare series for the symmetric group $S_{n+1}$ considered as a Coxeter group of type $A_n$. The answer is therefore the number of permutations in $S_{n+1}$ that can be minimally expressed as a product of $n$ adjacent transpositions. I think this is likely the best formula you will find for this number.


1

New Notations: Always fix $r$. Suppose $L=(c_1, c_2, \ldots, c_l)$ is a list of non-decreasing natural numbers. Denote by $|L|$ ($=l$) the length of the list and $\sum L = c_1 + \ldots + c_l$ the sum of entries in $L$. Let $T(n, L)$ count the number of sets $U = \{u_1, \ldots, u_{m}\}$, where $m=\sum L$, each $u_i$ is an $r$-subset of $[n]$ and $\cup U = ...


3

Let us write $y=\ln x$. The question is equivalent to compute $$a_j(x)=\sum_{i=0}^j\frac{(j-i)^i\;x^i}{(j-i)!\;i!}.$$ An elegant method is to use, as already said, the generating function $$f(x,y)=\sum_{j=0}^\infty a_j(x) y^j=\sum_{j=0}^\infty y^j\sum_{i=0}^j \frac{(j-i)^i}{(j-i)!}\frac{x^i}{i!}.$$ Using the little diagram $$j\uparrow ...


0

Here is a partial answer, which reduces the problem to counting $T_{n,r,m}(1)$, that is, counting the number of sets that have a connected intersection graph ($c=1$). The reduction occurs through a recurrence, with $c=1$ corresponding to the base cases. First let me change the notation. Let $r$ be given as before. Since $r$ is held fixed, I suppress it as an ...


1

what you are after if the coefficient of $x^{10}$ in the expansion $$\begin{align}[x^{10}](1-x)^{-5}(1-x^5)^5 &=[x^{10}] \left( 1 + {5 \choose 1}x + {6 \choose 2 }x^2 + \cdots \right)\left(1 - {5 \choose 1}x^5 + {5 \choose 2}x^{10} + \cdots\right)\\&={5 \choose 2} - {9 \choose 5} {5 \choose 1}+ {14 \choose 10}. \end{align} $$


1

You are looking for the coefficient of $x^{24}$ in:$$x^{12}\left(\frac{1-x^6}{1-x}\right)^4$$ Which is the same as the coefficient of $x^{24-12}=x^{12}$ in $$\left(\frac{1-x^6}{1-x}\right)^4\tag{1}$$ Now, $$(1-x^6)^4 = 1-4x^6+6x^{12}-4x^{18}-x^{24}$$ And $$\frac{1}{(1-x)^4} = \sum_{n=0}^{\infty} \binom{n+3}{3}x^n$$ So what is the coefficient of $x^{12}$ ...


4

Here is an alternate derivation of the generating function by @MarkusScheuer. Suppose we are trying to evaluate $$A(z) = \sum_{n\ge 0} \frac{z^n}{n!} \sum_{k=0}^n {n\choose k} (kx)^{n-k}.$$ Introduce the integral representation $$(kx)^{n-k} = \frac{(n-k)!}{2\pi i} \int_{|w|=R} \frac{1}{w^{n-k+1}} \exp(kxw) \; dw.$$ which certainly holds for $0\lt ...


1

I side with Andrew Woods on this question. The correct coefficient to use is $$P(n,k) = \left(\binom{2n-k}{k}+\binom{2n-k-1}{k-1}\right)\text{,}$$ the number of ways to distribute $k$ non-overlapping pairs in a circle of $2n$ items. $$\text{Andrew}(n) = \sum_{k=0}^{n} (-1)^k \left(\binom{2n-k}{k}+\binom{2n-k-1}{k-1}\right)(2n-2k-1)!!$$ This does not give ...


1

I think the binomial term, representing the number of ways to pick $k$ pairs of adjacent people in a circle of $2n$ people, should in general $(k>0)$ be $$\left(\binom{2n-k}{k}+\binom{2n-k-1}{k-1}\right)$$ Model the circle of people with a necklace of black and white beads, with the arbitrarily chosen "first" person just clockwise of the clasp. Let's say ...


0

$\bf hint:$ you can use partial fractions. $$\frac 1{1-4z+3z^2} = \frac A{1-z} + \frac B{ 1 - 3z} = 1 + z + z^2 + \cdots + 1 + 3z + 9z^2 + \cdots $$ yoiu find that $A = -\frac 12, B = \frac 32$ so that $$\begin{align} \frac 2{1-4z+3z^2} &= \frac 3{ 1 - 3z} - \frac 1{1-z}\\ & = 3\left( 1 + 3z + 9z^2 + \cdots \right) - \left(1+z + z^2 + \cdots ...


5

Note: This answer does not provide a closed expression but a generating function which might also be helpful for further calculations. Let's consider OPs sum by exchanging for (my) convenience $i,j$ with $n,k$ and ignoring the factor $\ln(x)^n$. \begin{align*} \frac{1}{n!}&\sum_{k=0}^n\binom{n}{k}(n-k)^kx^k\tag{1}\\ ...


-2

This is in particular equation (9) in Tilings of Rectangular Regions by Rectangular Tiles: Counts Derived from Transfer Matrices, ArXiv:1406.7788 by Richard J. Mathar.


4

Marko’s comprehensive answer is a bit overwhelming if you’ve not encountered that approach; let me see if I can offer one closer to what you’ve seen before. Once you have a root, you can hang three trees from it: one is its left subtree, another is its centre subtree, and the third is its right subtree. (These are ordered trees, so left, centre, and right ...


0

Consider the difference equation $a_{n+1} - a_{n} = n^{2}$ where $n \geq 0$ and $a_{0} = 1$. It can be quickly determined that \begin{align} \sum_{n=0}^{\infty} n^{2} x^{n} = \frac{x(1+x)}{(1-x)^{3}} \end{align} for which \begin{align} \sum_{n=0}^{\infty} a_{n+1} x^{n} - \sum_{n=0}^{\infty} a_{n} x^{n} &= \frac{x(1+x)}{(1-x)^{3}} \\ \frac{1}{x} \cdot ...


0

$\begin{array}\\ A(x) &=\sum_{n=0}^{\infty} a_n x^n\\ &=a_0+\sum_{n=1}^{\infty} a_n x^n\\ &=a_0+\sum_{n=0}^{\infty} a_{n+1} x^{n+1}\\ &=a_0+\sum_{n=0}^{\infty} (a_{n}+n^2) x^{n+1}\\ &=a_0+x\sum_{n=0}^{\infty} (a_{n}+n^2) x^{n}\\ &=a_0+x\left(\sum_{n=0}^{\infty} a_{n}x^{n}+\sum_{n=0}^{\infty} n^2 x^{n}\right)\\ &=a_0+x\left(A(x)+ ...


0

The species here is $$\mathcal{T} = \epsilon + \mathcal{Z}\mathcal{T}^3$$ or alternatively $$\mathcal{T} = \epsilon + \mathcal{Z}\mathfrak{S}_{=3}(\mathcal{T})$$ which gives the functional equation for the generating function $$T(z) = 1 + z T(z)^3.$$ Extracting coefficients we get $t_0=1$ and for $n>0$ $$t_n = \sum_{p=0}^{n-1}\sum_{q=0}^{n-1-p} t_p t_q ...


2

For first, prove by induction that: $$ F_0 + F_2 + \ldots + F_{2m} = F_{2m+1}-1. \tag{1}$$ Then sum the previous identities for $m=1,2,\ldots, n$, getting: $$ n F_0 + (n-1) F_2 + \ldots +F_{2n} = \left( F_3+F_5+\ldots+F_{2n+1}\right)-n.\tag{2}$$ Since we can prove: $$ F_3 + F_5 + \ldots + F_{2n+1} = F_{2n+2}-2 \tag{3}$$ just like we proved $(1)$, by $(2)$ ...


1

There are many ways to prove this. One way is to notice that $$ F_{2n} = F_{2n-1} + F_{2n-2} = 2F_{2n-2} + F_{2n-3} = 2F_{2n-2} + F_{2n-3} + F_{2n-4} - F_{2n-4} = 3F_{2n-2} - F_{2n-4}. $$ Therefore $$ g_n = 3g_{n-1} - g_{n-2}. $$ Given this, it is easy to prove the claim by induction. Let's rephrase it slightly: $$ g_n = \sum_{i=1}^{n-1} ig_{n-i} + n. $$ In ...


3

You made a mistake in solving $$ x(1+x)= A(1-x)^3+B(1-x)^2+C(1-x)+D$$ A faster way to solve this is the following: $$x = 1 \Rightarrow D=2$$ Next derivate $$1+2x=-3A(1-x)^2-2B(1-x)-C$$ plug in $x=1$. Then derivate again, and plug in $x=1$. Continue...


0

Please note that you can find a complete and detailed answer as part of this follow-up answer of mine. You will find the solution of this question starting there with expression (48).


2

From your last identity giving $P(z)$, for $z\neq1$, you may write $$ \begin{align} P(z) &= \frac{p_0\mu(1-z^{-1})}{\lambda(1-z^r)+\mu(1-z^{-1})}\\\\ &=\frac{p_0\mu}{\mu+\lambda\dfrac{1-z^r\:}{1-z^{-1}}}\\\\ &=\frac{p_0\mu}{\mu-\lambda z\dfrac{1-z^r}{1-z}}\\\\ &=\frac{p_0\mu}{\mu-\lambda z\left(1+z+\ldots+z^{r-1} \right)}\\\\ ...


1

For yet another answer, $$ \frac1{1-x} = \sum_{n=0}^\infty x^n,$$ and $$ \frac1{1-\frac13 x} = \sum_{n=0}^\infty \left(\frac13\right)^n x^n.$$ Differentiating we have $$ \frac{\frac13}{\left(1-\frac13 x\right)^2} = \sum_{n=0}^\infty(n+1)\left(\frac13\right)^{n+1}x^n. $$ Hence $$\frac1{\left(1-\frac13 x\right)^2} = ...


1

If there were complicated rules relating the frequencies of different parts, then there would be no obvious way to write a generating function. Here however it is simple: a first part $1$ is obligatory, then every part $2$ brings along one part$~1$, and then there may be some parts$~1$ left that get in unaccompanied. So effectively you are allowing parts $1$ ...


1

$$\frac{1}{(1-\frac{x}{3})^2}=\frac{1}{1-\frac{x}{3}}\cdot\frac{1}{1-\frac{x}{3}}$$ $$=\sum\limits_{n=0}^\infty(\frac{x}{3})^n\cdot\sum\limits_{n=0}^\infty(\frac{x}{3})^n $$ $$=(1+\frac{x}{3}+(\frac{x}{3})^2+\ldots)(1+\frac{x}{3}+(\frac{x}{3})^2+\ldots).$$ Now we want a single sum in the form of $\sum a_nx^n$, and so we're going to find all of the terms ...


0

Same, just use the binomial coefficient $\binom{-2}{k}$. If you feel scared, just set $\alpha=-2$ and do the Binomial expansion. You should get something like $(-1)^k k(k+1)$ I think.


2

In general, by computing the Taylor series expansion. In this case it happens to work to use $\frac{1}{(1-z)^2}=\frac{\partial}{\partial z}\frac{1}{1-z}$. But a more widely applicable bit of knowledge is that if $f(z)=\sum_{n=0}^\infty a_nz^n$, then $$\frac{1}{1-z}\,f(z)=\sum_{n=0}^\infty\left(\sum_{k=0}^n a_k\right)z^k.$$ And ...


4

Consider that: $$\sum_{n\geq 0} z^n = \frac{1}{1-z}, $$ then differentiate both terms eleven times. You will get: $$\sum_{n\geq 11} n(n-1)\cdot\ldots\cdot(n-10)\,z^{n-11}=\frac{11!}{(1-z)^{12}}$$ or: $$\frac{1}{(1-z)^{12}}=\sum_{n\geq 0}\binom{n+11}{11}z^n .$$


1

$$\begin{align*} \frac32\cdot\frac{x+1}{3-x}&=\frac12\cdot\frac{x+1}{1-\frac{x}3}\\ &=\frac12\left(x\sum_{n\ge 0}\left(\frac13\right)^nx^n+\sum_{n\ge 0}\left(\frac13\right)^nx^n\right)\\ &=\frac12\left(\sum_{n\ge 0}\left(\frac13\right)^nx^{n+1}+\sum_{n\ge 0}\left(\frac13\right)^nx^n\right)\\ &=\frac12\left(\sum_{n\ge ...


1

Write $$\frac{3}{6}\frac{x}{1 - \frac{x}{3}} + \frac{3}{6} \frac{1}{1 - \frac{x}{3}}$$ and use that $$\frac{1}{1 - \frac{x}{3}} = \sum_{n=0}^{\infty} \bigg( \frac{x}{3}\bigg)^n$$


1

Well, I guess I have figured that out: \begin{multline*} \sum_{(\alpha, \beta, \gamma, \delta) \in L^4} x^{\alpha + \beta + \gamma + \delta} = \sum_{\alpha \in L} \sum_{\beta \in L} \sum_{\gamma \in L} \sum_{\delta \in L} x^{\alpha + \beta + \gamma + \delta} = \\ = \sum_{(\alpha, \beta, \gamma) \in L^3} \left(x^{\alpha + \beta + \gamma} \cdot \sum_{\delta ...


2

Hint: If the generating function of a sequence $\{a_n\}$ is $A(x) = \displaystyle\sum_{n = 0}^{\infty}a_nx^n$, then its derivative is simply $A'(x) = \displaystyle\sum_{n = 0}^{\infty}na_nx^{n-1}$, and so, $xA'(x) = \displaystyle\sum_{n = 0}^{\infty}na_nx^{n}$.


4

I’ll get you started. Consider the product $$(x_1+x_1^3+x_1^5+\ldots)(x_2+x_2^3+x_2^5+\ldots)(x_3+x_3^3+x_3^5+\ldots)(x_4+x_4^3+x_4^5+\ldots)\;;$$ a typical term has the form $x_1^\alpha x_2^\beta x_3^\gamma x_4^\delta$, where $\alpha,\beta,\gamma$, and $\delta$ are odd positive integers. If you were to drop the subscripts on the indeterminates, that would ...


1

HINT: $\frac{1-x^{p+1}}{1-x}=1+x+x^2+x^3+...+x^p$ (is called the "Geometric series") for arbitrary number $p$.



Top 50 recent answers are included