来自人教群的计数题

kuing

鲁Q教师XYZ(3306*****) 2023/12/7 9:09:55
有20个相同的棋子，某人多次拿走棋子，每次可以拿走1，2，3或4个，但每次剩下的棋子数量必须既不是3的倍数也不是4的倍数（0除外），这样，把所有棋子都拿走有多种不同的方法？

相当于由 0 走到 20，每一步的长度可取 1, 2, 3, 4，并且中途的落点既不是 3 的倍数也不是 4 的倍数。

$ \xymatrix@C=0.6cm{
0 \ar[r] \ar@/_1.5pc/[rr] & 1 \ar[r] \ar@/_1.5pc/[rr] & 2 \ar[r] & 5 \ar[r] & 7 \ar[r] \ar@/_1.5pc/[rr] & 10 \ar[r] \ar@/_1.5pc/[rr] \ar@/^2pc/[rrr] & 11 \ar[r] \ar@/_1.5pc/[rr] & 13 \ar[r] \ar@/_1.5pc/[rr] & 14 \ar[r] & 17 \ar[r] \ar@/_1.5pc/[rr] & 19 \ar[r] & 20\\
} $

所有可行的步法如上图所示，可以看到 7 和 17 是必经的，所以可分为三阶段：

• 前面 0 到 7 显然有 3 条路径；
• 后面 17 到 20 显然有 2 条路径；
• 中间 7 到 17 的麻烦一点，下面分类讨论：
  [list]
• 全走直的，1 条；
• 走一个小弯的，4 条；
• 走两个小弯的，3 条（分别是 (7, 11, 14, 17)、(7, 11, 13, 17)、(7, 10, 13, 17)）；
• 走 10 - 14 这个大弯的，1 条。
  

所以由 7 到 17 有 9 条路径。
[/list]综上所述，总的可行路径数为 `3\times9\times2=54` 条。

不知有没有更高级的方法处理，要不然如果数字再大一些，那得算死人。

PS、上面路径图的代码如下

1. $\xymatrix@C=0.6cm{
2. 0 \ar[r] \ar@/_1.5pc/[rr] & 1 \ar[r] \ar@/_1.5pc/[rr] & 2 \ar[r] & 5 \ar[r] & 7 \ar[r] \ar@/_1.5pc/[rr] & 10 \ar[r] \ar@/_1.5pc/[rr] \ar@/^2pc/[rrr] & 11 \ar[r] \ar@/_1.5pc/[rr] & 13 \ar[r] \ar@/_1.5pc/[rr] & 14 \ar[r] & 17 \ar[r] \ar@/_1.5pc/[rr] & 19 \ar[r] & 20\\
3. }$

Copy the Code

业余的业余

显然反过来从 $0$ 加到目标数的走法数是相同的。

mod $12$ 的合法剩余 $\{1,2,5,7,10,11\}$, 即 $\{1,2,5,-5,-2,-1\}$ 如果数大的话，可注意到 $5$-$17$ 是一个周期。记$0$到$5$ 的走法数为 $c_1$, $5$ 到 $17$ 的走法数为 $c_2$, 从 $5$ 到$a, 5\le a<17$ 的走法数为 $c_a$.

那么 对正整数 $n\ge 5$, 走法数为 $c_1(c_2)^{\left\lfloor(n-5)/12\right\rfloor}c_a$.其中 $c_a$ 中的 $a$ 为 $（n-5 \text{ mod } 12）+5$.

业余的业余

xymatrix很有意思。试用一下。
$\newcommand\c[1]{\enclose{circle}{#1}}$
状态0到5的FSA
$\xymatrix@C=0.6cm@R=0.6cm{
\c 0\ar[r]\ar@/_/[rd]&\c1\ar[r]\ar[d]&\c5\\&\c2\ar@/_/[ru]
}$
显然 $c_1=2$.

状态5到状态17的状态机:
$\xymatrix@C=0.9cm@R=0.9cm{
\c5\ar[r]&\c7\ar[r]\ar@/_/[rd]&\c{10}\ar[r]\ar[d]\ar[rd]&\c{13}\ar[r]\ar[d]&\c{17}\\&&\c{11}\ar[r]\ar[ru]&\c{14}\ar@/_/[ru]
}$
$c_2=9$, 如酷版主贴。
$c_5=c_6=c_7=1$
$\xymatrix@C=0.6cm@R=0.6cm{
\c5\ar[r]\ar@/_/[rd]&\c7\ar[d]\\&\c8
}$
$c_8=2$
$\xymatrix@C=0.6cm@R=0.6cm{
\c5\ar[r]\ar@/_/[rd]&\c7\ar[d]\\&\c9
}$
$c_9=2$
$c_{10}=1$
$c_{11}=2$
$c_{12}=3$
$c_{13}=3$
$c_{14}=6$
$c_{15}=10$(比 $c_2$ 的图多了从11直接走到15的一条路)
$c_{16}=9$(与 $c_2$ 的图完全相同)

kuing

业余的业余 发表于 2023-12-10 23:10
xymatrix很有意思。试用一下。

状态0到5的FSA ...

难得有人用 xymatrix 😃

PS、那个 @C=0.6cm 是设置列距为 0.6cm，默认比这个大，我怕超宽所以设小了。
行距的话是 @R=... ，比如可以再添一个 @R=0.6cm ，感觉会好看一点。

业余的业余

kuing 发表于 2023-12-10 23:37
难得有人用 xymatrix 😃

PS、那个 @C=0.6cm 是设置列距为 0.6cm，默认比这个大，我怕超宽所以设小了。

谢谢！简单、强大，值得掌握！

kuing

业余的业余 发表于 2023-12-11 00:00
谢谢！简单、强大，值得掌握！

xymatrix 本身也能加圈圈，还有其他效果：
$ \xymatrix{
*[F]{M} & *[o][F]{M} & *+[o][F]{M} & *++[o][F]{M} & *+++[o][F]{M} \\
*[F-,]{M} & *[o][F.]{M} & *+[o][F--]{M} & *++[o][F=]{M} & *+++[o][F==]{M} \\
*+[F=:<10pt>]{\displaystyle\frac12+\sqrt\sum}
} $
代码：

1. $ \xymatrix{
2. *[F]{M} & *[o][F]{M} & *+[o][F]{M} & *++[o][F]{M} & *+++[o][F]{M} \\
3. *[F-,]{M} & *[o][F.]{M} & *+[o][F--]{M} & *++[o][F=]{M} & *+++[o][F==]{M} \\
4. *+[F=:<10pt>]{\displaystyle\frac12+\sqrt\sum}
5. } $

Copy the Code

业余的业余

谢谢酷版，学习了！