New answers tagged

3

I think you are going in the opposite direction from the direction you want to be going. Although $\frac{1}{(1+x)(1-x)^3}$ is more compact, the expression in your first equation, which is the partial fraction decomposition of $\frac{1}{(1+x)(1-x)^3}$, is the more useful for getting the general term in the series. The partial fraction decomposition is a sum ...


2

$\dfrac{x^2(1+x)}{(1-x)^3}=(2-1)^2x^2+(3-1)^2x^3+(4-1)^2x^4+\cdots$ appeared to be the correct answer, but actually the $a_0=(0-1)^2=1$ term is missing. It corresponds to the constant term $1x^0$ in the generating function. So a $1$ should be added to $\dfrac{x^2(1+x)}{(1-x)^3}$ ...


2

Hint: $Y$ is the sum of $N$ independent random variables, each the count of successes in $m$ iid Bernoulli trials with success rate $q$. So, therefore $Y$ is the count of ... what ?   What distribution does this have? Once you have identified the name of this distribution, you should know what is the probability generating function $\Pi_{Y\mid N}(z)$ ...


0

The conditions are already fulfilled if they're fulfilled for $n=1$ and $n=2$, that is, for triples and quintuples. The triples condition implies that no two boys are adjacent. It follows that for any $n=2k+1$, the neighbourhood consists of a triple and $2k$ adjacent pairs which each contain at most one boy; and for any $n=2k$ the neighbourhood consists of a ...


0

The transformations that you plan to apply to $U_1$, $V_1$, $W_1$ will result in variables $Z_1$, $Y_1$, $X_1$ with the same correlation structure compared to before, so your algorithm will have the desired effect (assuming the desire is to retain the correlation matrix as $R$). This follows from the definition of correlation $$ ...


0

I don't see any way to do this mathematically. Here's code that computes the winning probability using dynamic programming and checks the result with a simulation. You didn't specify what happens when the deck runs out and you can't fill the board; I assumed that in this case you nevertheless remove cards of identical suits in the partially filled board and ...


1

To find the coefficients of the expansion, you can follow the usual "cover" up rule which is essentially the results you have shown albeit buried in indices and what not: $$ \frac{1}{(1-x)(1-2x)...(1-kx)} = \sum_{j=1}^{k} \frac{\alpha_j}{1-jx} $$ say we would want to find an arbitrary $\alpha_j$ for some value of $j \in \{1,2,...,k\}$. We call this $r$ to ...


1

My edition of the book doesn’t have $$\alpha_r = \frac{1}{(1-x)\ldots(1-(r-1)x)(1-(r+1)x)\ldots(1-kx)}\;,$$ which in any case makes no sense, since $\alpha_r$ is a constant and the righthand side is not. However, after letting $x=\frac1r$ it does show $$\begin{align*} \alpha_r&=\frac1{(1-1/r)(1-2/r)\cdots(1-(r-1)/r)(1-(r+1)/r)\cdots(1-k/r)}\\ ...


1

It appears that the $\alpha_j$ coefficients are being computed by the standard Heaviside method (sometimes called the "cover up" method). Heaviside's Method for partial fraction expansion


3

If you assume $\forall n\geq 1$, then I gather any primitive of $f(x) =\frac{e^x-1}{x}$ should do. The rationale behind it is to find a power series $F$ with $F(x) = \sum_{n=1}^\infty \frac{f^{(n)}(0)}{n!} x^n$ (and non-zero radius of convergence) satisfying what you want. That is, $$ F(x) = \sum_{n=1}^\infty \frac{x^n}{n\cdot n!}. $$ Deriving this, you get ...


-2

There infinitely many of them... obviously as long as the function is $n$-times differentiable and $f^{(n)}(0)\neq 0$ you can always multiply constant to modify it to be $1/n$. One example is $e^x/n$


2

Addendum to the generating function part of the answer of @callculus. Assuming WA is not available, it's not too hard to calculate the coefficient by hand. In order to do so it's convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series. This way we can write e.g. \begin{align*} [x^j](1+x)^n=\binom{n}{j} ...


1

The usual technique is to study the function $$f(a, q) = \prod_{n = 1}^{\infty}\frac{1}{1 - aq^{n - 1}}\tag{1}$$ and then express it as a series $$f(a, q) = \sum_{n = 0}^{\infty}x_{n}a^{n}\tag{2}$$ Now we can see that $$f(aq, q) = (1 - a)f(a, q)\tag{3}$$ so that $$\sum_{n = 0}^{\infty}x_{n}a^{n}q^{n} = (1 - a)\sum_{n = 0}^{\infty}x_{n}a^{n}\tag{4}$$ and thus ...


2

The generating function for school A,B,C and D are $ \sum_{k=3}^{\infty }x^k, \sum_{k=2}^{5 }x^k , \sum_{k=0}^{4}x^k,\sum_{k=0}^{\infty }x^k$ I think the limits are self explaining. For all four schools together the generating function is $ \sum_{k=3}^{\infty }x^k\cdot \sum_{k=2}^{5 }x^k \cdot \sum_{k=0}^{4}x^k\cdot \sum_{k=0}^{\infty }x^k$ Only 19 ...


