如何计算（弱）递减的数字序列的数量？

Question

我想解决一个没有循环的问题。假设我们有 N 个地方，对于每个地方你可以 select 一个介于 [p,q] 之间的数字，但是第 i+1 处的数字应该小于或等于第 i 处的数字。现在如何计算所有可能的字符串而不用蛮力。

例如，假设我们有 2 个地方，您可以 select [2,3] 之间的数字，那么可能的序列可以是：

3 3

3 2

2 2

由于p和q的个数没有限制，所以简单的循环是解决不了的

Answer 1

是choose(q-p+N, N) 其中choose是二项式系数

p 和 q 之间的弱递减序列与长度为 q-p+N 的 0 和 1 序列双射，其中序列恰好有 N 个 1。很明显，这样的序列的个数是choose(q-p+N, N)，因为这就是从q-p+N个东西中选择N个东西的方法数。

两个集合双射的证明

给定长度为 q-p+N 和 N 个 1 的 0 和 1 的序列 xs，此伪代码生成 p 和 q 之间的弱递减数字序列：

 c = q
 for x in xs
     if x = 1 then output c
     if x = 0 then c <- c - 1

相反，给定 p 和 q 之间长度为 N 的弱递减序列 xs，此伪代码生成长度为 q-p+N 的 0 和 1 序列，恰好有 N 个 1。

 c = q
 while xs is not empty
     if c = head(hs) then
         output 1
         xs <- tail(xs)
     else
         output 0
         c <- c - 1
 while c > p
     output 0
     c <- c - 1

这里 head(xs) 表示 xs 列表中的第一件事，tail(xs) 表示列表的其余部分。

如何计算（弱）递减的数字序列的数量？

How to count number of (weakly) decreasing sequences of numbers?

algorithm

counting

两个集合双射的证明