Multiset naar set om cardinality terug te krijgen?

[wacco]

Nouja, de titel zegt het al nietwaar?*

Laat ik eerst even m'n probleem verwoorden. Ik heb voor een theorietje waar ik aan het klussen ben in feite dit nodig; Je hebt n vakken en x kleuren, elk vak kan elke kleur aannemen. Uit alle mogelijke combinaties, hoe vaak zijn er i kleuren aanwezig?

En ik wil dit dus wiskundig/formeel net definiëren. Omdat programmeren me toch wel een stuk beter af gaat heb ik het even gisteravond uitgetikt in C, voor code zie hier: http://metadirc.nl/MetaBin/show/284
Dit geeft bijvoorbeeld:

eve:~/Desktop$ ./math 7 4
 4 buckets the same: 7
 3 buckets the same: 294
 2 buckets the same: 1260
No buckets the same: 840
Num of combinations: 2401

Ik wil dit definiëren als iets ala f(i, n, x) die ik dan weer in andere formules kan plakken, maar ik heb niet echt een idee hoe dit te doen. M'n idee was om alle mogelijke combinaties te zien als een multiset, dan de cardinality van de onderliggende set te nemen, en dan tellen hoe vaak die cardinality overeenkomt met i over alle mogelijkheden. Dit is in feite wat m'n code ook doet en ik zie niet 123 een andere 'nette' (we gaan het maar niet over big O hebben) manier.

Dus, ehm,
Alle mogelijke combinaties (is hier een symbool voor? Ik wou U zeggen, maar zie verder) -> (A, m) waar |A| = n
Is er iets ala N^x misschien? Wikipedia heeft het over de universe voor A welke gedefinieerd moet zijn zodat m : U -> N ipv m : A -> N_≥1 kan, maar ik wil niet alle N, maar slechts 0 t/m x en een universe van n dan, volgens mij.
En dan f(i, n, x) = ∑ (van 1 t/m |U|) waar ehh, ik heb werkelijk geen idee. de |A| == i tellen?

Zoals je ziet is deze tak van de wiskunde nog niet echt m'n sterkste kant en zit ik een beetje vast. Iemand suggesties?

*Volgens mij klopt de titel dus niet helemaal maar geen clue wat het wel moet zijn, als ik dat wist, was dit topic niet nodig.

[Pooh]

Ik snap je voorbeeld niet, en ik snap ook niet waarom je zo ingewikkeld doet. Gaat je voorbeeld over 7 emmers en 4 kleuren, of over 4 emmers en 7 kleuren?

Neem het 2e geval: 4 vakken, 7 kleuren.

Aantal mogelijkheden met 1 kleur: 4^1 * (7!/1!6!) = 28
Aantal mogelijkheden met 2 kleuren: 4^2 * (7!/2!5!) = 336
Aantal mogelijkheden met 3 kleuren: 4^3 * (7!/3!4!) = 2240
Aantal mogelijkheden met 4 kleuren: 4^4 * (7!/4!3!) = 8960

[wacco]

M'n voorbeeld was 4 vakken, 7 kleuren.

En ik doe misschien wel te ingewikkeld, maar dat is dan omdat ik geen idee heb hoe ik het goed zou moeten aanpakken.

Jou getallen lijken me een beetje onmogelijk. Hoe kan je met het gebruiken van 1 kleur, en het hebben van 7 kleuren, 28 verschillende invullingen hebben? Verder heb je met 4 vakken dus 7⁴ mogelijke combinaties, dus je kan ook niet boven de 2401 komen. Lang verhaal kort; ik snap niet wat je formule probeert te doen.

[Pooh]

.

[ Voor 96% gewijzigd door Pooh op 07-10-2009 14:38 . Reden: oeps ]

[Pooh]

Verder heb je gelijk, ik zit te slapen.

Mijn redenering was:

(zie Wikipedia: Binomiaalcoëfficiënt)
Aantal manieren om 1 kleur uit 7 te kiezen: (7!/1!6!) = 7
Aantal manieren om 2 kleuren uit 7 te kiezen: (7!/2!5!) = 21
Aantal manieren om 3 kleuren uit 7 te kiezen: (7!/3!4!) = 35
Aantal manieren om 4 kleuren uit 7 te kiezen: (7!/4!3!) = 35

Aantal manieren om 4 vakken te vullen met 1 kleur = 1
Aantal manieren om 4 vakken te vullen met exact 2 kleuren: 14 *
Aantal manieren om 4 vakken te vullen met exact 3 kleuren = 36 *
Aantal manieren om 4 vakken te vullen met exact 4 kleuren = 4! = 24

Combinerend:
totaal 1 kleur = 7 * 1 = 7
totaal 2 kleuren = 21 * 14 = 294
totaal 3 kleuren = 35 * 36 = 1260
totaal 4 kleuren = 35 * 24 = 840

