18
$\begingroup$

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

I would like to find the function $P(n,d)$:

$P(n,d)$ where $n$ is base, $d$ is digit; Some examples: $n=3$ , $d=3$;

$$(000)_3$$ $$(111)_3$$ $$(222)_3$$

$P(3,3)=3$


It is easy that we can generalize for 3 digit numbers that $P(n,3)=n$

$P(3,4)=3.\cfrac{4!}{4!}+\cfrac{3.2}{2!}.\cfrac{4!}{(2!)^2}=21$

  • $(0000)_3 , (1111)_3$ two examples for $3.\cfrac{4!}{4!}$
  • $(0011)_3 ,(1212)_3$ two examples for $\cfrac{3.2}{2!}.\cfrac{4!}{(2!)^2}$

$P(4,4)=4.\cfrac{4!}{4!}+\cfrac{4.3}{2!}\cfrac{4!}{2!.2!}=40$

  • $(0000)_4, (1111)_4$ two examples in $4.\cfrac{4!}{4!}$
  • $(0011)_4 ,(3232)_4 $ two examples in $\cfrac{4.3}{2!}\cfrac{4!}{2!.2!}$

$P(3,5)=3.\cfrac{5!}{5!}+3.2\cfrac{5!}{3!.2!}=63$

  • $(00000)_3 ,(22222)_3$ two examples in $3.\cfrac{5!}{5!}$
  • $(00110)_3 ,(02020)_3 $ two examples in $3.2\cfrac{5!}{3!.2!}$

$P(3,6)=3.\cfrac{6!}{6!}+\cfrac{3.2}{2!}\cfrac{6!}{3!.3!}+(3.2)\cfrac{6!}{2!.4!}+\cfrac{3.2.1}{3!}\cfrac{6!}{2!.2!.2!}=243$

  • $(000000)_3 , (222222)_3$ two examples in $3.\cfrac{6!}{6!}$
  • $(001101)_3 , (020220)_3$ two examples in $\cfrac{3.2}{2!}\cfrac{6!}{3!.3!}$
  • $(002200)_3 , (111122)_3$ two examples in $(3.2)\cfrac{6!}{2!.4!}$
  • $(112200)_3 , (102021)_3$ two examples in $\cfrac{3.2.1}{3!}\cfrac{6!}{2!.2!.2!}$

Thanks for helps

EDIT: (2/21/2016)

I have noticed my mistakes in my formulas above and I corrected . Thanks a lot for answers.

