免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] 从(0,0,0)走8步到(1,-2,3)

在空间直角坐标系下,点P从原点O开始运动,记向三条坐标轴的正或负方向运动一单位为走一步(比如P从原点到(1,0,0)),那么P从原点走8步到M(1,-2,3)(中途可经过M)的走法共有_____种

$3640=C_8^2C_6^1C_5^2+C_8^1C_7^3C_4^1+C_8^1C_7^2C_5^1$

模拟卷都玩出花了,$m\times n$矩形街道走法的加强版
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

下次走它10步

TOP

回复 1# realnumber

从二维到三维了。。。

TOP

回复  realnumber

从二维到三维了。。。
isee 发表于 2018-5-20 07:57

因为多走了2步,某个方向往返各算一维的话,相当于4维了
而10步的话,相当于5维了
12步以上,都6维了-----这个装B

TOP

回复 4# realnumber

10步的话是不是 `C_{10}^3 C_7^2 C_5^3 + C_{10}^1 C_9^4 C_5^3 + C_{10}^1 C_9^2 C_7^5 + 2(C_{10}^2 C_8^3 C_5^3 + C_{10}^2 C_8^2 C_6^4 + C_{10}^1 C_9^3 C_6^4) = 158760` ?

TOP

我想说,这个点 P 真的闲的蛋疼。。。

TOP

回复 6# zhcosin

你能不能编程验算一下我5楼的结果正确不?

TOP

回复 7# kuing

你想用枚举烧坏我的 CPU ?

TOP

你们都太 low 了,什么三维四维八步十步的,干脆上个压轴大招:
在 $n$ 维空间中,点 $P$ 由原点出发经过 $n$ 步到达 $(a_1,a_2,\ldots,a_n)$(坐标分量都是整数),问有多少种走法?

TOP

你们都太 low 了,什么三维四维八步十步的,干脆上个压轴大招:
在 $n$ 维空间中,点 $P$ 由原点出发经过 $ ...
zhcosin 发表于 2018-5-21 17:03

鼓掌,大招

TOP

