6
$\begingroup$

Let

  • $a(n)$ be A375540, i.e., an integer sequence such that $$ a(n) = 2^n n! [x^n] (1/2 - \exp(-x))^n. $$
  • Start with vector $\nu$ of fixed length $m$ with elements $\nu_i = 1$ (that is, $\nu = \{1,1,\dotsc,1\}$), set $t := \nu$ and for $i$ from $1$ to $m-1$, for $j$ from $i$ to $1$ (with decreasing step equals $1$) apply $\nu_j := i(\nu_j + \nu_{j+1})$ and $t_{i+1} := \nu_1$ (after ending each cycle for $j$).

I conjecture that after the whole transform we have $a(n) = t_{n+1}$.

Note that here $m$ is any natural number. In other words, if you need to compute $n$ first terms of $a(n)$ starting from $a(0)$ up to $a(n-1)$ just set $m = n$. Obviously, $t$ is a vector, so $t_i$ is the $i$-th element of it.

Here is the PARI/GP program to check it numerically:

a(n) = 2^n*n!*polcoeff((1/2 - exp(-x+x*O(x^n)))^n, n, x)
upto(n) = {my(v, t); 
v = vector(n, i, 1); 
t = v; 
for(i=1, n-1, 
forstep(j=i, 1, -1, 
v[j] = i*(v[j] + v[j+1])); 
t[i+1] = v[1]); 
t}
test(n) = vector(n, i, a(i-1)) == upto(n)

For example, here is the PARI/GP output for $n=5$ where we print vectors [v, t] after ending each cycle for i:

[[2, 1, 1, 1, 1], [1, 2, 1, 1, 1]]
[[12, 4, 1, 1, 1], [1, 2, 12, 1, 1]]
[[126, 30, 6, 1, 1], [1, 2, 12, 126, 1]]
[[1880, 344, 56, 8, 1], [1, 2, 12, 126, 1880]]

UPD1: changing $\nu_i = 1$ to $\nu_i = x^i$ leads to another conjecture: $$ a(n) = \sum\limits_{i=0}^{n} \binom{n}{i} \sum\limits_{j=0}^{i} \binom{i}{j} (n-j)^n (-1)^j = \sum\limits_{k=0}^{n} \binom{n}{k} k^n 2^k (-1)^{n-k}. $$

Here is the PARI/GP program to check it numerically:

a(n) = 2^n*n!*polcoeff((1/2 - exp(-x+x*O(x^n)))^n, n, x)
b(n) = my(v1); v1 = Vec((2-x)^n); sum(i=0, n, i^n*v1[i+1])
test(n) = a(n) == b(n)

Is there a way to prove it?

$\endgroup$
9
  • 1
    $\begingroup$ What is $m$? Is $t_i$ a number or a sequence? It would be easier to understand if you could provide an example. $\endgroup$ Commented Jul 29 at 20:11
  • 1
    $\begingroup$ Did you use different letters in the description and in the code just to confuse the reader? Or there is another reason? $\endgroup$ Commented Jul 30 at 0:15
  • 2
    $\begingroup$ Observations: $a(n)$ is the number of pairs $(f,g)$ where $f:[n]\to[n]$ and $g:\operatorname{range}(f)\to[2]$. That is, $a(n)$ is the number of ways to send $n$ children to $n$ schools and choose, for each selected school, whether to provide a bus. Also, $[x^n] (\frac12 - e^{-x})^n=[x^n] (-\frac12 + e^x)^n$ by parity considerations. (The number of schools to which an even number of children are assigned is always even.) $\endgroup$ Commented Jul 30 at 23:38
  • 1
    $\begingroup$ How did you come up with the algorithm? Do you have an idea for a combinatorial interpretation of the elements of $v$? $\endgroup$ Commented Jul 30 at 23:47
  • 1
    $\begingroup$ I've convinced myself that your algorithm computes $b(n)=c(n,n)$ where $c(n,k)$ is the number of pairs $(f,g)$ with $f:[k]\to[n]$ and $g:\operatorname{range}(f)\to[2]$. The step $c(n,k+1)=n(c(n,k)+c(n-1,k))$ comes from choosing a school for the new child and accounting for cases where the chosen school is new so you need to decide about the bus. $\endgroup$ Commented Jul 31 at 12:02

