In cate moduri pot trece 6 cai linia de sosire? Trebuie precizat ca doi sau mai multi cai pot termina la egalitate pe acelasi loc.

Sper sa nu ma insel la ora asta, dar cred ca are legatura cu

Nu inteleg din pacate structura ce ne face sa scriem cele de mai sus.

Scriu C(k,n) pentru n! / (k!(n-k)!)
Caii ii numerotez cu 1,2,3,4,5,6.

Suma de mai sus are termenii:

6! C(5,5) = 6! si banuiesc ca numara fiecare finish in care nu sunt doi cai ce termina simultan. Pur si simplu luam permutarile multimii cailor.
De exemplu 362145 este o ordine posibila. (Calul 3 castiga.)

Restul termenilor nu stiu de unde vin...

O solutie "foarte enumerativa" este urmatoarea.
Exista urmatoarele moduri de a-l partitiona pe 6:

1+1+1+1+1+1
1+1+1+1+2
1+1+2+2
2+2+2
1+1+1+3
1+2+3
3+3
1+1+4
2+4
5+1
6

Pentru fiecare din aceste partitii calculam explicit numarul de "finish"-uri posibile, in care grupele de cai situate pe acelasi loc au cardinalitati termeni din sumele de mai sus, intr-o ordine obtinuta dupa rearanjarea termenilor.

Iau cazurile pe rand:

1+1+1+1+1+1 : Cei sase cai termina pe locuri diferite, nu exista cai ce trec linia de sosire in acelasi timp. Avem 6! posibilitati.

1+1+1+1+2 = 1+1+1+2+1 = 1+1+2+1+1 = 1+2+1+1+1 = 2+1+1+1+1+1 .
Avem 5 posibilitati de aranjare a sumei.
Sa zicem ca ne legam de prima. 1+1+1+1+2.
Luam o permutare la intamplare a numerelor 1,2,3,4,5,6, sa zicem ca este (fara virgule)
abcdef
si plasam caii la sosire astfel:
[ a ] [ b ] [ c ] [ d ] [ e f ]

(e,f au ajuns simultan pe ultimul loc la linia de sosire.)
Desigur ca trebuie sa "identificam" (numaram o singura data) cazurile
[ a ] [ b ] [ c ] [ d ] [ e f ]
[ a ] [ b ] [ c ] [ d ] [ f e ]

Dam atunci de
5 . 6! / 2! moduri diferite de alegere a unui finish in care exact doi cai ajung simultan in finish.

1+1+2+2 = 1+2+1+2 = 2+1+1+2 = 1+2+2+1 = 2+1+2+1 = 2+2+1+1
In primul caz luam o permutare arbitrara abcdef, plasam literele in ordine in "boxele" de sosire
[ x ] [ x ] [ x x ] [ x x ]
si obtinem ceva de forma
[ a ] [ b ] [ c d ] [ e f ]
dar desigur ca aceeasi constelatie de sosire este obtinuta daca permutam in boxe.
Dam atunci de
6 . 6! / (2!2!) moduri diferite de alegere a unui finish in care exact doua grupe de doi cai ajung simultan in finish.

2+2+2 . Dam de 1 . 6! / (2!2!2!) moduri de plasare.

1+1+1+3 = 1+1+3+1 = 1+3+1+1 = 3+1+1+1 .
Dam de 4 . 6! / 3! moduri de plasare.

1+2+3 = ... Avem 3!=6 moduri de schimbat termenii intre ei.
Dam de 3! . 6! / (2!3!) moduri de plasare.

3+3 . Dam de 1 . 6! / (3!3!) moduri de plasare.

1+1+4 = 1+4+1 = 4+1+1 .
Dam de 3 . 6! / 4! moduri de plasare.

2+4 = 4+2 .
Dam de 2 . 6! / (2!4!) moduri de plasare.

1+5 = 5+1 .
Dam de 2 . 6! / 5! moduri de plasare.

6 .
Dam de 1 . 6! / 6! , un mod de plasare.

Mai ramane sa adunam.
Daca nu vedem nici un fel de alta structura, trebuie sa ne declaram cu aceasta schema de numarare.

Eu am obtinut astfel:
6! ( 1 + 5/2! + 6/(2!2!) + 1/(2!2!2!) + 4/3! + 3!/(2!3!) + 1/(3!3!) + 3/4! + 2/(2!4!) + 2/5! + 1/6! ) .

Acest numar este:
(22:42) gp > 6! * ( 1 + 5/2! + 6/(2!*2!) + 1/(2!*2!*2!) + 4/3! + 3!/(2!*3!) + 1/(3!*3!) + 3/4! + 2/(2!*4!) + 2/5! + 1/6! )
%33 = 4683

Probabil ca am gresit pe undeva.
Acasa caut o solutie mai structurala, trebuie sa trimit si sa plec...

