How many different numbers can be written if each used digit symbol is used at least 2 times?

Solution 1:

Here we consider two examples and derive a general formula from them. A small table with a reference to OEIS is provided at the end.

[2016-02-22] Some formulas for diagonals $P(n+m,n)$ and generating functions added.

[2016-02-23] Epilogue added.

Example $P(4,4)$:

With $n=4$ and $d=4$ we have four digits $0,1,2,3$ and four positions to place them. The allowed numbers contain either one digit placed on four positions or two digits each of them placed on two positions.

We consider \begin{array}{lccl} \text{type}&\text{nr of digits}&\text{nr type arrangements}&\text{nr placements of digits}\\ 4&\binom{4}{1}&\frac{1!}{1!}&\binom{4}{4}\\ 2,2&\binom{4}{2}&\frac{2!}{1!1!}&\binom{4}{2}\binom{2}{2}\\ \end{array}

and get \begin{align*} P(4,4)&=\binom{4}{1}\frac{1!}{1!}\binom{4}{4}+\binom{4}{2}\frac{2!}{2!}\binom{4}{2}\binom{2}{2}\\ &=4\cdot1\cdot1+6\cdot1\cdot6\cdot1\\ &=4+36\\ &=40 \end{align*}

Comment:

• Nr of digits: In case of type $(2,2)$ there are $\binom{4}{2}$ ways to select two digits from $0,1,2,3$.

• Nr of type arrangements: Since the position of the digits within a number is relevant there are $\frac{2!}{1!1!}$ ways to map two digits to the type $(2,2)$. This is more evident when looking e.g. at the type $(3,2,2)$ which means three occurrences of one digit and two occurrences of the second digit and two of the third digit. The number of different type arrangements in this case is \begin{align*} \frac{3!}{1!2!} \end{align*}

• Nr of placements of digits: We can place the first digit in $\binom{4}{2}$ ways at two positions, leaving $\binom{2}{2}$ ways placing the other digit at two positions.

We consider one more example.

Example $P(3,6)$: Here we have to consider four different types $(6),(4,2),(3,3)$ and $(2,2,2)$.

We obtain \begin{array}{lccl} \text{type}&\text{nr of digits}&\text{nr type arrangements}&\text{nr placements of digits}\\ 6&\binom{3}{1}&\frac{1!}{1!}&\binom{6}{6}\\ 4,2&\binom{3}{2}&\frac{2!}{1!1!}&\binom{6}{4}\binom{2}{2}\\ 3,3&\binom{3}{2}&\frac{2!}{2!}&\binom{6}{3}\binom{3}{3}\\ 2,2,2&\binom{3}{3}&\frac{3!}{3!}&\binom{6}{2}\binom{4}{2}\binom{2}{2}\\ \end{array}

We get \begin{align*} P(3,6)&=\binom{3}{1}\frac{1!}{1!}\binom{6}{6}+ \binom{3}{2}\frac{2!}{1!1!}\binom{6}{4}\binom{2}{2}+ \binom{3}{2}\frac{2!}{2!}\binom{6}{3}\binom{3}{3}+ \binom{3}{3}\frac{3!}{3!}\binom{6}{2}\binom{4}{2}\binom{2}{2}\\ &=3\cdot1\cdot1+3\cdot2\cdot15\cdot1+3\cdot1\cdot20\cdot1+1\cdot1\cdot15\cdot6\cdot1\\ &=3+90+60+90\\ &=243 \end{align*}

Note: The values $P(4,4)=40$ and $P(3,6)=243$ can also be derived from the recursion formula stated in the answer by @ChristianBlatter.

Formula for $P(n,d)$

From the examples above we can derive a formula for $P(n,d)$ for $n\geq 1, d\geq 2$.

\begin{align*} P(n,d)=\sum_{k=1}^{\lfloor\frac{d}{2}\rfloor}\binom{n}{k}\sum_{{r_1+r_2+\cdots+r_k=d}\atop{r_j\geq 2}} \binom{k}{r_1,\ldots, r_k}\prod_{j=1}^{k}\binom{d-\sum_{l=1}^{j-1}r_l}{r_j}\tag{1} \end{align*}

Table of $P(n,d)$

Using formula (1) or maybe more effectively using the recursion formula from @ChristianBlatter we find for small values of $n$ and $d$

\begin{array}{crrrrrr} n\backslash d&2&3&4&5&6&7\\ 1&1&1&1&1&1&1\\ 2&\color{blue}{2}&2&8&22&52&114\\ 3&3&\color{blue}{3}&21&63&243&969\\ 4&4&4&\color{blue}{40}&124&664&3196\\ 5&5&5&65&\color{blue}{205}&1405&7425\\ 6&6&6&96&306&\color{blue}{2556}&14286\\ 7&7&7&133&427&4207&\color{blue}{24409}\\ \end{array}

