Find the formula (can be in the form of a sum) expressing, for a fixed natural number $n \geq 1$, the number of all binary strings $(a_1, . . . , a_{3n})$ of length $3n$ such that for every ordered triple $(c_1, c_2, c_3)$, where $c_i \in \{ 0, 1 \}$, there exists a number $k \in [n]$ such that $(c_1, c_2, c_3) = (a_{3k-2}, a_{3k-1}, a_{3k})$.
As I understand the problem - I need to find the formula to express the number of binary strings such that for every possible combination of $3$ consecutive binary numbers, it exists in the string and is placed in such way that the last index it ocupies is divisible by $3$.
So we have to place our $8$ possible combinations: $000, 111, 001, 010, 100, 110, 101, 011, $ in the string. Therefore the smallest string possible consists of $3 \cdot 8 = 24$ digits.
I think the answer would be: ${{n}\choose{8}}8! \cdot 2^{3n-24}$. We first choose $8$ triplets out of $n$ avaliable, then we swap those $8$ triplets as we wish. At the end we choose $1$s and $0$s for the remainning digits.
Is that correct? In the statement of the problem they speak about the final expression being in a form of a sum which throws me off a bit.
This is just a devious way of asking for the number of surjections from $[n]$ to $[8]$.
The answer is $8!S(n,8)$ where $S(n,k)$ is the number of partitions of the set $[n]$ into $k$ (nonempty) parts, a so-called Stirling number of the second kind.
Alternatively, let $E$ be the set of all maps from $[n]$ to $[8]$, and for $i\in[8]$ let $E_i$ be the set of all maps from $[n]$ to $[8]\setminus[i]$. The number of surjections from $[n]$ to $[8]$ is equal to $$|E\setminus(E_1\cup E_2\cup E_3\cup E_4\cup E_5\cup E_6\cup E_7\cup E_8)|.$$ By the in-and-out formula this is equal to $$\sum_{k=0}^8(-1)^k\binom8k(8-k)^n=$$$$8^n-8\cdot7^n+28\cdot6^n-56\cdot5^n+70\cdot4^n-56\cdot3^n+28\cdot2^n-8\cdot1^n+0^n.$$