# The ratio in terms of sets

The recurrence $a_{n+1}=a_n(n-1/2)$ is related to $\Gamma(n+1/2)$ ( not difficult to prove) and it could be represented in a way like $\frac {(2n-1)!!} {2^n}$ Also I know that $(2n-1)!!$ is the number of permutations of 2n whose cycle type consists of n parts equal to 2; these are the involutions without fixed points (A).

Also, for each $n \in N$, let $f(n)$ is the number of subsets of set $[n]=\ {1,2,...,n}$. Then $f(n)=2^n$ (B)

I wonder about the understanding of the meaning ( sense) of the ration: A/B? What could be the meaning of $\frac {(2n-1)!!} {2^n}$ in terms of sets?

-
Can you clarify your question? Your first question asks about A/B, which is then $\frac{(2n-1)!!}{4^n}$, and you second asks about A which you seem to have answered already. –  Mitch Feb 23 '11 at 23:56
I changed the tags. –  JDH Feb 24 '11 at 5:20

I suspect that your looking for a combinatorial interpretation to the formula $\frac{\left(2n-1\right)!!}{2^n}$. Since $\mbox{gcd}\left(2^n,\left(2n-1\right)!!\right) = 1$ for all $n \geq 1$, this formula cannot be interpreted as enumerating the points in some specified finite set. Since $2^n < \left(2n-1\right)!!$ for all $n\geq 3$, this formula cannot be interpreted as a probability of some kind.
The formula $\frac{\left(2n-1\right)!!}{n!2^n}$ can be interpreted as giving the probability that if two people each flip two separate fair coins $n$ times, then each person gets heads the same number of times. I worked this out by unraveling $\frac{A}{B}$ using binomial identities until I got something that looked like the probability of some easily described random event.
Thank you, it's very helpful. Actually, there is one problem that the real recurrence is $a(n+1)=a(n)(n-1/2)+o(1/n). Do you know a way to select an interval when your interpretation works for the slightly changed recurrence? – Mikhail G Feb 24 '11 at 19:41 I don't know of any ways to modify this game with respect to small changes in your recurrence in such a way that the new game has the same relationship to the new recurrence as the old game had to the original recurrence. I'm not even sure what I meant by "same relationship" in the previous sentence. This doesn't mean that it's not possible to do such a thing though. – Albert Steppi Feb 26 '11 at 23:14 @Albert: The recurrence$M(n+1)/M(n)=n-1/2+o(1/n)$is related to Kendall-Mann property http://oeis.org/A181609 Could you look at the answer from Moron please Recurrence representation(s):$a(n+1)=a(n)(n-1/2)+o(1/n)$and$a(n+1)=a(n)(n-1/2+o(1/n))$It seems to me that your game is a good interpretation, am I right? - I'm glad I could be of help before, but I don't think I know enough to add anything more. It seems that$M\left(n\right)$will tend to$C\frac{\left(2n-1\right)!!}{2^n}$, for some constant$C$, but I don't know how to connect the above game to the Mahonian distribution. It might have something to do with the Mahonian and Binomial distributions both being asymptotically normal, but I don't know much about this stuff, and you probably shouldn't listen to me. – Albert Steppi Feb 28 '11 at 16:32 Well, I just know that "Mixing of Diffusing Particles" tends to be Mahonian arxiv.org/abs/1010.2563. But I do not know any answer about the meaning for the large number n in the process. It looks like you jump from one level to another($M(n+1)/M(n)\$) and this produce some results. Also, it has some relation to Markov chains. All in one, everything is unclear now to me. –  Mikhail G Feb 28 '11 at 17:41