[wiskunde] combinatoriek en rijen

Moderators: ArcherBarry, Fuzzwood

Reageer
Berichten: 64

[wiskunde] combinatoriek en rijen

Hallo

Ik ben was aan het zoeken naar een beetje info over rijen en combinatoriek.
Ik kwam een aantal eigenschappen van de rij van Padovan tegen, een daarvan is:

P(2n-2)= het aantal geordende manieren om n te schrijven als som waarin geen enkele term 2 is.
bv. P(2*3 - 2) = P(4) = 2 dus er zijn 2 manieren om 3 te schrijven als som waarin geen enkele term 2 is: 1 + 1 + 1 ; 3

Nu lijkt het me raar dat het getal 3 ook als een som beschouwd wordt. Je kunt ook niet zeggen dat er daar een "onzichtbare" + nul er bij staat want het is het aantal GEORDENDE manieren dus zou 0+3 ook een manier moeten zijn en dan zal de stelling niet meer kloppen.
Dus is er een logische verklaring daarvoor?

De oorspronkelijke eigenschap is in het engels: The number of ways of writing n as an ordered sum in which no term is 2 is P(2n − 2).

Berichten: 463

Re: [wiskunde] combinatoriek en rijen

Er wordt onderscheid gemaakt tussen een optelling (En: addition) en sommatie (En: summation), vergelijk:
https://en.wikipedia.org/wiki/Addition
en
https://en.wikipedia.org/wiki/Summation

Bij optellen gaat het om de operatie + (="plus"), die 2 termen optelt tot 1 resultaat = de som (En: sum) van die 2 termen.

Daarentegen is een sommatie ook gedefinieerd voor 1 term en zelfs ook voor nul termen, zie:
https://en.wikipedia.org/wiki/Summation#Special_cases
(en ook de formele definitie die direct daaronder volgt op die wiki-pagina).
Het resultaat van de sommatie wordt ook weer een som (En: sum) genoemd.

In de oorspronkelijke eigenschap bedoelen ze met 'sum' dus 'summation'.
De definitie van sommatie voor 1 en nul termen wordt in de combinatoriek overigens veel vaker gebruikt:
doorgaans benoemen we daar reeksen (en rijen) vanaf 0 of 1 termen (elementen).

Berichten: 463

Re: [wiskunde] combinatoriek en rijen

AAAA schreef: ma 30 mar 2020, 12:37 De oorspronkelijke eigenschap is in het engels:
The number of ways of writing n as an ordered sum in which no term is 2 is P(2n − 2).
Lukt het je ook om deze eigenschap te bewijzen?

Berichten: 64

Re: [wiskunde] combinatoriek en rijen

RedCat schreef: di 31 mar 2020, 15:02
AAAA schreef: ma 30 mar 2020, 12:37 De oorspronkelijke eigenschap is in het engels:
The number of ways of writing n as an ordered sum in which no term is 2 is P(2n − 2).
Lukt het je ook om deze eigenschap te bewijzen?
Neen, heeft u een voorstel?

Berichten: 64

Re: [wiskunde] combinatoriek en rijen

RedCat schreef: di 31 mar 2020, 11:22 Er wordt onderscheid gemaakt tussen een optelling (En: addition) en sommatie (En: summation), vergelijk:
https://en.wikipedia.org/wiki/Addition
en
https://en.wikipedia.org/wiki/Summation

Bij optellen gaat het om de operatie + (="plus"), die 2 termen optelt tot 1 resultaat = de som (En: sum) van die 2 termen.

Daarentegen is een sommatie ook gedefinieerd voor 1 term en zelfs ook voor nul termen, zie:
https://en.wikipedia.org/wiki/Summation#Special_cases
(en ook de formele definitie die direct daaronder volgt op die wiki-pagina).
Het resultaat van de sommatie wordt ook weer een som (En: sum) genoemd.

In de oorspronkelijke eigenschap bedoelen ze met 'sum' dus 'summation'.
De definitie van sommatie voor 1 en nul termen wordt in de combinatoriek overigens veel vaker gebruikt:
doorgaans benoemen we daar reeksen (en rijen) vanaf 0 of 1 termen (elementen).
bedankt!

Berichten: 463

Re: [wiskunde] combinatoriek en rijen

Te bewijzen: the number of ways of writing n as an ordered sum in which no term is 2 is P(2n − 2).

