Two Enumeration Questions

**gutnedawg** · January 13th 2011, 05:29 PM

are we finished with f(a).b and when a is odd f(a)=-(a+1)/2 and when a is even f(a)=a/2 ?

**emakarov** · January 14th 2011, 03:17 AM

Originally Posted by DrSteve

$\mathbb{N}\rightarrow \mathbb{N}\times \mathbb{N}\rightarrow \mathbb{Z}\times \mathbb{N}\rightarrow \mathbb{Q}$ .

The first is the inverse of the pairing function. The second is the map $(a,b)\rightarrow (f(a),b)$ where f is the function we've previously discussed, and the third is the map $(a,b)\rightarrow a.b$ .

For the function suggested by Plato, one can take $p_1(n)=\max\{k\in\mathbb{N}\mid\text{$2^k$ divides $n$}\}+1$ and $p_2(n)=(n/p_1(n)+1)/2$ . (One must check whether $p_1(n)$ and $p_2(n)$ need to assume 0 and whether they actually do.) Then $n\mapsto(p_1(n),p_2(n))$ is a bijection $\mathbb{Z}^+\to\mathbb{Z}^+\times\mathbb{Z}^+$ , which is the first step in the chain at the top of this post.

**DrSteve** · January 14th 2011, 04:00 AM

Thanks emakarov - I didn't remember which direction was technically called the pairing function.

gutnedawg, you essentially got my idea right. The bijection $F:\mathbb{N}\rightarrow A$ is given by $F(n)=f(a).b$ where $f$ is the function you described and $\pi(a,b)=n$ , where $\pi$ is the pairing function.

(Here $A$ is the set of rational numbers with terminating decimal expansions.)

Thread: Two Enumeration Questions

LinkBack

Thread Tools

Display

Similar Math Help Forum Discussions

Enumeration question

Enumeration question

Clarification on enumeration

Enumeration problem

enumeration

Search Tags