22,221 reputation
33761
bio website
location
age
visits member for 3 years, 9 months
seen 2 hours ago

?


6h
comment calculate the proportion of n-node trees whose root has only one or two subtrees.
@jschnei: Yes from the expressions for R and G, I assume the intention is a plane (= rooted ordered) tree, unlabelled.
2d
comment Using a reverse polynomial for a partial fraction decomposition in a recurrence relation problem
At the very least, you have a minus-sign missing: it's not true that $x^2 + x - 1 = (1-px)(1-\hat{p}x)$, instead $x^2 + x - 1 = -(1-px)(1-\hat{p}x)$. (Another way of seeing it: $x^2 + x - 1$ can't be written in the form $(1-ax)(1-bx)$ as the constant term is different, so we can scale it so that it's right: writing $-(x^2 + x - 1) = (1 - ax)(1 - bx)$ gives $ab = -1$ and $a + b = 1$, so $a$ and $b$ are roots of $t^2 - t -1 = 0$.)
2d
comment Solving the non-homogeneous recurrence relation: $g_{n} = 12g_{n-2}-16g_{n-3}+6\cdot 2^n+25n$
Also confirmed that the messy expression for $g_n$ given by the above, namely $19 - 2(n+1)2^n + 5(n+1) + 2\frac{(n+1)(n+2)}{2}2^n - (-4)^n$ does indeed simplify to $-(-4)^n + 2^n(n+1)n + 5n + 24$ as you got. :-)
2d
comment Solving the non-homogeneous recurrence relation: $g_{n} = 12g_{n-2}-16g_{n-3}+6\cdot 2^n+25n$
I independently got the same $A(z)$ as you. (Well, I plugged in $\dfrac{23 + 12z - 284z^2 + 48z^3/(1-2z) + 25z/(1-z)^2}{1 - 12z^2 + 16z^3}$ into Wolfram Alpha: apart from the first expression above, it also gives the partial fraction decomposition thankfully.) The OP mistakenly wrote the $48z^3/(1-2z)$ term as $6/(1-2z)$, so that's the reason for the difference.
2d
comment Solving the non-homogeneous recurrence relation: $g_{n} = 12g_{n-2}-16g_{n-3}+6\cdot 2^n+25n$
@JackReacher: Actually the right expression is $48z^3/(1-2z)$: need to pull out both $2^3$ and $z^3$, to make the sum run from $0$ instead of $3$. Or you can do it as $6/(1-2z) - 6(1 + 2z + 2^2z^2)$ and get the same thing.
2d
comment Solving the non-homogeneous recurrence relation: $g_{n} = 12g_{n-2}-16g_{n-3}+6\cdot 2^n+25n$
By the way, $\sum_{n = 3}^{\infty} 6 \cdot 2^nz^n = (6)(2^3)\sum_{n = 0}^\infty 2^nz^n$, so your $\frac{6}{1-2z}$ term should actually be $\frac{48}{1-2z}$, right?
2d
comment Solving the non-homogeneous recurrence relation: $g_{n} = 12g_{n-2}-16g_{n-3}+6\cdot 2^n+25n$
You're right about it being pretty nasty. The generating function is useful to get asymptotics (you only need to look at the singularities), but actually carrying out the partial fraction decomposition seems to require more persistence than is justifiable. :-)
2d
comment Probability of at least one card matching when flipping through two separate decks.
+1; numerically, the probability of at least one match is $923/924 \approx 0.9989$.
2d
comment Recurrence relation with generating function problem
I was going to post an answer suggesting this "simpler way", but I feel the OP's way actually turns out to be simpler here.
2d
comment Combinatorial explanation for why $n^2 = {n \choose 2} + {n+1 \choose 2}$
Yes, seems more satisfying now. :-) By the way, your geometric picture along with the proof that $1 + 2 + \dots + n = \binom{n + 1}{2}$ might make for an elegant version!
2d
comment Combinatorial explanation for why $n^2 = {n \choose 2} + {n+1 \choose 2}$
What is the combinatorial argument that the latter number is $\binom{n+1}{2}$ ?
2d
comment How do I prove that an order of a cycle is its length?
Might be worth adding a clarifying note that "order" here means its order in the permutation group, i.e. the smallest $n$ such that $\sigma^n$ is the identity permutation. (Someone had proposed an edit to the question with wording like "order of the cycle generator", which I find even more confusing.)
Apr
20
comment Prove that there are two frogs in one square.
There is no probability in the quoted question; "prove that it is possible..." just means that there exists some way of arranging things.
Apr
20
comment Hint finding exact value of half-angle when $\tan (\theta) = {3}$
In the fraction under the square root (in my comment above), the numerator $(10 + \sqrt{10})(10 + \sqrt{10})$ is of course $(10 + \sqrt{10})^2$ (you can leave it like that, because you're going to take its square root next). The denominator $(10 - \sqrt{10})(10 + \sqrt{10})$ is $10^2 - (\sqrt{10})^2 = 100 - 10 = 90$. You've made some mistake somewhere in your calculation.
Apr
20
comment Hint finding exact value of half-angle when $\tan (\theta) = {3}$
You are doing right so far: your $$\sqrt{{10+\sqrt{10}}\over{10-\sqrt{10}}}$$ is equal to (by your idea of "multiplying the top and bottom by the conjugate") $$\sqrt{\frac{10 + \sqrt{10}}{10 - \sqrt{10}}\frac{10+\sqrt{10}}{10 + \sqrt{10}}}$$ If you get stuck again, note that $\sqrt{90} = 3\sqrt{10}$.
Apr
20
comment Hint finding exact value of half-angle when $\tan (\theta) = {3}$
@JasonS.: the formula gives $\tan(2y)$ in terms of $\tan y$. What you've done is find $\tan(2\theta)$, instead of finding $\tan(\theta/2)$ as the question asks. Instead, try letting $y = \theta/2$, and apply the formula and see what turns up.
Apr
20
comment combinatorial proof $\sum_{i=0}^m x^i=\frac{x^{m+1}-1}{{x-1}}$
@user4140: The second one also works only for $x$ being positive integers, not arbitrary $x$. In fact, it holds for only countably many $x$ rather than the uncountably many in $[0, 1]$ :-)
Apr
20
comment combinatorial proof $\sum_{i=0}^m x^i=\frac{x^{m+1}-1}{{x-1}}$
@user4140: What is the combinatorial interpretation of $x$ in that proof?
Apr
20
comment combinatorial proof $\sum_{i=0}^m x^i=\frac{x^{m+1}-1}{{x-1}}$
@user4140: Do you know of a combinatorial proof of any identity involving an arbitrary $x$ ?
Apr
18
comment Kind of basic combinatorical problems and (exponential) generating functions
Also, you need ordinary generating functions here, not exponential ones (at least, not in the way you wrote them). Although the dice are distinguishable, there is no ordering in the set of results.