We kijken eerst naar het aantal manieren om een getal n als geordende som (dat wil zeggen: "de volgorde van de termen is van belang") te schrijven, waarbij geen enkele term gelijk is aan 2.
Noem die rij van aantallen A, waarbij a[n] het aantal mogelijkheden is voor getal n
Je had al gevonden:
a[1] = 1, namelijk 1
a[2] = 1, namelijk 1+1
a[3] = 2, namelijk 1+1+1 en 3

We willen nu eerst een recursieve formule voor deze rij opstellen
(zoals we bijvoorbeeld al hebben voor de rij van Padovan: P[n] = P[n-2] + P[n-3]).

Eerst een voorbeeld:
Stel we willen a[6] weten = het aantal mogelijkheden om getal 6 als geordende som (zonder 2) te schrijven.
Kijk dan naar de laatste term van onze som met uitkomst 6:
- als de laatste term een 1 is, dan hebben we a[5] mogelijkheden om voor die 1 een geordende som met uitkomst 5 te schrijven
- de laatste term een 2 is verboden (geen enkele term mag 2 zijn)
- als de laatste term een 3 is, dan hebben we a[3] mogelijkheden om voor die 3 een geordende som met uitkomst 3 te schrijven
- als de laatste term een 4 is, dan hebben we a[2] mogelijkheden om voor die 4 een geordende som met uitkomst 2 te schrijven
- als de laatste term een 5 is, dan hebben we a[1] mogelijkheden om voor die 5 een geordende som met uitkomst 1 te schrijven
- als de laatste term een 6 is, dan mogen we er niets voor plaatsen, dus precies 1 mogelijkheid.

Dus a[6] = a[5] + a[3] + a[2] + a[1] + 1
Als we a[0] = 1 definieren, dan wordt dit
a[6] = a[5] + a[3] + a[2] + a[1] + a[0]
In deze vergelijking komen bijna alle voorgaande termen terug (behalve a[4]). Dat moet eenvoudiger kunnen.
We kijken daarom eerst naar de overeenkomstige formule voor a[5]:
a[5] = a[4] + a[2] + a[1] + a[0]
Tellen we hier links en rechts nog een keer a[5] bij op, dan krijgen we:
a[5] + a[5] = a[5] + a[4] + a[2] + a[1] + a[0]
ofwel:
2a[5] = a[5] + a[4] + a[2] + a[1] + a[0]
Dit lijkt al op a[6], alleen moeten we er nog a[4] van af trekken en a[3] bij optellen:
2a[5] - a[4] + a[3] = a[5] + a[3] + a[2] + a[1] + a[0]
Dus:
a[6] = 2a[5] - a[4] + a[3]

Bewijs nu zelf op soortgelijke wijze het algemene geval (voor elke n > 3):
a[n] = 2a[n-1] - a[n-2] + a[n-3]

Samen met de 3 beginwaarden die je al gevonden had ligt deze rij nu vast:
a[4] = 2a[3] - a[2] + a[1] = 2*2 - 1 + 1 = 4
Ter controle: dit zijn (met laatste term resp 1,1,3,4):
1 + 1 + 1 + 1
3 + 1
1 + 3
4
a[5] = 2a[4] - a[3] + a[2] = 2*4 - 2 + 1 = 7
Ter controle: dit zijn (met laatste term resp 1,1,1,1,3,4,5):
1 + 1 + 1 + 1 + 1
3 + 1 + 1
1 + 3 + 1
4 + 1
1 + 1 + 3
1 + 4
5
Als we dit nog verder doorrekenen komen we uit op deze rij (beginnend met a[1]):
A = 1, 1, 2, 4, 7, 12, 21, 37, 65, 114, 200, 351, 616, 1081, 1897, 3329, 5842, ...


Nu moeten we nog bewijzen dat deze betrekking ook geldt voor het gegeven gedeelte van de rij van Padovan:
n = 1: P[2*1-2] = P[0] = 1 = a[1]
n = 2: P[2*2-2] = P[2] = 1 = a[2]
n = 3: P[2*3-2] = P[4] = 2 = a[3]
Alle beginwaarden kloppen dus.

Nu de recurrente betrekking:
a[n] = 2a[n-1] - a[n-2] + a[n-3],
die moet dan worden:
P[2n-2] = 2*P[2(n-1)-2] - P[2(n-2)-2] + P[2(n-3)-2]
ofwel
P[2n-2] = 2*P[2n-4] - P[2n-6] + P[2n-8]
Kan je bewijzen dat dit geldt in de rij van Padovan (waarin volgens de definitie geldt: P[n] = P[n-2] + P[n-3])?

