Constraint Satisfaction Problems are a broad class of combinatorial problems, including several classical decision problems such as graph colouring and SAT, and a range of problems' from other areas, including statistical physics, DNA sequencing and scheduling problems. There are a variety of dichotomy theorems for various subclasses of CSP in various complexity classes, one of the most noteable is Bulatov's proof that a dichotomy holds for #CSP [Bu108], that is, all #CSP problems are either #P-complete or in FP. In this thesis, we look at the complexity of modular counting in some restricted classes of CSP, answering questions of the sort "What is the number of solutions to this CSP modulo k? for various k. In particular, we discuss CSP restricted to relations on the domain of size 2, Boolean CSP or Generalised Sat- isfiability, and CSP restricted to a single, symmetric, binary relation, or Graph Homomorphism. In [CH96], Creignou and Hermann proved a dichotomy the- orem for counting solutions to Boolean CSP problems, and characterised the easy cases. We provide a proof of a dichotomy theorem for #kBoolean CSP for all k, characterising the easy cases. In [DG00], Dyer and Greenhill proved a dichotomy theorem for counting the number of homomorphisms into a fixed graph H, or H-colouring, and provided a characterisation of the types of H for which the problem is tractable. We give some results on O H-colouring. We give a conjectured dichotomy for the general O H-colouring problem, based on a condition related to the automorphism group of H. We show that this dichotomy holds for the case in which H is restricted to be a tree, and give some results about the complexity of determining, given an arbitrary H, whether the associated H-colouring problem is tractable assuming the dichotomy holds.

Cette thèse se divise en deux grandes parties, la première traite la combinatoire associée à l’ordre normal des opérateurs non-commutatifs et la seconde aborde des distributions symétriques du nombre de croisements et du nombre d’emboîtements, respectivement k-croisements et k-emboîtements, dans des structures combinatoires (partitions, permutations, permutations colorées, …). La première partie étudie l’ordre normal des opérateurs en termes de placements de tours. Nous étudions la forme de l’ordre normal en connectant deux opérateurs non-commutatifs D et U, et des polynômes orthogonaux spéciaux, et établissons des bijonctions entre les coefficients de (D+U)n et le nombre de placements de tours sur un diagramme de Ferrers. Nous donnons également des preuves combinatoires à des conjectures quantiques posées par des physiciens. Dans la seconde partie, nous définissons des statistiques, comme emboîtements et k-emboîtements, sur l’ensemble des permutations du groupe de Coxeter de type B. Nous donnons également des extensions au type B des résultats sur les croisements et les emboîtements, respectivement k-croisements et k-emboîtements dans les permutations de type A, en termes de distributions symétriques. De plus, nous étudions le lien entre les opérateurs non-commutatifs et ces statistiques. D’autres extensions de la distribution de ces statistiques sur les ensembles de partitions colorées et de permutations colorées de types A et B sont ainsi établies / This thesis is divided into two parts, the first deals with the combinatorics associated to the normal ordering form of noncommutative operators and the second addresses the symmetric distributions of the crossing numbers and nesting numbers, respectively k-crossings and k-nestings, in combinatorial structures (partitions, permutations, colored permutations, …). The first part studies the normal order of operators in terms of rook placements. We study the normal ordering form connecting two noncommutative operators D and U, and some special orthogonal polynomials, and establish bijonctions between coefficients of (D+U)n and rook placements in Ferrers diagrams. We also give combinatorial proofs and alternatives to some quantum conjectures posed by physicists. In the second part, we define the notions of statistics, nestings and k-nestings, on the sets of permutations of the Coxeter group of type B. We also give extensions to type B of the results of the crossings and nestings, respectivelu k-crossings and K-nestings in the set of permutations of type A, in terms of symmetric distributions. Likewise, we study the link between non-commutative operators and these statistics. Other extensions of the distribution of these statistics on the sets of colored partitions and colored permutations of type A and B are established