I've decided to explore Friedman's stuff better. I should start with n(k) because it's slowest widely known function defined by him.

Let's define the function L(n,m) as the number of Friedman strings which have n letters from alphabet {1,2,...,m}.

For example, let's compute L(4,2). First, we write all strings with n letters from alphabet {1,2,...,m}:

**1111**

**1112**

**1121**

1122

1211

**1212**

1221

1222

2111

2112

**2121**

2122

2211

**2212**

**2221**

**2222**

Then we remove strings written in bold text from this list because they're not Friedman. It contains 8 strings and so L(4,2) = 8.

Now we can redefine n(k) as the largest p so that L(p,k) > 0. The problem drops to explore the behavior of L(p,k) function.

For k = 2, we have the following sequence:

L(1,2) = 2

L(2,2) = 4

L(3,2) = 8

L(4,2) = 8

L(5,2) = 16

L(6,2) = 12

L(7,2) = 24

L(8,2) = 4

L(9,2) = 8

L(10,2) = 2

L(11,2) = 4

L(12,2) = 0

L(i,2) = 0 (for i > 12)

We can note that if m is even, then L(m+1,n) = L(m,n)*n. If m is odd, then it's not clear how L(m+1,n) compares to L(m,n). If we find that out, bounding n(k) might be straightforward.