Kombinatorik och Gruppkonstellationer

Var lite osäker på vilket forum jag skulle lägga tråden i, hoppas det här blir bra!

Fick en liten tanke angående kombinatorik som i alla fall vid första anblick inte verkar helt lättlöst.

Tänk att vi har p personer som vi ska dela upp i n grupper, och låt oss anta att n | p och säg m=p/n, det vill säga antalet personer per grupp. Hur många gruppkonstellationer kan vi då konstruera, så att i varje uppsättning grupper så är alla personer i grupp endast med personer de inte är i grupp med i någon annan uppsättning.

Om vi t.ex. har p=6, n=3, m=2 och vi kallar personerna för a,b,c,d,e,f så uppfyller grupperna

{a,b} {c,d} {e,f} och {a,c} {b,e} {d,f} kriteriet.

Om m>n så är svaret uppenbarligen 1, men om m<=n så tycks det inte vara så lätt. Någon som har koll på hur man kan tänkas lösa detta?

Om jag inte tänker helt fel så borde det totala antalet möjliga konstellationer vara

p!/((m!)^n * n!)

men mycket längre än så kommer jag inte.

Jag tror att det här är vad du är ute efter. http://en.wikipedia.org/wiki/Stirlin...he_second_kind

Jag tror tyvärr inte det.

Tänk att 20 personer delas upp i fem grupper med fyra i varje. Kalla grupperna A,B,C,D,E.

Sedan gör vi fem nya grupper med fyra i varje, där ingen ifrån grupp A är med någon annan i grupp A, samma med B osv. Kalla dessa grupper A2, B2, C2, ...

Sedan gör vi en tredje uppsättning av fem grupper med fyra i varje, där varje person ifrån grupp A2 inte är med någon annan ifrån grupp A2 etc. Dessutom är ingen med någon de var med i den första uppsättningen.

Min fråga är vad det maximala antalet sådana uppsättningar man kan skapa är, där alla i varje ny uppsättning inte är i samma grupp som någon de varit med i någon tidigare uppsättning.

För m=2 är svaret p - 1. Detta kan ses såhär:

Totalt finns exakt p(p-1)/2 möjliga par. Eftersom inget par får förekomma i två gruppkonstellationer, och varje gruppkonstellation innehåller p/2 par, så är antalet indelningar uppåt begränsat av (p(p-1)/2)/(p/2), vilket är just p-1.

Å andra sidan kan man få p-1 konstellationer, genom att använda konstruktionen här.

Vidare, om m=n så är svaret m+1. Detta inses om man tänker sig en matris av deltagare:

a1 a2 a3 a4
b1 b2 b3 b4
c1 c2 c3 c4
d1 d2 d3 d4

Om vi kallar A={a1 a2 a3 a4} B={b1 b2 b3 b4} etc. för konstellation 1 så gäller för alla andra konstellationer att de måste innehålla exakt en person ifrån varje rad. Person a1 kan "välja" fyra olika personer i rad b. Det leder till fyra till möjliga konstellationer; en där alla är med de med samma siffra ({a1 b1 c1 d1} {a2 b2 c2 d2} ...) en där alla är med de med en siffra högre, ända upp till tre siffror högre.

Jag har inte kommit på något generellt sätt att utvidga detta till n>m dock.

Jag förstår itne riktigt. Den andra är konstellationen är

{a1 b1 c1 d1} {a2 b2 c2 d2} {a3 b3 c3 d3} {a4 b4 c4 d4}

Den tredje är, om jag har förstått dig rätt,

{a1 b2 c3 d4} {a2 b3 c4 d1} {a3 b4 c1 d2} {a4 b1 c2 d3}.

Vilka skulle de fjärde och femte konstellationerna vara?

Jag tänkte galet, menade att den fjärde skulle vara {a1 b3 c1 d3} etc. vilket såklart inte fungerar eftersom den största gemensamma delaren hos 4 och 2 är 2. Den "femte" skulle däremot vara

{a1 b4 c3 d2} {a2 b1 c4 d3} {a3 b2 c1 d4} {a4 b3 c2 d1}

Kan det vara så att svaret då m=n är

"antalet tal vars största gemensamme delare med m är 1" + 1?

Snart får jag ta och skriva ett program som tar reda på svaret för specifika värden och se om man kan hitta ett mönster!

C(20,4)*C(16,4)*C(12,4)*C(8,4)*C(4,4)

Nu är du nog ute och cyklar är jag rädd, läs vad jag skrev en gång till.

Du har rätt, hade inte förstått frågan rätt, och tänkte onödigt komplicerat.

Snarare för simpelt, menar du väl? Eller har du något lösningsförslag?

p = antal personer
m = antal i gruppen
n = antal grupper; n * m = p
Varje person kan höra till ( p - 1 ) / ( m - 1 ) grupper.
Möjliga grupper ( p - 1 ) / ( m - 1 ) * p / m
Möjliga konstellationer ( p - 1 ) / ( m - 1 ) * p / m / n = ( p - 1 ) / ( m - 1 )
Om p = 16, m = 4. Blir 5 möjliga konstellationer.
Om antalet är stora kan det bli lite knepigt att få ihop konstellationerna, men antalet är lätt att räkna.

Gjorde snabbt ett förslag, hoppas det blev rätt.

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

1 14 11 8
5 2 15 12
9 6 3 16
13 10 7 4

1 10 7 16
5 14 11 4
9 2 15 8
13 6 3 12

1 6 15 12
5 10 3 16
9 14 7 4
13 2 11 8

1 5 9 13
6 10 14 2
15 3 7 11
12 16 4 8