During my research on $P(n,d)$ , I got a conjecture. Thus the question has been going into very interesting points. (I do not know if it is known conjecture or not? Please let me know if you heard it. If it is true, this can let us to generalize The Fermat's Little theorem for any positive number. )

Fermat's little theorem: $n^{p}\equiv n \pmod {p}$ where $p$ is prime number; $n$ is positive integer and $\gcd(n,p)=1$.

My conjecture:

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

where $d$ and $n$ are any positive integers.

The conjecture is true for the (7X7) table that @Markus Scheuer gave in his answer. All values in the table were tested with success. I need your contribution to test my conjecture for large numbers. I have not found any counter-example to disprove my conjecture yet.

Note that I have the conjecture without proof. How can the conjecture be proven?

I would like to share some my results for $P(n,d)$ . Please let me know if any fault in my formulas below.

$$P(n,1)=0$$

$$P(n,2)=n$$

$$P(n,3)=n$$

$$P(n,4)=n+\cfrac{n(n-1)}{2!}\cfrac{4!}{2!2!}=3n^2-2n$$

$$P(n,5)=n+\cfrac{n(n-1)}{1!}\cfrac{5!}{2!3!}=10n^2-9n$$

$$P(n,6)=n+\cfrac{n(n-1)}{2!}\cfrac{6!}{3!3!}+\cfrac{n(n-1)}{1!}\cfrac{6!}{4!2!}+\cfrac{n(n-1)(n-2)}{3!}\cfrac{6!}{2!2!2!}$$

$$P(n,6)=n+25n(n-1)+15n(n-1)(n-2)=15n^3-20n^2+6n$$

$$P(n,7)=n+\cfrac{n(n-1)}{1!}\cfrac{7!}{4!3!}+\cfrac{n(n-1)}{1!}\cfrac{7!}{2!5!}+\cfrac{n(n-1)(n-2)}{2!}\cfrac{7!}{3!2!2!}$$

$$P(n,7)=n+56n(n-1)+105n(n-1)(n-2)$$

Note that those formulas above satisfy the $(7x7)$ (n/d) table that @Markus Scheuer gave in his answer.

We can write more terms if we want.

$$P(n,8)=n+\cfrac{n(n-1)}{1!}\cfrac{8!}{2!6!}+\cfrac{n(n-1)}{1!}\cfrac{8!}{3!5!} +\cfrac{n(n-1)}{2!}\cfrac{8!}{4!4!}+\cfrac{n(n-1)(n-2)}{2!}\cfrac{8!}{2!2!4!}+\cfrac{n(n-1)(n-2)}{2!}\cfrac{8!}{2!3!3!}+\cfrac{n(n-1)(n-2)(n-3)}{4!}\cfrac{8!}{2!2!2!2!}$$

..

..

$$P(n,d)=n+\cfrac{n(n-1)}{1!}\cfrac{d!}{2!(d-2)!}+\cfrac{n(n-1)}{1!}\cfrac{d!}{3!(d-3)!} +\cfrac{n(n-1)}{1!}\cfrac{d!}{4!(d-4)!}+.....$$


$$n^{d}\equiv P(n,d) \pmod {d}$$ If we put the results on above in my conjecture , we can get:

$$n^{2}\equiv n \pmod {2}$$ $$n^{3}\equiv n \pmod {3}$$ $$n^{4}\equiv 3n^2-2n \pmod {4}$$ $$n^{5}\equiv 10n^2-9n\pmod {5}\equiv -9n\pmod {5}\equiv n\pmod {5}$$ $$n^{6}\equiv 15n^3-20n^2+6n \pmod {6} \equiv 3n^3-2n^2 \pmod {6}$$ $$n^{7}\equiv n+56n(n-1)+105n(n-1)(n-2) \pmod {7}\equiv n \pmod {7}$$ $$n^{8}\equiv n^2(n-2)^2 \pmod {8}$$

EDIT: (2/22/2016)

An observation:

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

$$(n+1)^{d}\equiv \sum_{k=0}^{d}{d\choose k}\>n^k \pmod {d}$$

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

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

Because of ${d\choose d-1}=d$

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

This result is very similar result with the recursion formula of @Christian Blatter wrote in his answer.

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

EDIT

I have tested my conjecture with big numbers.

According to the table in sequence A231797 (Thanks a lot to @MarkusScheuer for the link)

There is an output for big numbers Table of n, a(n) for n = 0..410 . I tested for $n=d=410$

$P(410,410)$ is 990 digits integer, you can see in the table that I gave in the link above.

I confirmed in an online calculator that my conjecture is still true for that big number.

$$410^{410}\equiv 0 \pmod {410}$$

$$P(410,410)\equiv 0 \pmod {410}$$

$$410^{410}\equiv P(410,410) \pmod {410}$$

Note: I have not tested my conjecture with big numbers for the case that $d \neq n$ . I do not know a generating function for the case $d \neq n$ as we have for $d=n$ as Markus Scheuer informed in his answer. Any idea for generating function for $d \neq n$?

Generating function for $d = n$

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

Thanks for helps and contributions

EDIT (26/2/2016): I have posted a proof for my conjecture above. You can find it below as an answer. Please feel free to write comments on it.

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

where $d$ and $n$ are any positive integers.

Many special thanks to @ChristianBlatter and @MarkusScheuer for their contributions to prove it. Especially Christian Blatter's recurrence formula for $P(n,d)$ is the key to prove the conjecture. Thanks a lot for sharing his idea with us.

I have not found a related link for that theorem in the internet. Could you please share reference books or links if you know it?

Thanks a lot for your helps

$\endgroup$
6
  • $\begingroup$ +1 for an interesting question and the work already put in. $\endgroup$
    – Shailesh
    Feb 19, 2016 at 14:08
  • $\begingroup$ @Mathlover: I've added some aspects around the diagonals $P(n+m,n)$. $\endgroup$ Feb 22, 2016 at 22:54
  • $\begingroup$ @Mathlover: Very nice! I see my answer is helpful and you derive from it some new observations! :-) $\endgroup$ Feb 23, 2016 at 10:43
  • $\begingroup$ @MarkusScheuer : Thank you a lot for your answer. It gave me a great point how to find the general formula of $P(n,d)$. Now I am testing it for some values. Best Regards $\endgroup$
    – Mathlover
    Feb 23, 2016 at 10:49
  • 1
    $\begingroup$ @MarkusScheuer Thank you for your advice and help . I added an answer that shows the proof of my conjecture. Please advice if there is a mistake in it. Best Regards $\endgroup$
    – Mathlover
    Feb 23, 2016 at 15:03

