23,568 reputation
34263
bio website
location
age
visits member for 4 years
seen 7 hours ago

?


Apr
23
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.
Apr
21
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$.)
Apr
21
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. :-)
Apr
21
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.
Apr
21
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.
Apr
21
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?
Apr
21
revised Solving the non-homogeneous recurrence relation: $g_{n} = 12g_{n-2}-16g_{n-3}+6\cdot 2^n+25n$
fix missing +
Apr
21
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. :-)
Apr
21
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$.
Apr
21
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.
Apr
21
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!
Apr
21
answered Why do exponents not distribute over addition?
Apr
20
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}$ ?
Apr
20
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
reviewed Reject suggested edit on How do I prove that an order of a cycle is its length?
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]$ :-)