Möglichkeiten von Betrag n ct < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Für [mm] n\in \IN_0 [/mm] bezeichne [mm] a_n, [/mm] die Anzahl von Möglichkeiten einen Betrag von nct durch 1ct, 2ct und 5ct Münzen darzustellen:
[mm] a_n=|\{(m_1,m_2,m_5)\in\IN^3_0: 1*m_1+2*m_2+5*m_5=n \}|
[/mm]
Bestimmen Sie die erzeugende Funktion [mm] GF(a_n)(z). [/mm] Berechnen Sie damit eine explizite Darstellung für [mm] a_n.
[/mm]
Bestimmen Sie die Anzahl an Möglichkeiten einen Betrag von nct durch 1ct, 2ct und 5ct Münzen darzustellen, wobei höchstens drei 1ct, höchstens 2ct Münzen verwendet werden dürfen, in ABhängigkeit von [mm] (a_n)_{n\ge 0} [/mm] unter Verwendung der Siebformel |
hallo,
ich komme einfach nicht weiter und hoffe Ihr könnt mir da weiterhelfen.
Da fängt es schon an, dass ich probleme bei der Bestimmung der erzeugende Funktion habe.
ich wäre folgende herangegangen:
[mm] GF(a_n)(z)=GF(1*m_1+2*m_2+5*m_5=n)(z)=GF(n)(z)=GF(n*1)(z)=(zD)GF(1)(z)=(zD)\bruch{1}{1-z}=\bruch{z}{(1-z)^2}
[/mm]
dann habe ich mir überlegt wie sich n ct durch die Münzen 1ct, 2ct und 5ct darstellen lässt, dabei darf höchsten drei 1ct und höchsten zwei 2ct verwendet werden:
dabei steht grün für die Anzahl der 1 ct
rot: Anzahl der 2 ct
1* 3 +2* 2 [mm] +5*m_{5}=n \Rightarrow m_5=\bruch{n-7}{5}
[/mm]
1* 2 +2* 2 [mm] +5*m_{5}=n \Rightarrow m_5=\bruch{n-6}{5}
[/mm]
1* 1 +2* 2 [mm] +5*m_{5}=n \Rightarrow m_5=\bruch{n-5}{5}
[/mm]
1* 3 +2* 1 [mm] +5*m_{5}=n \Rightarrow m_5=\bruch{n-4}{5}
[/mm]
1* 2 +2* 1 [mm] +5*m_{5}=n \Rightarrow m_5=\bruch{n-3}{5}
[/mm]
1* 1 +1* 2 [mm] +5*m_{5}=n \Rightarrow m_5=\bruch{n-2}{5}
[/mm]
1* 1 +2* 0 [mm] +5*m_{5}=n \Rightarrow m_5=\bruch{n-1}{5}
[/mm]
1* 2 +2* 0 [mm] +5*m_{5}=n \Rightarrow m_5=\bruch{n-2}{5}
[/mm]
1* 3 +2* 0 [mm] +5*m_{5}=n \Rightarrow m_5=\bruch{n-3}{5}
[/mm]
1* 0 +2* 2 [mm] +5*m_{5}=n \Rightarrow m_5=\bruch{n-2}{5}
[/mm]
1* 0 +2* 1 [mm] +5*m_{5}=n \Rightarrow m_5=\bruch{n-7}{5}
[/mm]
1* 0 +2* 0 [mm] +5*m_{5}=n \Rightarrow m_5=\bruch{n}{5}
[/mm]
d.h 12 Möglichkeiten
ich stehe total auf dem Schlauch, daher bin ich für jeden Tipp dankbar.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:19 So 04.12.2016 | | Autor: | leduart |
Hallo
1. Deine Aufstellung ist nicht gut. weil ja die Teilbarkeit von n nicht eingeht.
1. 5|n also n=5m
allgemeines [mm] a_n
[/mm]
eine Möglichkeit eine Möglichkeit nur 5c Münzen. danach m jede der k Münzen kann durch 2+2+1 oder 2+1+1+1 oder 1+1+1+1+1 ersetzt werden
damit sind alle Möglichkeiten nächsten n=5m+1 usw dieselbe Anzahl wie bei n=5n
n=5m+2 zusätzlich die Möglichkeit 1+1 oder 2 also [mm] a_{5m+2}=a_{5m}+1
[/mm]
usw. wenn du nur 3*1 und 2*2 verwenden kannst entfällt das Aufteilen der Fünfer von mehr als 1 Fünfer.
Gruß ledum
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:42 So 04.12.2016 | | Autor: | abakus |
Hallo leduart,
wo im Aufgabentext liest du, dass n durch 5 teilbar sein soll?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:07 Mi 07.12.2016 | | Autor: | leduart |
Hallo Abakus
das hab ich nie behauptet, sondern Wenn 5|n dannn usw.
Gruß leduart
|
|
|
| |
|
nochmals danke, aber ich hätte noch einige Fragen dazu.
Wie bestimmt man von [mm] a_n [/mm] die erzeugenden Funktion?
ich würde ertsmal überlegen. n mit 1ct nur dartsellen, d.h [mm] m_1=n [/mm] 1ct Münzen (1)
n nur mit 2 ct darstellen: [mm] m_2=\bruch{n}{2} [/mm] (2)
n nur mit 5ct darstellen: [mm] m_5=\bruch{n}{5} [/mm] (3)
würdest es dann heißen n muss duch 5 und 2 teilbar sein?
würde dann die einzelnen erzeugenden funktion dann so anschauen:
(1) [mm] \bruch{1}{1-z}
[/mm]
(2) [mm] \bruch{1}{1-\bruch{1}{2}z}
[/mm]
(3) [mm] \bruch{1}{1-\bruch{1}{5}z} [/mm] ?
Wie bestimmt man die explizite Form?
tschuldigung für die vielen Fragen erstmal.
Dankeschön im voraus für die Beantwortung der Fragen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:20 Do 08.12.2016 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
