The thread Widely accepted mathematical results that were later shown to be wrong? contains combinatorial examples, for example
- the Perko pair in knot enumeration [Perko, Kenneth A. jun., On the classification of knots, Proc. Am. Math. Soc. 45, 262-266 (1974). ZBL0256.55004.]
- the classification of all convex pentagons that tile the plane [Kershner, R. B., On paving the plane, Am. Math. Mon. 75, 839-844 (1968). ZBL0165.23801.]
- Frolov's wrong claim that there is no series of 7 distinct odd numbers, from 1 to 49, with sum 175 and sum of squares 5775 he used proving the non-existence of 7th-order bimagic squares [Frolov, Michel, Equalities of the second and third degree, Bull. Soc. Math. Fr. 20, 69-84 (1892). ZBL24.0176.01.]
- the number of knight's tours.
The following three and more examples are given in [Grünbaum, Branko, An enduring error, Elem. Math. 64, No. 3, 89-101 (2009). ZBL1176.52002)]):
- the number of of collections of 12 lines and 12 points, each incident with three of the others
- the enumeration of 4-dimensional simple polytopes with eight facets
- the number of uniform tilings of three-dimensional space.
More examples might be found by checking published errata/corrigenda/retractions in the field, though most are likely not due to computational errors. For example [Lam, Clement; Tonchev, Vladimir D., Classification of affine resolvable (2)-((27,9,4)) designs, J. Stat. Plann. Inference 56, No. 2, 187-202 (1996); corrigendum ibid. 86, 277-278 (2000). ZBL0874.05009] contained a wrong table with design computations, as explained in https://doi.org/10.1016/S0378-3758(99)00055-5.
P.S. Just saw that the question has been modified inbetween; now it's clear that not all examples above satisfy all given criteria. In fact, if we look into the set of combinatorial papers with corrections/retractions/errata/corrigenda that involve software, we obtain only 16 results, most of which have non-computational corrections. This supports the impression that these cases are relatively rare. The only example that may fulfill all criteria among them seems to be [Cormode, Graham; Jowhari, Hossein, Corrigendum to: “A second look at counting triangles in graph streams”, Theor. Comput. Sci. 683, 31-32 (2017). ZBL1370.68121.], where the algorithm needed a substantial correction which also led to a significantly modified result.
