Dénombrement

[L.A.]

Bonjour à tous,

j'ai un ensemble F de parties de {1,...,n} qui vérifie la propriété suivante : pour tout et tout on a .

Des idées pour calculer la somme ?

Merci.

[DamX]

Salut,

juste un cas dégradé pour faire avancer, que tu as peut-être déjà fait :

Il y a moyen je pense de caractériser F par un certains nombres de "générateurs", c'est à dire de parties de [|1,n|] telles que si on prend pour chaque générateur l'ensemble de toutes les parties de [|1,n|] qui incluent ce générateur et que l'on en fait la réunion de ces ensembles, on a F.

exemple : n = 3, générateurs = {1,2}, {1,3}
{1,2} -> {{1,2},{1,2,3}}
{1,3} -> {{1,3},{1,2,3}}

=> F = {{1,2},{1,3},{1,2,3}}

Bref, le cas particulier que l'on peut facilement calculer est lorsque F est générable par un seul élément de P([|1,n|]).

On suppose que le générateur a p éléments,
Dans ce cas, on peut dénombrer les éléments de F par cardinal facilmenent :
on en a un qui a un cardinal p (le générateur), on en a (1 parmi n-p) qui on une longueur p+1 (le nombre de choix pour l'élément non contraint), (2 parmi n-p) de longueur p+2, etc...

au final, on peut réorganiser la somme par cardinal, et cela donne :



exemple : n=4, e = {1,2}, F = Gén({e}) = {{1,2},{1,2,3},{1,2,4},{1,2,3,4}}, S = 1+(-1)+(-1)+1 = 0

Donc lorsque F est générable par un seul élément, la somme est nulle.

En revanche tout se complique lorsque l'on a plusieurs générateurs, à voir si cette notion peut être utilisée (en devant définir un ensemble minimal/libre de générateurs c'est à dire dont chacun des générateurs ne peut être obtenu à partir des autres), ou si ça ne sert à rien pour le cas général :we:

Damien

[L.A.]

En effet, c'est la même piste que j'étais en train de suivre :zen:
Mais au lieu de "générateurs", je parlerais plutôt des éléments minimaux de F (c'est bien ce que c'est)
J'ai en effet remarqué que la somme était nulle pour un F qui n'a qu'un seul élément minimal (un minimum)... sauf si F est réduit au singleton F = {{1,...,n}}, dans ce cas la somme vaut (-1)^n (dans ton binôme (1-1)^{n-n} = 1).


Et on peut en fait passer au cas général en utilisant le principe d'inclusion exclusion (ou théorème de Poincaré, je crois) : si on appelle alors



et la dernière somme est nulle, à moins que .

[SLA]

En effet, c'est la même piste que j'étais en train de suivre :zen:
Mais au lieu de "générateurs", je parlerais plutôt des éléments minimaux de F (c'est bien ce que c'est)
J'ai en effet remarqué que la somme était nulle pour un F qui n'a qu'un seul élément minimal (un minimum)... sauf si F est réduit au singleton F = {{1,...,n}}, dans ce cas la somme vaut (-1)^n (dans ton binôme (1-1)^{n-n} = 1).


Et on peut en fait passer au cas général en utilisant le principe d'inclusion exclusion (ou théorème de Poincaré, je crois) : si on appelle alors



et la dernière somme est nulle, à moins que .

Salut,
ça me semble plus compliqué que ça, puisque les ne forment pas une partition de F.
Ne serait-ce que si pour n=2, la somme vaut -1 (si je ne me trompe pas).
Je regarde ça, ça a l'air sympa.
@+

[L.A.]

Ca ne contredit pas puisque ton F = {{1},{2},{1,2}} n'est pas de la forme F(m),
il est de la forme F(m_1)uF(m_2).

Et le fait que les F(m_i) s'intersectent éventuellement (et même souvent) est pris en compte dans le théorème de Poincaré (pour mémoire c'est la généralisation de #(AUB) = #A + #B - #(AnB)).

Rmq : l'intersection des F(m_i) est F(réunion des m_i).

[L.A.]

Autre remarque :

Si tout est bon jusque là,



avec F' l'ensemble des I tels que , qui vérifie la même propriété que F : si et alors .

Donc il y a une forme de dualité visiblement...

[L.A.]

Toujours sur ce problème... :triste:

Je vais aller un peu plus en profondeur en vous disant comment j'obtiens mon F.
Je considère un tableau à m lignes et n colonnes où chaque case est soit vide 0, soit cochée X.
Chaque partie R de {1,...,n} correspond à un ensemble de colonnes, et j'attribue à R un certain poids b(R) comme ceci : c'est le nombre de lignes qui comportent au moins une croix dans une des colonnes de R.

Par exemple, si R est un singleton/une seule colonne, son poids est le nombre de cases cochées dans cette colonne ; si mon tableau a deux colonnes qui sont

12

0X
XX
00
XX
X0
0X

alors b({1}) = 3, b({2}) = 4, b({1,2}) = 5.

Ensuite je définis F_j = {R | b(R) supérieur ou égal à j} pour tout j entre 0 et m.

Si quelqu'un pouvait me trouver une formule pour la somme des (-1)^R qui se base sur les lignes plutôt que les colonnes par exemple, je crois que ça me serait utile...

Merci :zen: