Matematické Fórum

xxdadxx · 02. 11. 2019 12:21

Veľmi rada by som bola ak by ste mi pomohli s touto úlohou.

Kompozíciou čísla n rozumieme každú jeho usporiadanú partíciu v tvare $x_{1}+...+x_{k}=n$ , kde $k\ge 1$ a $x_{i}\ge 1$ pre $i=1,...,k$ . Spočítajte počet kompozícií čísla $n\ge 1$ .

Za každú pomoc vopred ďakujem!

vanok · 02. 11. 2019 14:22 — Editoval vanok (02. 11. 2019 15:58)

Poznamka
( stale za predpokladu, ze n a k su dane)
Este jedna kombinatoricka myslienka: vyuzi, ze ked urcime vhodne $( x_1;....; x_{k-1})$ , $x_k$ je automaticky urcene.

Honzc · 03. 11. 2019 07:32

↑ xxdadxx:
I když tvoje zadání je velmi nedostatečné, zkus se podívat např. Sem

krakonoš

↑ Honzc:
Zadání má smysl pro pevná n, k.
Stačí si představit n jako n korálků, kde vzniká n-1 mezer. K vytvoření k tříd stačí k-1 mezer vybarvit černě.Jde pak o normální příklad na kombinaci.

Honzc · 03. 11. 2019 10:55 — Editoval Honzc (03. 11. 2019 10:56)

↑ krakonoš:
Ono totiž chtělo napsat, že n a xi jsou přirozená čísla a pak to smysl má.

krakonoš · 03. 11. 2019 11:10

↑ Honzc:
Já to uvažovala jako čísla z N, už jen z toho náznaku , že součet je značen n.Kdyby $x_{i}$ nebylo přirozené, tak by to ani smysl nemělo.Možná to ani tak neni chyba studenta, ale zadavatelę toho příkladu

vanok · 03. 11. 2019 17:11 — Editoval vanok (04. 11. 2019 00:06)

Ahoj ↑ krakonoš:,

Dovolim, si pridat malu poznamku.

To tvoje riesenie je asi najjednoduchsie a ↑ xxdadxx: iste ho z radostou pouzije.

Su aj metody, kde sa da povodny problem transformovat na iny, no to nie je take rychle ako tvoj postup (a je to aj dlhsie, preto som skryl moje #2 ).

Inac, pre niekoho co ma rad lopatisticke pristupy je mozna aj metoda kde sa vyuzije patricia prirodzeneho n na k clenov.

Maly doplnok, ktory upresnuje tu posledny vetu.

Este ma napadlo, ze vseobecny problem v #1 sa da riesit « rekurentne »
Presnejsie pre n=1 mame jedinu kompoziciu.
*
Pre n = 2, mame tieto:
n=2 a

n=1+1 cize dve kompozicie.
*
Pre n=3, mame :
n=3

n=2+1
n=1+2

n =1+1+1
co ukazuje, ze su 4.
*

Pre n=4 mame tieto
n=4

n=1+3

n=1+1+2
n=2+2

n=1+1+1+1
n=1+2+1
n=2+1+1
n=3+1

A tak pre n=4 mame 8 kompozicii.

***
Vidime, ze na kazdej nasledujucej etape vzdy musime pouzit vsetky predchadzajuce.

( to uz vedie k tomu, ze vysledok by mal byt , ze $C(n)=2^{n-1}$ … a tuto uvaha uz len treba z formalizovat ....)

zdenek1 · 03. 11. 2019 17:54

↑ krakonoš:
Já jsem zadání pochopil tak, že $k$ není pevné, tj. tvé výsledky je třeba posčítat pro všechna přípustná $k$ , při daném $n$ .

krakonoš · 03. 11. 2019 18:43

↑ zdenek1:
Ahoj.
Zřejmě ano.Já jen uvažovala, co s tím pro pevná n,k.

krakonoš · 03. 11. 2019 19:43

↑ zdenek1:
Ale na internetu jsem pojem kompozice čísla vůbec nenašla, abych vyšla z přesné definice. Možná se to česky řekne jinak.

zdenek1 · 03. 11. 2019 20:16

↑ krakonoš:
Něco je v odkazu v příspěvku #4, ale nepomůže to v pochopení "Co autor příkladu vlastně chce?"

Na můj vkus je pevné $k$ moc jednoduché. :)

check_drummer · 03. 11. 2019 20:54

↑ xxdadxx:
Ahoj, zkus se podívat sem.

krakonoš · 03. 11. 2019 21:32

↑ zdenek1:↑ check_drummer:
Ten článek je hezký, díky.
To vysčítání podle k s pomocí binomické věty je vlastně už jen maličkost.

