也谈网格不反向路径种数的计算公式

《中学数学杂志》2003年第4期刊登了《网格不反向路径种数的计算公式》一文,文中探究了网络不反向路径的公式,其问题如下: 题l 如图1,在某个城市中,M、N两地之间有整齐的街道网,若规定只能向东或北两个方向沿图中的街道前进,则从M到N的不同走法共有( ) A.25种B.15种C.13种D.10种     

递推法解排列组合问题

[例1] 走上10级的阶梯,每步可一级或两级,问有多少种不同的走法? 解法1 按每种走法中一步上两级的步数k(k=0,1,2,3,4,5)分成6类,走上10级阶梯的步数是10-k,这一类的走法数是C_(10-k)~k。由加法原理,不同走法总数为 N=C_10~0+C_9~1+C_8~2+C_7~2+C_6~4+C_5~5=89。下面是递推法。解法2 设走上n级阶梯的走法有a_n种,易知a_1=1,a_2=2,当n>2时,若第一步上一级则有a_(n-1)种走法,第一步上两级则有a_(n-2)种走法,故a_n=a_(n-1)+a_(n-2)(n≥3)。于是当阶梯级数n=1,2,…,10时,走法数依次是 1,2,3,5,8,13,21,34,55,89。即a_(10)=89。注意到解法2中的数列{a_n}就是菲波那奇数列,它的通项公式为     

网格不反向路径走法的计算

关于网格不反向路径走法的问题，有很多种解法，但不是过于复杂，就是不易于理解，现给出二种简单易行的方法．     

网格不反向路径种数的计算公式

1　问题的提出( 1)网格不反向路径种数问题散见于各种资料中 ,但都是些具体的数值计算 ,笔者尚未见到对这一问题的一般性解答 本文旨在就该一般性问题给出解决的思路方法及计算的公式 ( 2 )具体问题 :①如图 1,在某个城市中 ,Ｍ、Ｎ两地之间有整齐的道路网 ,若规定只能向东或北两个方向沿图中矩形的边前进 ,则从Ｍ到Ｎ不同走法共有 (　　 ) Ａ 2 5种　　Ｂ 15种Ｃ 13种　　Ｄ 10种②如图 2 ,某区有 7条南北向街道 ,5条东西向街道 图中从Ａ到Ｂ的最短走法有多少种 ?图 1　　　　　　　　图 2( 3)一般问题 :将上题中的“7”、“5”分别换…     

利用递推思想解决计数问题

我们经常碰到有些计数问题看似排列组合应用题 ,但其复杂的情形常令人无从下手 ,若从元素的递增考虑 ,建立递推数列往往能迎刃而解 .例 1　有一楼梯共 10级 ,如果规定每步只能跨上一级或二级 ,要走上 10级 ,共有多少种走法 ?解　设上n级楼梯共有an 种走法 ,当n= 1时 ,一级楼梯只有 1种走法 ,a1 =1;当n= 2时 ,两级楼梯共有两种走法 ,a2 =2 ,n 1级楼梯的走法分两种情况 :第一种情况 :走完前n级楼梯有an 种走法 ,走第n 1级楼梯只有 1种走法 ;第二种情况 :走完前n-1级楼梯有an - 1种走法 ,第n级楼梯与第n 1级楼梯一步走 ,也是一种走法 .由分类…     

数出不同的走法

<正>公园里有两处景点,如下图,图中的线表示道路,绿色表示草地,蓝色表示人工湖。如果从A点出发后不能再返回A点,那么你能数出从A点到B点各有多少种走法吗？要想既不重复又不遗漏地数出从A点到B点的所有走法,我们可以采取画线标注的方法来数。图1中,我们可以发现从A点直接到B点（不经过C点）有两种走法;经过C点,则有2×2=4 （种）走法。所以,图1中从A点直接到B点,一共有2+4=6 （种）走法,见图3。     

道路网走法的一般解法

题目　图 1是某城市道路网的局部 ,横向ｍ个格子 ,纵向ｎ个格子 ,若只允许向东或向北走 ,则从Ａ处到Ｂ处有多少种不同走法 ?本题在很多资料中都能见到 ,其解法是把道路网简化成较少格子后分步求 ,或猜想出一般性结论 ,而没有证明 .下面用组合知识给出其一般性的推导过程及结论 .从Ａ处到Ｂ处走每个格子的一边作为一步 ,则对于ｍ×ｎ的网格共走ｍ+ｎ步 ,我们把这ｍ+ｎ步看作ｍ +ｎ个位置 .由于每种走法均为向东走了ｍ步 ,向北走了ｎ步 ,这样 ,当从ｍ +ｎ个位置中选出ｍ个位置作为向东走的各种情形 ,有Ｃｍｍ +ｎ 种选法 ,剩余ｎ个位置为向北…     

上楼的问题(2)——对起步进行分类

问题有人要上楼,该人每步能向上走1阶或2阶,如果一层楼有18阶,他上一层楼有多少种不同的走法? 如果用上次“让符号说话”的方法解决,一定很麻烦.现在改用另一种方法——对起步进行分类的方法试一试. 用α_n表示上n阶的走法种数,上次计算结果表明α_6=13(即上6阶有13种不同的走法). 如果只上1阶,当然只有1种走法,即α_1=1(如图1); 如果上2阶,有几种走法呢?由图2可以知道α_2=2.     