M-am gandit in felul urmator:
Avem sase cai, cu 5 "spatii intre ei".
Daca toti termina pe primul loc, atunci nu punem "nicio bara" in acele "spatii" pentru a-i separa, si astfel am format o multime.
Daca unii termina pe primul loc si altii pe al doilea, trebuie sa punem o singura "bara" in unul dintre cele 5 spatii. Exista C(5,1) moduri de a pune acea bara. Am format doua multimi, pe care la putem pune in alta ordine (in 2! feluri).
Si rationamentul continua.
Este un fel de a partitiona multimea, dar ordinea multimilor sa conteze.
Sper ca in procedand in aceasta maniera numaram toate posibilitatile cailor de a termina.

Imi cer scuze ca intreb, dar ce cazuri le numar de mai multe ori sau nu le numar deloc?
Multumesc.

[Citat] M-am gandit in felul urmator: Avem sase cai, cu 5 "spatii intre ei". Daca toti termina pe primul loc, atunci nu punem "nicio bara" in acele "spatii" pentru a-i separa, si astfel am format o multime. Daca unii termina pe primul loc si altii pe al doilea, trebuie sa punem o singura "bara" in unul dintre cele 5 spatii. Exista C(5,1) moduri de a pune acea bara. Am format doua multimi, pe care la putem pune in alta ordine (in 2! feluri). Si rationamentul continua. Este un fel de a partitiona multimea, dar ordinea multimilor sa conteze. Sper ca in procedand in aceasta maniera numaram toate posibilitatile cailor de a termina.

S? numerot?m caii. Atunci 12|3456 înseamn? c? au sosit simultan pe primul loc caii 1 ?i 2, iar 3,4,5,6 au sosit simultan pe locul 2. Unde pune?i "bara" dac? sosesc simultan pe primul loc caii 1 ?i 3?

Se pare ca am omis acele cazuri. Ma scuzati.

Atunci daca spun:

[Citat] Atunci daca spun:

Este foarte aproape de formula recursiva de mai sus, in care "spargem" combinatorica si ne legam de posibilitatea de alegere a primului grup de cai, urmata de inmultirea cu plasarile pe locurile ce urmeaza, pe care presupunem ca am calculat-o (inductiv) deja.

Pe de alta parte, scriind k1+k2+... = 6 si evitand recursiunea dam de solutia foarte enumerativa de mai sus, chiar am luat la mana toate aceste posibilitati de a-l scrie pe 6 ca suma de bucati. (Partitiile lui 6 nu sunt prea multe.)

La incercarea de numarat "cu plasari si bare" cred ca am inteles asa metoda de numarare, ilustrata pe cazul cu 4 cai.

Caii sunt a,b,c,d.
Locurile pentru casi sunt x-urile din schema ce vine
x ? x ? x ? x

si in loc de ? avem fie o bara fie un spatiu liber.
Atunci

- Daca punem peste tot o bara avem 4! posibilitati, dar in suma din postarea initiala am vazut doar un 3! (prin analogie), este motivul pentru care am postat explicit toate cazurile. Deci cazul cu
x|x|x|x
are 4! posibilitati.

- Daca punem 2 din 3 bare avem o situatie ceva mai complicata. (Conteaza unde nu o punem
x|x|x x
x|x x|x
x x|x|x
Situatia este homogena, avem 4! posibilitati de umplut x-urile, apoi in fiecare caz cate 2! cazuri ce trebuie identificate.

Deci avem 3.4!/2! cazuri. Nu am inteles in formula initiala in ce termen le regasesc.

- cu o bara avem 3 locuri de plasat bara. Anume
x|x x x
x x|x x
x x x|x
dar identificarea locurilor nu este aceeasi.
In primul caz, plasarea explicita
a|bcd este aceeasi in ca si in celelalte cazuri, de toate sunt 3!.
a|bdc
a|cdb
a|cbd
a|dbc
a|dcb
cam la fel se intampla si cu xxx|x,
dar cazul xx|xx are alt coeficient de identificare, anume 2!2!.
"Homogenitatea" in numarare se pierde, in cazuri de mai multi cai de fapt aici se ascunde combinatorica.

Problema in cazul de fata este una combinatoriala si in acelasi timp una de prezentare. Cea mai simpla solutie este cea in care dam formula de recursiune (de mai sus) si calculam primii termeni...

Notand cu

numarul de ierarhii pentru n cai, termenii sirului obtinut se numesc (in engleza caci nu cunosc terminologia in romana) ordered Bell numbers. Putem vedea si un alt mod de a scrie recurenta de exemplu in cursul An Introduction to
Mathematical Methods in Combinatorics, de Renzo Sprugnoli, disponibil online la
http://www.dsi.unifi.it/~resp/Handbook.pdf

Vedeti sectiunea 2.12.

Este interesant ca eu am aflat de aceasta problema pornind de la o discutie asupra C*-algebrelor asociate k-grafurilor, context in care este necesara aceasi numarare.