Hint: kijk bijvoorbeeld eerst eens voor n = 6:
Te bewijzen:
P[10] = 2*P[8] - P[6] + P[4]
We weten (volgens de definitie van de rij van Padovan):
P[8] = P[6] + P[5]
dus
2*P[8] = P[8] + P[8] = P[8] + P[6] + P[5]
en moeten we aantonen:
P[10] = 2*P[8] - P[6] + P[4]
ofwel
P[10] = (P[8] + P[6] + P[5]) - P[6] + P[4]
ofwel
P[10] = P[8] + P[5] + P[4]
En waaraan is P[5] + P[4] gelijk in de rij van Padovan?
Klopt dit voor P[10] in deze rij?:
P[10] = P[8] + ...

En aan jou verder het algemene geval.


PS: nogal wat tekst, maar hopelijk te volgen.
Zo niet, blijf dan gewoon doorvragen.

Berichten: 64

Re: [wiskunde] combinatoriek en rijen

Bewijs nu zelf op soortgelijke wijze het algemene geval (voor elke n > 3):
a[n] = 2a[n-1] - a[n-2] + a[n-3]

Kan je hier ook hint geven?

Berichten: 463

Re: [wiskunde] combinatoriek en rijen

De redenatie is identiek aan die voor het speciale geval dat n=6:
Als we 2 niet mogen gebruiken, dan kan van elke som met uitkomst n (n>3)
de laatste term 1, 3, 4, 5, ..., n-2, n-1, n zijn, dus alle getallen van 1 t/m n behalve 2.
Voor elk van deze laatste termen hebben we dus:
(een geldige som die optelt tot n-1) + 1 = n
(een geldige som die optelt tot n-3) + 3 = n
(een geldige som die optelt tot n-4) + 4 = n
(een geldige som die optelt tot n-5) + 5 = n
...
(een geldige som die optelt tot 2) + (n-2) = n
(een geldige som die optelt tot 1) + (n-1) = n
(een geldige som die optelt tot 0) + n = n

Het aantal manieren om een geldige som met uitkomst n te vormen is dus gelijk aan:
het aantal manieren om een geldige som met uitkomst n-1 te vormen (als we hier 1 bij optellen komen we uit op n)
+
het aantal manieren om een geldige som met uitkomst n-3 te vormen (als we hier 3 bij optellen komen we uit op n)
+
het aantal manieren om een geldige som met uitkomst n-4 te vormen (als we hier 4 bij optellen komen we uit op n)
+
...
+
het aantal manieren om een geldige som met uitkomst 1 te vormen (als we hier (n-1) bij optellen komen we uit op n)
+
1 (het laatste geval: een sommatie bestaande uit 1 term, namelijk n)

ofwel:
a[n] = a[n-1] + a[n-3] + a[n-4] + a[n-5] + ... + a[2] + a[1] + 1

Evenzo geldt voor n-1 (merk op: hier mogen we a[(n-1)-2] = a[n-3] niet gebruiken):
a[n-1] = a[n-2] + a[n-4] + a[n-5] + ... + a[2] + a[1] + 1
Als we hier vervolgens beiderzijds a[n-1] bij optellen, dan krijgen we
a[n-1] + a[n-1] = a[n-1] + a[n-2] + a[n-4] + a[n-5] + ... + a[2] + a[1] + 1
ofwel
2*a[n-1] = a[n-1] + a[n-2] + a[n-4] + a[n-5] + ... + a[2] + a[1] + 1

Wat moet er nog gebeuren om deze laatste som gelijk te maken aan de som van a[n] hierboven?

Berichten: 64

Re: [wiskunde] combinatoriek en rijen

RedCat schreef: wo 01 apr 2020, 11:50 De redenatie is identiek aan die voor het speciale geval dat n=6:
Als we 2 niet mogen gebruiken, dan kan van elke som met uitkomst n (n>3)
de laatste term 1, 3, 4, 5, ..., n-2, n-1, n zijn, dus alle getallen van 1 t/m n behalve 2.
Voor elk van deze laatste termen hebben we dus:
(een geldige som die optelt tot n-1) + 1 = n
(een geldige som die optelt tot n-3) + 3 = n
(een geldige som die optelt tot n-4) + 4 = n
(een geldige som die optelt tot n-5) + 5 = n
...
(een geldige som die optelt tot 2) + (n-2) = n
(een geldige som die optelt tot 1) + (n-1) = n
(een geldige som die optelt tot 0) + n = n

