[es] - Spisak stranica mnogougla (kombinatorika)

Farenhajt
Goran Kapetanović
Beograd

Član broj: 78132
Poruke: 449
..252.195.adsl.dyn.beotel.net.

+6 Profil

Spisak stranica mnogougla (kombinatorika)

^{26.07.2011. u 06:13 - pre 155 meseci}

Ako je dat trougao ABC, njegove stranice možemo obeležiti kao AB ili BA, AC ili CA, BC ili CB. Želimo sve njegove stranice da stavimo na spisak (tačno po jedanput), ali tako da, za svake dve susedne stavke na spisku, krajnja tačka prethodne stavke bude različita od početne tačke naredne stavke.

Ilustracija: Spisak AB-BC-AC nije dozvoljen jer se "B" u AB podudara sa "B" u BC. Isto važi i za BA-BC-CA. S druge strane, svi naredni spiskovi su dozvoljeni: AB-AC-BC, BC-AB-CA, CA-CB-AB itd.

Primedba: Spiskovi su linearni, a ne kružni, te stoga odnos između početne tačke prve stavke i krajnje tačke poslednje stavke nije bitan.

Pitanje: Koliko ima takvih spiskova za
i) trougao;
ii) n-tougao?

Odgovor na temu

Bojan Basic
Novi Sad

SuperModerator
Član broj: 6578
Poruke: 3996
*.dynamic.sbb.rs.

Jabber: bojan_basic@elitesecurity.org
ICQ: 305820253

+605 Profil

Re: Spisak stranica mnogougla (kombinatorika)

^{26.07.2011. u 08:00 - pre 155 meseci}

Ako nisam pogrešio u kodu, za trougao, četvorougao, itd. do sedmougla, traženih spiskova ima 30, 232, 2330, 27948, 391286, redom. Ovo pak jako liči na niz koji prebrojava izometrije

-dimenzionalne hiperkocke koje su rastroji poretka njenih

-dimenzionalnih hiperstrana: pogledaj ovaj rad, strana 7 — razlika je samo u naizmeničnom dodavanju i oduzimanju jedinice. Niz je zabeležen i u Slounovoj enciklopediji, ovde. Brojevi su previše veliki da bi bila slučajnost, a i ne deluje nelogično da se ovo tvoje pitanje zaista može svesti na izometrije hiperkocaka. Trenutno nemam vremena da razmišljam o dokazu (a moguće da je čak i trivijalan).

Ljubičice crvena, što si plava kô zelena trava.

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
89.216.32.*

+2789 Profil

Re: Spisak stranica mnogougla (kombinatorika)

^{26.07.2011. u 10:02 - pre 155 meseci}

Bojane, ovakav tvoj odgovor je nepotpun bez prilaganja izvornog koda programa.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

Bojan Basic
Novi Sad

SuperModerator
Član broj: 6578
Poruke: 3996
*.dynamic.sbb.rs.

Jabber: bojan_basic@elitesecurity.org
ICQ: 305820253

+605 Profil

Re: Spisak stranica mnogougla (kombinatorika)

^{26.07.2011. u 17:36 - pre 155 meseci}

Odgovor je svakako nepotpun (ne samo iz razloga koji si naveo), trebalo je samo da ukaže na jedan moguć pristup problemu, onoliko koliko sam na brzinu uočio a što deluje obećavajuće. No, prilaganje koda zaista bi učinilo moju opasku malo kompletnijom.

Do onih brojeva sam došao tako što sam u Mathematici najpre definisao sledeće pomoćne funkcije:

Code:
str[n_] := Append[Table[{i, i + 1}, {i, 1, n - 1}], {1, n}]

Code:
Inn[l1_, l2_] := If[l2[[#]] == 1, l1[[#]], Reverse[l1[[#]]]] & /@ Range[Length[l1]]

Code:
mogucn[n_] := Inn[str[n], #] & /@ Tuples[{1, 2}, n]

Code:
OK[niz_] := And @@ (niz[[#, 2]] != niz[[# + 1, 1]] & /@ Range[Length[niz] - 1])

Potom se rezultat dobija pokretanjem sledećeg koda:

Code:
For[n = 3, n <= 7, n++,
Print[Length[Select[Flatten[Permutations[#] & /@ mogucn[n], 1], OK[#] &]]]
]

Ljubičice crvena, što si plava kô zelena trava.

Odgovor na temu

Farenhajt
Goran Kapetanović
Beograd

Član broj: 78132
Poruke: 449
..252.195.adsl.dyn.beotel.net.

+6 Profil

Re: Spisak stranica mnogougla (kombinatorika)

^{27.07.2011. u 00:46 - pre 155 meseci}

Hvala

Odgovor na temu