数学中国

 找回密码
 注册
搜索
热搜: 活动 交友 discuz
查看: 106|回复: 8

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

[复制链接]
发表于 2020-11-18 10:42 | 显示全部楼层 |阅读模式
题:试证\(\,f(i,j)=((i+j)^2+i+3j)/2\) 是\(\mathbb{N}^2\)到\(\,\mathbb{N}\) 的一一对应.
\(\qquad\) 其中\(\,\mathbb{N}\,\)是非负整数全体, \(\mathbb{N}^2\) 是非负整数对全体.
 楼主| 发表于 2020-11-18 15:05 | 显示全部楼层
本帖最后由 elim 于 2020-11-18 00:53 编辑




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

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-11-18 15:47 | 显示全部楼层
本帖最后由 elim 于 2020-11-18 18:01 编辑

现在求\(\,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\)

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-11-19 09:21 | 显示全部楼层
接下去要问, 如何构造双射 \(g_k:\mathbb{N}^k\to\mathbb{N}\)?
回复 支持 反对

使用道具 举报

发表于 2020-11-19 10:28 | 显示全部楼层
楼上 elim 的帖子很好!已收藏。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-11-20 09:48 | 显示全部楼层
构造\(\,\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))\)

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-11-20 11:00 | 显示全部楼层
王守恩老师看看, 找个更简单直观的对应法? Mathematica 能不能帮上忙?
回复 支持 反对

使用道具 举报

发表于 2020-11-20 19:18 | 显示全部楼层
本帖最后由 王守恩 于 2020-11-21 09:46 编辑
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}}

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



回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-11-20 20:59 | 显示全部楼层
本帖最后由 elim 于 2020-11-20 22:17 编辑

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

考虑 \(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}\)

待续

回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2020-11-25 10:04 , Processed in 0.065429 second(s), 16 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表