Suite récurrente avec des coef binomiaux

azuria
azuria
dans Arithmétique
Bonjour,

j'ai une suite Un = Somme de k = 1 à n : coefficient binomiaux de (n, k) x U(n-k)

Vous savez comment on peut la définir en fonction de n ?

Merci

Réponses

  • Blacksheep1
    Blacksheep1
    Juste une idée : regarde les premiers termes, essaye d'"intuiter" une forme en utilisant le binôme de Newton, puis récurrence.
  • azuria
    azuria
    Merci
    J'ai oublié de dire Uo = c

    U1 = 1 x c = c

    U2 = c x (2 + 1) = 3c

    U3 = c x (6 + 3 + 3 + 1) = 13c

    U4 = c x (24 + 12 + 12 + 4 + 12 + 6 + 4 + 1) = 75c

    U5 = c x (120 + 60 + 60 + 20 + 60 + 30 + 20 + 5 + 60 + 30 + 30 + 10 + 20 + 10 + 5 + 1) = 541c
  • Blacksheep1
    Blacksheep1
    Oui mais utilise les formules sur les coefficients binomiaux alors.
  • Math Coss
    Math Coss
    C'est un exercice ou une question plus avancée ? Le calcul des premiers termes, un peu au-delà de ce que tu as fait, conduit à la suite A000670 de l'OEIS, qui ne semble pas avoir d'expression facile.
  • azuria
    azuria
    Ah intéressant !
    Je n'ai plus le résultat sous les yeux mais je pense que c'est la même suite
  • kolotoko
    kolotoko
    Bonjour,

    comme chacun sait les nombres de Fubini peuvent s'obtenir facilement à partir du triangle d'Euler : A008292, A123125 ou A173018 dans OEIS.

    On peut aussi utiliser A131689 ou A129062.

    Consulter les livres de Louis Comtet me parait bien utile.

    Bien cordialement.

    kolotoko
  • Math Coss
    Math Coss
    Tu veux dire A008292, A123125, A173018, A131689 et A129062 ?
  • kolotoko
    kolotoko
    Bonjour,

    les 3 premiers triangles sont équivalents (des variantes).

    Les deux autres triangles donnent les nombres de A000670 en additionnant ligne à ligne .

    Bien cordialement.

    kolotoko
  • claude quitté
    claude quitté
    In https://tel.archives-ouvertes.fr/tel-01404298/document 2.2.4 Partitions ordonnées d'ensembles. Ou https://tel.archives-ouvertes.fr/tel-00393631/document

    Je ne peux plus accéder à l'OEIS (configuration m.rd.que de ma machine). Alors je fais mumuse pour montrer les coefficients $b_n$ définis par ${1 \over 2 - \exp(x)} = \sum_{n \ge 0} b_n {x^n \over n!}$ 
    [color=#000000]
> Q := RationalField() ;                         
> Qx<x> := PowerSeriesRing(Q) ;
> S := 1 / (2 - Exp(x)) ;
> [Factorial(n)*Coefficient(S,n) : n in [0..10]] ;
[ 1, 1, 3, 13, 75, 541, 4683, 47293, 545835, 7087261, 102247563 ]
[/color]
  • azuria
    azuria
    Claude quitté, merci pour ta réponse.

    Comment obtiens-tu cette somme juste en fonction de n ?
  • claude quitté
    claude quitté
    $\newcommand {\Euler}[2]{\genfrac{\langle}{\rangle}{0pt}{}{#1}{#2}}$@azuria
    Je n'en sais rien et je n'y connais rien. Si j'en crois Math Coss, il ne doit pas y avoir d'expression facile de $b_n$ en fonction de $n$. Je ne peux pas accéder à l'OEIS comme déjà dit. Donc je ne sais pas quelles informations contiennent les pointeurs fournis. Par ailleurs, on ne peut pas dire que certains posts soient vraiment explicites (exemple ``comme chacun sait les nombres de Fubini peuvent s'obtenir facilement à partir du triangle d'Euler'').

    J'ajoute juste qu'il y a des nombres d'Euler $\Euler{n}{k}$ pour $0 \le k \le n$ (j'utilise les notations de Graham, Knuth, Patashnik, Concrete Mathematics, section 2.6 Eulerian numbers) qui compte le nombre de permutations du groupe symétrique $S_n$ ayant une certaine propriété en fonction de $k$ (je n'ai pas envie de rentrer dans les détails, cf la section ad-hoc de G.K.P.). En voici le triangle 
    [color=#000000]
> [[EulerianNumber(n,k) : k in [0..n]] : n in [0..8]] ;
[
    [ 1 ],
    [ 1, 0 ],
    [ 1, 1, 0 ],
    [ 1, 4, 1, 0 ],
    [ 1, 11, 11, 1, 0 ],
    [ 1, 26, 66, 26, 1, 0 ],
    [ 1, 57, 302, 302, 57, 1, 0 ],
    [ 1, 120, 1191, 2416, 1191, 120, 1, 0 ],
    [ 1, 247, 4293, 15619, 15619, 4293, 247, 1, 0 ]
]
[/color]
    On a $n! = \sum_{k=0}^n \Euler{n}{k}$. 
    [color=#000000]
> [&+[EulerianNumber(n,k) : k in [0..n]] : n in [0..8]] ;      
[ 1, 1, 2, 6, 24, 120, 720, 5040, 40320 ]
> [Factorial(n) : n in [0..8]] ;
[ 1, 1, 2, 6, 24, 120, 720, 5040, 40320 ]
[/color]
    Quant à $b_n$, le nombre que tu convoites, il s'exprime en fonction des $\Euler{n}{k}$
    $$
    b_n = \sum_{k=0}^n \Euler{n}{k}\ 2^k
    $$ 
    [color=#000000]
> b := func < n | &+[EulerianNumber(n,k)*2^k : k in [0..n]] > ;  
> 
> [b(n) : n in [0..10]] ;
[ 1, 1, 3, 13, 75, 541, 4683, 47293, 545835, 7087261, 102247563 ]
[/color]
    Cela ne répond pas à ta question, mais c'est tout ce que je peux faire.
  • claude quitté
    claude quitté
    $\newcommand {\Euler}[2]{\genfrac{\langle}{\rangle}{0pt}{}{#1}{#2}}$@azuria
    J'ajoute quelque chose qui ne fait pas avancer le schmilblick, c'est que les Eulerian numbers $\Euler{n}{k}$, on les retrouve dans le développement où intervient l'exponentielle :
    $$
    {t- 1 \over t - e^{x(t-1)}} = \sum_{n \ge 0} \left( \sum_{k=0}^n \Euler{n}{k} t^k \right)\, {x^n \over n!} \qquad \qquad (\star)
    $$ 
    [color=#000000]
> Q := RationalField() ;                               
> Qt<t> := PolynomialRing(Q) ;
> Qtx<x> := PowerSeriesRing(Qt) ;
> S := (t-1) / (t - Exp(x*(t-1))) ;
> [Qt| Factorial(n)*Coefficient(S,n) : n in [0..8]] ;
[
    1,
    1,
    t + 1,
    t^2 + 4*t + 1,
    t^3 + 11*t^2 + 11*t + 1,
    t^4 + 26*t^3 + 66*t^2 + 26*t + 1,
    t^5 + 57*t^4 + 302*t^3 + 302*t^2 + 57*t + 1,
    t^6 + 120*t^5 + 1191*t^4 + 2416*t^3 + 1191*t^2 + 120*t + 1,
    t^7 + 247*t^6 + 4293*t^5 + 15619*t^4 + 15619*t^3 + 4293*t^2 + 247*t + 1
]
> [[EulerianNumber(n,k) : k in [0..n]] : n in [0..8]] ;
[
    [ 1 ],
    [ 1, 0 ],
    [ 1, 1, 0 ],
    [ 1, 4, 1, 0 ],
    [ 1, 11, 11, 1, 0 ],
    [ 1, 26, 66, 26, 1, 0 ],
    [ 1, 57, 302, 302, 57, 1, 0 ],
    [ 1, 120, 1191, 2416, 1191, 120, 1, 0 ],
    [ 1, 247, 4293, 15619, 15619, 4293, 247, 1, 0 ]
]
[/color]
    Faire $t = 2$ dans $(\star)$ permet de faire apparaître tes $b_n$.
  • kolotoko
    kolotoko
    Bonjour,

    @ claude quitté :
    le '' comme chacun sait etc '' signifiait l'existence de la formule que tu donnes.

    Bien cordialement.

    kolotoko
  • azuria
    azuria
    @claude quitté, merci je vais regarder ca attentivement
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 3

3 Invités