Het aantal manieren om een geldige som met uitkomst n te vormen is dus gelijk aan:
het aantal manieren om een geldige som met uitkomst n-1 te vormen (als we hier 1 bij optellen komen we uit op n)
+
het aantal manieren om een geldige som met uitkomst n-3 te vormen (als we hier 3 bij optellen komen we uit op n)
+
het aantal manieren om een geldige som met uitkomst n-4 te vormen (als we hier 4 bij optellen komen we uit op n)
+
...
+
het aantal manieren om een geldige som met uitkomst 1 te vormen (als we hier (n-1) bij optellen komen we uit op n)
+
1 (het laatste geval: een sommatie bestaande uit 1 term, namelijk n)

ofwel:
a[n] = a[n-1] + a[n-3] + a[n-4] + a[n-5] + ... + a[2] + a[1] + 1

Evenzo geldt voor n-1 (merk op: hier mogen we a[(n-1)-2] = a[n-3] niet gebruiken):
a[n-1] = a[n-2] + a[n-4] + a[n-5] + ... + a[2] + a[1] + 1
Als we hier vervolgens beiderzijds a[n-1] bij optellen, dan krijgen we
a[n-1] + a[n-1] = a[n-1] + a[n-2] + a[n-4] + a[n-5] + ... + a[2] + a[1] + 1
ofwel
2*a[n-1] = a[n-1] + a[n-2] + a[n-4] + a[n-5] + ... + a[2] + a[1] + 1

Wat moet er nog gebeuren om deze laatste som gelijk te maken aan de som van a[n] hierboven?
Sorry, ik had even geen verbinding. En ik had inderdaad iets verkeerd verstaan in het eerste voorbeeld.

Erg bedankt voor de hulp.

Berichten: 463

Re: [wiskunde] combinatoriek en rijen

OK.

Wat wellicht ook nog leuk is om te zien:

Stel F = het aantal geordende sommen met uitkomst n zonder 1:
n=1: niet mogelijk: f[1] = 0
n=2: 2: f[2] = 1
n=3: 3: f[3] = 1
n=4: 2+2, 4: f[4] = 2
En voor de recursie vergelijkbaar met wat we hierboven zagen (voor n>4):
f[n] = f[n-2] + f[n-3] + f[n-4]+ f[n-5] + ... + f[2] + f[1] + 1
f[n-2] = f[n-4]+ f[n-5] + ... + f[2] + f[1] + 1
2*f[n-2] = f[n-2] + (f[n-4]+ f[n-5] + ... + f[2] + f[1] + 1)
2*f[n-2] + f[n-3] = f[n-2] + f[n-3] +f[n-4]+ f[n-5] + ... + f[2] + f[1] + 1 = f[n]
dus
f[n] = 2*f[n-2] + f[n-3]
met beginwaarden f[1]=0, f[2]=1, f[3]=1

Maar dit is hetzelfde als de rij van Fibonacci, want omdat:
Fib[n] = Fib[n-1] + Fib[n-2]
en dus
Fib[n-1] = Fib[n-2] + Fib[n-3]
is
Fib[n] = Fib[n-1] + Fib[n-2] = (Fib[n-2] + Fib[n-3]) + Fib[n-2] = 2*Fib[n-2] + Fib[n-3]
We kunnen onze rij F dus ook vereenvoudigen tot
f[n] = f[n-1] + f[n-2]
met beginwaarden f[1]=0, f[2]=1

F = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...
(start bij f[1])


Stel G = het aantal geordende sommen met uitkomst n zonder beperking:
g[n] = g[n-1] + g[n-2] + g[n-3] + ... + g[2] + g[1] + 1
g[n-1] = g[n-2] + g[n-3] + ... + g[2] + g[1] + 1
2*g[n-1] = g[n-1] + (g[n-2] + g[n-3] + ... + g[2] + g[1] + 1) = g[n]
dus
g[n] = 2*g[n-1], met g[1] = 1
deze herhalende verdubbeling levert de directe = gesloten formule:
\(g[n] = 2^{n-1}\)
G = 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, ...
(start bij g[1])

Berichten: 64

Re: [wiskunde] combinatoriek en rijen

RedCat schreef: do 02 apr 2020, 15:56 OK.

Wat wellicht ook nog leuk is om te zien:

Stel F = het aantal geordende sommen met uitkomst n zonder 1:
n=1: niet mogelijk: f[1] = 0
n=2: 2: f[2] = 1
n=3: 3: f[3] = 1
n=4: 2+2, 4: f[4] = 2
En voor de recursie vergelijkbaar met wat we hierboven zagen (voor n>4):
f[n] = f[n-2] + f[n-3] + f[n-4]+ f[n-5] + ... + f[2] + f[1] + 1
f[n-2] = f[n-4]+ f[n-5] + ... + f[2] + f[1] + 1
2*f[n-2] = f[n-2] + (f[n-4]+ f[n-5] + ... + f[2] + f[1] + 1)
2*f[n-2] + f[n-3] = f[n-2] + f[n-3] +f[n-4]+ f[n-5] + ... + f[2] + f[1] + 1 = f[n]
dus
f[n] = 2*f[n-2] + f[n-3]
met beginwaarden f[1]=0, f[2]=1, f[3]=1

