格点图形计数

1/29目录格点正三角形计数.................................................................................................2一、可见三角形计数...........................................................................2二、格点三角形计数...........................................................................3可见平行四边形计数...........................................................................................11方法一.................................................................................................11方法二.................................................................................................12方法三.................................................................................................14格点正方形计数...................................................................................................15一、可见正方形计数.........................................................................15二、格点正方形计数.........................................................................15格点正六边形计数...............................................................................................17一、可见正六边形计数.....................................................................17二、格点正六边形计数.....................................................................22结语.......................................................................................................................292/29格点图形计数总题目（可见类）：一个边长为n的正多边形被平行于其边的直线分割成边长为1的正多边形，求可见的正多边形有多少个？总题目（格点类）：一个边长为n的正多边形被平行于其边的直线分割成边长为1的正多边形，求顶点在格点上的正多边形有多少个？格点正三角形计数一、可见三角形计数题目：一个边长为n的正三角形被平行于其边的直线分割成边长为1的正三角形，求可见的正三角形有多少个？根据上篇文章中的方法，我们在计数时按照正放和倒放两种类型，并在每一类中又按照边长为1，边长为2⋯⋯来有序计算是很容易得出准确答案的。有的同学就会问，是否有某个一般性的表达式让我们可以直接计算，而不必每次都分类计数？当然有，我之前也提到了，只要将我们的过程总结为任意层（假设为n层）并计算即可求出一个确定的符合一般规律的表达式。由于在中间变化中并非完全是一个一个的递变，而是存在两个两个递变的情形，所以我们要分成奇数层和偶数层来单独分析（虽然有可能得出一个奇偶层都符合的表达式，但是目前尚不确定，需要看具体结果）。以下苏老师根据之前的方法写了一个奇怪的表达式并计算出了一个不奇怪的我们可以使用的表达式。当n为奇数时：12221111112318nniiijijjjnnn当n为偶数时：3/29212111112218nniiijijjjnnn从结果可见，奇数层和偶数层的表达式比较接近但是并不相同。如果大家能够记住这两个式子，那么以后再看到这种数三角形的题就不必分类算了，直接将层数n的具体值代入式子计算即可。比如一个5层的正三角形网格，它所包含的可见的正三角形就有215125351488个，【由于5是奇数，所以要将n=5代入这个式子2112318nnn】。其实这类正三角形个数计数相对而言是比较简单的，略复杂的是格点正三角形的计数，也就是所有顶点落在格点上的正三角形都要数。比如图1-1-1中的红色正三角形。二、格点三角形计数题目：一个边长为4的正三角形被平行于其边的直线分割成边长为1的正三角形，以这些正三角形的顶点为顶点的正三角形有多少个？补充说明：其一，“平正多边形”。在一个三角形格点中，有很多格点正三角形，他们有些是平放的，有些是斜着的，我把某边（通常是上面那条边）平行于给定的大正三角形的某边图1-1-14/29（通常是上面那条边）的正三角形称为平正三角形。其他多边形同理。比如图1-2-3所示的红色三角形，蓝色三角形和绿色三角形都是平正三角形。其二，“旋量”。我们在图1-2-1所示的正三角形格点中可以数出很多格点正三角形，有些正三角形的上边平行于最大的外框三角形（即上述的平正三角形），而有些则略有倾斜——边并不平行于外框三角形的边，但是我们可以将那些边并不平行于外框三角形的边的正三角形理解成由那些边平行于外框三角形的边的正三角形通过旋转和缩放构成的。图1-2-1HGKBDINMFLJCAEO图1-2-2重心HGKBDINMFLJCAEO5/29比如三角形AOE经过旋转和缩小后就得到了三角形BMI，当然也可以得到三角形CJK和DFN，而且这些旋缩后的正三角形都与大正三角形AOE相接。我们如果每次都用旋转和缩放来描述某个三角形不太方便，所以我就选择该三角形的左上点跟与它外接的平放的三角形的左上点的单位距离来衡量，而且这个距离我把它称为旋缩量，简称旋量。比如，三角形BMI就是三角形AOE的旋量为1（AB的单位距离为1）的正三角形，或者直接说三角形BMI的旋量为1。当然，有了这个概念我们也可以将三角形AOE理解为旋量为0的三角形，也就是它自己本身就是自己的旋量为0的正三角形。总结一下，在图1-2-2中，对于三角形AOE而言，旋量为0的三角形是三角形AOE，旋量为1的三角形是三角形BMI，旋量为2的三角形是三角形CJK，旋量为3的三角形是三角形DFN。除了正三角形，其他的多边形格点我们也可以用同样的方法来描述与之相接的多边形。比如在如图1-2-3所示的4×4的正方形网格中，对于正方形ABCD而言，旋量为0的正方形是正方形ABCD，旋量为1的正方形是正方形EFGH，图1-2-3AKLIFGHECJDB6/29旋量为2的正方形是正方形IJKL。其三，“旋数”。通过上述旋量的解释我们知道，任何一个边长为n个单位长度的的正多边形所包含的内接的正多边形有旋量为0的，旋量为1的，旋量为2的，⋯⋯旋量为n-1的，总共有n个，也就是说某个正多边形的所有旋量图形的个数跟它的边长的单位长度是相等的。比如图1-2-4中，边长为4的平正六边形的旋数为4，旋量分别是0,1,2,3,相应的正六边形分别是棕色的正六边形，红色的正六边形，绿色的正六边形和蓝色的正六边形。有了这些基础知识，我们就可以进行后续工作了。题目让我们计数所有的格点正三角形的个数，那么我们就从边长和旋量来综合分析。这些所有的正三角形先不管边长的话都可认为是平正三角形（也即旋量为0的正三角形）和旋缩后产生的正三角形。由之前的旋量解释知道，当图1-2-47/29确定了某一边长后，其实旋数也就确定了，也意味着，我们只需要计算出某边长的所有平正三角形的个数，再用这个个数乘以旋数即可得到该边长下的所有正三角形（包含内接的，也就是旋量非0的）。图1-2-5中红色部分给出了边长为1的所有平正三角形，他们只有旋量为0的正三角形，所以总个数为：454+3+2+111102图1-2-5HGKBDINMFLJCAEO图1-2-6HGKBDINMFLJCAEHGKBDINMFLJCAEHGKBDINMFLJCAEHGKBDINMFLJCAEHGKBDINMFLJCAEHGKBDINMFLJCAEOOOOOO8/29图1-2-6中给出了边长为2的所有平正三角形，他们都有旋量为0和旋量为1（旋量为1时恰好是倒放的）的正三角形，所以总个数为：343+2+122122图1-2-7中给出了边长为3的所有平正三角形，他们都有旋量为0、旋量为1和旋量为2的正三角形（如图1-2-8所示），所以总个数为：232+13392图1-2-7HGKBDINMFLJCAEHGKBDINMFLJCAEHGKBDINMFLJCAEOOO红色：旋量为0绿色：旋量为1蓝色：旋量为2图1-2-8HGKBDINMFLJCAEO9/29图1-2-9中给出了边长为4的平正三角形，他有旋量为0、旋量为1、旋量为2和旋量为3的正三角形（如图1-2-10所示），所以总个数为：1214442我们把上述分散的式子连贯起来可能更有利于发现规律。1+2+3+41+1+2+32+1+23+1445342312=1+2+3+42222图1-2-9HGKBDINMFLJCAEO红色：旋量为0蓝色：旋量为1青色：旋量为2黑色：旋量为3图1-2-10HGKBDINMFLJCAEO10/2922225432=1+2+3+4=10+12+9+4=35CCCC不难发现：其实就是从某几个中选两个再乘以边长的一个简单组合！如果我们把公式写成n项（即有任意n层时），就是下面这样的：222211243=1+2+3++=nnnnCCCnCC当然化简后的式子43nC可能让大家很费解，不过等大家学了高中的排列组合就容易理解了，其实就是一个组合恒等式而已。我在此也给出一个参考的理解方式。43nC很容易理解，也就是从n+3个选出4个。那为什么43nC等于22221121+2+3++nnnCCCnC呢？我把它变得标准一点更有利于大家理解：4121212123112312=++++nnnnnCCCCCCCCC。我们选出的4个数必然存在大小关系，第2大的数是有范围的，只能在n+2，n+1，n，n-1，⋯⋯，4，3内，第2大的数不可能为n+3，因为n+3是最大的；也不可能为2，1因为即便取到最小的4个数4,3,2,1，排第2大的起码是3。有了这个范围我们只需将第2大的数的所有情况相加即等于从n+3个选出4个的所有组合情况了。当第2大的为n+2时，因为第2大的确定了，只需在比n+2大的数中选1个当老大，在比n+2小的数中选2个当老三、老四即可，有1211nCC种；当第2大的为n+1时，因为第2大的确定了，只需在比n+1大的数11/29中选1个当老大，在比n+1小的数中选2个当老三、老四即可，有122nCC种；依次类推，将所有种数相加即是12121212112312++++nnnnCCCCCCCC，故等式成立！总结：1、对于n层的格点三角形计数，我