Matematické Fórum

↑ Dunemaster:
To asi není moc těžké. Protože se čísla nemohou opakovat a nezáleží na pořadí, pak jejich počet je dán jako kombinace k-té třídy z n prvků , tedy počet
A praktiké vyjádření také nebude složité.
Třeba pro n=5, k=3 to bude rozepsáno nejjednodušeji takto: (10 možností)
123
124
125
134
135
145
234
235
245
345

↑ Dunemaster:
Zajímavý příklad.
Přeformuluji to:
Mějme množinu o prvcích. Mějme číslo , . Kolik existuje uspořádání na množině (všech k-tic množiny ) splňující:
,
kde je relace bezprostředního předchůdce uspořádání .
Možná tato formulace není vhodná k řešení, ale zdá se mi srozumitelná.

Ahoj,
co mě napadlo: stará dobrá indukce.

Chceme vhodně uspořádat prvků. Nechť pro jednoduchost je N:={1,..,n}. Budeme postupovat indukcí dle . Zřejmé jsou případy i . V ostatních případech pro dané N rozdělme na množiny A a B, kde každá k-tice z A neobsahuje a každá k-tice z B obsahuje prvek n. Dle indukce lze A uspořádat a rovněž i B lze uspořádat - odstraníme ze všech k-tic v B prvek n, dle indukce ji uspořádáme a následně se přidáním prvku n k těmto k-1 ticím na korektnosti uspořádání nic nezmění.

Zbývá dořešit otázku, jak napojit uspořádané A na uspořádané B. To je ale jednoduché - lze totitž jednoduše dosáhnout toho, aby první nebo poslední k-tice v A i v B byla taková jakou chceme - jednoduše zpermutujeme vhodně prvky množiny, ze které k-tice vybíráme. A i B lze ovšem zpermutovat odlišně a tak lze dosáhnout toho, že poslední prvek A je {1,2,..,k-1,k} a první prvek B je {1,2,..,k-1,n}, čímž je úloha vyřešena.

Snad tam není někde slabé místo.

↑ check_drummer:

pro dané N rozdělme N na množiny A a B, kde každá k-tice z A neobsahuje a každá k-tice z B obsahuje prvek n.

Jak rozdělit N tak, jak píšeš? Nebo píšeš o rozdělení = množiny všech k prvkových podmnožin množiny N - na A a B, kde ...
Ráda si ten důkaz projdu později, teď musím pryč, ale narazila jsem na problém výše.

↑ Honzc:
Jak víš, že takových uspořádání je právě ?

↑ Andrejka3:
Ahoj, omlouvám se, jde o rozdělení množiny všech k prvkových podmnožin množiny N - na A a B. Opravím to.

↑ Andrejka3:
Nekonecna postupnost v mojej interpretaci je skutocna postupnost
Dunemaster-ovov podmienkov  tykajuca sa dvoch susednych clenov:
" su pripustne v zmysle Dunemaster-a"

Napriklad v situacii (k,n)=(3,5)
mame tuto Dunemaster-ovu (periodicku) postupnost
(1,2,3);(1,2,4);(1,2,3);(1,2,4);...
alebo
(1,2,3);(1,2,4);(1,2,5);(1,2,4);(1,4, 5);...

↑ vanok:
Ahoj, pod přípustnou nekonečnou D-posloupností (D jako Dunemaster) máš na mysli, že použiješ všechny k-tice v nějakém pořadí a následně toto pořadí stále opakuješ? Tj. posloupnost je vždy periodická? Pokud ne, pak lze volit např. (1,2,3),(1,2,4),(1,2,5),(1,2,4),(1,2,5),... Pokud ano, pak se vlastně jedná o to mé zobecnění, kdy pro první a poslední člen této posloupnosti musí rovněž platit, že se liší v jednom členu. A Tvé tvrzení tedy říká, že pro k=3 jde o tentýž případ jako původní problém - to je zajímavé. Ale příklad, který uvedl Honzc je dle mého protipříklad, díky kterému Tvé tvrzení neplatí...

↑ vanok:
Ahoj, podle mého jsou všechny délky kromě 2 možné (povolíme-li, aby se členy posloupnosti opakovaly - což je nejspíš povoleno, protože zkoumáme případ, kdy se první člen objeví znovu, tj. opakuje se) pro k<n a lichou délku a navíc pro n>2 a sudou délku. Např. posloupnost délky 3 získáme jako (1,2,X), (1,3,X), (1,2,X) a posloupnost délky 4 jako (1,2,X), (1,3,X), (2,3,X), (1,2,X), kde X jsou prvky doplňující k-tici. Následně můžeme postupovat indukcí a podposloupnost A1 o jednom členu rozšířit na posloupnost A1,..,A1 o lichém počtu členů.