vanok · 04. 11. 2019 00:04

Ahoj ↑ krakonoš:,
V #8 som trochu rozvinul tu rekurentnu mysienku vo vseobecnom pripade riesenia. Ak sa ti chce to mozes formalnejsie napisat .

vanok · 06. 11. 2019 12:42

Mozno som mal upresnit, ze v ↑ vanok: ide o dokaz indukciou, toho, ze $C(n)=2^{n-1}$ .
V texte so ukazal, ze vzorec plati pre C(1); C(2); C(3) a C(4) ( aj ked to, ze plati pre C(1) staci na dokaz).
Vieme
$C(n)=2^{n-1}$ sa pise aj takto
$P(n):1+C(1)+C(2)+...+C(n-1)= C(n)$ .

A ukazme, ze to nam da P(n+1). ( dokoncite...).

krakonoš

↑ vanok:
Ahoj
Mně příjde, že nejlépe ten rozklad i počet kompozic ukazuje s největším přehledem Pascalův trojúhelník.Tam je vlastně i rovnou ta indukce vidět a všechny zákonitosti najednou, alespoň u některých čísel.
Tam je krásně vidět, když zvolíš n, jak se vždy můžeš vydat dvojí cestou směrem nahoru.Radost pohledět!
Pro určení počtu kompozic je to asi nejrychlejší, stačí si uvědomit, že můžeš zvolit vždy dvě cesty a postoupit o patro výš, něco podobného jako u některých čísel v tomto trojúhelníku. Př zvolím 5=4+1 nebo 5=1+4 a přejdu o patro výš k číslu 4.....
Vlastně každé n můžeš zakódovat pomocí doprava, doleva $2^{n-1}$ způsoby, a ani na to ty kombinace vlastně nepotřebuješ přímo.
Já si totiž po letech v první chvíli ani na to nevzpomněla a nebyla jsem ani zvyklá to používat výpočtu n nad k.😊

vanok · 06. 11. 2019 14:47

Poznamka.
Viaceri sme tu dali rozne pohlady ( a aj odkazy na web). No vsak ↑ xxdadxx: vobec nenapisal co vlastne chcel vediet. A to je skoda.

krakonoš · 06. 11. 2019 14:55

↑ vanok:
Já myslím, že nejde jen o dotyčného studenta, který dotaz zadal.Podle mě to má i velký přínos pro ostatní, kteří se toho účastní, tedy alespoň co se mě týče.Pochopitelně nemohu mluvit za jiné lidi z fóra.

vanok · 06. 11. 2019 15:37

↑ krakonoš:
To je pravda, no ten co chcel o tom nieco vediet nakoniec to mozno ani necita.

Matematické Fórum

#1 02. 11. 2019 12:21

Počet kompozícií čísla

#2 02. 11. 2019 14:06 — Editoval vanok (02. 11. 2019 15:58) Příspěvek uživatele vanok byl skryt uživatelem vanok. Důvod: Zbytocne komplikovane

#3 02. 11. 2019 14:22 — Editoval vanok (02. 11. 2019 15:58)

Re: Počet kompozícií čísla

#4 03. 11. 2019 07:32

Re: Počet kompozícií čísla

#5 03. 11. 2019 08:57 — Editoval krakonoš (03. 11. 2019 09:05)

Re: Počet kompozícií čísla

#6 03. 11. 2019 10:55 — Editoval Honzc (03. 11. 2019 10:56)

Re: Počet kompozícií čísla

#7 03. 11. 2019 11:10

Re: Počet kompozícií čísla

#8 03. 11. 2019 17:11 — Editoval vanok (04. 11. 2019 00:06)

Re: Počet kompozícií čísla

#9 03. 11. 2019 17:54

Re: Počet kompozícií čísla

#10 03. 11. 2019 18:43

Re: Počet kompozícií čísla

#11 03. 11. 2019 19:43

Re: Počet kompozícií čísla

#12 03. 11. 2019 20:16

Re: Počet kompozícií čísla

#13 03. 11. 2019 20:54

Re: Počet kompozícií čísla

#14 03. 11. 2019 21:32

Re: Počet kompozícií čísla

#15 04. 11. 2019 00:04

Re: Počet kompozícií čísla

#16 06. 11. 2019 12:42

Re: Počet kompozícií čísla

#17 06. 11. 2019 13:31 — Editoval krakonoš (06. 11. 2019 22:22)

Re: Počet kompozícií čísla

#18 06. 11. 2019 14:47

Re: Počet kompozícií čísla

#19 06. 11. 2019 14:55

Re: Počet kompozícií čísla

#20 06. 11. 2019 15:37

Re: Počet kompozícií čísla

Zápatí