Intereting Posts

“The Galois group of $\pi$ is $\mathbb{Z}$”
Probability that a random binary matrix is invertible?
Help with this trigonometry problem
On radial limits of Blaschke Products
Why can any affine transformaton be constructed from a sequence of rotations, translations, and scalings?
Possible distinct binary tree structures at depth d
Prove that invertible metrices set is an open set in a given space, and the determinant is continuous
Floor of Square Root Summation problem
Proof of Different Polynomial Decompositions into Linear Factors
Projective space, explicit descriptions of maps.
Did Zariski really define the Zariski topology on the prime spectrum of a ring?
Prove that for a real matrix $A$, $\ker(A) = \ker(A^TA)$
Recurrence relation for the integral, $ I_n=\int\frac{dx}{(1+x^2)^n} $
Another way of expressing $\sum_{k=0}^{n} \frac{H_{k+1}}{n-k+1}$
Olympiad Inequality $\sum\limits_{cyc} \frac{x^4}{8x^3+5y^3} \geqslant \frac{x+y+z}{13}$

An integer $m$ is **acceptable** iff in it’s decimal representation all digits are different. For example $9876543210$ is the largest acceptable integer. For each $n\in \Bbb N$, $\theta(n)$ is the number of all acceptable positive integers not greater than $n$.

Is there a simple formula for $\theta(n)$?

- In how many ways a train can stop at $K$ of $N$ intermediate stations without stopping in any consecutive stations
- A closed form for $T_N = 1 + \sum\limits_{k=0}^{N-2}{(N-1-k)T_k}$?
- number of strictly increasing sequences of length $K$ with elements from $\{1, 2,\cdots,N\}$?
- Why do graph degree sequences always have at least one number repeated?
- Exercise from Comtet's Advanced Combinatorics: prove $27\sum_{n=1}^{\infty }1/\binom{2n}{n}=9+2\pi \sqrt{3}$
- Generating function solution to previous question $a_{n}=a_{\lfloor n/2\rfloor}+a_{\lfloor n/3 \rfloor}+a_{\lfloor n/6\rfloor}$

- Coupon collector's problem using inclusion-exclusion
- For which number does multiplying it by 99 add a 1 to each end of its decimal representation?
- A functional relation which is satisfied by $\cos x$ and $\sin x$
- Tricky (extremal?) combinatorics problem
- How many ways are there to color vertexes of a $n\times n$ square that in every $1\times 1$ squares we should have $2$ blue and $2$ red vertexes?
- Combinatorial Proof of $\binom{\binom{n}{2}}{2} = 3 \binom{n}{3}+ 3 \binom{n}{4}$ for $n \geq 4$
- Positivity of the alternating sum associated to at most five subspaces
- How many triangles in picture
- Number of subsets of a set $S$ of n elements , is $2^n$
- Race Problem counting

This is not a math answer, but if you’re only interested in the results I guess my approach is much simpler to understand. I simply let the computer calculate the numbers.

This one works, but is slow:

```
def isAcceptable(number):
s = str(number)
for i in range(len(s)-1):
for j in range(i+1,len(s)):
if s[i] == s[j]:
return False
return True
def getNumberOfAcceptableNumbers(n):
acceptable = 0
i = 1
while i <= n:
if isAcceptable(i):
acceptable += 1
i += 1
return acceptable
print(getNumberOfAcceptableNumbers(98765432))
```

It took over 5 minutes on my machine for 98765432. The result was 2,345,850.

I’m currently implementing this in Java. For 98765432 it takes only 32 seconds and I’m currently improving it.

