`N`颗糖果的取法数

Question

我有一个问题，我不知道如何开始解决它。您认识这样的公式、算法或类型的问题吗？

我只有N、N个糖果，我需要统计N个糖果的取走方式，除了第一个取走的糖果，第一个取走的糖果必须与以前吃过的糖果之一相邻。例如如果N = 3有4种取法：

先吃1号糖果；然后糖果2、3.
先吃2号糖果；然后是 1、3。
先吃2号糖果；然后是 3、1.
先吃3号糖果；然后糖果 2, 1.

Answer 1

n种糖果的方式数是pascal's triangle第n-1行的总和。

Answer 2

看格局：

number of candies
1   2   3   4
1   12  123 1234
    21  213 2134
        231 2314
        321 2341
            3214
            3241
            3421
            4321
1   2   4   8
total ways

这是否让你想起了什么？

Answer 3

另一种实现，理论上可能更有用：

给定一个索引为 1 的数组 C 的糖果弹珠（1 表示尚未取走，0 表示已取走，全部从 1 开始）和起点 N:

如果 N 为负数、零或大于 C 的大小，则结束而不做任何事情。
如果C[N]为0，什么也不做就结束
如果 C[N] 为 1，则将其设置为 0，将可能路径的计数加 1，然后对照此算法检查 C[N-1] 和 C[N+1]。

只需对 C 中的每个有效索引重复此算法。另外，确保每个递归都有一个 C 的副本，而不是原始的 C，但它们都共享路径总数。

逐步完成示例的第一部分：

C[1]为1，所以我们设置为0，加1，检查C[0]和C[2].
0 是 0，所以我们停止递归。
C[2]为1，所以我们设置为0，检查C[1]和C[3].
C[1] 为 0。
C[3] is 1, so we set it to 0 and checkC[2]andC[4]`.
C[2] 为 0。
4 大于 3。

重复 N=2 和 N=3，对于更长的数组，只需循环即可。

Answer 4

如果你先拿糖果k，那么剩下的有choose(n-1, k-1)种选择方式（其中choose(n, k)是二项式系数nCk）。那是因为在第一个之后，你要么拿走 k 左边最右边未选中的糖果，要么拿走 k 右边最左边未选中的糖果，并且 k 左边有 (k-1) 个糖果。

对 k 求和，为您提供考虑第一个选择的所有可能方法：sum(k=1...n)choose(n-1, k-1)。

因为 choose(n-1, k-1) 是从 n-1 项中选择 k-1 项的方式数，所以这个总和等于从 n 中选择任意数量项目的方式数-1 项。那是 2^(n-1).

Answer 5

假设我们先拿 i-th 糖果。然后左边有 i - 1 个糖果，右边有 N - i 个糖果。下一个拿走的糖果是左边最右边的，或者是右边最左边的。左右部分是独立的，因此获取所有糖果的可能方式的数量是序列 LLLL....LLLRRR....RRR 的唯一排列数，其中 i - 1 L's 和 N - i R's.

此类排列的总数为：

SequenceLength!/(count(L)!*count(R)!) = (N - 1)!/((i - 1)! * (N - i)!)

现在，如果我们对所有可能的 i 值求和，我们有：

Answer 6

您不需要通过二项式系数。

有2^(n-1)个长度为n-1的Rs和Ls序列。通过写下你的下一个糖果是在你之前拿过的糖果的右边还是左边，这些与拿糖果的顺序是双射的。任意一个Rs和Ls的序列唯一确定了第一颗糖果的位置：如果有一个Ls，那么第一颗糖果一定在a+1的位置。

`N`颗糖果的取法数

Number of ways of taking `N` candies

algorithm

math

puzzle