\(\newcommand\ctg[2]{\binom{#1}{\begin{matrix}#2\end{matrix}}}\)

还是稍微解释一下吧,不然别人看着一堆 $C$ 也不知什么意思。

为了叙述更清晰,将终点一般化记为 $Q(x,y,z)$($x$, $y$, $z\inN^+$),令 $n=x+y+z$,记向量 $\bm i=(1,0,0)$, $\bm j=(0,1,0)$, $\bm k=(0,0,1)$。

由原点到 $Q$ 至少需要 $n$ 步,要走 $n+2$ 步的话,有两步多余,如果它们是与 $x$ 轴平行的,那么整个过程中就有:

$x+1$ 步 $\bm i$,$1$ 步 $-\bm i$,$y$ 步 $\bm j$,$z$ 步 $\bm k$。

故这种情况的方法数为 $C_{n+2}^{x+1}C_{n-x+1}^1C_{n-x}^yC_{n-x-y}^z$,另两种情况类似。

为了方便书写(其实主要是为了自定义代码方便),下面把公式化简一下并引入新记号。

设 $n=n_1+n_2+\cdots +n_k$,则不难证明
\[C_n^{n_1}C_{n-n_1}^{n_2}C_{n-n_1-n_2}^{n_3}\cdots C_{n-n_1-n_2\cdots -n_{k-1}}^{n_k}=\frac {n!}{n_1!n_2!\cdots n_k!},\]

\[\ctg n{n_1 & n_2 & \cdots & n_k}=\frac{n!}{n_1!n_2!\cdots n_k!},\]
则要走 $n+2$ 步的时候的结果为
\[\ctg{n+2}{x+1&1&y&z}+\ctg{n+2}{x&y+1&1&z}+\ctg{n+2}{x&y&z+1&1},\]
通分后为
\[\frac{(n+2)!\sum(y+1)(z+1)}{(x+1)!(y+1)!(z+1)!}.\]

要走 $n+4$ 步时,有 4 步多余,需要分更多的类。

如果它们都是与 $x$ 轴平行的,过程中就有:

$x+2$ 步 $\bm i$,$2$ 步 $-\bm i$,$y$ 步 $\bm j$,$z$ 步 $\bm k$;

如果既有与 $x$ 轴平行,也有与 $y$ 轴平行,过程中就有:

$x+1$ 步 $\bm i$,$1$ 步 $-\bm i$,$y+1$ 步 $\bm j$,$1$ 步 $-\bm j$,$z$ 步 $\bm k$;

其余情况就不列了,加起来就是:
\begin{gather*}
\ctg{n+4}{x+2&2&y&z}+\ctg{n+4}{x&y+2&2&z}+\ctg{n+4}{x&y&z+2&2}\\
{}+\ctg{n+4}{x+1&1&y+1&1&z}+\ctg{n+4}{x+1&1&y&z+1&1}\\
{}+\ctg{n+4}{x&y+1&1&z+1&1},
\end{gather*}
通分后为
\[\frac{(n+4)![\sum(y+1)(y+2)(z+1)(z+2)+2\sum(x+2)(y+2)(z+1)(z+2)]}{2(x+2)!(y+2)!(z+2)!}.\]

要走 $n+6$ 步就更复杂了:
\begin{gather*}
\ctg{n+6}{x+3&3&y&z}+\ctg{n+6}{x&y+3&3&z}+\ctg{n+6}{x&y&z+3&3}\\
{}+\ctg{n+6}{x+2&2&y+1&1&z}+\ctg{n+6}{x+1&1&y+2&2&z}\\
{}+\ctg{n+6}{x+2&2&y&z+1&1}+\ctg{n+6}{x+1&1&y&z+2&2}\\
{}+\ctg{n+6}{x&y+2&2&z+1&1}+\ctg{n+6}{x&y+1&1&z+2&2}\\
{}+\ctg{n+6}{x+1&1&y+1&1&z+1&1},
\end{gather*}
这个就不通分了……

不知道有没有化简公式……
$\href{https://kuingggg.github.io/}{\text{About Me}}$

TOP

回复 5# kuing


    觉得应该这样,多余4步加在x轴方向$C_{10}^3C_7^2C_5^2$
多余4步加在y轴方向$C_{10}^1C_9^2C_7^4$
多余4步加在z轴方向$C_{10}^1C_9^2C_7^2$
多余4步加在x,y轴方向各2步$C_{10}^2C_8^1C_7^3C_4^1$
多余4步加在x,z轴方向各2步$C_{10}^2C_8^1C_7^2C_5^1$
多余4步加在z,y轴方向各2步$C_{10}^2C_9^3C_6^1C_5^1$
没了

TOP

我竟然还想编程,简直是笨死了,直接展开
\[\left(x+\frac1x+y+\frac1y+z+\frac1z\right)^{10}\]
看看 `xy^2z^3` 的系数不就行了吗

在MMC上用 Expand[(x + y + z + 1/x + 1/y + 1/z)^10] 果然能查找到 158760 x y^2 z^3 这一项看来上面的公式还是没错嘀

噢,原来还有 Coefficient 命令可以直接提取系数:
In[1]:= Coefficient[Expand[(x + y + z + 1/x + 1/y + 1/z)^8], x y^2 z^3]

Out[1]= 3640

In[2]:= Coefficient[Expand[(x + y + z + 1/x + 1/y + 1/z)^10], x y^2 z^3]

Out[2]= 158760

In[3]:= Coefficient[Expand[(x + y + z + 1/x + 1/y + 1/z)^12], x y^2 z^3]

Out[3]= 6126120

最后这个 6126120 与用上面11#最后那个公式算出来也是一样的,看来那公式也没错了。

TOP

鼓掌,9楼的大招也被你破解一部分了

TOP

回复 14# realnumber

大招也是一样的啊,在 `n` 维空间中,由原点出发经过 `N` 步到达 `(a_1,a_2,\ldots,a_n)`(坐标分量都是整数)的走法数为
\[\left(x_1+\frac1{x_1}+x_2+\frac1{x_2}+\cdots+x_n+\frac1{x_n}\right)^N\]的展开式中 `x_1^{a_1}x_2^{a_2}\cdots x_n^{a_n}` 的系数。
1

评分人数

    • zhcosin: 牛逼的裤子都快掉了。威望 + 1

TOP

这个问题看的我有点晕啊!

TOP

原题多的2步必是沿同一轴所在直线来回各一次,如果多$2k$步那就复杂了。牛逼的人的想法总是很牛逼,坐等学习

TOP

返回列表 回复 发帖