The diagonal (blue) values $P(n,n)$ equal to $2,3,40,205,2556,24409,\ldots$ are stated as sequence A231797 in OEIS. We find there

\begin{align*} P(n,n)=n![x^n]\left(e^x-x\right)^n\qquad\qquad n\geq 0 \end{align*}

Addendum [2016-02-22]

Some more aspects around $P(n,d)$. We start with an explicit formula of $P(n,n)$ and state a conjecture for $P(n+m,n)$. Then we provide a relationship of corresponding generating functions. I think this relationship of generating functions is the key to prove the conjecture.

A Formula for $P(n,n)$:

The following is valid \begin{align*} P(n,n)=\sum_{k=0}^n(-1)^{n-k}\frac{n!}{k!}\binom{n}{k}k^k \end{align*}

Indeed, this follows easily from (2) since

\begin{align*} P(n,n)&=n![x^n]\left(e^x-x\right)^n\\ &=n![x^n]\sum_{k=0}^n\binom{n}{k}e^{kx}(-x)^{n-k}\tag{2}\\ &=n!\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}[x^k]e^{kx}\\ &=n!\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}[x^k]\sum_{j=0}^\infty\frac{(kx)^j}{j!}\\ &=\sum_{k=0}^n(-1)^{n-k}\frac{n!}{k!}\binom{n}{k}k^k \end{align*}

Comment:

• In (2) we rearrange the sum and use the rule $[x^{n+m}]A(x)=[x^n]x^{-m}A(x)$

Conjecture for $P(n+m,n)$:

Playing with values of $P(n+m,n)$ for small $m$ gives rise to following conjecture:

\begin{align*} P(n+m,n)=\sum_{k=m}^n(-1)^{n-k}\frac{n!}{k!}\binom{n-m}{k-m}k^{k-m}\qquad 0\leq m\leq n \end{align*}

$$ $$

Generating functions:

We consider an exponential generating function $A_n(x)$ for $P(n,d)$ \begin{align*} A_n(x)=\sum_{d=0}^{\infty}P(n,d)\frac{x^d}{d!}\qquad\qquad n\geq 1 \end{align*} and provide a functional relationship between them.

The following is valid \begin{align*} A_{n+1}(x)=(e^x-x)A_n(x)\qquad\qquad n\geq 1\tag{3} \end{align*}

We obtain

\begin{align*} e^xA_{n}(x)&=\left(\sum_{j=0}^{\infty}\frac{x^j}{j!}\right)\left(\sum_{d=0}^{\infty}P(n,d)\frac{x^d}{d!}\right)\\ &=\sum_{d=0}^{\infty}\left(\sum_{{k+j=d}\atop{k,j\geq 0}}\frac{P(n,k)}{k!j!}\right)x^d\\ &=\sum_{d=0}^{\infty}\left(\sum_{k=0}^d\binom{d}{k}P(n,k)\right)\frac{x^d}{d!}\\ &=\sum_{d=0}^{\infty}\left(P(n,d)+\sum_{k=0}^{d-2}\binom{d}{k}P(n,k)\right)\frac{x^d}{d!}+\sum_{d=0}^{\infty}dP(n,d-1)\frac{x^d}{d!}\tag{4}\\ &=\sum_{d=0}^\infty P(n+1,d)\frac{x^d}{d!}+x\sum_{d=1}^{\infty}P(n,d-1)\frac{x^{d-1}}{(d-1)!}\\ &=A_{n+1}(x)+xA_n(x) \end{align*}

and the claim follows.

Comment:

• In (4) we apply the recurrence relation stated by @ChristianBlatter

Conclusion: From (3) we obtain a closed expression for $A_n(x)$ \begin{align*} A_n(x)=\sum_{d=0}^{\infty}P(n,d)\frac{x^d}{d!} =(e^x-x)^n\qquad\qquad n\geq 1\tag{5} \end{align*}

Note: The conjecture and the general representation of $P(n,d)$ follows from (5). This is shown in an answer by OP below.

Addendum [2016-02-23]

Epilogue: Some reflections adressing the relationship with generating functions

• Binomial inverse pair: The recurrence relation provided by @ChristianBlatter $$P(n+1,d)=\sum_{{k=0}\atop{k\ne 1}}^{d}\binom{d}{k}P(n,k)\qquad\qquad n\geq 1, d\geq 0$$

  is an example for a binomial inverse pair. To show this kind of relationship we multiply exponential generating functions. Let $A(x)=\sum_{n\ge0}a_{n}\frac{x^n}{n!}$ and $B(x)=\sum_{n\ge0}b_{n}\frac{x^n}{n!}$ with $B(x)=A(x)e^x$. Comparing coefficients gives the following binomial inverse pair \begin{align*} B(x)&=A(x)e^x&A(x)&=B(x)e^{-x}\\ b_n&=\sum_{k=0}^{n}\binom{n}{k}a_k&a_n&=\sum_{k=0}^{n}\binom{n}{k}(-1)^{n-k}b_k \end{align*} This simple one and many other examples of binomial inverse pairs can be found e.g. in Combinatorial Identities a classic from John Riordan ($1968$).

