24,416 reputation
34469
bio website
location
age
visits member for 4 years, 4 months
seen 1 hour ago

?


May
6
comment Proving a recurrence relationship for a sequence
Really nice solution, congratulations. :-) The main trick seems to be making sure that the $(n-1)b_{n-2}$ term gets multiplied by $x^{n-1}/(n-1)!$ rather than say $x^n/n!$ or $x^{n-2}/(n-2)!$, so that the $(n-1)$ factor cancels cleanly and we don't have to solve too-complicated differential equations.
May
5
comment Expected number of loops
Just for completeness: yes, $H_n = 1 + \frac12 + \dots + \frac1n$ (harmonic number), and the asymptotics $(\ln n)/2 + 0.98$ mentioned above does indeed give about $3.28$ for $n=100$.
May
5
comment Proving a recurrence relationship for a sequence
Yes definitely the right question is to find an EGF; note that $\exp(x + x^2/2) = 1+x+\frac{2x^2}{2!}+ \frac{4x^3}{3!} + \frac{10x^4}{4!} + \dots$ and the coefficients satisfy the recurrence.
May
5
comment Proving a recurrence relationship for a sequence
Aside: I think the question, in place of "Let $B(x)$ be the recurrence relation for the sequence $b_n$", should have "Let $B(x)$ be the [exponential] generating function for the sequence $b_n$".
Apr
29
comment Placing indistinguishable objects on a indistinguishable shelve
The answer is not $10!$ for either, because if you think about it, the fact that there are $3$ shelves surely matters and must figure in the answer.
Apr
28
comment When tossing a coin, what's the likelihood of coming up heads when it came up 999 tails consecutively?
By the way, if you see TTT, the expected number of heads and tails among the remaining $7$ is $7/2$ each, so the expected total number of heads and tails (among the ten tosses) would now be $7/2 = 3.5$ and $3 + 7/2 = 6.5$ respectively, no longer $5$ and $5$ (that's only the expected value before the results of any tosses).
Apr
28
comment When tossing a coin, what's the likelihood of coming up heads when it came up 999 tails consecutively?
This question is one duplicate, though I expect there are others.
Apr
28
comment When tossing a coin, what's the likelihood of coming up heads when it came up 999 tails consecutively?
The coin has no memory. See gambler's fallacy. This question has been asked and answered many times on this site before.
Apr
28
awarded  Good Answer
Apr
27
comment Find the probability of n different people having the same birthday month
Are there a fixed set of $n$ people? You shouldn't have the leading $n$ factor (e.g. imagine choosing the first of the $n$ people...)
Apr
25
comment Visually deceptive “proofs” which are mathematically wrong
What is the visually deceptive proof here?
Apr
24
comment Is there any good reason not to define $0^0=1$ , such as contradictions in algebra or arithmetic?
@anorton: That is not an inconsistency: the fact that $0^x = 0$ for all positive $x$ (only) does not force anything about the value $x=0$, especially considering the fact that $0^x$ cannot be defined for any $x<0$.
Apr
24
comment How to calculate the following sums?
@user4140: Given that the actual answer involves an irrational constant, I don't see how you can expect that. I mean, yes we could we avoid it somehow, but it's implicitly going to turn up in the answer. What is your goal / what are you trying to do?
Apr
24
comment calculate the proportion of n-node trees whose root has only one or two subtrees.
By the way, note that you can get the fact that (for $n > 2$ as you got) $h_n = 2g_{n-1}$ directly from the generating functions, without calculating any coefficients. Though to actually find $h_n / g_n = 2 g_{n-1} / g_n$ you need the coefficients I guess. Let's wait and see whether this is really what the OP intended, but +1 anyway for answering the question as asked.
Apr
24
comment calculate the proportion of n-node trees whose root has only one or two subtrees.
@cinvro: Isn't $\mathcal{G} = \mathcal{Z} \cdot \operatorname{S\scriptsize EQ}(\mathcal{G})$, so your specification for $\mathcal{R}$ should actually be $\mathcal{R} = \mathcal{Z} \cdot \mathcal{G} + \mathcal{Z} \cdot \mathcal{G} \cdot \mathcal{G}$ (as jschnei does in the answer below)? (Also, $G(z) = (1 - \sqrt{1-4z})/2$, and not what you've written.)
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.