我有一个问题，我不知道如何开始解决它。
我只有数字N，N糖果，我需要计算服用N糖果的方式数量，但除了第一个糖果，所服用的糖果必须与之前服用的糖果之一相邻。例如，如果N = 3有 4 种服用方式：
先吃 1 号糖果；然后是糖果 2，3。
先吃 2 号糖果；然后是 1，3。
先吃 2 号糖果；然后是 3，1。
先吃 3 号糖果；然后是糖果 2，1。
3
n糖果的路数是pascal's 的第n-1行的总和。
2
如果您先拿糖果 k，则可以选择（n-1，k-1）选择其余糖果的方式（其中 choose（n，k）是二项式系数 nCk）。这是因为在第一个之后，您必须将最右边的未选择的糖果放在 k 的左侧，或者将最左边的未选择的糖果放在 k 的右侧，并且在 k 的左侧有（k-1）糖果。
总结在 k，给你所有可能的方式考虑到第一选择：总和（K = 1...N）选择（N-1，K-1）。
由于 choose（n-1，k-1）是从 n-1 个项目中选择 k-1 个项目的方式数，因此该总和等于从 n-1 个项目中选择任意数量的项目的方式数。
1
看看模式：
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
这让你想起什么了吗？
1
假设我们首先拿i-th糖果。然后我们在左边有i - 1糖果，在右边有N - i。接下来的每个糖果都是从左边最右边的，或者是从右边最左边的。左右部分是独立的，因此获取所有糖果的可能方式的数量是序列
此类排列的总数为：
SequenceLength!/(count(L)!*count(R)!) = (N - 1)!/((i - 1)! * (N - i)!)
现在，如果我们总结所有可能的i值，我们有：
本站系公益性非盈利分享网址，本文来自用户投稿，不代表码文网立场，如若转载，请注明出处
评论列表（35条）