• Generalisation: The generating function of the recurrence relation is \begin{align*} A_{n+1}(x)=(e^x-x)A_n(x)\qquad\qquad n\geq 1 \end{align*} There seems to be a strong relationship of the term $-x$ in $(e^x-x)$ and the skipped index $k=1$ in the recurrence relation. A natural generalsation could ask for relationship and interpretation of \begin{align*} B_{n+1}(x)=(e^x-\sum_{k=1}^m\frac{x^k}{k!})B_n(x)\qquad\qquad m,n\geq 1 \end{align*}

• Divisibility property: The nice property $P(n,d)\equiv n^d\pmod{d}$ has following representation via generating function \begin{align*}\ d\left|\left(P(n,d)-n^d\right)\right.\qquad\qquad\qquad \frac{1}{x}\left((e^x-x)^n-e^{nx}\right)\qquad\qquad n\geq 1 \end{align*} The claim divisibility of $P(n,d)-n^d$ by $d$ is equivalent to the claim that the coefficients of the generating functions are integral. Looking at the generating function for a short time and this becomes obvious.

Solution 2:

One has the following recursion: $$P(1,0)=1,\quad P(1,1)=0,\quad P(1,d)=1\quad(d\geq2),$$ and then $$\eqalign{P(n+1,0)&=1,\quad P(n+1,1)=0,\cr P(n+1,d)&=P(n,d)+\sum_{k=0}^{d-2}{d\choose k}\>P(n,k)\qquad(d\geq2)\ .\cr}$$ Proof of the recursion formula: One obtains an admissible string of length $d$ over the alphabet $[n+1]$ by choosing $k\in\{0,2,3,\ldots,d\}$ cells to place the digit $n+1$ and then filling the remaining cells with an admissible word of length $d-k$ over the alphabet $[n]$. This leads to $$P(n+1,d)=\sum_{0\leq k\leq d, \ k\ne1}{d\choose k}P(n,d-k)\ ,$$ which is easily transformed into the above formula.

Solution 3:

We can keep this simple. The labeled species of sequences of $q$ sets with at least two elements is given by

$$\mathfrak{S}_{=q}(\mathfrak{P}_{\ge 2}(\mathcal{Z})).$$

We get the admissible contributions to $P(n,d)$ by choosing $q$ values from the $n$ different digits and letting the first set be the positions of the smallest chosen digit, the next one of the second smallest and so on. This yields the species

$$\sum_{q=1}^n {n\choose q} \mathfrak{S}_{=q}(\mathfrak{P}_{\ge 2}(\mathcal{Z})).$$

Translating to generating functions we have

$$\sum_{q=1}^n {n\choose q} (\exp(z)-1-z)^q = -1 + (\exp(z)-z)^n.$$

This finally yields the closed formula

$$d! [z^d] (\exp(z)-z)^n.$$

Writing this with Stirling numbers we get

$$d! [z^d] (\exp(z)-1+1-z)^n = d! [z^d] \sum_{p=0}^n {n\choose p} (\exp(z)-1)^p (1-z)^{n-p} \\ = d! \sum_{p=0}^n {n\choose p} \sum_{q=0}^d [z^q] (\exp(z)-1)^p [z^{d-q}] (1-z)^{n-p} \\ = d! \sum_{p=0}^n {n\choose p} \sum_{q=0}^d \frac{p!}{q!} {q\brace n} (-1)^{d-q} {n-p\choose d-q}.$$

Solution 4:

After applying the generating function idea that @MarkusScheuer gave in his answer.We can get the addition formula of $P(n+m,d)$

$$A_{n}(x)=\sum_{d=0}^\infty P(n,d)\frac{x^d}{d!}$$

$$A_{n+1}(x)=(e^x-x)A_{n}(x)$$

$$A_{1}(x)=(e^x-x)$$

$$A_{n}(x)=(e^x-x)^n$$

$$(e^x-x)^n=\sum_{d=0}^\infty P(n,d)\frac{x^d}{d!}$$

We can easily get the relation from that generation function some important properties.

$$(e^x-x)^n.(e^x-x)^m=(e^x-x)^{n+m}$$ $$A_{n}(x).A_{m}(x)=A_{n+m}(x)$$

$$A_{n}(x)=\sum_{d=0}^\infty P(n,d)\frac{x^d}{d!}$$