Aangepast. Weet even niet hoe je die * handig berekent.

[ Voor 18% gewijzigd door Pooh op 07-10-2009 15:01 ]

[Verwijderd]

K(a) = { k ∈ ℕ | k>0 ∧ k≤a }
C(n, a) = K(a)ⁿ
f(i, n, a) = |{ c ∈ C(n, a) | ∀x∈K(a)( (cₓ=c₁ ∧ x<i) ∨ (cₓ≠c₁ ∧ x>i) ) }|

[wacco]

Je hebt 4 buckets, dus de eerste pakt een kleur van de 7, dan de tweede eentje uit de 7, etc. Je krijgt dus 7 mogelijkheden x 7 mogelijkheden ... ofwel 7^4. Niet andersom.

Dat binomiaalcoëfficiënt is wel een interessante aanpak, vroeger wel eens gehad volgens mij. Maar van de wikipedia pagina; uit n (verschillende) objecten er zonder terugleggen k kan kiezen. (empasis mine)
Dat gaat lastig worden volgens mij, want in mijn probleem gebeurd dat dus wel.

Verwijderd schreef op woensdag 07 oktober 2009 @ 14:55:
K(a) = { k ∈ ℕ | k>0 ∧ k≤a }
C(n, a) = K(a)ⁿ
f(i, n, a) = |{ c ∈ C(n, a) | ∀x∈K(a)( (cₓ=c₁ ∧ x<i) ∨ (cₓ≠c₁ ∧ x>i) ) }|

Zow hey, ehm. K is kleur, C is combinatie en dan die laatste regel bijt ik me nog even op stuk. Maar ziet er wel indrukwekkend uit

M'n rekenmachine zal het alleen niet begrijpen ben ik bang. Maar dat gebeurd wel vaker met dit soort wiskunde.

[Verwijderd]

Omdat wacco er naar vraagt:

Verwijderd schreef op woensdag 07 oktober 2009 @ 14:55:
K(a) = { k ∈ ℕ | k>0 ∧ k≤a }

K(a) is dus een set van natuurlijke nummers, groter dan 0, en kleiner of gelijk aan a

C(n, a) = K(a)ⁿ

C(n, a) is de set met alle mogelijke combinaties van a kleuren, met n vlakken.
Let er op dat deze set tuples bevat.

c

c is een element uit C(n, a) en dus een tuple.

c₁

c₁ is de eerste waarde uit de tuple.

cₓ

cₓ is de x-ste waarde in de tuple.

cₓ=c₁ ∧ x≤i

cₓ is gelijk aan c₁ en x is lager of gelijk aan i.
(merk op dat ik hier een fout gevonden heb in mijn originele formule)

cₓ≠c₁ ∧ x>i

cₓ is ongelijk aan c₁ en x is hoger dan i.

(cₓ=c₁ ∧ x≤i) ∨ (cₓ≠c₁ ∧ x>i)

(cₓ=c₁ ∧ x≤i) of (cₓ≠c₁ ∧ x>i), dat wil zeggen;
als x lager of gelijk is aan i dan en slechts dan als c₁ gelijk is aan cₓ
een alternatief: x≤i ↔ cₓ=c₁

∀x∈K(a)( (cₓ=c₁ ∧ x≤i) ∨ (cₓ≠c₁ ∧ x>i) )

Voor elke x in K(a) geld dat (cₓ=c₁ ∧ x≤i) ∨ (cₓ≠c₁ ∧ x>i)

{ c ∈ C(n, a) | ∀x∈K(a)( (cₓ=c₁ ∧ x≤i) ∨ (cₓ≠c₁ ∧ x>i) ) }

Dit is de set van elementen uit C(n, a) waarvoor ∀x∈K(a)( (cₓ=c₁ ∧ x≤i) ∨ (cₓ≠c₁ ∧ x>i) ) waar is.

f(i, n, a) = |{ c ∈ C(n, a) | ∀x∈K(a)( (cₓ=c₁ ∧ x≤i) ∨ (cₓ≠c₁ ∧ x>i) ) }|

Dit geeft het aantal elementen uit de hierboven genoemde set.

Merk op dat ik hier slechts controleer of c₁ gelijk is aan cₓ waarbij x lager of gelijk aan i. Dit betekent dat elke combinatie maar 1x geteld wordt. Als je de alle combinaties van de kleuren 1, 1, 2 en 2 neemt, dan telt dit 2x als dubbele combinatie, niet 4 keer.
Ik weet niet of dit is zoals de C code van wacco het ook doet.
Dit is dus eventueel een punt om verder uit te werken.

[wacco]

Verwijderd schreef op woensdag 07 oktober 2009 @ 15:43:
.snip.

[...]

Dit geeft het aantal elementen uit de hierboven genoemde set.

