我有一个有2^N个节点的DAG，值从0到2^N-1如果x
提前谢谢
最佳答案
迈克尔有一些很好的见解，但我不确定我是否理解他的全部论点。这是我的解决办法。
假设N=4，K=2所以节点的范围从0（00002）到15（11112）。
现在让我们考虑节点2（00102）。有一条从2到3的边（00112），因为2概括地说：对于任何x，考虑x中的所有0位。通过将0位中的任何一位翻转为1，可以得到一个大于x且与x相差一位的数字y。所以从x到y有一个边。
x中1位的数目通常称为x的总体计数。我将使用pop（x）来表示x的总体计数。
我们处理的是N位数字（当我们包含前导零时），所以x中0位的数量是N-pop（x）。
我们用“j-路径”这个词来表示长度为j的路径，我们要计算k-路径的数量。
每个节点x都有N-pop（x）个传出边每个边都是一条路径。
让我们考虑节点5（01012）。节点5具有到7的边（01112），节点7具有到15的边（11112）。节点5还具有到13（11012）的边，节点13具有到15（11112）的边。所以节点5有两条路径：5-7-15和5-13-15。
接下来我们再来看节点2（00102）节点2具有到3（00112）的边，其具有到7（01112）和11（10112）的边节点2还具有到节点6的边（01102），其具有到7（01112）和14（11102）的边。最后，节点2具有到节点10的边（10102），其具有到11（10112）和14（11102）的边。总共有6条出节点2的2-路径：2-3-7、2-3-11、2-6-7、2-6-14、2-10-11和2-10-14。
其模式是，对于z位设置为零的任何节点x，其中z≥k，有一些k路径在x之外。要找到x之外的k路径，可以从零位中选择任意k。把这些位一个一个地翻过来，就可以找到路径。你可以按你想要的顺序翻转这些位；每个顺序都给出不同的路径。
当您想从一组n个项目中按特定顺序挑选k个项目时，这称为无替换的有序样本，并且有n! / (n-k)!方法可以做到这一点。这通常是n p k编写的，但是在这里输入p（n，k）比较容易。
所以，正好有2个零位的节点有p（2，2）=2！/（2-2）=2条2路（注意0=1.）只有3个零位的节点有p（3,2）=3！/1个=6条2路。正好有4个零位的节点有p（4,2）=4！/2个！=12条2路。（因为我在示例中使用的是N=4，所以只有一个节点正好有4个零位，即节点0。）
但是我们需要知道，有多少节点有2个零位？好吧，当有n个项目可供选择时，我们想从中选择k个，而我们不关心所选项目的顺序，这就是所谓的无替换无序样本，有n个/（k（n-k）！）方法这被称为“n choose k”，它通常是以一种在堆栈溢出时无法重现的方式编写的，所以我将其写为C（n，k）。
对于我们的N=4的例子，有C（4,2）=6个节点，正好有2位设置为零这些节点是3（00112）、5（01012）、6（01102）、9（10012）、10（10102）和12（11002）。每一个节点都有p（2,2）2路，这意味着有c（4,2）*p（2,2）=6*2=12个2路，节点正好有两个0位。
然后有C（4,3）=4个节点，正好有3位设置为零这些节点是1（00012）、2（00102）、4（01002）和8（10002）。每个节点都有p（3,2）2条路径，因此有c（4,3）*p（3,2）=4*6=24条2条路径，正好是3个0位的节点。
最后，有c（4，4）=1个节点，正好有4位设置为零。这个节点有p（4,2）=12个2路。
所以当N=4时2路的总数是C（4,2）*P（2,2）+C（4,3）*P（3,2）+C（4,4）*P（4,2）=12+24+12=48。
对于一般的n和k（其中k≤n），k-路径的数目是k≤z≤n时c（n，z）*p（z，k）的和。
我可以把它输入Wolfram Alpha（或Mathematica）中，如下所示：
Sum[n!/(z! (n - z)!) z!/(z - k)!, {z, k, n}]
And it simplifies it to this：
2^(n-k) n! / (n-k)!