Maar dit is hetzelfde als de rij van Fibonacci, want omdat:
Fib[n] = Fib[n-1] + Fib[n-2]
en dus
Fib[n-1] = Fib[n-2] + Fib[n-3]
is
Fib[n] = Fib[n-1] + Fib[n-2] = (Fib[n-2] + Fib[n-3]) + Fib[n-2] = 2*Fib[n-2] + Fib[n-3]
We kunnen onze rij F dus ook vereenvoudigen tot
f[n] = f[n-1] + f[n-2]
met beginwaarden f[1]=0, f[2]=1

F = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...
(start bij f[1])


Stel G = het aantal geordende sommen met uitkomst n zonder beperking:
g[n] = g[n-1] + g[n-2] + g[n-3] + ... + g[2] + g[1] + 1
g[n-1] = g[n-2] + g[n-3] + ... + g[2] + g[1] + 1
2*g[n-1] = g[n-1] + (g[n-2] + g[n-3] + ... + g[2] + g[1] + 1) = g[n]
dus
g[n] = 2*g[n-1], met g[1] = 1
deze herhalende verdubbeling levert de directe = gesloten formule:
\(g[n] = 2^{n-1}\)
G = 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, ...
(start bij g[1])
Die formule van G(n) is dan enkel geldig voor de rij van Fib. of ben ik verkeerd?

Berichten: 463

Re: [wiskunde] combinatoriek en rijen

De rij F[n]:
f[n] geeft het aantal geordende sommaties met uitkomst n waarbij getal 1 verboden is:
Bijvoorbeeld: f[5] = 3:
3 + 2
2 + 3
5
De rij van F is:
f[1]=0, f[2]=1, f[3]=1, f[4]=2, f[5]=3, f[6]=5, f[7]=8, f[8]=13, ...
ofwel:
F = 0, 1, 1, 2, 3, 5, 8, 13, ...
en deze rij is hetzelfde als de rij van Fibonacci:
Fib = 0, 1, 1, 2, 3, 5, 8, 13, ...
De recursieve formules zijn:
f[n] = f[n-1] + f[n-2]
resp:
Fib[n] = Fib[n-1] + Fib[n-2]
Alleen start onze rij F met f[1]=0 en f[2]=1, en de rij van Fibonacci met Fib[0]=0 en Fib[1]=1


De rij G[n]:
De rij g[n] geeft het aantal geordende sommaties met uitkomst n waarbij alle getallen van 1 t/m n gebruikt mogen worden:
Bijvoorbeeld: g[5] = 16 (= 2^4):
1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1
1 + 2 + 1 + 1
3 + 1 + 1
1 + 1 + 2 + 1
2 + 2 + 1
1 + 3 + 1
4 + 1
1 + 1 + 1 + 2
2 + 1 + 2
1 + 2 + 2
3 + 2
1 + 1 + 3
2 + 3
1 + 4
5
De rij voor g[n] is:
G = 1, 2, 4, 8, 16, 32, 64, 128, 256, ...
De recursie hier is:
g[n] = 2*g[n-1]
met g[1]=1.
Elke waarde van g[n] is dus het dubbele van de vorige waarde, namelijk g[n-1].
Dit levert de formule
\(g[n] = 2^{n-1}\)
De rij van G is niet gelijk aan de rij van Fibonacci, de rij van Fibonacci kunnen we dan ook NIET met deze formule bepalen.


De rij A[n] (= de rij die we oorspronkelijk onderzocht hebben):
a[n] geeft het aantal geordende sommaties met uitkomst n waarbij getal 2 verboden is:
Bijvoorbeeld: a[5] = 7:
1 + 1 + 1 + 1 + 1
3 + 1 + 1
1 + 3 + 1
4 + 1
1 + 1 + 3
1 + 4
5
De rij van a[n] is:
A = 1, 1, 2, 4, 7, 12, 21, 37, 65, 114, 200, 351, 616,
met recursieve formule:
a[n] = 2a[n-1] - a[n-2] + a[n-3]
en beginwaarden a[1]=1, a[2]=1 en a[3]=2.

En deze rij komt overeen met de even elementen van de rij van Padovan: a[n] = P[2n-2]

Reageer