3
$\begingroup$

enter image description here

enter image description here

It appears the solutions to my problem are the Binomial Coefficients, as seen above

Suppose a combination lock with 2 dials exists, where each dial has 2 settings (for example, 0 and 1, but any two distinct numbers could capture two distinct settings). It has, of course, 2 x 2 unique settings. However, suppose the locksmith made a serious mistake, such that both the setting {0 1} and {1 0} open the lock. In this case, there are now 3, not 4 unique settings or "unlocks".

More generally, suppose a lock with D dials exists, where each dial has S settings, and suppose the lock defect specifically as follows:

The same set of numbers in any sequence reduce to one distinct "unlock".

Examples of reductions:

  • {1 0 2} and {1 2 0} (and four other permutations) open the lock.

  • {1 0 3 0} and {0 3 1 0} (and ten other permutations) open the lock.

Examples of non-reductions:

  • {1 0 2} and {1 0 0} are distinct.

Question: How many distinct "unlocks" are there in general in the defective lock?

Application / Background: I am working on a problem with an immense configuration space. The good news is that what matters for my overall problem is the characteristics of each state, and not the order of them. In that way, there are many states with the same effect. I wish to find the number of states with distinct effects, and that problem can be reduced to the one I have specified here.

I have used MATLAB to crunch the numbers shown in the table. I think the numbers are interesting, in that the ratios of these numbers (ii : i) converge upon a constant. Perhaps someone here is capable of finding the formula that captures what exactly these constants are?

$\endgroup$
  • 1
    $\begingroup$ In the general case how many numerical values are possible in each point in the sequence? $\endgroup$ – Michael R. Chernick Jun 29 '17 at 21:04
  • $\begingroup$ You might have to consider whether the number of possible ways to open the lock depends on the numbers in the code. $\endgroup$ – CloudyGloudy Jun 29 '17 at 21:05
  • 1
    $\begingroup$ @MichaelChernick there are S. $\endgroup$ – user120911 Jun 29 '17 at 21:08
  • $\begingroup$ @user120911 I think maybe what he meant is, after you've selected the first number in the sequence, how many options are left for the next number? $\endgroup$ – CloudyGloudy Jun 29 '17 at 21:09
  • $\begingroup$ Please clarify what you mean by "the way described above," because the patterns you give do not suggest a unique interpretation of the problem. You need to give criteria that let us know exactly which sets of combinations open the lock. $\endgroup$ – whuber Jun 29 '17 at 21:10
2
$\begingroup$

This problem, as I have interpreted it, has an easy one-line solution. This answer states my interpretation, outlines the background theory, presents the solution, gives a worked example, and appends an alternative solution (also a one-liner) for those familiar with generating functions.

Statement of the problem

Let's be as clear as possible about the problem. The settings on the "dials" may be construed as a vector $\mathbf{d}=(d_1,d_2, \ldots, d_D)$ where each $d_i$ is set to one of $S$ possible values, which we might as well designate $0, 1, \ldots, S-1$, as in the question. Ordinarily, a unique setting $\mathbf{d}$ "opens" the lock. The "defect" is that any permutation of this setting opens the lock too. How many permutations are there?

The answer depends on $\mathbf d$. This is apparent even in the simplest case $D=2,S=2$. The question notes there are two permutations of $\mathbf{d}=(0,1)$. However, there is only one permutation of $(1,1)$ and only one permutation of $(0,0)$. Evidently, the presence of repeat values in $\mathbf d$ reduces the number of (distinguishable) permutations.

The well-known Orbit-Stabilizer Theorem provides a quick answer. To see how it applies, let's examine the (obvious) group action. After that's out of the way, I will quote the theorem and apply it.


The group action

The symmetric group $\mathfrak{S}_D$ acts on the set of all these vectors, $S^D$, by permuting their components. For $\sigma \in \mathfrak{S}_D$ and $\mathbf {d}\in S^D$ let's write $\mathbf{d}^\sigma$ for the result of applying $\sigma$ to $\mathbf d$. The permutations of $\mathbf{d}$ form its orbit,

$$\mathfrak{S}_D \cdot \mathbf{d} = \{\mathbf{d}^\sigma\mid \sigma\in\mathfrak{S}_D\}.$$

Some of these permutations fix $\mathbf d$. This is the stabilizer subgroup

