Dénombrement

[L.A.]

Bonjour à tous, voici le petit dénombrement du matin :dodo: :zen:



où la somme parcourt l'ensemble des couples soumis à la condition k=1 ou l=1, et les conditions au bord sont ().

Toute suggestion sera la bienvenue, merci

[DamX]

Bonjour à tous, voici le petit dénombrement du matin :dodo: :zen:



où la somme parcourt l'ensemble des couples soumis à la condition k=1 ou l=1, et les conditions au bord sont ().

Toute suggestion sera la bienvenue, merci

Hello,
C'est un peu étrange cette formulation, ou alors j'ai loupé un truc. Vu la condition sur les indices, c'est une double somme tres artificielle, et ce sont plutôt deux sommes simples :

C'est bien ça ?

Damien

[L.A.]

Oui c'est bien ça, mais je ne crois pas que ça soit forcément plus facile sous cette forme...

[DamX]

Oui c'est bien ça, mais je ne crois pas que ça soit forcément plus facile sous cette forme...

OK. Pour savoir ça sort de quel contexte ? Au sens est-ce que c'est une question ouverte issue d'un problème ou est-ce sûr qu'il y a une formule sympa à trouver ?

Parce qu'à vue de nez ça a l'air de se complexifier lourdement au fur et à mesure que tu te rapproches de la diagonale n1=n2.

Par contre, sauf erreur de ma part (je n'ai pas tout rédigé proprement), on a les croissances asymptotiques suivantes en n1 et en n2, qui sont d'ailleurs symétriques (sans grande surprise vu que la relation de récurrence est quasi-symétrique) :





Ca ne donne peut-être pas une expression exacte mais c'est sympa quand même comme info.

Damien

[L.A.]

Ca croit très rapidement en effet, mais c'est vraiment une valeur exacte qu'il me faudrait.

Non je ne suis pas sûr qu'il y ait une solution, mais je peux te dire d'où ça vient : c'est le nombre de parties de qui se projettent surjectivement sur les deux facteurs tout en étant minimales (cad qui ne contiennent aucune sous-partie stricte ayant cette propriété). D'ailleurs je m'attendais à une formule plus symétrique en n_1,n_2 puisque le résultat final doit l'être, mais il semblerait (sauf erreur) que ce soit bien n_2-1 et l-1.

Sinon j'ai abordé mon problème sous un angle tout à fait différent (qui semble plus séduisant et plus près de marcher : si on fait agir le groupe de permutation des lignes et des colonnes sur l'ensemble des parties en question est une réunion d'orbites pour lesquelles on peut extraire un représentant bien sympa) et qui tourne autour d'un calcul de puissances de la série formelle



Si vous la connaissez faites-moi signe, je donnerai des précisions quand j'en saurai un peu plus.

[L.A.]

Edit de l'edit : difficile de regarder les puissances d'une série formelle dont le support est Z, même si celle-ci doit avoir de bonnes propriétés de convergence :doh: voilà ce que c'est que de vouloir se prendre pour Euler. En fait c'est simplement un polynôme dont j'ai besoin



Du coup je pense que tout est bon.
Donc on peut trouver dans chaque orbite un unique représentant de la forme suivante

XOOOOOO
XOOOOOO
XOOOOOO
XOOOOOO
OXOOOOO
OXOOOOO
OOXOOOO
OOOXXOO
OOOOOXX

soit une sorte de "courbe continue convexe" qui relie les deux sommets diamétralement opposés ("convexe" au sens où on a d'abord des blocs verticaux de taille décroissante, puis des croix, puis des blocs horizontaux de taille croissante). On peut lui associer une fonction s de Z dans N

-3 -> 1, -1 -> 1, 0 -> 1, 1 -> 2,
x -> 0 pour tout autre x

qui compte le nombre de blocs de taille donnée et d'orientation donnée par le signe. Si n_1 est le nombre de lignes et n_2 le nombre de colonnes, cette fonction est à support dans I = {-n_1+2,...,n_2-2}.

On a les relation suivantes :

n_c = nombre total de croix = somme des (|i|+1)s(i)
n_b = nombre total de blocs = somme des s(i)

n_1+n_2 = n_b + n_c
n_2-n_1 = somme des i.s(i)

ordre du stabilisateur = produit des s(i)!((|i|+1)!)^{s(i)}

Si le nombre de blocs n_b est fixé, la réunion des orbites correspondantes est



où s parcourt l'ensemble des fonctions à support dans I vérifiant les conditions demandées, ce qui revient à trouver le coefficient de X^{n_2-n_1}Y^{n_2+n_1-n_b} dans A(X,Y)^{n_b}.