It is not necessary to pass the whole "N", "O" array - we only need to know how many of each remains (I've substituted the array param with `nRemainingCount` and `oRemainingCount`).

The bruteforce solution would be to generate all permutations, then filter out entries which violate the "never more "O"s than "N"s preceding it" rule afterwards. I believe this would be O(n^2) - n being the length of the input array.

    private static IEnumerable<string> Permutations(string aggregate,
              int nAggregateCount, int oAggregateCount, int nRemainingCount, int oRemainingCount)
    {
        var nAppended = Enumerable.Empty<string>();
        var oAppended = Enumerable.Empty<string>();

        if (nRemainingCount != 0)
        {
            nAppended = Permutations(aggregate + "N", nAggregateCount + 1, oAggregateCount, nRemainingCount - 1, oRemainingCount);
        }

        if (oRemainingCount != 0 && nAggregateCount != oAggregateCount)
        {
            oAppended = Permutations(aggregate + "O", nAggregateCount, oAggregateCount + 1, nRemainingCount, oRemainingCount - 1);
        }

        return nAppended.Concat(oAppended);
    }

We could improve that by adding the filter early at the start of the function, resulting in:

    private static IEnumerable<string> Permutations(string aggregate,
              int nAggregateCount, int oAggregateCount, int nRemainingCount, int oRemainingCount)
    {
        var areBothEmpty = nRemainingCount == 0 && oRemainingCount == 0;
        var isBlockedByNrule = oRemainingCount == 0 && nAggregateCount == oAggregateCount;
        if (areBothEmpty || isBlockedByNrule) return new[] { aggregate };

        var nAppended = Enumerable.Empty<string>();
        var oAppended = Enumerable.Empty<string>();

        if (nRemainingCount != 0)
        {
            nAppended = Permutations(aggregate + "N", nAggregateCount + 1, oAggregateCount, nRemainingCount - 1, oRemainingCount);
        }

        if (oRemainingCount != 0 && nAggregateCount != oAggregateCount)
        {
            oAppended = Permutations(aggregate + "O", nAggregateCount, oAggregateCount + 1, nRemainingCount, oRemainingCount - 1);
        }

        return nAppended.Concat(oAppended);
    }

I don't dare to guess of which algorithmic complexity this is (I think less than O(n^2) though).

We could further improve by introducing a lookup table - as there are repeating sequences of { nAggregateCount == oAggregateCount, nRemainingCount, oRemainingCount } occuring in the "search tree" - with the same tail generated.