For a directed graphGwith edge set {1, 2, . . . ,k}, a feasible permutations forGis a permutation π on {1, 2, . . . ,k} such that there exists an injective weight functionp: {1, 2, . . . ,k} → Z+for which the sum of the weights of all incoming edges equals the sum of the weights of all outgoing edges at every vertex ofG, provided that ifp(i1)p(i2)p(ik), then π(it) =tfor everyt∈ {1, . . . ,k}. In this paper, we study the number of feasible permutations (denoted byFq,ℓ) for the De Bruijn graphGq,ℓ−1, whereq> 2 is the size of the alphabet. In the caseq= 4, the corresponding De Bruijn graph is used in DNA data storage. To enumerate these feasible permutations, we establish a connection between feasible permutations and regions in a special hyperplane arrangement, denoted byA. Using Zaslavsky’s formula, we present some numerical results and obtain the exact number ofF3,2andF4,2. Since the formula becomes complicated for larger values ofqand ℓ, we concentrate on the case ℓ = 2 and then by counting the regions in a hyperplane sub-arrangement ofA, we provide a lower bound onFq,2. We compare our bound with the latest lower bound onFq,2and show that our bound is Ω(q3J(q)) while the previous one is Ω(q2J(q)), whereJ(q)= (q2−2q+1)!(q2)!/(q2−q)!.