Anzahlprobleme "99"

16/03/2008 - 14:08 von Armin Saam | Report spam
Seit kurzem beschàftigt mich folgendes Anzahlproblem:

Es sei A die Menge aller Zahlen, die in ihrer Dezimaldarstellung keine zwei
benacharten 9en haben, a(n) sei die Anzahl der Elemente von A mit n Ziffern
(also von 0 bis 10^n -1).
B sei die Menge aller n-ziffrigen Zahlen, die in ihrer Dezimaldarstellung
genau ein Paar 99 besitzen; b(n) sei Anzahl der Elemente von B mit n
Ziffern.

Zu B gehören zum Beispiel 49909, 1934995519, nicht jedoch 7999223 oder
99399.

Gesucht ist sind die Anzahlfunktionen a(n) und b(n).

Mit meinen ersten Lösungsversuchen bin ich noch nicht zu einem
befriedigenden Resultat gekommen. Fest steht für mich allerdings schon
jetzt, dass es zwei knifflige Problemchen sind, die ihren Reiz haben. Wenn's
keine einfache explizite Lösung gibt, so wàren mir auch Rekursionsformeln
recht (und für meine Zwecke ausreichend).

Schöne Grüße
Armin Saam
 

Lesen sie die antworten

#1 Stefan Kirchner
16/03/2008 - 16:24 | Warnen spam
On Sun, 16 Mar 2008, Armin Saam wrote:

Seit kurzem beschàftigt mich folgendes Anzahlproblem:

Es sei A die Menge aller Zahlen, die in ihrer Dezimaldarstellung keine zwei
benacharten 9en haben, a(n) sei die Anzahl der Elemente von A mit n Ziffern
(also von 0 bis 10^n -1).



Hallo Armin,

ich unterteile die Menge A noch weiter, je nachdem, ob die Zahl auf 9
endet oder nicht. Sei also a_9(n) die Anzahl der Elemente aus A mit n
Ziffern, die auf 9 enden und a_*(n) die Anzahl der Elemente aus A mit n
Ziffern, die nicht auf 9 enden.

Dann gilt zunàchst a(n) = a_9(n) + a_.(n)

Gesucht ist sind die Anzahlfunktionen a(n) und b(n).

Mit meinen ersten Lösungsversuchen bin ich noch nicht zu einem
befriedigenden Resultat gekommen. Fest steht für mich allerdings schon
jetzt, dass es zwei knifflige Problemchen sind, die ihren Reiz haben.
Wenn's keine einfache explizite Lösung gibt, so wàren mir auch
Rekursionsformeln recht (und für meine Zwecke ausreichend).




In der Hoffnung, keinem Irrtum zu unterliegen:

Es gilt a_9(n+1) = a_.(n), denn es wird einfach eine neun rechts
angehàngt.
Außerdem gilt a_.(n+1) = 9 * a_(n), denn man kann jeweils neun gültige
Ziffern {0,...,8} an jede Zahl aus A(n) an rechts dranhàngen, um eine
Zahl mit n+1 Ziffern zu erhalten, die nicht auf 9 endet.

Insgesamt folgt daraus die Rekursiongleichung
a_.(n+2) = 9 * a_(n+1)
= 9 * (a_9(n+1) + a_.(n+1))
= 9 * (a_.(n) + a_.(n+1)),

also eine Art skalierte Fibonaccirekursion -- hat diese einen speziellen
Namen? Wie auch immer, es handelt sich allgemein um eine lineare
Differenzengleichung zweiter Ordnung, die mit Standardmitteln in eine
explizite Darstellung überführt werden kann. Daraus làßt sich dann auch
a_9(n), a(n) und b(n) gewinnen.

Startwerte sind dabei a_9(1) = 1 und a_.(1) = 8 [0 gehöre nicht dazu]
und a_9(2) = 8 und a_.(2) = 81




Gruß Stefan

Ähnliche fragen