1 Answer 1

Reset to default
2
$\begingroup$

Note that $a_n$ can also be written as:

$$ a_n = n! [x^n] (2e^x - 1)^n. $$

Next, we analyze OP's algorithm and obtain an equivalent formulation. Indeed, define $(c_{i,j})_{0 \leq j \leq i}$ recursively by

$$ c_{i,j} = \begin{cases} 1, & \text{if $j = 0$}, \\ 0, & \text{if $j \geq 1$ and $i = 0$}, \\ i (c_{i-1,j-1} + c_{i,j-1}), & \text{if $j \geq 1$ and $i \geq 1$}. \end{cases} $$

Lemma. Let $\nu$ be the vector in OP's algorithm with infinite length. (i.e., $m = \infty$.) Then, after the $i$th step of the outer loop has been completed, we have

$$ \nu_j = c_{i,i+1-j} \tag{1}\label{e:equiv} $$

for all $i \in \mathbb{N}_0$ and $j \in \{1, \ldots, i+1\}$.

Proof. The base case $i = 0$ corresponds to the initial condition, hence, we have $\nu_1 = 1 = c_{0,0}$ and the claim holds true in this case.

Next, let $i \geq 1$ and assume that the claim holds true for $i-1$. This inductive hypothesis tells that, just before the step $i$ starts, we have $\nu_j = c_{i-1,i-j}$ for $j \in \{1, \ldots, i\}$. Consequently, the inner loop at step $i$ can be recast as: $$ \nu_j = i (c_{i-1,i-j} + \nu_{j+1}), \qquad \nu_{i+1} = 1 = c_{i, 0}.$$ It is easy to check that this in turn implies $\eqref{e:equiv}$, completing the inductive step.

Therefore the claim holds for all $i$ by the principle of mathematical induction.

In particular, this shows that $t_{i+1} = c_{i,i}$. Now we prove:

Theorem. For any $n \geq 1$, we have

$$ (2e^x - 1)^n = \sum_{j=0}^{\infty} \frac{c_{n,j}}{j!} x^j. \tag{2}\label{e:gen} $$

The upshot of this theorem is that

$$ t_{n+1} = c_{n,n} = n![x^n](2e^x - 1)^n = a_n, $$

confirming OP's observation. So, let us turn to proving the theorem.

Proof of Theorem. When $n = 0$, both sides of $\eqref{e:gen}$ are $1$ and the claim holds true.

Let $n \geq 1$ and assume that the claim holds for $n - 1$. Write $f_n(x) = \sum_{j=0}^{\infty} \frac{c_{n,j}}{j!} x^j$ for simplicity. Then

$$\begin{align*} f_n'(x) &= \sum_{j=0}^{\infty} \frac{c_{n,j+1}}{j!} x^j \\ &= \sum_{j=0}^{\infty} \frac{n(c_{n-1,j} + c_{n,j})}{j!} x^j \\ &= n(f_{n-1}(x) + f_n(x)). \end{align*}$$

Applying the inductive hypothesis, we obtain the following differential equation:

$$ f_n'(x) - nf_n(x) = n (2e^x - 1)^{n-1}, \qquad f_n(0) = 1. $$

Solving this equation yields

$$ f_n(x) = (2e^x - 1)^n $$

and hence the inductive step holds true, proving the desired theorem. $\square$

$\endgroup$
1
  • $\begingroup$ Could you please also look at my newest similar question? $\endgroup$ Commented Aug 1 at 13:36

You must log in to answer this question.