Ivan Shishkin, Rye (1878)

Discussions

Inversion de Pascal

0 messages

Back to problem

Solution

Solution by Darius CHITU · FR

  1. Soit ϕ∈End(R[X])\phi \in \text{End}(\mathbb{R}[X]) tel que ϕ(P)(X)=P(X−1)\phi(P)(X)=P(X-1) pour tout P∈R[X]P \in \R[X]. Comme (φ∘ϕ)(P)(X)=P(X)(\varphi \circ \phi)(P)(X)= P(X) et aussi (ϕ∘φ)(P)(X)=P(X)(\phi \circ \varphi)(P)(X) = P(X) pour tout P∈R[X]P \in \R[X], on déduit que φ\varphi est bijectif et que φ−1=ϕ\varphi^{-1} = \phi.
  2. En remarquant que φ(Xj)=(X+1)j=∑0⩽i⩽jCjiXi\varphi(X^{j}) = (X+1)^j = \sum_{0 \leqslant i \leqslant j} C_{j}^{i} X^{i} pour tout j∈Nj \in \mathbb{N}, la matrice de l’endomorphisme φ\varphi dans la base canonique B=(1,X,X2,…)\mathcal{B}=(1,X,X^{2},\ldots) satisfait la relation suivante :
    ∀i,j∈N: (Mφ,B)i,j={Cji si i⩽j0 si i>j,\forall i,j \in \N: \ \left( M_{\varphi, \mathcal{B}} \right)_{i,j} = \begin{cases} C_{j}^{i} &\text{ si } i \leqslant j \\ 0 &\text{ si } i > j \end{cases},ce qui montre que la matrice inversible Mφ,BM_{\varphi,\mathcal{B}} est triangulaire supérieure.
  3. On rappelle que Mφ,B−1=Mφ−1,BM_{\varphi,\mathcal{B}}^{-1} = M_{\varphi^{-1}, \mathcal{B}}. Car φ−1(Xj)=(X−1)j=∑0⩽i⩽j(−1)j−iCjiXi\varphi^{-1} (X^{j}) = (X-1)^{j} = \sum_{0 \leqslant i \leqslant j} (-1)^{j-i} C_j^{i} X^{i} pour tout j∈Nj \in \N, on peut écrire de la même manière que la matrice de φ−1\varphi^{-1} dans la base canonique B\mathcal{B} satisfait cette relation :
    ∀i,j∈N: (Mφ,B−1)i,j=(Mφ−1,B)i,j={(−1)j−iCji si i⩽j0 si i>j.\forall i,j \in \N: \ \left( M_{\varphi,\mathcal{B}}^{{-1}} \right)_{i,j}=\left( M_{\varphi^{-1}, \mathcal{B}} \right)_{i,j} = \begin{cases} (-1)^{j-i}C_{j}^{i} &\text{ si } i \leqslant j \\ 0 &\text{ si } i > j \end{cases}.
  4. La relation exprimée dans l’énoncé s’écrit avec les vecteurs ligne va=(a0,a1,a2,…){v}_{a}=(a_{0},a_{1}, a_{2}, \ldots) et vb=(b0,b1,b2,…)v_{b} = (b_{0}, b_{1}, b_{2},\ldots) comme vb=va⋅Mφ,Bv_{b} = v_{a} \cdot M_{\varphi,\mathcal{B}}. En multipliant à droite par l’inverse de la matrice, on a va=vb⋅Mφ,B−1v_{a} = v_{b} \cdot M_{\varphi,\mathcal{B}}^{-1}, ce qui implique évidemment la formule d’inversion de Pascal:
    ∀n∈N: an=∑k=0n(Mφ,B−1)k,nbk=∑k=0n(−1)n−kCnkbk.\forall n \in \N: \ a_{n} = \sum_{k=0}^{n} \left( M_{\varphi,\mathcal{B}}^{{-1}} \right)_{k,n} b_{k} = \sum_{k=0}^{n} (-1)^{n-k} C_{n}^{k} b_{k}.
  5. On comptera le nombre de permutations de taille nn de deux façons. Premièrement, leur nombre est ∣Sn∣=n!|\mathcal{S}_{n}| =n!. Deuxièmement, le nombre de permutations de taille nn est la somme des permutations de taille nn avec n−kn-k points fixes, où k∈⟦0,n⟧k \in \llbracket 0,n \rrbracket. Pour ce type de permutations, on choisit d’abord les positions de ces points fixes, pour lesquelles on a Cnn−k=CnkC_{n}^{n-k} = C_{n}^{k} possibilités, et ensuite on peut permuter les kk positions restantes, action pour laquelle on a dkd_{k} possibilités. Enfin, le nombre de permutations de taille nn est ∣Sn∣=∑0⩽k⩽nCnkdk|\mathcal{S}_n| = \sum_{0 \leqslant k \leqslant n} C_{n}^{k} d_{k}.
    Ainsi, n!=∑0⩽k⩽nCnkdkn! = \sum_{0 \leqslant k \leqslant n} C_{n}^{k} d_{k} et, par la formule d’inversion de Pascal, on arrive à la conclusion:
    dn=∑k=0n(−1)n−kCnkk!=∑k=0n(−1)kCnn−k(n−k)!=n!∑k=0n(−1)kk!.d_{n} = \sum_{k=0}^{n} (-1)^{n-k} C_{n}^{k} k! = \sum_{k=0}^{n} (-1)^{k} C_{n}^{n-k} (n-k)! = n! \sum_{k=0}^{n} \frac{(-1)^{k}}{k!}.

No messages yet.