试证：f(i,j)=[(i+j)^2+i+3j]／2 是非负整数对全体 N^2 到非负整数全体 N 的一一对应

elim

题：试证\(\,f(i,j)=((i+j)^2+i+3j)/2\) 是\(\mathbb{N}^2\)到\(\,\mathbb{N}\) 的一一对应.
\(\qquad\) 其中\(\,\mathbb{N}\,\)是非负整数全体, \(\mathbb{N}^2\) 是非负整数对全体.

elim

现在的问题是, \(g^{-1}: \mathbb{N}\to\mathbb{N}^2\) 的表达式是什么?

elim

现在求\(\,g^{-1}.\;\)从 \(g(m,n)={\small\dfrac{(m+n)(m+n+1)}{2}}+n=k\) 知道,
对 \(\sigma_k = \max \{u\in\mathbb{N}: \frac{u(u+1)}{2}\le k\}=\big\lfloor\large\frac{-1+\sqrt{1+8k}}{2}\big\rfloor,\)
\(n_k = k-{\large\frac{\sigma_k(\sigma_k+1)}{2}},\;m_k=\sigma_k-n_k.\)
于是\(\,g^{-1}(k)=(m_k,n_k),\;\;g(m_k,n_k)=k\)

elim

接下去要问, 如何构造双射 \(g_k:\mathbb{N}^k\to\mathbb{N}\)?

luyuanhong

楼上 elim 的帖子很好！已收藏。

elim

构造\(\,\mathbb{N}^k\,\)到\(\,\mathbb{N}\,\)的双射,本质上就是将\(\,\mathbb{N}^k\,\)的元素不漏不重地
排成一个序列\(\small\{P_k\}_{k=0}^{\infty}\). 从主贴可以看出,定义\(\,g_1=\textbf{id}_{\mathbb{N}},\)
\(\quad g_2=g,\;g_{k+1}(m_1,\ldots,m_{k+1})=g(m_1,g_k(m_2,\ldots,m_k)),\)
则\(\,g_k:\mathbb{N}^k\to\mathbb{N}\,\)是双射.其逆映射亦可归纳地给出:
\(\quad g_2^{-1}=g^{-1},\;g_{k+1}^{-1}=(g^{-1}(k)\cdot(1,0)),g_k^{-1}(g^{-1}(k)\cdot(0,1))\)

elim

王守恩老师看看, 找个更简单直观的对应法? Mathematica 能不能帮上忙?

王守恩

elim 发表于 2020-11-20 11:00
王守恩老师看看, 找个更简单直观的对应法? Mathematica 能不能帮上忙?

Table[Table[((j + i)^2 + 3 j + i)/2, {j, 0, 15}], {i, 0, 9}]

{{0, 2, 5,  9, 14, 20, 27, 35, 44, 54, 65, 77, 90, 104, 119, 135},
{1, 4,  8, 13, 19, 26, 34, 43, 53, 64, 76, 89, 103, 118, 134, 151},
{3, 7, 12, 18, 25, 33, 42, 52, 63, 75, 88, 102, 117, 133, 150, 168},
{6, 11, 17, 24, 32, 41, 51, 62, 74, 87, 101, 116, 132, 149, 167, 186},
{10, 16, 23, 31, 40, 50, 61, 73, 86, 100, 115, 131, 148, 166, 185,205},
{15, 22, 30, 39, 49, 60, 72, 85, 99, 114, 130, 147, 165, 184, 204, 225},
{21, 29, 38, 48, 59, 71, 84, 98, 113, 129, 146, 164, 183, 203, 224, 246},
{28, 37, 47, 58, 70, 83, 97, 112, 128, 145, 163, 182, 202, 223, 245, 268},
{36, 46, 57, 69, 82, 96, 111, 127,  144, 162, 181, 201, 222, 244, 267, 291},
{45, 56, 68, 81, 95, 110, 126, 143, 161, 180, 200, 221, 243, 266, 290, 315}}

在这里，我们可以将所有自然数不漏不重地罗列出来。
虽然行有无数行，列有无数列。但从对角线出发，还是可以排序的。

elim

这就是主贴的对应. 还有没有更自然对称的?

考虑 \(E_m=\{(a_1,...., a_k)\in\mathbb{N}^k; a_1+\cdots+a_k=m\}\)
则 \(\displaystyle\bigcup_{m=0}^{\infty}E_m = \mathbb{N}^K\) 是不交并. \(|E_m|=\small\dbinom{k+m-1}{m}\)
\(\displaystyle\big|\bigcup_{m=0}^n E_m\big|=\sum_{m=0}^n{\small\dbinom{k+m-1}{m}}=\small\dbinom{n+k}{n}\)

待续