Merk op dat ik hier slechts controleer of c₁ gelijk is aan cₓ waarbij x lager of gelijk aan i. Dit betekent dat elke combinatie maar 1x geteld wordt. Als je de alle combinaties van de kleuren 1, 1, 2 en 2 neemt, dan telt dit 2x als dubbele combinatie, niet 4 keer.
Ik weet niet of dit is zoals de C code van wacco het ook doet.
Dit is dus eventueel een punt om verder uit te werken.

Mijn code loopt dus alle mogelijke combinaties gewoon langs, dus:

1122 1212 1221 2112 2121 2211

Tellen bijvoorbeeld allemaal mee. Ik snapte al niet helemaal wat je met c₁ van plan was, alleen vergelijken met de eerste variabele lijkt me dat je dingen als 1221 compleet overslaat.

[Verwijderd]

wacco schreef op woensdag 07 oktober 2009 @ 15:57:
[...]


Mijn code loopt dus alle mogelijke combinaties gewoon langs, dus:

1122 1212 1221 2112 2121 2211

Tellen bijvoorbeeld allemaal mee. Ik snapte al niet helemaal wat je met c₁ van plan was, alleen vergelijken met de eerste variabele lijkt me dat je dingen als 1221 compleet overslaat.

Ja, maar zo maak je het, denk ik, een beetje onduidelijk (mischien moet ik je code eens goed doorlezen).

Of 1122 en 1212 (en de andere) allebij tellen is weer een ander verhaal (waar ik nog niet bij stil had gestaan).
Eventueel kan de formule daarvoor aangepast worden met een extra kwantor.

Waar ik op doelde is, waar telt 11222 dan aan mee? 1x aan i=2, en 1x aan i=3? want dan zou 1122 ook 2x moeten tellen bij i=2, lijkt me? En dat doet mijn code dus.

[wacco]

Verwijderd schreef op woensdag 07 oktober 2009 @ 16:07:
Waar ik op doelde is, waar telt 11222 dan aan mee? 1x aan i=2, en 1x aan i=3? want dan zou 1122 ook 2x moeten tellen bij i=2, lijkt me? En dat doet mijn code dus.

1x aan i=2, want er zijn maar 2 kleuren in die combo. Het gaat om hoeveel kleuren er in een mogelijkheid staan, niet hoe vaak een kleur er in voor komt.

[Verwijderd]

wacco schreef op woensdag 07 oktober 2009 @ 16:09:
[...]

1x aan i=2, want er zijn maar 2 kleuren in die combo. Het gaat om hoeveel kleuren er in een mogelijkheid staan, niet hoe vaak een kleur er in voor komt.

Ja, zeg dat dan

Blijkbaar deed je dat ook, dus dan kan mijn formule gewoon de prullenbak in

Ik ging er een beetje blindelings vanuit dat het probleem het zelfde was als waar je gisteren over begon, maar blijkbaar had je toen al de probleemstelling voor het gemak aangepast

Ik zal me zo wagen aan een herkansing...

[Verwijderd]

K(a) = { k ∈ ℕ | k>0 ∧ k≤a }
C(n, a) = K(a)ⁿ

Deze zijn het zelfde gebleven.

o(c, n, a) = |{ k ∈ K(a) | ∃x∈ℕ( x≤n ∧ cₓ = k ) }|

Het aantal van de set van kleuren dat voor komt in de tuple c.

f(i, n, a) = |{ c ∈ C(n, a) | o(c, n, a) = i ) }|

Het aantal combinaties waarbij o(c, n, a) gelijk is aan i

[wacco]

Ja, dat lijkt idd te kloppen. Super, thanks!
Irritant altijd dat als het klopt, het plots zo simpel lijkt. Niet om je kunsten te ondermijnen verder, ik zou er dus niet op gekomen zijn.

Maar, ik heb zelf nog wat verder zitten knoeien met de oplossing van Pooh omdat die toch wat makkelijker in te kloppen is op een rekenmachine. Alleen dat stukje wat hij 'even' niet wist houd me de hele avond al bezig. M'n laatste poging;

Bij een 3 kleuren, 4 vakken hebben we aan in te vullen getallen 123 + een extra. Dan krijg je (aantal_kleuren * (aantal_kleuren * aantal_lege_vakjes_over)) mogelijke combinaties van getallen. In dit voorbeeld dus 3 * (3 * 1) = 9, bij bijvoorbeeld 2 kleuren in 4 vakken is het 4 * (2 * 2) = 8. Nu kunnen die op 4! manieren ingevuld worden in de vakken dus 9 * 4! = 216 mogelijkheden in totaal.

Enige wat rest is het aantal dubbelen eraf trekken, maar die krijg ik niet netjes gedefinieerd wat me doet denken dat ook dit weer een dood eind is. Zo moeilijk zou het toch niet moeten zijn?