REVIEW 3 major objections 5 minor 8 references
From Exponential to Polynomial Complexity: Efficient Permutation Counting with Subword Constraints
T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read The paper derives closed-form, polynomial-time formulas for counting words that contain specified subwords exactly a prescribed number of times, replacing exponential brute-force enumeration.
desk verdict The single-subword count is standard; the multi-subword theorem fails a 16-case brute-force check, so the paper's only new claim collapses. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the relative position of an unoccupied letter: after laying down copies of a subword, every remaining position sits in one of the gaps before, between, or after the copies. The multiset coefficient counts how many ways the free letters can be assigned to those gaps, the alternating sum removes overcounts from choosing which copies are counted, and the multinomial factor in the multi-subword case treats copies of different subwords as distinct objects to be ordered. Lemmas 4 and 6 provide the binomial-sum identities that turn these placement counts into the closed forms.
What would settle it
Take $t=3$, alphabet $\{0,1\}$, and require subword 01 exactly once and subword 10 exactly once; exhaustive listing gives exactly the two words 010 and 101, while the nested sum in Theorem 8 returns zero because it treats the two required copies as occupying four distinct positions. This one computation decides whether the multi-subword formula counts all words or only non-overlapping arrangements.
Extended reading notes
Core claim
On its own terms, the paper establishes Theorem 5 for one non-self-intersecting subword: the number of words of length $t$ containing subword $A$ exactly $x$ times is a finite alternating sum over the possible number of copies $i$, with terms $(-1)^{i+1} q^{t-ai}$ times a multiset coefficient distributing the $t-ai$ unoccupied positions among the $i+1$ relative positions around the copies, times $\binom{i}{i-x}$. Theorem 8 extends this to $d$ subwords by nested sums whose terms multiply the per-subword binomial factors by a multinomial factor $i_t! / \prod_p i_p!$ that reorders the distinct subword copies. The claimed complexity is $O(t^2)$ for one subword and $O((t/a_{\min})^d\,t)$ for $d$ fixed subwords, against $O(q^t)$ for brute-force enumeration.
Load-bearing premise
The proof assumes copies of different subwords occupy disjoint positions, so the total occupied length is simply the sum of each subword's length times its required count; overlapping placements, such as the word 010 containing both 01 and 10, are outside what the formula counts.
Editorial extensions
If this is right
- For one non-self-intersecting subword of fixed length, the count is evaluable in $O(t^2)$ time rather than $O(q^t)$.
- For a fixed number $d$ of subwords, the nested-sum formula is polynomial in $t$, with the exponential cost confined to $d$.
- The same formulas apply directly to counting DNA sequences with prescribed motif multiplicities and passwords meeting multiple pattern constraints.
- The results are exact integer counts, so they can serve as standalone checks for randomized or approximate sequence generators.
Reading between the lines
- The authors do not pursue counting overlapping copies of different subwords, but that case would require inclusion-exclusion over shared positions; the $t=3$ binary example with subwords 01 and 10 marks the boundary of the current formula.
- I infer the practical win is for small fixed $d$: the $(t/a_{\min})^d$ factor is polynomial in $t$ but exponential in $d$, so the method is not meant for a growing list of motifs.
- The same relative-position idea could be adapted to self-intersecting subwords by handling border overlaps directly, a direction the conclusion names as future work.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims to derive closed-form formulas for counting words of length t over a q-letter alphabet that contain a given subword A exactly x times (Theorem 5), and then extends this to a list of subwords with prescribed multiplicities (Theorem 8). It further claims that these formulas reduce counting complexity from exponential to polynomial in t, with a polynomial but d-dependent cost for multiple subwords, and it sketches applications to DNA motif counting and password-policy counting. The multi-subword formula is the advertised main contribution.
Significance. If the formulas were correct, the paper would provide a useful polynomial-time counting tool and would extend the single-pattern case to several patterns. The paper contains no fitted parameters and presents explicit, testable closed-form expressions, which is a strength. However, the central multi-subword formula is invalid, so the claimed advance is not established; the polynomial-time multi-pattern counting result is unsupported.
major comments (3)
- [Section 3.2, Eqs. (23)-(24)] Theorem 8 is false as stated. The proof after Eq. (26) claims that the sums for different subwords are independent because they do not share an index, so the counts can be multiplied and then combined by a multinomial factor. This confuses independence of summation indices with independence of placements in an actual word: occurrences of distinct subwords can overlap or constrain one another. A counterexample satisfying all stated hypotheses is q=2, t=4, A1="01", A2="10", x1=x2=1; both subwords are non-self-intersecting. Exhaustive enumeration of the 16 binary strings of length 4 gives exactly 6 words containing each subword exactly once: 0010, 0100, 0110, 1001, 1011, and 1101. In Eq. (24) the only admissible index pair is (i1,i2)=(1,1), and the term equals (-1)^3 * 2^0 * ((3 choose 0)) * ((1 choose 0))^2 * (2!/(1!1!)) = -2. A count cannot be negative. The limitation note in Section 5.3 says that overlapping subwords are left to future work, but Theorem 8 does not exclude overlaps, so this is not a boundary case but a failure of the theorem's central step.
- [Section 3.1, Theorem 5] The proof of Theorem 5 is too sketchy to meet journal standards. Lemma 6 is justified only through informal statements about 'slight rearrangements' and 'simplified in relation to its neighbors,' and the derivation of the final alternating sum from an across-sum is asserted rather than proved. Since Theorem 5 is the foundation for Theorem 8, a complete inclusion-exclusion proof is required. My own spot checks did not contradict Theorem 5, but the current presentation does not provide a rigorous basis for the claimed single-subword result.
- [Section 5, Applications] The paper gives no numerical verification against brute-force enumeration for any small case. The applications in Sections 5.1 and 5.2 merely display formulas and do not report computed values or compare them with exhaustive counts. A simple brute-force check for the multi-subword example would have exposed the failure of Eq. (24). Any revision must include such machine-checked tables for small t, q, and d.
minor comments (5)
- [Section 3.1, Eq. (5)] The double-parentheses notation for multiset binomial coefficients is never defined; the reader must infer it from context.
- [Section 3.2, Eqs. (23)-(25)] The notation '1∑ p=d' is nonstandard and should be written as a conventional summation, for example ∑_{p=1}^{d}.
- [Section 3.1, Definitions 1-3] The notions of 'unoccupied position' and 'relative position' are informal; the proof assumes an ordering of copies of A that is never defined formally.
- [Section 3.1, Definition of Y] The set S is defined as a set of multisets of contiguous subwords, but |Y| is used as the number of words; this conflates words with their subword multisets and should be clarified.
- [Section 4.3, Table 1] The traditional multi-subword complexity is written as O(q^t · t^d), but q^t already dominates all polynomial factors in t, so the t^d factor is misleading.
Circularity Check
No significant circularity: the paper's claimed derivations are not equivalent to their inputs by construction, though Theorem 8 rests on an unproven independence assumption that is a correctness concern, not a circular one.
full rationale
This manuscript does not fit any of the enumerated circularity patterns. No parameter is fitted to data and then renamed as a prediction: the formulas in Theorems 5 and 8 are explicit closed-form expressions in t, q, and the subword parameters, with no free coefficients calibrated to the target output. The paper's citations are to standard combinatorics references (Stanley, Plaza, Brualdi, Grimaldi, Shahriari) and to the authors' own software repository [8]; none of these citations is load-bearing in the derivation of the counting formula in the way a self-citation chain would be, and the software repository is only an implementation aid, not evidence for the theorem. The proof of Theorem 8 does contain a critical gap: after equation (26) it asserts that across-sums that do not share an index are 'independent', and therefore multiplies them. This is mathematically false for occurrences of different subwords in the same word and yields wrong counts (e.g., for q=2, t=4, A1='01', A2='10', the formula gives -2 instead of the enumerated count 6). However, that error is an invalid inference from the definitions, not a case of the theorem being equivalent to its input by construction. The claimed complexity reduction is derived from counting summation iterations, not assumed from the result. Accordingly, under the hard rules, no circular step can be quoted, and the score is 0; the mathematical flaw belongs under correctness risk rather than circularity.
Assumptions & free parameters
assumptions (3)
- domain assumption The subword A has no non-trivial self-overlap (Definition 3).
- domain assumption For multiple subwords, placements factorize as a product of independent per-subword placement counts, corrected only by a multinomial ordering factor.
- standard math Lemma 6 binomial identity is valid.
Cite this review
Pith. "Pith review of From Exponential to Polynomial Complexity: Efficient Permutation Counting with Subword Constraints." pith.science (2026). https://pith.science/paper/ASJC3LTQ
@misc{pith2026241116744,
author = {Pith},
title = {Pith review of: From Exponential to Polynomial Complexity: Efficient Permutation Counting with Subword Constraints},
year = {2026},
howpublished = {\url{https://pith.science/paper/ASJC3LTQ}},
note = {Machine review of arXiv:2411.16744}
}
read the original abstract
Counting distinct permutations with replacement, especially when involving multiple subwords, is a longstanding challenge in combinatorial analysis, with critical applications in cryptography, bioinformatics, and statistical modeling. This paper introduces a novel framework that presents closed-form formulas for calculating distinct permutations with replacement, fundamentally reducing the time complexity from exponential to linear relative to the sequence length for single-subword calculations. We then extend our foundational formula to handle multiple subwords through the development of an additional formula. Unlike traditional methods relying on brute-force enumeration or recursive algorithms, our approach leverages novel combinatorial constructs and advanced mathematical techniques to achieve unprecedented efficiency. This comprehensive advancement in reducing computational complexity not only simplifies permutation counting but also establishes a new benchmark for scalability and versatility. We also demonstrate the practical utility of our formulas through diverse applications, including the simultaneous identification of multiple genetic motifs in DNA sequences and complex pattern analysis in cryptographic systems, using a computer program that runs the proposed formulae.
Reference graph
Works this paper leans on
-
[1]
Richard P. Stanley. Enumerative Combinatorics: Volume 1 . 2nd edition, 2011
work page 2011
-
[2]
Proof without words: Alternating row sums in pascal’s t riangle
´Angel Plaza. Proof without words: Alternating row sums in pascal’s t riangle. Mathematics Magazine, 89(4):281, 2016
work page 2016
-
[3]
Richard A. Brualdi. Introductory Combinatorics. Prentice-Hall, 5th edition, 2010
work page 2010
- [4]
-
[5]
An Invitation to Combinatorics
Shahriar Shahriari. An Invitation to Combinatorics . Cambridge University Press, 2021
work page 2021
-
[6]
Counting occurrences of some subword patterns
Alexander Burstein and Toufik Mansour. Counting occurrences of some subword patterns. arXiv preprint math/0204320 , 2003. 14
work page Pith review arXiv 2003
-
[7]
Counting s ubwords in a partition of a set
Toufik Mansour, Mark Shattuck, and Sherry HF Yan. Counting s ubwords in a partition of a set. The Electronic Journal of Combinatorics , 17:R19, 2010
work page 2010
-
[8]
Combinatorics formula repository, 2024
Martin Mathew. Combinatorics formula repository, 2024. Acces sed: 2024-11-16. 15
work page 2024
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.