Nombre de surjections linéaires
Bonjour,
pour dénombrer le nombre de surjections de deux ensembles de cardinaux finis, on peut utiliser la formule du crible.
Cependant, comment faire pour dénombrer le nombre de surjections linéaires d'un K-espace vectoriel E de dimension finie n, vers un K-espace vectoriel F, de dimension finie m, sachant que K est un corps fini à p éléments ?
Quel serait ce nombre ?
En résumé : dimE = n, dimF = m et Card K = p et n $\geq$ m.
Par avance, merci.
pour dénombrer le nombre de surjections de deux ensembles de cardinaux finis, on peut utiliser la formule du crible.
Cependant, comment faire pour dénombrer le nombre de surjections linéaires d'un K-espace vectoriel E de dimension finie n, vers un K-espace vectoriel F, de dimension finie m, sachant que K est un corps fini à p éléments ?
Quel serait ce nombre ?
En résumé : dimE = n, dimF = m et Card K = p et n $\geq$ m.
Par avance, merci.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Un résultat plus général figure dans la proposition 3.1 de l'article de D. Laksov & A. Thorup (Counting matrices with coordinates in finite fields and of fixed rank) https://www.mscand.dk/article/view/12477
Fixons une base de $E$. L'ensemble des applications linéaires $E\to F$ est alors en bijection avec l'ensemble des images possibles de la base fixée. Donc le nombre de surjections linéaires $E\to F$ est égal au nombre de familles génératrices ordonnées de $F$ à $n=\dim E$ éléments.
Édit : Mais je n'ai pas réfléchi au dénombrement de ces familles génératrices. Je ne sais pas si ça se fait bien. Là, c'est l'heure du film à la télé.
On compte ne nombre de noyaux possibles de nos surjections linéaires (1) et pour chaque noyau possible on prend un supplémentaire $S$ et on compte le nombre d'isomorphismes $S\to F$ (2). Le résultat est (1) $\times$ (2). Pour ça on a d'abord besoin de calculer le nombre de familles libres d'un cardinal donné dans un K-ev de dimension donnée puis le nombre d'injections d'une K-ev de dimension finie dans un autre. Avec ces dénombrements préliminaires, on peut calculer (1) et (2).
Mais peut-être que c'est fait dans le document donné par Claude. En tout cas, c'est un problème intéressant !
$$
Q_r(X) = (X-1) (X - q) \cdots (X - q^{r-1})
$$En ce qui concerne les surjections (linéaires) $K^n \twoheadrightarrow K^m$ (où $K$ est fini de cardinal $q$), il faut faire $t = n$ et $r = m$, ce qui donne
$$
\fbox {$Q_m(q^n)$ surjections linéaires $K^n \twoheadrightarrow K^m$ ($\#K = q$)}
$$Moi, étant retraité, je n'ai pas le temps de m'amuser, c'est bien connu. Histoire de participer j'ai fait $m=1$, ce qui donne $q^n-1$ formes linéaires surjectives $K^n \twoheadrightarrow K$. Pas mal, non ? Ensuite, j'ai fait $m=2$ et j'ai trouvé (si, si) $(q^n - 1)(q^n - q)$ surjections linéaires $K^n \twoheadrightarrow K^2$.
Le papier pointé contient beaucoup d'autres résultats, en particulier certains liés au $q$-coefficient binomial
$$
\Binom{t}{r}_q = {(q^t - 1) (q^{t-1} - 1) \cdots (q^{t-r+1} - 1) \over (q^r - 1)(q^{r-1} - 1) \cdots (q - 1)}
$$Le papier pointé de Laksov & Thorup date de 1994 et le Landsberg cité de 1893 (si j'en crois les auteurs).
Bon courage.
@Calli : pourrais-tu m'expliquer ta démarche heuristique s'il te plait ? C'est-à-dire comment as-tu fait pour avoir ces idées ?
Car je ne savais pas par quel bout commencer.
Je suis très admiratif.
Je ne suis pas Calli mais je réponds quand même.
$\bullet$ En ce qui concerne le nombre $(q^n-1)(q^n -q)$ trouvé pour le nombre de surjections linéaires $K^n \twoheadrightarrow K^2$. Par transposée, c'est le nombre d'injections (linéaires) $K^2 \hookrightarrow K^n$ c.a.d. le nombre de couples $(x,y) \in K^n \times K^n$ linéairement indépendants. Ou encore, le nombre de couples $(x,y)$ avec $x \in K^n \setminus \{0\}$ et $y \in K^n \setminus K.x$ : $q^n -1$ choix pour $x$, $q^n - q$ choix pour $y$. D'où le $(q^n -1)(q^n - q)$.
$\bullet$ Ensuite, pour le nombre de surjections linéaires $K^n \twoheadrightarrow K^3$, pareil. Par transposée, c'est le nombre d'injections (linéaires) $K^3 \hookrightarrow K^n$ c.a.d. le nombre de triplets $(x,y,z) \in K^n \times K^n \times K^n$ linéairement indépendants. Ou encore, le nombre de triplets $(x,y,z)$ avec
$$
x \in K^n \setminus \{0\}, \quad y \in K^n \setminus K.x, \quad z \in K^n \setminus (K.x \oplus K.y)
$$Bilan : $q^n -1$ choix pour $x$, $q^n - q$ choix pour $y$, $q^n - q^2$ choix pour $z$. Donc en tout $(q^n -1)(q^n - q)(q^n - q^2)$ triplets $(x,y,z) \in K^n \times K^n \times K^n$ linéairement indépendants.
$\bullet$ And so on pour le nombre de surjections linéaires $K^n \twoheadrightarrow K^m$ avec $m \le n$.
A vrai dire, la partie dénombrement ne me pose pas de problème. C'est la partie qui mène à ce dénombrement.
Notamment d'introduire la notion de supplémentaire et de réfléchir spécifiquement avec des noyaux.
Quel construction et cheminement mental se cache derrière cela ?
Car d'abord @Calli est parti sur une piste (en parlant de famille génératrice), puis est parti sur une autre idée.
Là je ne peux pas répondre à la place de Calli sur sa méthode. De mon côté, je n'ai pas parlé ni de noyaux ni de supplémentaires mais de transposées. Pour de vrai, comme j'ai dit, j'ai commencé par traiter le cas $m=1$ puis $m=2$. Et ensuite ...
Oui, oh c'est juste le nombre de formes linéaires non nulles. 8-)(:P)
Pour les surjections ($r=m$) on tombe sur la formule plus simple $Q_m(q^n)$, comme tu l'as dis Claude. C'est égal au nombre d'injection dans l'autre sens $F\hookrightarrow E$, donc il y avait forcément une bonne raison à ça, mais je ne l'ai pas trouvée. C'est toi qui me l'a donnée avec la transposée, donc merci.
J'avais déjà dénombré une fois ${\rm GL}_n(K)$ en mettant en bijection les automorphismes de $K^n$ avec les bases de $K^n$ (à un automorphisme, on associe l'image d'une base fixée). Ici, j'ai voulu faire pareil. J'ai cru que les familles génératrices à $n$ éléments seraient faciles à dénombrer, mais en fait pas tellement (en tout cas je n'avais pas d'idée). Donc j'ai cherché une autre description des éléments de ${\rm Hom}_K(E,F)$. La combinatoire, c'est faire des bijections (disons-le comme un slogan, avec les exagérations que peut contenir un slogan) et régulièrement dans le but de trouver une description alternative, plus simple, des objets qu'on veut dénombrer (cf. les nombres de Catalan). En l'occurence une application linéaire, ç'a en gros deux morceaux : le noyau sur lequel elle est nulle et le reste (rigoureusement, un supplémentaire du noyau) sur lequel elle n'est pas nulle (rigoureusement, elle est injective). Je savais déjà dénombrer les applications linéaires injectives comme je l'ai dit, et pour dénombrer les sev il n'y a qu'un pas de plus à franchir, donc banco.
En guise de modeste cadeau pour le travail de Calli : le polynôme $\Binom{n}{d}_q$ pour $n=7$ et $0 \le d \le n$. La colonne de gauche, c'est $d$, ensuite le $q$-polynôme binomial en question et enfin le coefficient binomial $\binom{n}{d}$ habituel que l'on obtient en faisant $q = 1$ dans $\Binom{n}{d}_q$. J'attache la définition de $\Binom{n}{d}_q$ en fonction de la $q$-factorielle. Il faut juste se convaincre que le quotient est un polynôme en $q$.
Je crois me souvenir de l'existence d'un fil (il y a un certain temps) où l'on essayait de compter le nombre de points sur $\F_q$ d'une variété torique : il me semble que c'est un polynôme en $q$.
Le titre du fil c'est $q$-polynôme (y'a peut être un " s ") !
Ok, pour le titre $q$-polynôme(s). Je ne sais plus ce que l'on avait fabriqué dans ce fil. Je me souviens juste que j'étais largué concernant vos posts (toi et Lupulus) où il était question de drapeaux.
Mode en aparté (sorry Rietveld)
J'ai vu que tu lisais SGA1 en planquette. De mon côté, histoire d'apprendre un peu de maths, j'ai essayé de comprendre ce qu'était une variété de Schubert. Ma ma mia. Et figure toi que le Dan Laksov du papier que j'ai pointé ici, c'est le fameux Dan Laksov (avec Kleiman) du Schubert Calculus http://people.reed.edu/~davidp/pcmi/laksov.pdf
Et visiblement Dan Laksov & Anders Thorup (les auteurs du papier pointé ici) sont peut-être nés avec du Schubert dans leur berceau, cf http://web.math.ku.dk/~thorup/temp/flagat.pdf. Pourquoi c'est toujours les mêmes qui font avancer la science ?
Fin du mode en aparté.
En effet. Je n'avais pas remarqué que l'équivalent $q^\alpha -1 \underset{q\to 1}\sim \alpha (q-1)$ montre que $\Binomq{n}{r}_q =\frac{(q^n-1)\cdots(q^{n-r+1}-1) }{ (q^r-1)\cdots(q-1)} \underset{q\to 1}\rightarrow \binom{n}{r}$.
Pour m'en convaincre j'ai trouvé l'argument suivant. Soit $$(X^n-1)\cdots(X^{n-r+1}-1) = E(X) \cdot (X^r-1)\cdots(X-1) +F(X)$$ la division euclidienne de $(X^n-1)\cdots(X^{n-r+1}-1) $ par $(X^r-1)\cdots(X-1)$. Alors $\Binomq{n}{r}_q = E(q) + \frac{F(q)}{(q^r-1)\cdots(q-1) } \underset{q\to\infty}= E(q) +o(1) $. Or $E(X) \in\Bbb Z[X]$ car $(X^r-1)\cdots(X-1)$ est unitaire, et $\Binomq{n}{r}_q$ prend des valeurs entières lorsque $q$ est entier [édit] une puissance d'un nombre premier car c'est le nombre de sev de dimension $r$ de $\Bbb F_q^n$. Donc le $o(1)$ est entier et est nul à partir d'un certain. D'où $F(X)=0$ et $\Binomq{n}{r}_X = E(X)\in\Bbb Z[X]$. As-tu un meilleur argument, Claude ?
Et on peut s'amuser à trouver ou retrouver des identités sur les $\Binomq{n}r$ par méthode combinatoire.
Quand $q=1$, on retrouve le cas particulier de la formule du binôme $ \sum\limits_{r=0}^n \binom{n}r (X-1)^r = X^n$. Ça me fait me demander : existe-t-il un analogue de la formule du binôme pour les $q$-coefficients binomiaux ? J'ai essayé de regarder $\sum\limits_{r=0}^n \Binomq{n}r Q_r(X) Q_{n-r}(Y)$ pour $n=2$ mais je n'ai rien obtenu de satisfaisant.
Je ne sais pas si c'est un meilleur argument, car c'est un peu "bricolage" mais on peut essayer de montrer "à la main" que c'est en polynôme: les racines de $q^k - 1$ sont les racines $k$-ièmes de l'unité. Si je fixe un entier $k$ dans $\left\{1, \ldots r \right\}$ et $\zeta_k$ une racine primitive $k$-ième de l'unité, $\zeta_k$ est racine simple de $X^l - 1$ pour tout multiple de $k$. Donc $\zeta_k$ est une racine du dénominateur, de multiplicité le nombre de multiples de $k$ dans $\left\{ 1, \ldots, r \right\}$. Au numérateur: idem, $\zeta_k$ est racine, de multiplicité le nombre de multiples de $k$ dans $\left\{ n- r + 1, \ldots, n \right\}$. Il suffit donc de montrer que le cardinal de l'ensemble $k\mathbb{Z} \cap \left\{ 1, \ldots, r \right\}$ est inférieur ou égal au cardinal de l'ensemble $k\mathbb{Z} \cap \left\{ n- r + 1, \ldots, n \right\}$.
Si je n'ai pas fait de boulette, dans le premier intervalle, il y a exactement $\lfloor \frac{r}{k} \rfloor$ multiples de $k$, dans le deuxième, il y en a au moins $\lfloor \frac{n - (n-r+1) + 1}{k }\rfloor$, c'est-à-dire au moins $\lfloor \frac{r}{k} \rfloor$, c'est gagné.
Aussi @Calli: il y a un chapitre du second tome (ancienne édition) des H2G2 (Histoires Hédonistes de Groupes et de Géométries, par Caldero-Germoni) qui traite justement des coefficient $q$-binomiaux, avec pas mal de choses rigolotes, vu que ça a l'air de te plaire, tu devrais y jeter un œil.
$\bullet$ Je réponds à ton AVANT dernier post : $\Binom{n}{r}_q$ est un polynôme en $q$. Je n'ai pas d'argument personnel si bien que je pompe sur les autres. Par exemple sur toi. Bien joué ; sauf qu'à un moment donné, tu ne peux pas dire que $\Binom{n}{r}_q$ est entier lorsque $q$ est entier au prétexte que c'est le nombre de ....etc.. Il faut limiter $q$ à $q$ puissance d'un premier. Mais cela marche quand même donc encore deux magnifiques cadeaux (cf plus loin).
Voilà comment procèdent Berndt, Evans & Williams au début de leur ouvrage ``Gauss and Jacobi Sums''. Ils définissent (page 18) une fraction rationnelle en $q$, pour $0 \le r \le n$ :
$$
\Binom{n}{r}_q = {(q^n - 1) (q^{n-1} - 1) \cdots (q^{n-r+1} - 1) \over (q-1) (q^2 - 1) \cdots (q^r - 1)}
$$Et via un petit calcul (je zappe) montrent les deux relations de récurrence (une suffit à nos besoins)
$$
\Binom{n}{r}_q = \Binom{n-1}{r-1}_q + q^r \Binom{n-1}{r}_q = \Binom{n-1}{r}_q + q^{n-r} \Binom{n-1}{r-1}_q
$$Par récurrence sur $n$, on en déduit que $\Binom{n}{r}_q$ est un polynôme en $q$ avec le bonus suivant : il est unitaire de degré $r(n-r)$ et à coefficients entiers $\ge 0$. En fait, je crois que TOUS ses coefficients, du degré $0$ au degré $r(n-r)$, sont des entiers $\ge 1$.
$\bullet$ Formule du binôme. Je ne sais pas si ce qui suit répond à la question de ton dernier post. J'ai vu cela à la première page de https://arxiv.org/pdf/math/0407093.pdf. C'est dû à Schüterzenberger dit Henry Cohn. En non commutatif, on considère 3 variables $x,y,q$ :
$$
xq = qx, \quad yq = qy, \qquad yx = qxy \qquad\qquad \text{alors}\qquad (x + y)^n = \sum_{r=0}^n \Binom{n}{r}_q x^r y^{n-r}
$$Je trouve que c'est joli car cela montre pas mal de choses. Et quand on fait $q = 1$ ...etc.. Il y a bien sûr un problème d'oeuf(s) et de poule(s).
$\bullet$ Cadeau I. Via les parties $S$ de cardinal $r$ de $\{1..n\}$ en notant $\min = 1 + 2 + \cdots + r = \binom{r+1}{2}$ le minimum des sommes des éléments de $S$
$$
\Binom{n}{r}_q = \sum_{S \subset \{1..n\} \atop \#S = r} q^{\ \sum\limits_{s \in S} s - \min}
$$Et quand on fait $q = 1$ ...etc...
$\bullet$ Cadeau II. C'est lié au cadeau I. Histoire de faire savant, on parle de quantum-interprétation. Cela vient de https://arxiv.org/abs/1601.06110, lemme 2.1 page 5. Le lien est dans la preuve (j'attache un morceau). Pas eu le temps de réfléchir (à la retraite, on n'a pas le temps ...etc...)
$$
\Binom{n}{r}_q = \sum_{\lambda \subset (n-r)^r} q^{|\lambda|}
$$La somme porte sur les partitions $\lambda = (\lambda_1 \ge \lambda_2 \ge \cdots)$ qui sont les suites décroissantes d'entiers nulles à partir d'un certain rang. Et ici limitées par le rectangle $(n-r) \times r$, cf le papier pour cette contrainte. Et $|\lambda|$, c'est par définition $\sum_i \lambda_i$.
$\bullet$ Ca, c'est juste pour moi, pour ne pas oublier comment on détermine le $q$-polynôme d'une variété torique $X$, via les faces des cônes d'un fan de $X$. La valeur en $q$ de ce polynôme représente le nombre de points de $X$ sur $\F_q$
Merci pour le conseil sur H2G2. J'irai le feuilleter à la bibliothèque de l'école quand j'y retournerai. Pour l'instant je n'ai pas été un grand utilisateur de livres de maths. Le seul que j'ai eu en ma possession c'est Le théorème du parapluie de Mickaël Launay que mes parents m'ont offert cette année pour mon anniversaire, mais ça ne convenait pas du tout donc je l'ai échangé à la librairie contre un livre de Game of Thrones 8-). Mais il y a probablement plein de choses intéressantes à découvrir dans les livres de maths. (:D
C'est exact. Heureusement, ce n'est pas bien grave.
La formule de Schüterzenberger répond très bien à ma question. Mais un binôme non commutatif, ça je ne m'y attendais pas ! En général, ce genre de formule ne marche que dans les anneaux commutatifs.
Très astucieux, le passage du cadeau I au cadeau II.
$\bullet$ Un petit développement en série.
$$
\prod_{i=0}^n {1 \over 1 - q^ i t} = \sum_{r \ge 0} \Binom{n+r}{r}_q\, t^r
$$$\bullet$ Lien avec les fonctions symétriques complètes. La fonction symétrique complète de degré $d$ en $m$ variables est par définition la somme de tous les monômes de degré $d$ :
$$
h_d(X_1, \cdots, X_m) = \sum_{|\alpha| = d} X^\alpha
$$Alors
$$
\Binom{n}{r}_q = h_r(\overbrace{1, q, q^2, \cdots, q^{n-r}}^{n-r+1}) = h_{n-r}(\overbrace{1,q, \cdots, q^r}^{r+1})
$$Les évaluations $X_i := q^i$ ont un rôle important dans cette histoire. Je reprends l'exemple $n = 9$, $r =4$ pour lequel $n-r+1 = 6$. Je vais utiliser
$$
\Binom{9}{4}_q = h_4(1, q, q^2, \cdots, q^5) \qquad \text{d'où le besoin de 6 variables } x_0, \cdots, x_5
$$ C'est un peu nul de montrer cela mais après tout cela donne un exemple de fonction symétrique complète. Et je termine par l'évaluation qui doit donner ce qu'il faut : Je stoppe promis, juré. Et de ce pas, je pars en cure illico presto.
Pour le prouver, on utilise l'identité $\Binomq{n+1}{r+1} = \Binomq{n}{r} + \Binomq{n}{r+1} q^{r+1}$ : $$\begin{eqnarray*}
\sum_{r=0}^{n+1} \Binomq{n+1}r q^{\textstyle \binom{r}2} X^r Y^{n+1-r} &=& \sum_{r=0}^{n} \Binomq{n}r q^{\textstyle \binom{r+1}2} X^{r+1} Y^{n-r} + \sum_{r=0}^{n} \Binomq{n}r q^r q^{\textstyle \binom{r}2} X^r Y^{n+1-r}\\
&=& X \sum_{r=0}^{n} \Binomq{n}r q^{\textstyle \binom{r}2} (qX)^r Y^{n-r} + Y \sum_{r=0}^{n} \Binomq{n}r q^{\textstyle \binom{r}2} (qX)^r Y^{n-r} \\
&=& (X+Y) \sum_{r=0}^n \Binomq{n}r q^{\textstyle \binom{r}2} (qX)^r Y^{n-r}
\end{eqnarray*}$$
Le nom de "formule du binôme" n'est pas volé puisqu'on retombe bien sur le binôme classique quand $q=1$. Cas particuliers : (1) en évaluant $(X,Y)$ en $(-1,1)$ on retombe sur $\sum\limits_{r=0}^n \Binomq{n}r (-1)^r q^{\textstyle \binom{r}2}=0$ et (2) en évaluant $X$ en $1$ on a $\sum_{r=0}^n \Binomq{n}r \, q^{\textstyle \binom{r}2} Y^{n-r} = (-1)^n Q_n(-Y)$ puis $$\sum_{r=0}^n \Binomq{n}r q^{\textstyle \binom{r}2} (-1)^r X^{n-r} = Q_n(X).$$ Donc on a une expression de $Q_n(X)$ en fonction des $X^r$ et aussi une expression de $X^n$ en fonction des $Q_r(X)$ (cf. http://www.les-mathematiques.net/phorum/read.php?3,2042316,2043408#msg-2043408). La formule de $Q_n(X)$ que je viens d'écrire est aussi dans le premier article joint, mais elle y est prouvée différemment.
Il suffit de le prouver pour un monôme $X^m$. En évaluant $\sum\limits_{r=0}^n \Binomq{n}r \,q^{\textstyle \binom{r}2} (-1)^r X^{n-r} = Q_n(X)$ en $q^m$, on a $\sum\limits_{r=0}^n \Binomq{n}r \,q^{\textstyle \binom{r}2} (-1)^r (q^{n-r})^m$ $= Q_n(q^m) = \Binomq{m}{n} Q_n(q^n) = \Binomq{X^m}{n} Q_n(q^n)$ car $X^m = \sum_{r=0}^m \Binomq{m}r Q_r(X)$. CQFD
J'en suis à ton avant dernier post (binôme commutatif). Bien sûr, dans ta première ligne, ``en s'inspirant'' ne veut pas dire ``en utilisant'' : ton post est self-contained ! Une remarque : en faisant $Y = 1$ dans ton encadré, je vois mieux le lien entre la formule que j'ai donnée et la tienne. Encore bien joué mais je ne sais plus où donner de la tête.
Autre chose : le cadeau I, dans mon post http://www.les-mathematiques.net/phorum/read.php?3,2042316,2043574#msg-2043574, qui venait de https://arxiv.org/pdf/1601.06110.pdf, cela m'a rappelé quelque chose que j'avais fait dans le fil $q$-polynômes. A voir plus tard. En attendant, j'attache de nouveau un extrait de l'article ``quantum'', en plein milieu de la preuve (la référence [Stal12], c'est Stanley, Enumerative Combinatorics). Bref, cela explose dans tous les sens dans ma pauvre tête (bis).
PS : en ce qui concerne la cure, j'ai également réservé une place pour toi.
$\bullet$ Je reprends les formules d'hier
$$
\prod_{i=0}^{n-1} (1 + q^i X) = \sum_{r=0}^n \Binom{n}{r}_q q^\binom{r}{2}\, X^r
\qquad\qquad
\prod_{i=0}^{n-1} { 1 \over 1 - q^i X} = \sum_{r \ge 0} \Binom{n+r-1}{r}_q \, X^r
\qquad\qquad
\sum_{r=0}^n \Binom{n}{r}_q (-1)^r q^\binom{r}{2} = \cases {0&si $n \ge 1$\cr 1 &si $n=0$}
$$A gauche, c'est un cas particulier de ta formule du binôme avec $Y = 1$ (mais on peut retrouver ta formule du binôme en homogénéisant). Au milieu, c'est celle que j'ai fournie sans explication via la page 27 de MacDonald. Et à droite, une formule déjà établie (par tes soins) permettant de faire le lien entre la formule de gauche et celle du milieu (et on retrouve cette formule de droite via ta formule du binôme).
Bref, tout est prouvé, n'est ce pas ?
$\bullet$ Autre chose. Je note comme hier $h_k$ la fonction symétrique complète i.e. la somme de tous les monômes de degré $k$. On a facilement la formule de gauche
$$
\prod_{i=0}^{n} { 1 \over 1 - t X_i} = \sum_{k \ge 0} h_k(X_0, \cdots, X_n)\, t^k
\qquad\qquad \text{ que je spécialise en } X_i := q^i\qquad\qquad
\prod_{i=0}^{n} { 1 \over 1 - t q^ i} = \sum_{k \ge 0} h_k(1, q, , \cdots, q^n)\, t^k
$$J'utilise maintenant la formule du milieu du premier point en remplaçant $n-1$ par $n$ et $X$ par $t$
$$
\sum_{k \ge 0} h_k(1, q, , \cdots, q^n)\, t^k = \sum_{r \ge 0} \Binom{n+r}{r}_q \, t^r
\qquad\qquad \text{d'où} \qquad\qquad
\fbox{$\displaystyle{\Binom{n+r}{r}_q} = h_r(1,q, \cdots, q^n)$}
$$La formule encadrée à droite est celle que j'ai donnée hier, sans explication, avant d'annoncer que je partais en cure de désintoxication.
merci pour vos contributions, qui sont parties bien plus loin que mon questionnement de base.
Je ne connais absolument pas les champs de mathématiques que vous avez balayés, ne les ayant pas vu pendant mes études.
J'ai donc un peu de mal à suivre. Que désigne cette notation entre crochet $\begin{bmatrix}
n\\
r
\end{bmatrix}_{q}$, ça a l'odeur, la saveur et l'apparence d'un coefficient binomial, mais je n'ai pas l'impression que cela soit la même chose ?
Disons, pour quelqu'un qui ne l'aurait jamais abordé, d'où cela sort-il ? Quel questionnement y a-t-il de manière sous-jacente à l'introduction de cette notion ?
Il me semble que ceci http://www-groups.mcs.st-andrews.ac.uk/~pjc/Teaching/MT5821/1/l6.pdf peut servir d'introduction.
J'ai consulté l'article Wikipédia qui en parle : les coefficients binomiaux de Gauss
Dans le paragraphe "Nombre de combinaisons présentant un nombre d'inversions donné", il est questions du nombre d'inversions d'un mot.
J'avoue que j'ai un peu de mal à la comprendre. Je cherchais une illustration concrète de ces coefficients binomiaux de Gauss, mais la définition qui est donnée du "nombre d'inversion" me pose problème.
Il est indiqué que pour le mot 0101, il y a une inversion et pour 0110, il y en a 2 puis dans 1010, il y en a 3.
Je dois confondre avec le nombre d'inversions qu'on rencontre dans la formule du déterminant.
J'ai essayé de former des suites strictement décroissantes en prenant deux chiffres consécutifs du mot, mais ce n'est pas cela.
Comment trouve-t-on le nombre d'inversions dont il est question dans cet article ?
Oui (tu). Et avec ton dernier point, je vois d'où vient $\Binomq{n+r}{r} = h_r(1,q, \cdots, q^n)$. Encore une fois, c'est astucieux.
Je constate avec le lien donné par Rietveld que ce dont on a parlé était sur Wikipédia. J'étais conscient que je n'inventais rien, mais je ne m'attendais pas à ce qu'il y ait un article Wikipédia. Enfin, c'était amusant de trouver toutes ces petites formules par soi-même.
J'y vais de ce pas ! Et merci pour ta participation, Claude ! C'est très agréable de discuter avec toi. :-)