4 Answers 4

6
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Thanks a lot for answer . I edited my question with wonderful discover for $P(n,d)$. Could you please share your comments on my last edit? $\endgroup$
    – Mathlover
    Feb 21, 2016 at 20:33
  • $\begingroup$ Your answer is great. Have you read my conjecture : $n^{d}\equiv P(n,d) \pmod {d}$ , I have not found any counter-example yet. It satisfies for any number in your table but I do not know how to prove it .Thanks for helps. $\endgroup$
    – Mathlover
    Feb 21, 2016 at 20:50
  • $\begingroup$ @MarkusScheuner : I believe that $P(n,d)$ function can be a key function to detect prime numbers. It has wonderful features $\endgroup$
    – Mathlover
    Feb 21, 2016 at 20:52
  • $\begingroup$ @Mathlover: Congratulation to your new discoveries!:-) I will have a look at them soon. Best regards, $\endgroup$ Feb 21, 2016 at 21:28
  • $\begingroup$ @MarkusScheuner : Wonderful relations . Please check the relation while applying the recurrence relation in (4) . I think it should be $$\sum_{d=0}^\infty (P(n+1,d)+d.P(n,d-1))\frac{x^d}{d!}\\$$. then we can get $$A_{n+1}(x)=(e^x-x)A_{n}(x)$$ $\endgroup$
    – Mathlover
    Feb 23, 2016 at 8:32
5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ :Thanks a lot for answer . I edited my question with wonderful discover for $P(n,d)$. Could you please share your comments on my last edit? $\endgroup$
    – Mathlover
    Feb 21, 2016 at 20:37
  • $\begingroup$ @ChristianBlatter: Dear Professor! Many thanks for contributing this recurrence relation. It was source and inspiration for us to dig deeper into this example and to find some nice relations. ... and congratulation to the +100k ! :-) $\endgroup$ Feb 23, 2016 at 21:40
3
$\begingroup$

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}.$$

$\endgroup$
1
  • $\begingroup$ Nice approach, Marko! Many thanks! (+1) $\endgroup$ Feb 24, 2016 at 5:49
2
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Your proof is sound. A very nice relationship, congrats! I've updated and corrected my answer. Many thanks for your hints! I've also added some reflections which might be useful for you. It's a kind of bonus for the nice collaboration. :-) $\endgroup$ Feb 23, 2016 at 21:36
  • $\begingroup$ @MarkusScheuer I posted a proof where my object was to keep it simple. $\endgroup$ Feb 23, 2016 at 22:57
  • $\begingroup$ @MarkusScheuner Your last bonus opens a huge mysterical door for new research field. I have been searching the internet for $$ n^d \equiv P(n,d) \pmod {d}$$ but I have not found the theory. Have you found a related work in somewhere ? Best Regards $\endgroup$
    – Mathlover
    Feb 25, 2016 at 9:15
  • $\begingroup$ @Mathlover: It's not quite clear to me what information you are looking for. Maybe you want to clarify it or provide some details. Btw. please be careful to correctly write the user names, otherwise the user will not receive any notification. $\endgroup$ Feb 25, 2016 at 22:05
  • $\begingroup$ @MarkusScheuer: I have not found any book or link that shows that relation $n^{d}\equiv P(n,d) \pmod {d}$. I just wondered if you found any link about it. Please share if you found a link. Best Regards $\endgroup$
    – Mathlover
    Feb 26, 2016 at 7:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .