0

Here's a question I've been working on:

For which of the values of $n$ and $k$ does there exist a function of $n$ variables that has $k$ distinct variants?

For example, when $n = 2$ and $k = 1$, I claim that there does exist a function and I chose the function $x_1x_2$. It has two variables $(n = 2)$ and if we write down all the possible variants, we have $x_1x_2$ and $x_2x_1$, but these two are equivalent (commutative property of multiplication). In other words, $k = 1$. But, how about when $n$ is arbitrary and $n = k$? I'm not sure if this statement holds true or not.

John W. Smith
  • 1,597
  • Your definition of $k$ is a little strange. There are two versions of your function $x_1x_2$ and $x_2x_1$ so it would be more normal to define $k=2$ in your example. In your final question, your example would be a case of $n=k$ if you didn't subtract $1$ from $k$. Is that what you meant? – Ross Millikan Apr 03 '17 at 03:37
  • Ah yes I have several typos. I will revise right now. – John W. Smith Apr 03 '17 at 03:38
  • I'm not sure if the edit helped out or not, but feel free to ask anything. – John W. Smith Apr 03 '17 at 03:41
  • I don't think it helped. My point is that it seems more natural to say $k=2$ for this function as there are two permutations of the variables. That makes is much easier to cast the evaluation of $k$ in terms of multinomial coefficients. For example, if we use my $k$, for $n=k=3$ we can have the function $x_1x_1x_2$ which has three permutations. For your $k$ we would demand four permutations, the original one plus three. – Ross Millikan Apr 03 '17 at 03:50
  • Ahh okay I see how your looking at it then. Is it possible to show the result of the latter question I posted if we use your perspective of interpreting $k$? – John W. Smith Apr 03 '17 at 03:53

1 Answers1

1

If we redefine $k$ as the number of equivalent functions with total degree $n$ there is always a function with $n=k$. We can just use $x_1^{n-1}x_2$. The $x_2$ can go in any position in the string, so there are $n$ different functions.

If you insist on $n$ different variables, there are $n!$ permutations of them. Your example with two variables and two orders works because $2=2!$. The only other case of that is $1!=1$, so for $n=k=1$ there is a solution $x_1$, which has only one function.

Ross Millikan
  • 374,822
  • This does make sense. So is the top portion is basically how you would approach the question (based on how you evaluate $k$ and $n$) correct? The second half of your explanation is clear. – John W. Smith Apr 03 '17 at 04:10
  • It is correct if $n$ is total degree instead of the number of distinct variables. It comes from the mutinomial coefficient. You start with $n$ different variables, which gives $n!$ distinct functions. If you make $m$ of the variables the same, you divide the number of functions by $m!$. Since $\frac {n!}{(n-1)!}=n$ by identifying all the variables except one I get $n$ equivalent functions. – Ross Millikan Apr 03 '17 at 04:15
  • That's really interesting. It never occurred to even consider your perspective of the problem. But yes, this explanation clears it up. – John W. Smith Apr 03 '17 at 04:17