# Can you define a bijective function from $\mathbb{N}\longrightarrow \mathbb{N}_k\times \mathbb{N}$

Can you define a simple bijective function from $\mathbb{N}$ to $\mathbb{N}_k\times \mathbb{N}$ (or from $\mathbb{N}$ to $\mathbb{N}\times\mathbb{N}_k$)?
P.s.: $\mathbb{N}_k=\{1,2,3,\cdots, k\}$

• FYI, your $\mathbb{N}_k$ is normally written as $[k]$ in combinatorics. Commented Sep 13, 2015 at 17:20
• uhm - yes. Start, e.g., by mapping $\{1,2,\ldots, k\}$ to $(1,1), (2,1), \ldots (k,1)$ (if you start counting in $\mathbb{N}$ at $1$) Commented Sep 13, 2015 at 17:23
• @Thomas: Is $f(n)=(n,1), \quad \forall n\in \mathbb{N}$ bijective? Commented Sep 13, 2015 at 17:33
• No. The next step would be to map $k+1$ to $(1,2)$, then, $k+2$ to $(2, 2)$ and ($\ldots$) $2k$ to $(k,2)$. Then $2k+1$ to $(1,3)$, $2k+2$ to $(2,3)$. Can you recognize the pattern? Commented Sep 13, 2015 at 17:37
• @Thomas: I'd like to have a formula for $f$. Can you give me one? Commented Sep 13, 2015 at 17:42

(In particular, the Euclidean division algorithm produces, for each $n \in \{0,1,2,3,\dotsc\}$, a unique $q \in \{0,1,2,3,\dotsc\}$ and $r \in \{ 1,2,3,\dotsc,k-1 \}$ so that $n=qk+r$. You can then fiddle this around to get the particular bijection you want.)
• This is what I had in mind, too. :-) +$1$ Commented Sep 13, 2015 at 17:23