$$\left(\mathfrak{S}_D\right)_\mathbf{d} = \{\sigma\in\mathfrak{S}_D\mid \mathbf{d}^\sigma=\mathbf{d}\}.$$

The stabilizer is easy to characterize: for each possible setting $s\in S$, consider the components of $\mathbf d$ that equal $s$. (There may be none.) All permutations that move these components among themselves obviously leave $\mathbf d$ unchanged and any permutation that leaves $\mathbf d$ unchanged must be of this nature. Writing $n(s,\mathbf d)$ for the number of components of $\mathbf d$ equal to $s$, we see that the stabilizer of $\mathbf d$ is isomorphic to the product of the permutation groups on $n(s,\mathbf d)$ elements:

$$\left(\mathfrak{S}_D\right)_\mathbf{d} \cong \prod_{s\in S} \mathfrak{S}_{n(s,\mathbf d)}\tag{1}.$$

The Orbit-Stabilizer theorem asserts the number of elements in the orbit of $\mathbf d$ is the ratio of the sizes of the two groups in question: the "big group" $\mathfrak{S}_D$ and the stabilizer subgroup:

$$\vert \mathfrak{S}_D \cdot \mathbf{d} \vert = \frac{\vert \mathfrak{S}_D\vert}{\vert \left(\mathfrak{S}_D\right)_\mathbf{d} \vert} = \frac{\vert \mathfrak{S}_D\vert}{\prod_{s\in S} \vert \mathfrak{S}_{n(s,\mathbf d)}\vert }\tag{2}.$$

The second inequality follows from $(1)$. On the left is what we want to find.


The solution

Since the number of elements in any symmetric group $\mathfrak{S}_n$ is $n!$ (this often is taken as a definition of the factorial $n!$), we may immediately write down the solution from $(2)$ as

$$\vert \mathfrak{S}_D \cdot \mathbf{d} \vert = \frac{D!}{\prod_{s\in S}n(s,\mathbf d)!} = \binom{D}{n(0, \mathbf{d}), n(1, \mathbf{d}), \ldots, n(s-1, \mathbf{d})}.$$

This is the multinomial coefficient determined by $\mathbf d$.


Example

Let $\mathbf{d} = (0,3,1,0)$ with $S=\{0,1,2,3,4\}$. Counting,

$$\eqalign{n(0,\mathbf{d})=&2 \\ n(1,\mathbf{d})=&1 \\ n(2,\mathbf{d})=&0 \\ n(3,\mathbf{d})=&1 \\ n(4,\mathbf{d})=&0.}$$

Since $D =4$, the answer is

$$\vert \mathfrak{S}_D \cdot \mathbf{(0,1,3,0)} \vert = \binom{4}{2,1,0,1,0} = \frac{4!}{2!1!0!1!0!}= \frac{24}{2}=12.$$

Indeed, the twelve equivalent permutations of $\mathbf d$ are (in an abbreviated notation, dropping parentheses and commas)

$$\eqalign{\mathfrak{S}_4 \cdot 0130=\{ &0013,0031,0103,0130,0301,0310,\\&1003,1030,1300,3001,3010,3100\ \}.}$$


Alternative solution

Having seen the appearance of the multinomial coefficients, it becomes obvious the answer must be the coefficient of $\mathbf{x}^\mathbf{d} = x_0^{d_0}x_1^{d_1}\cdots x_{s-1}^{d_{s-1}}$ in the multinomial expansion of $$\left(\mathbf{x}\cdot \mathbf{1}\right)^D = (x_0+x_1+\cdots + x_{s-1})^D = \\\sum_{n_0+n_1+\cdots+n_{s-1}=D}\binom{D}{n_0,n_1,\ldots, n_{s-1}}x_0^{n_0}x_1^{n_1}\cdots x_{s-1}^{n_{s-1}},$$

because it counts the number of distinct ways of collecting $n(0,\mathbf d)$ zeros, $n(1,\mathbf {d})$ ones, etc, from the terms in the product and these enumerate all the distinguishable permutations of $\mathbf{d}$. In the case of two dials these coefficients obviously are the Binomial coefficients, as discovered in the edits to the question.

$\endgroup$
  • $\begingroup$ Thank you for your excellent answer! I was not aware of Orbit-Stabilizer Theorem. $\endgroup$ – user120911 Jun 30 '17 at 17:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.