导数应用中的四个误区

导数作为一种工具,在解决数学问题时应用极为方便,尤其是利用导数可以求函数的单调性、极值、最值以及曲线的切线.在学习的过程中,概念不清导致导数应用错误的情形时常发生.本文拟对导数应用中常见的误区进行简单剖析.一、对极值的条件理解不清例1函数f(x)=x3+ax2+bx+a2在x=1处有极值10,求a,b.误解由题意知f'(x)=3x2+2ax+b,且f'(1)=0,f(1)=10,即2a+b+3=0,a2+a+b+1=10.解得ab==4-,11,或ab==-33,.剖析本题误把f(x0)为极值的必要条件当成充分条件.要保证f(x0)为极值,还需验证f'(x)在x0两侧附近符号是否相异.当a=4,b=-11时,f'(x)=(3x+11)(x-1)在…     

电路——一个电子的通路

人教版高中数学第二册(下A)(以下简称“课本”)第80页有这样一个问题———“如图1,从甲地到乙地,可以乘火车,也可以乘汽车,一天中,火车有3班,汽车有2班,那么一天中,乘坐这些交通工具从甲地到乙地共有多少种不同的走法?”图1给出的答案是:“共有3 2=5种不同的走法·”并由此引出了分类计数原理·这是很正确的·因为“从甲地到乙地的走法”是指“一个人从甲地到乙地的走法”·“一些人乘火车1,另一些人乘汽车1”不能算作第6种走法·课本第83页习题10·1的第4题是———“如图2,一条电路从A处到B处接通时,可以有多少条不同的线路?”文[1]认…     

导数应用中的五个误区

导数作为一种工具,在解决数学问题时应用极为方便.尤其是利用导数可以求导数的单调性、极值、最值以及曲线的切线.但在学习的过程中由于概念不清而导致错误的情形也时常发生.本文拟对导数应用中常见的误区作一个简单的剖析.一、极值的条件理解不清例1函数f(x)=x~3+ax2+bx+a~2在x=1处有极值10,求a、b.误解f′(x)=3x~2+2ax+b,由题意知(?),即(?),解得(?),或(?)     

一个命题的修正及推广