```
import java.math.BigInteger;
public class DiffDigits {
/**
* All numbers that are not acceptable have at least one pair of two
* indices that have the same digit. Take the pair where the lower
* index is maximal. Return the lower index.
*
* @param number
* @return -1 iff number is acceptable, otherwise index as described above
*/
public static int getHighestIndexThatHasToChange(BigInteger number) {
String s = number.toString();
// i == 0 is the most significant digit
for (int i = 0; i < s.length() - 1; i++) {
for (int j = i + 1; j < s.length(); j++) {
if (s.charAt(i) == s.charAt(j)) {
return j;
}
}
}
return -1;
}
/**
* Get the amount of positive integers that are acceptable in range [i, end]
*
* @param i the first number to check
* @param end the last one to check
* @return
*/
public static int getNumberOfAcceptableNumbers(BigInteger i, BigInteger end) {
BigInteger one = new BigInteger("1");
BigInteger ten = new BigInteger("10");
int acceptable = 0;
while (i.compareTo(end) <= 0) {
int highestIndex = getHighestIndexThatHasToChange(i);
if (highestIndex == -1) {
acceptable++;
i = i.add(one);
} else {
i = i.add(ten.pow(i.toString().length() - 1 - highestIndex));
}
}
return acceptable;
}
public static void main(String[] args) {
System.out.println("Start");
long startTime = System.nanoTime();
System.out.println(getNumberOfAcceptableNumbers(new BigInteger("1"),
new BigInteger("9876543210")));
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println("Execution took " + duration / 1000000000.0
+ " seconds.");
System.out.println("End");
}
}
```

For $n = 9876543210$ there are 8,877,690 acceptable numbers. For this range, it took 56 seconds to execute. For every other range it will be less.

By the way, this sounds like a Project Euler task. Is it one? Which task is it?

Quite often, counting questions that are trivial for $n \le 10^d$ can be solved very efficiently in general by decomposing into decimal blocks of size $m\cdot 10^d$.

Define $\psi(n) = \theta(n-1)$ for convenience, and say you want to know $\psi(4537)$: decompose this into $$\psi(1000) + [\psi(4000)-\psi(1000)] + [\psi(4500)-\psi(4000)] + [\psi(4530)-\psi(4500) ] + [\psi(4537) – \psi(4530)].$$

Previous answers have already shown how to calculate $\psi(1000)$, but each of the remaining blocks is equally simple. For instance, $[\psi(4500)-\psi(4000)]$ is just the number of acceptable numbers between $4000$ and $4499$, inclusive. In this block the first digit is fixed, and the second digit is any of $0,1,2,3$ ($4$ being forbidden). The third digit has $8$ choices, and the fourth digit has $7$, so $\psi(4500)-\psi(4000) = 4\cdot8\cdot 7$.

The other blocks follow a quite similar pattern, they can all be computed using nothing more than “count how many digits of $x$ are at most $y$” and testing for distinctness, all very efficient operations even for bases much, much larger than $10$.

Yes. See this OEIS page or this MathWorld page.

$$ \theta(10^n – 1) = \sum_{k=1}^n \frac{9 \cdot 9!}{(10 – k)!} $$

- The first digit may be any of {1,2,…,9}, so 9 choices.
- The second digit may be any digit of {0,1,…,9}, except the first one. So 9 choices.
- The third digit may be any digit of {0,1,…,9}, except the first and the second one. So 8 choices.
- …
- The tenth digit may be any digit of {0,1,…,9}, except the nine previous,. So 1 choice.
- It is not possible to have 11 distinct digits.

So $θ(n)=9 \times 9 \times 8\times 7 … \times (10-n) = 9 \times \frac 9! {(-n)!}$

Apart for the $θ(n)=0$ for $n>10$ already mentioned, you also have an exception for 0, $θ(0)=10$ since $0$ is acceptable.

- $f,\overline f$ are both analytic in a domain $\Omega$ then $f$ is constant?
- Specific system of differential equations
- Prove that if for every $x \in \mathbb{R}^N$ $Ax=Bx$ then $A=B$
- Use Integration by Parts to prove that $\int x^{n}\ln{x}\ dx=\frac{x^{n+1}}{(n+1)^{2}}\left+c$
- Every planar graph has a vertex of degree at most 5.
- Torsion elements do not form a submodule.
- How to prove periodicity of $\sin(x)$ or $\cos(x)$ starting from the Taylor series expansion?
- Is it possible to generate a unique real number for each fixed length sequence of real numbers?
- Prove that $(x+y) \text{ mod } n = ((x \text{ mod } n)+(y \text{ mod } n)) \text{ mod } n$
- Show that the order of $a\times b$ is equal to $nm$ if gcd(n,m)=1
- Does $\sum_{n=1}^{\infty}\frac {\sin{\frac 1 n}} {\sqrt n}$ converge?
- Prove that the determinant of $ A^{-1} = \frac{1}{det(A)} $- Linear Algebra
- Sum of rational numbers
- Why is $|e^{i \lambda z}| |e^{- \lambda y}|= |e^{- \lambda y}|$ here?
- Does finite expectation imply bounded random variable?