
We study the computational complexity of distance games, a class of
combinatorial games played on graphs. A move consists of colouring an
uncoloured vertex subject to it not being at certain distances determined by
two sets, D and S. D is the set of forbidden distances for colouring vertices
in different colors, while S is the set of forbidden distances for the same
colour. The last player to move wins. Wellknown examples of distance games are
NodeKayles, Snort, and Col, whose complexities were shown to be PSPACEhard.
We show that many more distance games are also PSPACEhard.

We study the $\star$operator (Larsson et al. 2011) of impartial vector
subtraction games (Golomb 1965). Here we extend the notion to the mis\`ereplay
convention, and prove convergence and other properties; notably more structure
is obtained under mis\`ereplay as compared with the normalplay convention
(Larsson 2012).

The game of nim, with its simple rules, its elegant solution and its
historical importance is the quintessence of a combinatorial game, which is why
it led to so many generalizations and modifications. We present a modification
with a new spin: building nim. With given finite numbers of tokens and stacks,
this twoplayer game is played in two stages (thus belonging to the same family
of games as e.g. ninemen's morris): first building, where players alternate to
put one token on one of the, initially empty, stacks until all tokens have been
used. Then, the players play nim. Of course, because the solution for the game
of nim is known, the goal of the player who starts nim play is a placement of
the tokens so that the Nimsum of the stack heights at the end of building is
different from 0. This game is trivial if the total number of tokens is odd as
the Nimsum could never be 0, or if both the number of tokens and the number of
stacks are even, since a simple mimicking strategy results in a Nimsum of 0
after each of the second player's moves. We present the solution for this game
for some nontrivial cases and state a general conjecture.

A circular Nim game is a two player impartial combinatorial game consisting
of n stacks of tokens placed in a circle. A move consists of choosing k
consecutive stacks, and taking at least one token from one or more of the k
stacks. The last player able to make a move wins. We prove results on the
structure of the losing positions for small n and k and pose some open
questions for further investigations.

A classical result by Guibas and Odlyzko obtained in 1981 gives the
generating function for the number of strings that avoid a given set of
substrings with the property that no substring is contained in any of the
others. In this paper, we give an analogue of this result for the enumeration
of compositions that avoid a given set of prohibited substrings, subject to the
compositions' length (number of parts) and weight. We also give examples of
families of strings to be avoided that allow for an explicit formula for the
generating function. Our results extend recent results by Myers on avoidance of
strings in compositions subject to weight, but not length.

A partially ordered (generalized) pattern (POP) is a generalized pattern some
of whose letters are incomparable, an extension of generalized permutation
patterns introduced by Babson and Steingrimsson. POPs were introduced in the
symmetric group by Kitaev [Partially ordered generalized patterns, Discrete
Math. 298 (2005), 212229; Introduction to partially ordered patterns, Discrete
Appl. Math., to appear], and studied in the set of $k$ary words by Kitaev and
Mansour [Partially ordered generalized patterns and $k$ary words, Annals of
Combinatorics 7 (2003) 191200]. Moreover, Kitaev et al. [S. Kitaev, T.
McAllister and K. Petersen, Enumerating segmented patterns in compositions and
encoding with restricted permutations, preprint] introduced segmented POPs in
compositions. In this paper, we study avoidance of POPs in compositions and
generalize results for avoidance of POPs in permutations and words.
Specifically, we obtain results for the generating functions for the number of
compositions that avoid shuffle patterns and multipatterns. In addition, we
give the generating function for the distribution of the maximum number of
nonoverlapping occurrences of a segmented POP $\tau$ (that is allowed to have
repeated letters) among the compositions of $n$ with $m$ parts in a given set,
provided we know the generating function for the number of compositions of $n$
with $m$ parts in the given set that avoid $\tau$. This result is a
$q$analogue of the main result in [S. Kitaev, T. Mansour, Partially ordered
generalized patterns and $k$ary words, Annals of Combinatorics 7 (2003)
191200].

A composition of $n\in\NN$ is an ordered collection of one or more positive
integers whose sum is $n$. The number of summands is called the number of parts
of the composition. A palindromic composition of $n$ is a composition of $n$ in
which the summands are the same in the given or in reverse order. In this paper
we study the generating function for the number of compositions (respectively
palindromic compositions) of $n$ with $m$ parts in a given set $A\subseteq\NN$
with respect to the number of rises, levels, and drops. As a consequence, we
derive all the previously known results for this kind of problem, as well as
many new results.