[wiskunde] combinatoriek en rijen

[AAAA]

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).

[RedCat]

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).

[RedCat]

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?

[AAAA]

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?

[AAAA]

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!

[RedCat]

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.

[AAAA]

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?

[RedCat]

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?

[AAAA]

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.

[RedCat]

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])

[AAAA]

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?

[RedCat]

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]