《数学方法与解题方法论》第 130页有这样一个命题 :形如 aa…aan个bb…bbn个(a≠ 0 ,a,b∈ { 0 ,1,2 ,3,… ,8,9} ,n∈ N* )能够表示成两个连续自然数的乘积的充要条件是 a=1,b=2 .笔者经过仔细的证明 ,发现此命题是错误的 ,应修正为 :形如 aa… aan个bb… bbn个的自然数 (a≠ 0 ,a,b∈ { 0 ,1,2 ,3,… ,8,9} ,n∈N* )能够表示成两个连续自然数的乘积的充要条件是 a=1,b= 2或 a=4 ,b=2或 a=9,b=0 .证明　 (必要性 ) :aa…aan个bb…bbn个(n∈N* )=(1+10 1 +10 2 +… +10 n-1 )× 10 na+(1+10 1 +10 2 +… +10 n-1 ) b=(1+10 1 +10 2 +… +…     

从k到(k+1)思路受阻分析及转化策略

用数学归纳法证明不等式,特别是数列不等式,是一个行之有效的方法,也是中等数学中的一个基本方法,近些年高考试题中多次出现这类考题.运用这种方法证明不等式时,往往很多同学在证k到(k+1)的过程中卡了壳,断了思路,这是一种普遍现象.下面分析一下思路受阻的几种原因及转化策略.一、从k到(k+1)添项不足在从k到(k+1)的证明过程中,如果分析不透命题结构,就会造成添项不足,证明夭折.【例1】已知Sn=1+21+13+…+1n(n∈N*),用数学归纳法证明S2n&gt;1+2n(n≥2,n∈N*).思路受阻过程:(1)当n=2时,S22=1+21+31+41=1+1123&gt;1+22,命题成立.(2)设n=k(k≥3)时不等式成立,即S2k=1+21+31+…+21k&gt;1+2k,则当n=k+1时S2k+1=1+12+31+…+21k+2k1+1&gt;1+2k+2k1+1,要证明S2k+1&gt;1+k2+1,只须证1+2k+21k+1&gt;1+k2+1,即证2k1+1&gt;21.显然,当k≥2时这是不可能的,解题思路受到阻碍.受阻原因分析:∵Sn=1+21+31+…+1n,∴S2k+1=1+21+13+…+21k+2k1+1+2k1+2+…+...     

条件x+y=1下1/xn+λ/yn最小值的简单求法

文 [1]给出了条件 x+ y=1下 1xn+ λyn的最小值定理 ,并利用 (a2 + b2 ) (c2 + d2 )≥ (ac+ bd) 2 (a,b,c,d∈ (0 ,+∞ )和待定系数法证明之 .定理　已知 x,y,λ∈ (0 ,+∞ )且 x+ y=1,则当且仅当 y∶ x=λ1n+ 1 时 ,1xn+ λyn(n∈N* )取最小值 ,最小值为 (1+ λ1n+ 1 ) n+ 1 .本文给出定理的一个简单证明 .证明　∵x,y,λ∈ (0 ,+∞ ) ,n∈ N* ,且x+ y=1,∴ 1xn+ λyn=(1xn+ λyn) (x+ y) n =(1xn+λyn) (C0nxn+ C1 nxn-1 y+ C2nxn-2 y2 +… + Crnxn-ryr+… + Cnnyn)=1+ C1 nyx + C2ny2x2 +… + Crnyrxr +… + Cnnynxn+ λC0nxnyn + …     

全国初中数学竞赛初赛模拟试题

一、选择题(共8小题,每小题5分,满分40分.以下每小题均给出了代号为A,B,C,D的4个选项,其中有且只有一个选项是正确的.请将正确选项的代号填人题后的括号里.不填、多填或错填均得零分) 1.函数y=lx}一2的图像应该是()2.女口一十1士一二大标杰,点半 ‘即娜 (一l,2)在( A.第一部分B     

建立递推数列求解一类计数问题

排列组合中经常会碰到一类特殊的计数问题,看似排列组合应用题,但其复杂的情形常令人无从下手.若能根据题目特点建立递推数列则问题往往能迎刃而解.例1 有一楼梯共10级,如果规定每步只能跨上一级或二级,要走上这10级楼梯,共有多少种走法?解:设上 n 级共有 a_n 种走法,当 n=1时,一级楼梯只有1种走法,a_1=1;当 n=2时,两     

结构力学例题解析

1 计算图1所示桁架的支座反力及1、2杆的轴力。 图1桁架示意图 解:（1）求支座反力:由∑MA=0得: yB×4-20×4+40×6=0即yB=40kN（↓）由 ∑x=0得;xA=20kN（→）由∑y=0得:yA=20+40=60kN（↑） （2）求杆1、2的轴力:结点 E或截面法: ∑MB=0,N2=-44.7kN（压）结点D: ∑x=0,N1=28.26kN（拉）     

一类分式不等式的统一初等证法

在国内外数学竞赛以及一些数学杂志上出现了一类分式不等式 ,许多专家都曾对这类不等式作过研究 ,指出了较多好的证法 .本文旨在说明这类分式不等式有一种统一初等证法 ,就是都利用一个常见的简单不等式 (a1+a2 +… +an) (1a1+ 1a2 +… +1an)≥n2 (ai >0 ,i=1 ,2 ,3,… ,n)加以证明的 .问题 1　 (英国竞赛题 )设正数a1,a2 ,… ,an 之和为S ,求证 :a1 S -a1+a2S -a2+… +anS -an≥ nn - 1 (n∈N ,n≥ 2 ) .解析　原不等式等价于(a1 S-a1 +1 ) +(a2S-a2 +1 ) +… +(anS-an +1 )≥ nn - 1 +n ,即 SS-a1+ SS-a2 +… + SS-an ≥ n2n- 1 ,即…     

一个组合数恒等式的三种证法

一个有关组合数的恒等式是 :C1 n+ 2C2 n+3C3n+… +nCnn =n· 2 n- 1 (n∈N ) .下面给出它的三种不同证法 ,其中第三种证法出人意料 ,简洁优美 ,有绝妙之处 .证法 1　倒序相加法 .设Sn =C1 n + 2C2 n + 3C3n +… + (n-1)Cn - 1 n +nCnn,则Sn =nC0 n+ (n -1)C1 n+ (n-2 )C2 n+… +Cn- 1 n ,两式相加 ,得2Sn =n(C0 n+C1 n+C2 n+… +Cn - 1 n +Cnn)=n· 2 n.∴Sn =n· 2 n- 1 .证法 2　逐项转化法 .mCmn =m· n !m !(n -m) !=n· (n -1) !(m-1) !(n -m) !=nCm - 1 n- 1 ,分别令m =1,2 ,3 ,… ,n并分别相加得 .C1 n+ 2C2 n + 3C3n+…     

探索规律 深化结论

在一本奥林匹克数学书中有这样一道趣题 :图 1将 0到 9这 10个数字分别填在图 1的 10个黑点处 ,使相邻两数的乘积加 1都是完全平方数 .分析与解　我们用枚举的方法 ,凑数如下 :0× 1+1=12 ,0× 2 +1=12 ,… ,0 × 9+1=12 .又 1× 3+1=2 2 ,3× 5 +1=4 2 ,5× 7+1=6 2 ,7× 9+1=82 ,且 2 × 4 +1=32 ,4 × 6 +1=5 2 ,6 × 8+1=72 ,还有 8× 1+1=32 .图 2由此我们可得图 2 .仔细分析一下上述凑数的结果 ,发现如下三个有趣的性质 :(1) 0乘以任何数a再加 1,总是完全平方数 1:0 ×a +1=12 ;(2 )相邻两个奇数的乘积加 1是完全平方数 ;(3)相邻两个…