What is combinatorial explosion? In the theory of NP-completeness, researchers refer to the concept of combinatorial  explosion. Some researchers use it as justification for intractability or NP-completeness. Others use it to refer to the exponential growth of possible solutions of an intractable problem while others use to refer to the apparent exponential time required to solve NP-complete problems. I am interested in formal connection to combinatorics.


  Is there combinatorial basis that captures and explains the phenomena of combinatorial explosion?
There is no formal connection to anything because "combinatorial explosion" is an informal term. It refers to rapid growth of a function caused by the combinatorics of the situation.