$$\sum_{d=0}^\infty P(n,d)\frac{x^d}{d!}.\sum_{d=0}^\infty P(m,d)\frac{x^d}{d!}=\sum_{d=0}^\infty P(n+m,d)\frac{x^d}{d!}$$

$$P(n+m,d)=\sum_{k=0}^d {d\choose k} P(n,d-k)P(m,k)=\sum_{k=0}^d {d\choose k} P(m,d-k)P(n,k)$$

If we select $m=1$ , The recurrence formula that Christian Blatter wrote in his answer can be gotten.

$$P(n+1,d)=\sum_{k=0}^d {d\choose k} P(n,d-k)P(1,k)$$

$$P(1,0)=1$$ $$P(1,1)=0$$ $$P(1,j)=1$$ $$j\geq2$$ $$P(n+1,d)=P(n,d)+\sum_{k=2}^d {d\choose k} P(n,d-k)$$ $$d\geq2$$

After getting the generating function we can get $P(n,d)$ via the same method that shown by Markus Scheuer in his answer. $$A_{n}(x)=\sum_{d=0}^\infty P(n,d)\frac{x^d}{d!}$$

$$P(n,d)=d![x^d]\left(e^x-x\right)^n$$ $$=d![x^d]\sum_{k=0}^n\binom{n}{k}e^{kx}(-x)^{n-k}$$ $$=d!\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}[x^d]x^{n-k}e^{kx}$$ $$=d!\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}[x^d]\sum_{j=0}^\infty\frac{k^jx^{n-k+j}}{j!}$$ $$=\sum_{k=0}^n(-1)^{n-k}\frac{d!}{(d+k-n)!}\binom{n}{k}k^{d+k-n}$$

$$P(n,d)=n! d! \sum_{k=0}^n(-1)^{n-k}\frac{k^{d+k-n}}{(d+k-n)!(n-k)!k!}$$

or it can be written in opposite order after $m=n-k$ varible changing

$$P(n,d)=n! d! \sum_{m=0}^n(-1)^{m}\frac{(n-m)^{d-m}}{(d-m)!(n-m)!m!}$$

We can also write :

$$P(n,d)= \sum_{k=0}^n(-1)^{k}\frac{d!}{(d-k)!}\binom{n}{k}(n-k)^{d-k} \tag{1}$$

THE PROOF of MY CONJECTURE:

Part 1: The case ($d \geq n$))

$$n^{d}\equiv P(n,d) \pmod {d}$$

Proof: If we expand the $P(n,d)$ terms from $(1)$

$$P(n,d)= n^d-dn(n-1)^{d-1}+d(d-1)\binom{n}{2}(n-2)^{d-2}-.......+(-1)^{n-1} \frac{d!}{(d-(n-1))!} \binom{n}{n-1} 1^{d-1}$$

$$P(n,d)= n^d-dn(n-1)^{d-1}+d(d-1)\binom{n}{2}(n-2)^{d-2}-.......+(-1)^{n-1} d (d-1)...(d+1-(n-1)) n$$

As we can see all terms except $n^d$ has $d$ and also we know that binom series numbers are always integers.

Thus $$P(n,d) \equiv \sum_{k=0}^n(-1)^{k}\frac{d!}{(d-k)!}\binom{n}{k}(n-k)^{d-k} \pmod {d}$$

$$P(n,d) \equiv n^d \pmod {d}$$ The conjecture is proved for the case $d \geq n$ $$n^d \equiv P(n,d) \pmod {d}$$

Part 2: The case ($d < n$))

$$n^{d}\equiv P(n,d) \pmod {d}$$

Proof:

if $d<k$ and $d,k$ are non-negative integers

$$\cfrac{d!}{(d-k)!}=0 \tag{2}$$

Reference wiki link for (2)

If we expand the $P(n,d)$ terms in that case from $(1)$

$$P(n,d)= n^d-dn(n-1)^{d-1}+d(d-1)\binom{n}{2}(n-2)^{d-2}-.......+(-1)^{n-d} d! \binom{n}{d} (n-d)^{d-d}$$

$$P(n,d)= n^d-dn(n-1)^{d-1}+d(d-1)\binom{n}{2}(n-2)^{d-2}-.......+(-1)^{n-d} d! \binom{n}{d}$$

As we can see all terms except $n^d$ has $d$ and also we know that binom series numbers are always integers.

Thus $$P(n,d) \equiv \sum_{k=0}^n(-1)^{k}\frac{d!}{(d-k)!}\binom{n}{k}(n-k)^{d-k} \pmod {d}$$

$$P(n,d) \equiv n^d \pmod {d}$$

The conjecture is also proved for the case $d <n$
$$n^d \equiv P(n,d) \pmod {d}$$

The proof is completed.

Thanks a lot to Christian Blatter and Markus Scheuer for their contributions and answers.