My advice is that you should focus on the nature of the outcomes you are enumerating, rather than specific keywords in the language of the problem.
In the saleswoman question, ask yourself if it matters if the cities she visits are $A, B, C, D, E, F, G, H$ versus, say, $A, H, G, F, B, D, E, C$. If you are to interpret these as different outcomes, then you are looking at a permutation.
In the following example:
There is a bag of 9 marbles. 2 are red, 3 are blue, and 4 are green. How many ways are there to select a subset of 6 marbles from the bag such that there is at least one each of the three colors?
Does it matter if the marbles chosen are, say, $(r, r, g, g, b, b)$ versus $(r, g, b, g, r, b)$? Then a permutation on the individual outcomes is not applicable. But note that this question is a bit more complicated than a simple binomial coefficient computation, too. I mention it because counting methods ultimately rely not just on the question of "is it a permutation or combination" but other considerations as well.
You want to count ordered partitions of $n$ into parts of size at least $5$. You have $$A(x)=x^5+x^6+\dots= \frac{x^5}{1-x}$$
and
\begin{align}
B(x) &= \frac{1}{1-A(x)}
= \frac{1}{1-\frac{x^5}{1-x}}
= \frac{1-x}{1-x-x^5} \\
&= 1x^0 + 1x^5 + 1x^6 + 1x^7 + 1x^8 + 1x^9 + 2 x^{10} + 3 x^{11} + 4 x^{12} + 5 x^{13} + 6 x^{14} + 8 x^{15} + \dots
\end{align}
These coefficients look correct. For example, $2x^{10}$ corresponds to $10$ and $5+5$. The $3x^{11}$ corresponds to $11$, $6+5$, and $5+6$. Why do you doubt it?
Alternatively, let $b_n$ be the desired count of partitions. Clearly, $$b_n = \begin{cases}
1 &\text{if $n=0$}\\
0 &\text{if $n\in\{1,2,3,4\}$}\\
\end{cases} \tag1$$
For $n \ge 5$, condition on the size of the first part to obtain recurrence
$$b_n = \sum_{k=5}^n b_{n-k} \tag2$$
Now $(1)$ and $(2)$ imply that
\begin{align}
B(x) &= 1x^0 + \sum_{n=5}^\infty \left(\sum_{k=5}^n b_{n-k}\right)x^n\\
&= 1 +\sum_{k=5}^\infty x^k \sum_{n=k}^\infty b_{n-k} x^{n-k}\\
&= 1 +\sum_{k=5}^\infty x^k B(x) \\
&= 1 +B(x) \frac{x^5}{1-x}.
\end{align}
Solving for $B(x)$ yields
$$B(x)=\frac{1}{1-\frac{x^5}{1-x}}
=\frac{1-x}{1-x-x^5}.$$
Best Answer
We can consider polynomials with exponent "mod $k$". Then, your polynomial is
$$ I_n(x)=(1+x+\cdots+x^{k-1})P(x) $$
For all terms $c_sx^s$ of $P(x)$, the product $(1+x+\cdots+x^{k-1})(c_sx^s)$ is just $c_s(1+x+\cdots+x^{k-1})$, since remember the exponents are taken mod $k$. Therefore $I_n(x)$ is $S(1+x+\cdots+x^{k-1})$, where $S$ is the sum of the coefficients of $P$. Since all $k$ coefficients are equal, and they sum to $n!$ (as there are $n!$ permutations), each coefficient of $I_n(x)$ with exponents mod $k$ must be $n!/k$.