2

Let $A,B,C$ be the count of identical computers distributed to the relevant schools (and school D gets $19-A-B-C$).   Using the principle of inclusion and exclusion to avoid over-counting, you want the measure: $$\begin{align} & \lvert\{3{\leq}A~,2{\leq}B{\leq}5~,C{\leq}4\}\rvert \\[1ex] ...


2

In view of the possibility of connecting with the history of combinatorics I have also implemented the DFA method for sets of patterns as opposed to just one pattern. The algorithm is the same except that the DFA does not consist of a chain with backlinks as in the case of a single pattern but a tree of prefixes with backlinks to nodes ...


2

By way of enrichment I present an implementation in Maple of the DFA method for arbitrary count alphabets and arbitrary patterns to be avoided. The algorithm is the same as in the companion post: compute a DFA whose states represent the longest prefix of the pattern seen at the current position in the string as it is being scanned by the DFA, with ...


1

The coefficient of $x^n$ in $\frac1{1-x}$ is $1$. The coefficient of $x^n$ in $\frac1{1-x^a}$ is $1$ if $n$ ia a multiple of $a$, $0$ otherwise; in other words: it is the number of ways to partition $n$ into parts of size $a$. From the way the Cauchy product of power series work, this last interpretation can be generalized to your $G$: The coefficient of ...


4

This answer is based upon the Goulden-Jackson Cluster Method which is a convenient method to derive a generating function for problems of this kind. We consider the set of words in $ \mathcal{V}^{\star}$ of length $n\geq 0$ built from an alphabet $$\mathcal{V}=\{A,B\}$$ and the set $\mathcal{B}=\{ABBA\}$ of bad words, which are not allowed to be part of ...


3

