Bonjour
Voici un problème qu'on m'a posé et sur lequel je sèche...
Soit E un ensemble de cardinal n.
Soit p < n et soit F l'ensemble des parties de E de
cardinal p. On sait que Card F = C(n,p)
Soit p < k < n et soit G l'ensemble des parties de E
de cardinal k. On sait que Card G = C(n,k)
Question :
Comment construire H, sous-ensemble de G, tel que
tout élément F soit inclus dans au moins un élément de
H et tel que Card H soit le plus petit possible ?
Que vaut Card H ?
Merci,
Pierre
Dénombrement difficile
11 messages
- Page 1 sur 1
Re: Dénombrement difficile
par Anonyme » 30 Avr 2005, 17:09
Pierre Capdevila wrote:
> Bonjour
>
> Voici un problème qu'on m'a posé et sur lequel je sèche...
>
> Soit E un ensemble de cardinal n.
>
> Soit p cardinal p. On sait que Card F = C(n,p)
>
> Soit p de cardinal k. On sait que Card G = C(n,k)
>
> Question :
>
> Comment construire H, sous-ensemble de G, tel que
> tout élément F soit inclus dans au moins un élément de
> H et tel que Card H soit le plus petit possible ?
> Que vaut Card H ?
>
> Merci,
> Pierre
Pour tout élément X de F; je peux le compléter par k-p élément de E-X et
j'obtiens un élément de G qui contient un élément de F.
Les éléments que je construis sont deux à deux distincts. H contient donc
au moins C(n,p) parties. Comme le H que je viens de construire convient
(il n'est pas unique !!!) card H = C(n,p).
A+
> Bonjour
>
> Voici un problème qu'on m'a posé et sur lequel je sèche...
>
> Soit E un ensemble de cardinal n.
>
> Soit p cardinal p. On sait que Card F = C(n,p)
>
> Soit p de cardinal k. On sait que Card G = C(n,k)
>
> Question :
>
> Comment construire H, sous-ensemble de G, tel que
> tout élément F soit inclus dans au moins un élément de
> H et tel que Card H soit le plus petit possible ?
> Que vaut Card H ?
>
> Merci,
> Pierre
Pour tout élément X de F; je peux le compléter par k-p élément de E-X et
j'obtiens un élément de G qui contient un élément de F.
Les éléments que je construis sont deux à deux distincts. H contient donc
au moins C(n,p) parties. Comme le H que je viens de construire convient
(il n'est pas unique !!!) card H = C(n,p).
A+
Re: Dénombrement difficile
par Anonyme » 30 Avr 2005, 17:09
Et alors vous séchez aussi ?
Peut-être parce que j'ai oublié un mot,
il faut lire :
Comment construire H, sous-ensemble de G,
tel que tout élément **de** F soit inclus dans
au moins un élément de H et tel que Card H
soit le plus petit possible ?
Pierre
Peut-être parce que j'ai oublié un mot,
il faut lire :
Comment construire H, sous-ensemble de G,
tel que tout élément **de** F soit inclus dans
au moins un élément de H et tel que Card H
soit le plus petit possible ?
Pierre
Re: Dénombrement difficile
par Anonyme » 30 Avr 2005, 17:09
Alex G. a écrit
> Pour tout élément X de F; je peux le compléter par k-p élément de E-X et
> j'obtiens un élément de G qui contient un élément de F.
> Les éléments que je construis sont deux à deux distincts. H contient donc
> au moins C(n,p) parties. Comme le H que je viens de construire convient
> (il n'est pas unique !!!) card H = C(n,p).
En prenant l'un après l'autre tous les éléments de F,
on tombera fatalement sur un élément Y qui contiendra
certains des éléments qu'on a ajouté à ton X
Donc on va construire avec Y un ensemble qui a déjà été
construit à l'aide de X
Non ?
Pierre
> Pour tout élément X de F; je peux le compléter par k-p élément de E-X et
> j'obtiens un élément de G qui contient un élément de F.
> Les éléments que je construis sont deux à deux distincts. H contient donc
> au moins C(n,p) parties. Comme le H que je viens de construire convient
> (il n'est pas unique !!!) card H = C(n,p).
En prenant l'un après l'autre tous les éléments de F,
on tombera fatalement sur un élément Y qui contiendra
certains des éléments qu'on a ajouté à ton X
Donc on va construire avec Y un ensemble qui a déjà été
construit à l'aide de X
Non ?
Pierre
Re: Dénombrement difficile
par Anonyme » 30 Avr 2005, 17:09
Le Fri, 30 Apr 2004 22:17:33 +0200, Pierre Capdevila à écrit
>Alex G. a écrit[color=green]
>> Pour tout élément X de F; je peux le compléter par k-p élément de E-X et
>> j'obtiens un élément de G qui contient un élément de F.
>> Les éléments que je construis sont deux à deux distincts. H contient donc
>> au moins C(n,p) parties. Comme le H que je viens de construire convient
>> (il n'est pas unique !!!) card H = C(n,p).
>
>En prenant l'un après l'autre tous les éléments de F,
>on tombera fatalement sur un élément Y qui contiendra
>certains des éléments qu'on a ajouté à ton X
>
>Donc on va construire avec Y un ensemble qui a déjà été
>construit à l'aide de X
>
>Non ?
>
>Pierre[/color]
Oui je suis d'accord.
Si p=2 et k=n-1 alors il est évident que card(H) = 3
H = {1,2,...,n-1} U {2,3,...,n} U {1,3,....,n} convient toujours pour
y loger tous les couples de F.
--
zwim.
Rien n'est impossible que la mesure de la volonté humaine...
>Alex G. a écrit[color=green]
>> Pour tout élément X de F; je peux le compléter par k-p élément de E-X et
>> j'obtiens un élément de G qui contient un élément de F.
>> Les éléments que je construis sont deux à deux distincts. H contient donc
>> au moins C(n,p) parties. Comme le H que je viens de construire convient
>> (il n'est pas unique !!!) card H = C(n,p).
>
>En prenant l'un après l'autre tous les éléments de F,
>on tombera fatalement sur un élément Y qui contiendra
>certains des éléments qu'on a ajouté à ton X
>
>Donc on va construire avec Y un ensemble qui a déjà été
>construit à l'aide de X
>
>Non ?
>
>Pierre[/color]
Oui je suis d'accord.
Si p=2 et k=n-1 alors il est évident que card(H) = 3
H = {1,2,...,n-1} U {2,3,...,n} U {1,3,....,n} convient toujours pour
y loger tous les couples de F.
--
zwim.
Rien n'est impossible que la mesure de la volonté humaine...
Re: Dénombrement difficile
par Anonyme » 30 Avr 2005, 17:09
Le Fri, 30 Apr 2004 21:42:47 +0200, Pierre Capdevila à écrit
>Et alors vous séchez aussi ?
>
>Peut-être parce que j'ai oublié un mot,
>il faut lire :
>
>Comment construire H, sous-ensemble de G,
>tel que tout élément **de** F soit inclus dans
>au moins un élément de H et tel que Card H
>soit le plus petit possible ?
>
>Pierre
La question c'est bien ?
Si E = {1,2,3,4,5,6}
F parties de E à 2 éléments
G parties de E à 4 éléments
alors H = {1,2,3,4} U {3,4,5,6} U {1,2,5,6} qui a 3 éléments ?
Je vais essayer de chercher dans le cas général...
--
zwim.
Rien n'est impossible que la mesure de la volonté humaine...
>Et alors vous séchez aussi ?
>
>Peut-être parce que j'ai oublié un mot,
>il faut lire :
>
>Comment construire H, sous-ensemble de G,
>tel que tout élément **de** F soit inclus dans
>au moins un élément de H et tel que Card H
>soit le plus petit possible ?
>
>Pierre
La question c'est bien ?
Si E = {1,2,3,4,5,6}
F parties de E à 2 éléments
G parties de E à 4 éléments
alors H = {1,2,3,4} U {3,4,5,6} U {1,2,5,6} qui a 3 éléments ?
Je vais essayer de chercher dans le cas général...
--
zwim.
Rien n'est impossible que la mesure de la volonté humaine...
Re: Dénombrement difficile - denombrement.c (0/1)
par Anonyme » 30 Avr 2005, 17:14
Le Fri, 30 Apr 2004 12:47:10 +0100, Pierre Capdevila à écrit
>Bonjour
>
>Voici un problème qu'on m'a posé et sur lequel je sèche...
>
>Soit E un ensemble de cardinal n.
>
>Soit p cardinal p. On sait que Card F = C(n,p)
>
>Soit p de cardinal k. On sait que Card G = C(n,k)
>
>Question :
>
>Comment construire H, sous-ensemble de G, tel que
>tout élément F soit inclus dans au moins un élément de
>H et tel que Card H soit le plus petit possible ?
>Que vaut Card H ?
>
>Merci,
>Pierre
>
J'ai remis un peu le nez dans ce problème, mais je ne trouve pas de
formule explicite.
Pour m'aider j'ai fait un petit programme qui fait les dénombrements
pour moi, en espérant que cela me donne un idée théorique...
Voici ce à quoi je suis parvenu pour le moment :
*******************************************
n = 1
nb = 1 1
#(1,1) = 1
*******************************************
n = 2
nb = 1 1
nb = 1 2
#(1,1) = 2
nb = 2 12
#(1,2) = 1
nb = 1 12
#(2,2) = 1
*******************************************
n = 3
nb = 1 1
nb = 1 2
nb = 1 3
#(1,1) = 3
nb = 2 12
nb = 1 13
#(1,2) = 2
nb = 3 123
#(1,3) = 1
nb = 1 12
nb = 1 13
nb = 1 23
#(2,2) = 3
nb = 3 123
#(2,3) = 1
nb = 1 123
#(3,3) = 1
*******************************************
n = 4
nb = 1 1
nb = 1 2
nb = 1 3
nb = 1 4
#(1,1) = 4
nb = 2 12
nb = 2 34
#(1,2) = 2
nb = 3 123
nb = 1 124
#(1,3) = 2
nb = 4 1234
#(1,4) = 1
nb = 1 12
nb = 1 13
nb = 1 23
nb = 1 14
nb = 1 24
nb = 1 34
#(2,2) = 6
nb = 3 123
nb = 2 124
nb = 1 134
#(2,3) = 3
nb = 6 1234
#(2,4) = 1
nb = 1 123
nb = 1 124
nb = 1 134
nb = 1 234
#(3,3) = 4
nb = 4 1234
#(3,4) = 1
nb = 1 1234
#(4,4) = 1
*******************************************
n = 5
nb = 1 1
nb = 1 2
nb = 1 3
nb = 1 4
nb = 1 5
#(1,1) = 5
nb = 2 12
nb = 2 34
nb = 1 15
#(1,2) = 3
nb = 3 123
nb = 2 145
#(1,3) = 2
nb = 4 1234
nb = 1 1235
#(1,4) = 2
nb = 5 12345
#(1,5) = 1
nb = 1 12
nb = 1 13
nb = 1 23
nb = 1 14
nb = 1 24
nb = 1 34
nb = 1 15
nb = 1 25
nb = 1 35
nb = 1 45
#(2,2) = 10
nb = 3 123
nb = 3 145
nb = 2 234
nb = 2 235
#(2,3) = 4
nb = 6 1234
nb = 3 1235
nb = 1 1245
#(2,4) = 3
nb = 10 12345
#(2,5) = 1
nb = 1 123
nb = 1 124
nb = 1 134
nb = 1 234
nb = 1 125
nb = 1 135
nb = 1 235
nb = 1 145
nb = 1 245
nb = 1 345
#(3,3) = 10
nb = 4 1234
nb = 3 1235
nb = 2 1245
nb = 1 1345
#(3,4) = 4
nb = 10 12345
#(3,5) = 1
nb = 1 1234
nb = 1 1235
nb = 1 1245
nb = 1 1345
nb = 1 2345
#(4,4) = 5
nb = 5 12345
#(4,5) = 1
nb = 1 12345
#(5,5) = 1
*******************************************
n = 6
nb = 1 1
nb = 1 2
nb = 1 3
nb = 1 4
nb = 1 5
nb = 1 6
#(1,1) = 6
nb = 2 12
nb = 2 34
nb = 2 56
#(1,2) = 3
nb = 3 123
nb = 3 456
#(1,3) = 2
nb = 4 1234
nb = 2 1256
#(1,4) = 2
nb = 5 12345
nb = 1 12346
#(1,5) = 2
nb = 6 123456
#(1,6) = 1
nb = 1 12
nb = 1 13
nb = 1 23
nb = 1 14
nb = 1 24
nb = 1 34
nb = 1 15
nb = 1 25
nb = 1 35
nb = 1 45
nb = 1 16
nb = 1 26
nb = 1 36
nb = 1 46
nb = 1 56
#(2,2) = 15
nb = 3 123
nb = 3 145
nb = 3 246
nb = 3 356
nb = 1 134
nb = 1 125
nb = 1 126
#(2,3) = 7
nb = 6 1234
nb = 5 1256
nb = 4 3456
#(2,4) = 3
nb = 10 12345
nb = 4 12346
nb = 1 12356
#(2,5) = 3
nb = 15 123456
#(2,6) = 1
nb = 1 123
nb = 1 124
nb = 1 134
nb = 1 234
nb = 1 125
nb = 1 135
nb = 1 235
nb = 1 145
nb = 1 245
nb = 1 345
nb = 1 126
nb = 1 136
nb = 1 236
nb = 1 146
nb = 1 246
nb = 1 346
nb = 1 156
nb = 1 256
nb = 1 356
nb = 1 456
#(3,3) = 20
nb = 4 1234
nb = 4 1256
nb = 4 3456
nb = 2 1235
nb = 2 1245
nb = 2 1236
nb = 2 1246
#(3,4) = 7
nb = 10 12345
nb = 6 12346
nb = 3 12356
nb = 1 12456
#(3,5) = 4
nb = 20 123456
#(3,6) = 1
nb = 1 1234
nb = 1 1235
nb = 1 1245
nb = 1 1345
nb = 1 2345
nb = 1 1236
nb = 1 1246
nb = 1 1346
nb = 1 2346
nb = 1 1256
nb = 1 1356
nb = 1 2356
nb = 1 1456
nb = 1 2456
nb = 1 3456
#(4,4) = 15
nb = 5 12345
nb = 4 12346
nb = 3 12356
nb = 2 12456
nb = 1 13456
#(4,5) = 5
nb = 15 123456
#(4,6) = 1
nb = 1 12345
nb = 1 12346
nb = 1 12356
nb = 1 12456
nb = 1 13456
nb = 1 23456
#(5,5) = 6
nb = 6 123456
#(5,6) = 1
nb = 1 123456
#(6,6) = 1
*******************************************
n = 7
nb = 1 1
nb = 1 2
nb = 1 3
nb = 1 4
nb = 1 5
nb = 1 6
nb = 1 7
#(1,1) = 7
nb = 2 12
nb = 2 34
nb = 2 56
nb = 1 17
#(1,2) = 4
nb = 3 123
nb = 3 456
nb = 1 127
#(1,3) = 3
nb = 4 1234
nb = 3 1567
#(1,4) = 2
nb = 5 12345
nb = 2 12367
#(1,5) = 2
nb = 6 123456
nb = 1 123457
#(1,6) = 2
nb = 7 1234567
#(1,7) = 1
nb = 1 12
nb = 1 13
nb = 1 23
nb = 1 14
nb = 1 24
nb = 1 34
nb = 1 15
nb = 1 25
nb = 1 35
nb = 1 45
nb = 1 16
nb = 1 26
nb = 1 36
nb = 1 46
nb = 1 56
nb = 1 17
nb = 1 27
nb = 1 37
nb = 1 47
nb = 1 57
nb = 1 67
#(2,2) = 21
nb = 3 123
nb = 3 145
nb = 3 246
nb = 3 356
nb = 3 347
nb = 3 257
nb = 3 167
#(2,3) = 7
nb = 6 1234
nb = 6 1567
nb = 4 2356
nb = 3 2347
nb = 2 1456
#(2,4) = 5
nb = 10 12345
nb = 7 12367
nb = 4 14567
#(2,5) = 3
nb = 15 123456
nb = 5 123457
nb = 1 123467
#(2,6) = 3
nb = 21 1234567
#(2,7) = 1
nb = 1 123
nb = 1 124
nb = 1 134
nb = 1 234
nb = 1 125
nb = 1 135
nb = 1 235
nb = 1 145
nb = 1 245
nb = 1 345
nb = 1 126
nb = 1 136
nb = 1 236
nb = 1 146
nb = 1 246
nb = 1 346
nb = 1 156
nb = 1 256
nb = 1 356
nb = 1 456
nb = 1 127
nb = 1 137
nb = 1 237
nb = 1 147
nb = 1 247
nb = 1 347
nb = 1 157
nb = 1 257
nb = 1 357
nb = 1 457
nb = 1 167
nb = 1 267
nb = 1 367
nb = 1 467
nb = 1 567
#(3,3) = 35
nb = 4 1234
nb = 4 1256
nb = 4 3456
nb = 4 1357
nb = 4 2457
nb = 4 2367
nb = 4 1467
nb = 1 1235
nb = 1 1245
nb = 1 1236
nb = 1 1246
nb = 1 1237
nb = 1 1347
nb = 1 1567
#(3,4) = 14
nb = 10 12345
nb = 9 12367
nb = 8 14567
nb = 4 23456
nb = 4 23457
#(3,5) = 5
nb = 20 123456
nb = 10 123457
nb = 4 123467
nb = 1 123567
#(3,6) = 4
nb = 35 1234567
#(3,7) = 1
nb = 1 1234
nb = 1 1235
nb = 1 1245
nb = 1 1345
nb = 1 2345
nb = 1 1236
nb = 1 1246
nb = 1 1346
nb = 1 2346
nb = 1 1256
nb = 1 1356
nb = 1 2356
nb = 1 1456
nb = 1 2456
nb = 1 3456
nb = 1 1237
nb = 1 1247
nb = 1 1347
nb = 1 2347
nb = 1 1257
nb = 1 1357
nb = 1 2357
nb = 1 1457
nb = 1 2457
nb = 1 3457
nb = 1 1267
nb = 1 1367
nb = 1 2367
nb = 1 1467
nb = 1 2467
nb = 1 3467
nb = 1 1567
nb = 1 2567
nb = 1 3567
nb = 1 4567
#(4,4) = 35
nb = 5 12345
nb = 5 12367
nb = 5 14567
nb = 4 23456
nb = 4 23457
nb = 3 12467
nb = 3 13467
nb = 3 12567
nb = 3 13567
#(4,5) = 9
nb = 15 123456
nb = 10 123457
nb = 6 123467
nb = 3 123567
nb = 1 124567
#(4,6) = 5
nb = 35 1234567
#(4,7) = 1
nb = 1 12345
nb = 1 12346
nb = 1 12356
nb = 1 12456
nb = 1 13456
nb = 1 23456
nb = 1 12347
nb = 1 12357
nb = 1 12457
nb = 1 13457
nb = 1 23457
nb = 1 12367
nb = 1 12467
nb = 1 13467
nb = 1 23467
nb = 1 12567
nb = 1 13567
nb = 1 23567
nb = 1 14567
nb = 1 24567
nb = 1 34567
#(5,5) = 21
nb = 6 123456
nb = 5 123457
nb = 4 123467
nb = 3 123567
nb = 2 124567
nb = 1 134567
#(5,6) = 6
nb = 21 1234567
#(5,7) = 1
nb = 1 123456
nb = 1 123457
nb = 1 123467
nb = 1 123567
nb = 1 124567
nb = 1 134567
nb = 1 234567
#(6,6) = 7
nb = 7 1234567
#(6,7) = 1
nb = 1 1234567
#(7,7) = 1
--
zwim.
Rien n'est impossible que la mesure de la volonté humaine...
>Bonjour
>
>Voici un problème qu'on m'a posé et sur lequel je sèche...
>
>Soit E un ensemble de cardinal n.
>
>Soit p cardinal p. On sait que Card F = C(n,p)
>
>Soit p de cardinal k. On sait que Card G = C(n,k)
>
>Question :
>
>Comment construire H, sous-ensemble de G, tel que
>tout élément F soit inclus dans au moins un élément de
>H et tel que Card H soit le plus petit possible ?
>Que vaut Card H ?
>
>Merci,
>Pierre
>
J'ai remis un peu le nez dans ce problème, mais je ne trouve pas de
formule explicite.
Pour m'aider j'ai fait un petit programme qui fait les dénombrements
pour moi, en espérant que cela me donne un idée théorique...
Voici ce à quoi je suis parvenu pour le moment :
*******************************************
n = 1
nb = 1 1
#(1,1) = 1
*******************************************
n = 2
nb = 1 1
nb = 1 2
#(1,1) = 2
nb = 2 12
#(1,2) = 1
nb = 1 12
#(2,2) = 1
*******************************************
n = 3
nb = 1 1
nb = 1 2
nb = 1 3
#(1,1) = 3
nb = 2 12
nb = 1 13
#(1,2) = 2
nb = 3 123
#(1,3) = 1
nb = 1 12
nb = 1 13
nb = 1 23
#(2,2) = 3
nb = 3 123
#(2,3) = 1
nb = 1 123
#(3,3) = 1
*******************************************
n = 4
nb = 1 1
nb = 1 2
nb = 1 3
nb = 1 4
#(1,1) = 4
nb = 2 12
nb = 2 34
#(1,2) = 2
nb = 3 123
nb = 1 124
#(1,3) = 2
nb = 4 1234
#(1,4) = 1
nb = 1 12
nb = 1 13
nb = 1 23
nb = 1 14
nb = 1 24
nb = 1 34
#(2,2) = 6
nb = 3 123
nb = 2 124
nb = 1 134
#(2,3) = 3
nb = 6 1234
#(2,4) = 1
nb = 1 123
nb = 1 124
nb = 1 134
nb = 1 234
#(3,3) = 4
nb = 4 1234
#(3,4) = 1
nb = 1 1234
#(4,4) = 1
*******************************************
n = 5
nb = 1 1
nb = 1 2
nb = 1 3
nb = 1 4
nb = 1 5
#(1,1) = 5
nb = 2 12
nb = 2 34
nb = 1 15
#(1,2) = 3
nb = 3 123
nb = 2 145
#(1,3) = 2
nb = 4 1234
nb = 1 1235
#(1,4) = 2
nb = 5 12345
#(1,5) = 1
nb = 1 12
nb = 1 13
nb = 1 23
nb = 1 14
nb = 1 24
nb = 1 34
nb = 1 15
nb = 1 25
nb = 1 35
nb = 1 45
#(2,2) = 10
nb = 3 123
nb = 3 145
nb = 2 234
nb = 2 235
#(2,3) = 4
nb = 6 1234
nb = 3 1235
nb = 1 1245
#(2,4) = 3
nb = 10 12345
#(2,5) = 1
nb = 1 123
nb = 1 124
nb = 1 134
nb = 1 234
nb = 1 125
nb = 1 135
nb = 1 235
nb = 1 145
nb = 1 245
nb = 1 345
#(3,3) = 10
nb = 4 1234
nb = 3 1235
nb = 2 1245
nb = 1 1345
#(3,4) = 4
nb = 10 12345
#(3,5) = 1
nb = 1 1234
nb = 1 1235
nb = 1 1245
nb = 1 1345
nb = 1 2345
#(4,4) = 5
nb = 5 12345
#(4,5) = 1
nb = 1 12345
#(5,5) = 1
*******************************************
n = 6
nb = 1 1
nb = 1 2
nb = 1 3
nb = 1 4
nb = 1 5
nb = 1 6
#(1,1) = 6
nb = 2 12
nb = 2 34
nb = 2 56
#(1,2) = 3
nb = 3 123
nb = 3 456
#(1,3) = 2
nb = 4 1234
nb = 2 1256
#(1,4) = 2
nb = 5 12345
nb = 1 12346
#(1,5) = 2
nb = 6 123456
#(1,6) = 1
nb = 1 12
nb = 1 13
nb = 1 23
nb = 1 14
nb = 1 24
nb = 1 34
nb = 1 15
nb = 1 25
nb = 1 35
nb = 1 45
nb = 1 16
nb = 1 26
nb = 1 36
nb = 1 46
nb = 1 56
#(2,2) = 15
nb = 3 123
nb = 3 145
nb = 3 246
nb = 3 356
nb = 1 134
nb = 1 125
nb = 1 126
#(2,3) = 7
nb = 6 1234
nb = 5 1256
nb = 4 3456
#(2,4) = 3
nb = 10 12345
nb = 4 12346
nb = 1 12356
#(2,5) = 3
nb = 15 123456
#(2,6) = 1
nb = 1 123
nb = 1 124
nb = 1 134
nb = 1 234
nb = 1 125
nb = 1 135
nb = 1 235
nb = 1 145
nb = 1 245
nb = 1 345
nb = 1 126
nb = 1 136
nb = 1 236
nb = 1 146
nb = 1 246
nb = 1 346
nb = 1 156
nb = 1 256
nb = 1 356
nb = 1 456
#(3,3) = 20
nb = 4 1234
nb = 4 1256
nb = 4 3456
nb = 2 1235
nb = 2 1245
nb = 2 1236
nb = 2 1246
#(3,4) = 7
nb = 10 12345
nb = 6 12346
nb = 3 12356
nb = 1 12456
#(3,5) = 4
nb = 20 123456
#(3,6) = 1
nb = 1 1234
nb = 1 1235
nb = 1 1245
nb = 1 1345
nb = 1 2345
nb = 1 1236
nb = 1 1246
nb = 1 1346
nb = 1 2346
nb = 1 1256
nb = 1 1356
nb = 1 2356
nb = 1 1456
nb = 1 2456
nb = 1 3456
#(4,4) = 15
nb = 5 12345
nb = 4 12346
nb = 3 12356
nb = 2 12456
nb = 1 13456
#(4,5) = 5
nb = 15 123456
#(4,6) = 1
nb = 1 12345
nb = 1 12346
nb = 1 12356
nb = 1 12456
nb = 1 13456
nb = 1 23456
#(5,5) = 6
nb = 6 123456
#(5,6) = 1
nb = 1 123456
#(6,6) = 1
*******************************************
n = 7
nb = 1 1
nb = 1 2
nb = 1 3
nb = 1 4
nb = 1 5
nb = 1 6
nb = 1 7
#(1,1) = 7
nb = 2 12
nb = 2 34
nb = 2 56
nb = 1 17
#(1,2) = 4
nb = 3 123
nb = 3 456
nb = 1 127
#(1,3) = 3
nb = 4 1234
nb = 3 1567
#(1,4) = 2
nb = 5 12345
nb = 2 12367
#(1,5) = 2
nb = 6 123456
nb = 1 123457
#(1,6) = 2
nb = 7 1234567
#(1,7) = 1
nb = 1 12
nb = 1 13
nb = 1 23
nb = 1 14
nb = 1 24
nb = 1 34
nb = 1 15
nb = 1 25
nb = 1 35
nb = 1 45
nb = 1 16
nb = 1 26
nb = 1 36
nb = 1 46
nb = 1 56
nb = 1 17
nb = 1 27
nb = 1 37
nb = 1 47
nb = 1 57
nb = 1 67
#(2,2) = 21
nb = 3 123
nb = 3 145
nb = 3 246
nb = 3 356
nb = 3 347
nb = 3 257
nb = 3 167
#(2,3) = 7
nb = 6 1234
nb = 6 1567
nb = 4 2356
nb = 3 2347
nb = 2 1456
#(2,4) = 5
nb = 10 12345
nb = 7 12367
nb = 4 14567
#(2,5) = 3
nb = 15 123456
nb = 5 123457
nb = 1 123467
#(2,6) = 3
nb = 21 1234567
#(2,7) = 1
nb = 1 123
nb = 1 124
nb = 1 134
nb = 1 234
nb = 1 125
nb = 1 135
nb = 1 235
nb = 1 145
nb = 1 245
nb = 1 345
nb = 1 126
nb = 1 136
nb = 1 236
nb = 1 146
nb = 1 246
nb = 1 346
nb = 1 156
nb = 1 256
nb = 1 356
nb = 1 456
nb = 1 127
nb = 1 137
nb = 1 237
nb = 1 147
nb = 1 247
nb = 1 347
nb = 1 157
nb = 1 257
nb = 1 357
nb = 1 457
nb = 1 167
nb = 1 267
nb = 1 367
nb = 1 467
nb = 1 567
#(3,3) = 35
nb = 4 1234
nb = 4 1256
nb = 4 3456
nb = 4 1357
nb = 4 2457
nb = 4 2367
nb = 4 1467
nb = 1 1235
nb = 1 1245
nb = 1 1236
nb = 1 1246
nb = 1 1237
nb = 1 1347
nb = 1 1567
#(3,4) = 14
nb = 10 12345
nb = 9 12367
nb = 8 14567
nb = 4 23456
nb = 4 23457
#(3,5) = 5
nb = 20 123456
nb = 10 123457
nb = 4 123467
nb = 1 123567
#(3,6) = 4
nb = 35 1234567
#(3,7) = 1
nb = 1 1234
nb = 1 1235
nb = 1 1245
nb = 1 1345
nb = 1 2345
nb = 1 1236
nb = 1 1246
nb = 1 1346
nb = 1 2346
nb = 1 1256
nb = 1 1356
nb = 1 2356
nb = 1 1456
nb = 1 2456
nb = 1 3456
nb = 1 1237
nb = 1 1247
nb = 1 1347
nb = 1 2347
nb = 1 1257
nb = 1 1357
nb = 1 2357
nb = 1 1457
nb = 1 2457
nb = 1 3457
nb = 1 1267
nb = 1 1367
nb = 1 2367
nb = 1 1467
nb = 1 2467
nb = 1 3467
nb = 1 1567
nb = 1 2567
nb = 1 3567
nb = 1 4567
#(4,4) = 35
nb = 5 12345
nb = 5 12367
nb = 5 14567
nb = 4 23456
nb = 4 23457
nb = 3 12467
nb = 3 13467
nb = 3 12567
nb = 3 13567
#(4,5) = 9
nb = 15 123456
nb = 10 123457
nb = 6 123467
nb = 3 123567
nb = 1 124567
#(4,6) = 5
nb = 35 1234567
#(4,7) = 1
nb = 1 12345
nb = 1 12346
nb = 1 12356
nb = 1 12456
nb = 1 13456
nb = 1 23456
nb = 1 12347
nb = 1 12357
nb = 1 12457
nb = 1 13457
nb = 1 23457
nb = 1 12367
nb = 1 12467
nb = 1 13467
nb = 1 23467
nb = 1 12567
nb = 1 13567
nb = 1 23567
nb = 1 14567
nb = 1 24567
nb = 1 34567
#(5,5) = 21
nb = 6 123456
nb = 5 123457
nb = 4 123467
nb = 3 123567
nb = 2 124567
nb = 1 134567
#(5,6) = 6
nb = 21 1234567
#(5,7) = 1
nb = 1 123456
nb = 1 123457
nb = 1 123467
nb = 1 123567
nb = 1 124567
nb = 1 134567
nb = 1 234567
#(6,6) = 7
nb = 7 1234567
#(6,7) = 1
nb = 1 1234567
#(7,7) = 1
--
zwim.
Rien n'est impossible que la mesure de la volonté humaine...
Re: Dénombrement difficile - denombrement.c (0/1)
par Anonyme » 30 Avr 2005, 17:14
Le Thu, 27 May 2004 02:44:47 +0200, zwim à écrit
>Pour m'aider j'ai fait un petit programme qui fait les dénombrements
http://perso.wanadoo.fr/zwim/pub/C/denombrement.c
--
zwim.
Rien n'est impossible que la mesure de la volonté humaine...
>Pour m'aider j'ai fait un petit programme qui fait les dénombrements
http://perso.wanadoo.fr/zwim/pub/C/denombrement.c
--
zwim.
Rien n'est impossible que la mesure de la volonté humaine...
Re: Dénombrement difficile - denombrement.c (0/1)
par Anonyme » 30 Avr 2005, 17:14
Cela a l'air intéressant mais comme je ne suis
pas très fort en informatique (je suis même
totalement inculte) pourrais-tu STP me dire
comment lire le tableau ?
Merci
Pierre
pas très fort en informatique (je suis même
totalement inculte) pourrais-tu STP me dire
comment lire le tableau ?
Merci
Pierre
Re: Dénombrement difficile - denombrement.c (0/1)
par Anonyme » 30 Avr 2005, 17:15
Le Thu, 27 May 2004 15:24:29 +0100, Pierre Capdevila à écrit
>Cela a l'air intéressant mais comme je ne suis
>pas très fort en informatique (je suis même
>totalement inculte) pourrais-tu STP me dire
>comment lire le tableau ?
>
>Merci
>Pierre
>
Rappel :
E l'ensemble de cardinal n.
F l'ensemble des parties de E de cardinal p = p.
Question :
Comment construire H, sous-ensemble de G, tel que
tout élément F soit inclus dans au moins un élément de
H et tel que Card H soit le plus petit possible ?
Que vaut Card H ?
>*******************************************
>n = 4
On prend l'ensemble de départ E = {1,2,3,4}
> nb = 1 1
> nb = 1 2
> nb = 1 3
> nb = 1 4
Sur la colonne de droite les éléments de G qui composent H.
Sour la colonne de gauche, le nombre d'éléments de F (restants)
contenus dans cet élément de G.
>#(1,1) = 4
Je note CardH = #(p,k)
Ici si F est l'ensemble des parties de E à 1 élément et G aussi.
F = G = {{1},{2},{3},{4}}
> nb = 3 123
> nb = 2 124
> nb = 1 134
>#(2,3) = 3
Prenons un exemple plus concret
n=4 E = {1,2,3,4}
p=2 F = {12,13,14,23,24,34}
k=3 G = {123,124,134,234}
On choisit l'élémént de G = 123, qui contient les éléments 12,13,23 de
F, soit nb = 3 éléments.
Il reste alors dans F les éléments 14,24,34
On choisit ensuite l'élémént de G = 124, qui contient les éléments
14,24 de F, soit nb = 2 éléments.
Il reste alors dans F l'élément 34
On choisit enfin l'élémént de G = 134, qui contient l'élément 34 de F,
soit nb = 1 élément.
On a réussi à trouver H={123,124,134} de cardinal 3, qui contient tous
les éléments de F.
>*******************************************
En gros mon algo fait ceci.
Pour n,p,k donnés, je calcule E,F,G.
Je prend le premier élément disponible (non déjà utilisé) de G, qui
maximise le nombre d'éléments de F disponibles que l'on peut inclure
dedans. Je marque les éléments de F et de G utilisés comme
indisponibles et je continue.
Je pense que l'on obtient ainsi un H optimal que j'affiche avec son
cardinal.
--
zwim.
Rien n'est impossible que la mesure de la volonté humaine...
>Cela a l'air intéressant mais comme je ne suis
>pas très fort en informatique (je suis même
>totalement inculte) pourrais-tu STP me dire
>comment lire le tableau ?
>
>Merci
>Pierre
>
Rappel :
E l'ensemble de cardinal n.
F l'ensemble des parties de E de cardinal p = p.
Question :
Comment construire H, sous-ensemble de G, tel que
tout élément F soit inclus dans au moins un élément de
H et tel que Card H soit le plus petit possible ?
Que vaut Card H ?
>*******************************************
>n = 4
On prend l'ensemble de départ E = {1,2,3,4}
> nb = 1 1
> nb = 1 2
> nb = 1 3
> nb = 1 4
Sur la colonne de droite les éléments de G qui composent H.
Sour la colonne de gauche, le nombre d'éléments de F (restants)
contenus dans cet élément de G.
>#(1,1) = 4
Je note CardH = #(p,k)
Ici si F est l'ensemble des parties de E à 1 élément et G aussi.
F = G = {{1},{2},{3},{4}}
> nb = 3 123
> nb = 2 124
> nb = 1 134
>#(2,3) = 3
Prenons un exemple plus concret
n=4 E = {1,2,3,4}
p=2 F = {12,13,14,23,24,34}
k=3 G = {123,124,134,234}
On choisit l'élémént de G = 123, qui contient les éléments 12,13,23 de
F, soit nb = 3 éléments.
Il reste alors dans F les éléments 14,24,34
On choisit ensuite l'élémént de G = 124, qui contient les éléments
14,24 de F, soit nb = 2 éléments.
Il reste alors dans F l'élément 34
On choisit enfin l'élémént de G = 134, qui contient l'élément 34 de F,
soit nb = 1 élément.
On a réussi à trouver H={123,124,134} de cardinal 3, qui contient tous
les éléments de F.
>*******************************************
En gros mon algo fait ceci.
Pour n,p,k donnés, je calcule E,F,G.
Je prend le premier élément disponible (non déjà utilisé) de G, qui
maximise le nombre d'éléments de F disponibles que l'on peut inclure
dedans. Je marque les éléments de F et de G utilisés comme
indisponibles et je continue.
Je pense que l'on obtient ainsi un H optimal que j'affiche avec son
cardinal.
--
zwim.
Rien n'est impossible que la mesure de la volonté humaine...
11 messages
- Page 1 sur 1
Qui est en ligne
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 2 invités
Tu pars déja ?
Fais toi aider gratuitement sur Maths-forum !
Créé un compte en 1 minute et pose ta question dans le forum ;-)
Identification
Pas encore inscrit ?
Ou identifiez-vous :