c++ - Count the number of paths in DAG with length K -

i have dag 2^n nodes, values 0 2^n-1. there edge x y if x < y , x (xor) y = 2^p, x , y being node values , p non-negative integer. since n can large 100000, generating graph , proceeding counting take computational time. there way count paths length k (k being number of edges between 2 nodes), differently stated, there equation of sort kind of counting? in advance

michael's got insights, i'm not sure follow entire argument. here's solution.

let's n=4, k=2. nodes range 0 (0000₂) 15 (1111₂).

now let's consider node 2 (0010₂). there's edge 2 3 (0011₂) because 2 < 3 , xor(2,3) = 1 = 2⁰. there's edge 2 6 because 2 < 6 , xor(2,6) = 4 = 2². , there's edge 2 10 because 2 < 10 , xor(2,10) = 8 = 2³.

to generalize: x, consider of 0 bits in x. flipping of 0 bits 1, number y that's larger x , differs x 1 bit. there's edge x y.

the number of 1 bits in x typically called population count of x. i'll use pop(x) mean population count of x.

we're dealing n-bit numbers (when include leading zeroes), number of 0 bits in x n - pop(x).

let's use term “j-path” mean path of length j. want count number of k-paths.

every node x has n - pop(x) outgoing edges. each of these edges 1-path.

let's consider node 5 (0101₂). node 5 has edge 7 (0111₂), , node 7 has edge 15 (1111₂). node 5 has edge 13 (1101₂), , node 13 has edge 15 (1111₂). there 2 2-paths out of node 5: 5-7-15 , 5-13-15.

next let's @ node 2 (0010₂) again. node 2 has edge 3 (0011₂), has edges 7 (0111₂) , 11 (1011₂). node 2 has edge node 6 (0110₂), has edges 7 (0111₂) , 14 (1110₂). finally, node 2 has edge node 10 (1010₂), has edges 11 (1011₂) , 14 (1110₂). in all, there 6 2-paths out of node 2: 2-3-7, 2-3-11, 2-6-7, 2-6-14, 2-10-11, , 2-10-14.

the pattern that, node x z bits set zero, z ≥ k, there k-paths out of x. find k-path out of x, pick k of 0 bits. flipping bits 1, 1 one, gives path. can flip bits in order want; each order gives different path.

when want pick k items, in specific order, set of n items, that's called ordered sample without replacement, , there n! / (n-k)! ways it. written _np_k, it's easier type p(n,k) here.

so, nodes have 2 0 bits have p(2,2) = 2! / (2-2)! = 2 2-paths out of them. (note 0! = 1.) nodes have 3 0 bits have p(3,2) = 3! / 1! = 6 2-paths out of them. node has 4 0 bits has p(4,2)= 4! / 2! = 12 2-paths out of it. (since i'm using n=4 example, there 1 node 4 0 bits, node 0.)

but need know, how many nodes have 2 0 bits? well, when there n items choose from, , want choose k of them, , don't care order of chosen items, that's called unordered sample without replacement, , there n! / (k! (n-k)!) ways it. called “n choose k”, , it's written in way can't reproduce on stack overflow, i'll write c(n,k).

for our example n=4, there c(4,2) = 6 nodes 2 bits set zero. these nodes 3 (0011₂), 5 (0101₂), 6 (0110₂), 9 (1001₂), 10 (1010₂), , 12 (1100₂). each of these nodes has p(2,2) 2-paths out of it, means there c(4,2) * p(2,2) = 6 * 2 = 12 2-paths out of nodes 2 0 bits.

then there c(4,3) = 4 nodes 3 bits set zero. these nodes 1 (0001₂), 2 (0010₂), 4 (0100₂), , 8 (1000₂). each of these nodes has p(3,2) 2-paths out of it, there c(4,3) * p(3,2) = 4 * 6 = 24 2-paths out of nodes 3 0 bits.

finally, there c(4,4) = 1 node 4 bits set zero. node has p(4,2) = 12 2-paths out of it.

so total number of 2-paths when n=4 c(4,2)*p(2,2) + c(4,3)*p(3,2) + c(4,4)*p(4,2) = 12 + 24 + 12 = 48.

for general n , k (where k ≤ n), number of k-paths sum of c(n,z) * p(z,k) k ≤ z ≤ n.

i can type wolfram alpha (or mathematica) this:

sum[n!/(z! (n - z)!) z!/(z - k)!, {z, k, n}] 

and simplifies this:

2^(n-k) n! / (n-k)!