We seek to enumerate strings over $\{A,B\}$ that avoid the pattern $ABBA.$ With $z$ representing the letter $A$ and $w$ representing the value $B$ and marking interior ocurrences of $BB$ with $v$ we obtain the generating function $$G(z, w, v) = \frac{1}{1-w} + (1+w+w^2+w^3+\cdots) (z+z^2+\cdots) \\ \times \left(\sum_{q\ge 0} (w+vw^2+w^3+\cdots)^q ...


4

This will not be possible in general. Indeed, if you have both $H(x) = \Phi(x,G(x))$ and $H(x) = xG'(x) + G(x)$ for all $x$ (where $\Phi$ is a nice, regular function), then you can derive an expression of the form $\Phi(x, G(x)) = xG'(x) + G(x)$ for all $x$, i.e. a differential equation of the form $$G^\prime(x) = \Psi(x,G(x)).$$ (where $\Psi$ is ...


3

It shouldn't be possible to give a more simplified expression which is valid in general, since both $G(x)$ and $G'(x)$ depend on the choice of coefficients $(a_n)_n$ (albeit in a different manner). For example, let $G_1(x)=e^x$ and $G_2(x)=\sin x$. Then: $$H_1(x)=(x+1)G_1(x)$$ $$H_2(x)=xG_2(\frac{\pi}{2}-x)+G_2(x)$$ Thus while knowledge of $(a_n)_n$ ...


1

Note that $$(n+1)C_n=\binom{2n}{n}\qquad\qquad n\geq 0$$ are the Central Binomial Coefficients with the generating series representation \begin{align*} \sum_{n=0}^\infty\binom{2n}{n}x^n=\frac{1}{\sqrt{1-4x}}\qquad\qquad |4x|<1\tag{1} \end{align*} A generating function for $\{(n+2)C_{n+1}\}^\infty_{n=0}$ is therefore \begin{align*} \sum_{n= ...


-1

This is my best attempt: There are 30 pieces of fruit. Split them into 3 baskets containing 10 pieces of fruit each basket 1 30 ways for fruit 1 29 ways for fruit 2 ..... 21 ways for fruit 10 basket 2 20 ways for fruit 1 19 ways for fruit 2 .... 11 ways for fruit 10 basket 3 10 ways for fruit 1 9 ways for fruit 2 .... 1 way for fruit 10 Looking ...


1

This is not difficult using a CAS though I suspect something more clever is expected. The species here is $$\mathfrak{S}_{=3} (\mathfrak{M}_{=10}(\mathcal{A}+\mathcal{B}+\mathcal{P})).$$ This yields $$[A^{10} B^{12} P^8] (Z(S_{10})(A+B+P)))^3 = 1980.$$ The notation $Z(S_{10})$ refers to the cycle index of the symmetric group. We also use the fact ...


0

We need to be very careful about what we are assuming is distinguishable and what is not distinguishable. Both @almagest and @windircursed have correct answers with different sets of assumptions: @almagest assumed that both the baskets and the fruit are indistinguishable while @windircursed assumed that only the baskets were indistinguishable. A third ...


4

Assuming baskets are indistinguishable (as well as apples etc), there are surprisingly few arrangements possible. For apples the possible splits between baskets are: (5,2,0), (5,1,1), (4,3,0), (4,2,1), (3,3,1), (3,2,2). For type (5,2,0) the possible splits of lemons are: (0,3,2), (0,2,3), (0,1,4), (0,0,5) (and in each case the bananas are distributed to ...


1

First you have to choose 5 fruits for the first basket, you have $15\choose5$ combinations. When you choose fruits for the second basket, now you have 10 fruits and you need to choose 5 again, so you have $10\choose5$ combinations. Finally, you are left with 5 fruits and 1 basket, so there is $5\choose5$ which is 1 combination. Now just multiply the results: ...


0

Let $A(x)=\sum_{n=0}^\infty a_n x^n$. To get to the differential equation, we first note that $A'(x)=\sum_{n=1}^\infty n a_n x^{n-1}$. With this in mind, we multiply both sides of the recurrence by $x^{n-1}$ and sum from $n=0$ to $\infty$ to obtain $$A'(x)=3A(x)-4x A(x)+8x e^{3x}$$ where we have used the fact that $\displaystyle\sum_{n=0}^\infty ...


1

You can do this using inclusion-exclusion. The number of ways of distributing $15$ goals over $26$ games such that $2$ goals were scored in $k$ particular games and at least $4$ goals were scored in $l$ particular games is $$ \binom{15-2k-4l+26-k-1}{26-k-1}\;, $$ so the desired count is $$ ...


1

It is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series. We obtain \begin{align*} [x^{12}]&(1+x+x^2+x^3)^5\\ &=[x^{12}]\left(\frac{1-x^4}{1-x}\right)^5\tag{1}\\ &=[x^{12}]\left(\sum_{k=0}^{5}\binom{5}{k}(-1)^kx^{4k}\right)\left(\sum_{n=0}^\infty\binom{-5}{n}(-x)^n\right)\tag{2}\\ ...


2

Enough has been said about the generating function approach in other comments and answers. Perhaps it's also worth mentioning that generating functions can easily be expanded using Wolfram|Alpha. But in the present case generating functions are overkill. The most efficient solution to the problem is to note that you're looking for the number of ways of ...


0

You're correct in forming the generating function $$ F = (1 + x + x^2 + x^3)^5 $$ Now, you're looking for the coefficient of $x^{12}$ (Since each $x$ represents a figure, you want 12 of them. The coeffieint will tell you the number of ways $G$ produced the $12$ - which to us gives the number of ways to distribute $12$) However, expanding it out makes us ...


0

First, not every function has a convenient algebraic formula -- in general, for a function on $\{ 1, \ldots, n\}$, you should expect a polynomial formula to involve powers up to $x^{n-1}$, and even if you use trig or exponential functions, you generally don't save much. Second, you can build up a lot of functions that are "case based" by using a few ...


1

With as much detail as possible, $$\begin{align*} G_a(x) &= \sum_{n=0}^\infty a_n x^n \\ &= a_0 x^0 + a_1 x^1 + \sum_{n=2}^\infty a_n x^n \\ &= a_0 + a_1 x + \sum_{n=2}^\infty (a_{n-1} - a_{n-2}) x^n \\ &= a_0 + a_1 x + \sum_{n=2}^\infty a_{n-1} x^n - \sum_{n=2}^\infty a_{n-2} x^n \\ &= a_0 + a_1 x + \sum_{n=1}^\infty a_n x^{n+1} - ...


0

We can verify a certain periodicity in the terms without solving the recurrence $a_n$. In fact $$a_0=0\\a_1=1\\a_2=1\\a_3=0\\a_4=-1\\a_5=-1\\a_6=0\\a_7=1$$ Hence the sequence of values can be considered as beginning again from $a_6$ and $a_7$; an so on.... Consequently the asked generating function is ...


1

Well one place we could start would be to note that we could define 𝔾 on a larger set; namely any real sequence of coefficients for which the generating series is absolutely convergent or even Abel summable (namely the limit of the series exists as s→1 even if the series diverges when one substitutes s=1). If we are willing to consider quasiprobability ...


2

Hint. One has $$ g'(x) = \left(\sum^\infty_{n=0}F_n \frac{x^n}{n!}\right)'=\sum^\infty_{n=1}n \times F_n \frac{x^{n-1}}{n!}=\sum^\infty_{n=1}F_n \frac{x^{n-1}}{(n-1)!}=\sum^\infty_{n=0}F_{n+1} \frac{x^n}{n!} $$ Can you do the same with $g''(x)$? Then use $$ F_{n+2}=F_{n+1}+F_n, $$ to get the announced identity.


1

Here is my attempt at a Python implementation (2 or 3) of gf3 and gf5. I am only using builtin libraries, so hopefully that will encourage others to play with this. My results agree with the above for $1\leq n \leq30$ and $n=50$ but this will obviously need verification. The performance of gf5 is not great, over 400 seconds for $g_{55}(u)$ alone. I ...


0

I found very useful material in the following documents. Newman, structure of complex networks http://arxiv.org/abs/cond-mat/0303516 Newman, random graphs as models of networks http://www.santafe.edu/media/workingpapers/02-02-005.pdf Callaway at al. Network Robustness and Fragility: Percolation on Random Graphs ...



Top 50 recent answers are included