Die Mathe-Redaktion - 15.10.2019 03:26 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 750 Gäste und 3 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Inklusion-Exklusion » Inklusions-Exklusions-Prinzip - Anwendung
Druckversion
Druckversion
Autor
Universität/Hochschule J Inklusions-Exklusions-Prinzip - Anwendung
Newmath2012
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 26.09.2013
Mitteilungen: 363
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-09-20 14:48


Hallo allerseits,
meine Frage ist die gleiche wie in diesem Thread:
[EDIT: Ich hatte leider den falschen Thread verlinkt. Hier nun der richtige: matheplanet.com/default3.html?call=viewtopic.php?topic=227852&ref=https%3A%2F%2Fwww.google.com%2F]

Es geht also um die Frage, wieviele Zahlen 0 <= n < 10000 gibt es, bei denen in der Dezimaldarstellung keine zwei ungeraden Ziffern nebeneinander stehen?

Ich komme mit Anwendung des Inklusions- Exklusions- Prinzips auf 5000 und dieses Ergebnis scheint mir aber sehr unwahrscheinlich. In dem verlinkten Thread habe ich am Ende genau beschrieben, wie ich darauf gekommen bin: ich habe vierstellige Zahlen mit unterschiedlichen Ziffern belegt.
Nun frage ich mich aber, ob man nicht auch 1- 2- und 3- stellige Zahlen extra abhandeln muss (und wenn nicht, warum nicht)? Weil man sich da an den freien Stellen einfach 0er vorstellen kann? Und wenn ja, warum?



  Profil  Quote  Link auf diesen Beitrag Link
Diophant
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.01.2019
Mitteilungen: 1891
Aus: Rosenfeld, BW
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-09-20 15:46


Hallo,

also der verlinkte Thread behandelt aber eine grundsätzlich andere Frage. Hast du da aus Versehen den falschen Thread verlinkt?

Ich will jetzt nicht ausschließen, dass man das ganze mit der Siebformel (also dem Prinzip von Inklusion und Exklusion) angehen kann, das erscheint mir aber wenn überhaupt hier eher ziemlich 'oversized'.

Ich würde in der Tat alle vier möglichen Stellenzahlen getrennt behandeln und zwar schon aus dem Grund, dass für jede Stellenzahl die möglichen Konstellationen jeweils andere sind:

  • 1 Stelle: da werden alle gezählt.
  • 2 Stellen: alle Zahlen, die nicht aus zwei ungeraden Ziffern gebildet sind.
  • 3 Stellen: alle Zahlen mit entweder keiner oder genau einer ungeraden Ziffer. Außerdem mit zwei, wobei diese an der ersten und der letzten Stelle stehen müssen.
  • 4 Stellen: alle Zahlen mit keiner oder einer ungeraden Ziffer. Außerdem mit zwei, wobei folgende Ziffernbelegungen denkbar sind: gugu, uggu, ugug.


    Gruß, Diophant




  •   Profil  Quote  Link auf diesen Beitrag Link
    StrgAltEntf
    Senior Letzter Besuch: in der letzten Woche
    Dabei seit: 19.01.2013
    Mitteilungen: 5161
    Aus: Milchstraße
    Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2019-09-20 20:27


    Hallo,

    die 1-, 2- und 3-stelligen Zahlen brauchen nicht gesondert betrachtet zu werden.
    Insgesamt gibt es 8 Fälle:
    gggg
    gggu
    ggug
    gugg
    uggg
    gugu
    uggu
    ugug

    Für jedes g und jedes u gibt es 5 Möglichkeiten. Insgesamt also tatsächlich  8 * 5^4 = 5000 Möglichkeiten. (Überrascht mich auch smile )

    Die 1-, 2- und 3-stelligen Zahlen sind bei der Zählung enthalten, da sie als Zahlen mit führenden Nullen (die gerade sind) interpretiert werden können.



      Profil  Quote  Link auf diesen Beitrag Link
    Newmath2012
    Aktiv Letzter Besuch: in der letzten Woche
    Dabei seit: 26.09.2013
    Mitteilungen: 363
    Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2019-09-21 02:00


    Hallo Diophant,
    danke für deine Antwort und den Hinweis bzgl. Link. Ich hatte tatsächlich den falschen eingefügt und habe dies nun ausgebessert.
    Danke auch für deine Erklärung der alternativen Vorgehensweise! Ich werde mir anschauen, ob das auch mir einfacher erscheint. :)



      Profil  Quote  Link auf diesen Beitrag Link
    Newmath2012
    Aktiv Letzter Besuch: in der letzten Woche
    Dabei seit: 26.09.2013
    Mitteilungen: 363
    Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2019-09-21 02:03


    Hallo StrgAltEntf!
    Danke für deine Hilfe! (Und freut mich, dass sogar du über die 5.000 verwundert bist.^^)
    Das mit den führenden 0en finde ich irgendwie antiintuitiv, dass diese Fälle in den Fallunterscheidungen mit 4 Stellen schon inkludiert sind, weil es ja so "Spezialfälle" von gggg bzw. gggu sind. Aber das muss ich wohl einfach so hinnehmen.



      Profil  Quote  Link auf diesen Beitrag Link
    Diophant
    Senior Letzter Besuch: in der letzten Woche
    Dabei seit: 18.01.2019
    Mitteilungen: 1891
    Aus: Rosenfeld, BW
    Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2019-09-21 08:47


    Hallo zusammen,

    StrgAltEntf hat natürlich völlig Recht: ich habe da um zu viele Ecken herum gedacht.

    @Newmath2012:
    Mich würde es interessieren, wie dein Weg mit der Siebformel aussieht.


    Gruß, Diophant



      Profil  Quote  Link auf diesen Beitrag Link
    StrgAltEntf
    Senior Letzter Besuch: in der letzten Woche
    Dabei seit: 19.01.2013
    Mitteilungen: 5161
    Aus: Milchstraße
    Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2019-09-21 10:39


    Hallo Newmath2012 ,

    2019-09-21 02:03 - Newmath2012 in Beitrag No. 4 schreibt:
    Das mit den führenden 0en finde ich irgendwie antiintuitiv, dass diese Fälle in den Fallunterscheidungen mit 4 Stellen schon inkludiert sind, weil es ja so "Spezialfälle" von gggg bzw. gggu sind. Aber das muss ich wohl einfach so hinnehmen.

    Wir sind hier doch nicht bei den Juristen, wo man unlogische Gesetzgebungen "einfach so hinnehmen" muss.

    Hier ist es doch wirklich einfach: Eine dreistellige Zahl hat genau dann keine zwei benachbarten ungeraden Ziffern, wenn es für die Zahl gilt, bei der eine Null davor geschrieben wird. (Für ein- und zweistellige Zahlen entsprechend.) Das liegt daran, dass 0 gerade ist.

    Übrigens ist die Fragestellung "wie viele bis zu vierstellige Zahlen gibt es, die keine zwei benachbarten GERADEN Ziffern haben?" komplizierter. Beispielweise hat 234 keine zwei benachbarten geraden Ziffern, 0234 aber schon.



      Profil  Quote  Link auf diesen Beitrag Link
    OlgaBarati
    Aktiv Letzter Besuch: in der letzten Woche
    Dabei seit: 16.11.2018
    Mitteilungen: 178
    Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2019-09-21 14:57


    2019-09-21 10:39 - StrgAltEntf in Beitrag No. 6 schreibt:
    Übrigens ist die Fragestellung "wie viele bis zu vierstellige Zahlen gibt es, die keine zwei benachbarten GERADEN Ziffern haben?" komplizierter. Beispielweise hat 234 keine zwei benachbarten geraden Ziffern, 0234 aber schon.

    Das müssten analog auch 5000 von den insgesamt 10000 (0000 bis 9999) Möglichkeiten sein oder ?


    -----------------
    oLGa



      Profil  Quote  Link auf diesen Beitrag Link
    Diophant
    Senior Letzter Besuch: in der letzten Woche
    Dabei seit: 18.01.2019
    Mitteilungen: 1891
    Aus: Rosenfeld, BW
    Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2019-09-21 15:10


    @OlgaBarati:

    2019-09-21 14:57 - OlgaBarati in Beitrag No. 7 schreibt:
    2019-09-21 10:39 - StrgAltEntf in Beitrag No. 6 schreibt:
    Übrigens ist die Fragestellung "wie viele bis zu vierstellige Zahlen gibt es, die keine zwei benachbarten GERADEN Ziffern haben?" komplizierter. Beispielweise hat 234 keine zwei benachbarten geraden Ziffern, 0234 aber schon.

    Das müssten analog auch 5000 von den insgesamt 10000 (0000 bis 9999) Möglichkeiten sein oder ?

    Kommt es jetzt nicht darauf an, ob man die führenden Nullen berücksichtigt oder nicht? Für gewöhnlich tut man das nicht und dann sollten es IMO mehr sein.


    Gruß, Diophant



      Profil  Quote  Link auf diesen Beitrag Link
    OlgaBarati
    Aktiv Letzter Besuch: in der letzten Woche
    Dabei seit: 16.11.2018
    Mitteilungen: 178
    Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2019-09-21 15:33


    Ja, das stimmt, es gilt nur wenn die Nullen auch voran gestellt werden.
    Was richtigerweise bei "normaler" Dezimaldarstellung nicht der Fall ist und es somit mehr als 5000 Möglichkeiten wären. Richtig wäre es nur dann, wenn man die vier Stellen quasi als Code von einem Zahlenschloss betrachtet.


    -----------------
    oLGa



      Profil  Quote  Link auf diesen Beitrag Link
    OlgaBarati
    Aktiv Letzter Besuch: in der letzten Woche
    Dabei seit: 16.11.2018
    Mitteilungen: 178
    Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2019-09-21 16:00


    u	u	u	u	625
    u	u	u	g	625
    u	u	g	u	625
    u	g	u	u	625
    g	u	u	u	500
    u	g	u	g	625
    g	u	u	g	500
    g	u	g	u	500
             			4625
    10000-4625=5375
    Kann das stimmen ? Bin da gar nicht so sicher.


    -----------------
    oLGa



      Profil  Quote  Link auf diesen Beitrag Link
    Diophant
    Senior Letzter Besuch: in der letzten Woche
    Dabei seit: 18.01.2019
    Mitteilungen: 1891
    Aus: Rosenfeld, BW
    Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2019-09-21 16:13


    Hallo OlgaBarati,

    das* sind jetzt alle vierstelligen Zahlen. Dazu müsste man jetzt noch die Anzahl der gültigen ein- bis dreistelligen Zahlen addieren (denn du hast ja bei allen, die mit einer geraden Ziffer beginnen, die Null herausgehalten).

    Ich wäre es genauso angegangen. Die Frage ist, ob man das irgendwie geschlossen kombinatorisch knacken kann?


    Gruß, Diophant

    * EDIT: die abgezählten 4625.



      Profil  Quote  Link auf diesen Beitrag Link
    OlgaBarati
    Aktiv Letzter Besuch: in der letzten Woche
    Dabei seit: 16.11.2018
    Mitteilungen: 178
    Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2019-09-21 16:33


    2019-09-21 16:13 - Diophant in Beitrag No. 11 schreibt:
    Hallo OlgaBarati,
    ... Dazu müsste man jetzt noch die Anzahl der gültigen ein- bis dreistelligen Zahlen addieren...

    Genau das war der fragliche Punkt. Vor jeder dieser Zahlen steht ja zwangsläufig eine ungerade Zahl. Würde man mit der Addition der ein- bis dreistelligen Zahlen diese dann nicht doppelt zählen ?



    -----------------
    oLGa



      Profil  Quote  Link auf diesen Beitrag Link
    Diophant
    Senior Letzter Besuch: in der letzten Woche
    Dabei seit: 18.01.2019
    Mitteilungen: 1891
    Aus: Rosenfeld, BW
    Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2019-09-21 16:43


    2019-09-21 16:33 - OlgaBarati in Beitrag No. 12 schreibt:
    2019-09-21 16:13 - Diophant in Beitrag No. 11 schreibt:
    Hallo OlgaBarati,
    ... Dazu müsste man jetzt noch die Anzahl der gültigen ein- bis dreistelligen Zahlen addieren...
    Genau das war der fragliche Punkt. Vor jeder dieser Zahlen steht ja zwangsläufig eine ungerade Zahl. Würde man mit der Addition der ein- bis dreistelligen Zahlen diese dann nicht doppelt zählen ?

    Warum? wenn man eben keine führenden Nullen zulässt, dürfen diese Zahlen ja durchaus mit geraden Ziffern beginnen. Anderenfalls wären es ja in der Tat wieder die 5000 Möglichkeiten.

    Ich kann so langsam schon verstehen, warum der TS hier in Richtung Prinzip von Inklusion und Exklusion (Siebformel) überlegt hat. Ich sehe nur nicht, wie das gehen könnte...


    Gruß, Diophant



      Profil  Quote  Link auf diesen Beitrag Link
    OlgaBarati
    Aktiv Letzter Besuch: in der letzten Woche
    Dabei seit: 16.11.2018
    Mitteilungen: 178
    Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, eingetragen 2019-09-21 17:20


    Ja  so stimmts, stand da wohl auf dem Schlauch.


    -----------------
    oLGa



      Profil  Quote  Link auf diesen Beitrag Link
    StrgAltEntf
    Senior Letzter Besuch: in der letzten Woche
    Dabei seit: 19.01.2013
    Mitteilungen: 5161
    Aus: Milchstraße
    Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, eingetragen 2019-09-21 17:56


    2019-09-21 16:00 - OlgaBarati in Beitrag No. 10 schreibt:
    u	u	u	u	625
    u	u	u	g	625
    u	u	g	u	625
    u	g	u	u	625
    g	u	u	u	500
    u	g	u	g	625
    g	u	u	g	500
    g	u	g	u	500
             			4625


    Wie Diophant bereits bemerkte, fehlen
    u      5
    g      5
    u u    25
    u g    25
    g u    20
    u u u  125
    u u g  125
    u g u  125
    g u u  100
    g u g  100
           655
    Insgesamt also 5280.



      Profil  Quote  Link auf diesen Beitrag Link
    StrgAltEntf
    Senior Letzter Besuch: in der letzten Woche
    Dabei seit: 19.01.2013
    Mitteilungen: 5161
    Aus: Milchstraße
    Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, eingetragen 2019-09-21 18:49

    \(\begingroup\)\( \newcommand{\ba}{\begin{aligned}} \newcommand{\ea}{\end{aligned}} \newcommand{\bpm}{\begin{pmatrix}} \newcommand{\epm}{\end{pmatrix}} \newcommand{\bc}{\begin{cases}} \newcommand{\ec}{\end{cases}}\)
    2019-09-21 16:13 - Diophant in Beitrag No. 11 schreibt:
    Die Frage ist, ob man das irgendwie geschlossen kombinatorisch knacken kann?

    Hier mal eine Idee:
    Es sei
    \(u_n\) die Anzahl der n-stelligen Zahlen, bei denen keine zwei geraden Ziffern nebeneinander stehen und die auf eine ungerade Ziffer enden,
    \(g_n\) die Anzahl der n-stelligen Zahlen, bei denen keine zwei geraden Ziffern nebeneinander stehen und die auf eine gerade Ziffer enden.

    Dann gilt folgende Rekursion.
    \(u_{n+1}=5(u_n+g_n)\), \(g_{n+1}=5u_n\) für \(n\geq2\).
    Außerdem \(u_1=g_1=5\), \(u_2=45\), \(g_2=25\).
    n	u_n	g_n	u_n+g_n kumuliert
    1	5	5	10	10
    2	45	25	70	80
    3	350	225	575	655
    4	2875	1750	4625	5280
    5	23125	14375	37500	42780
    6	187500	115625	303125	345905
    7	1515625	937500	2453125	2799030
    (Man bemerke in der 4. Zeile die Zahlen 4625 und 5280.)

    Die Rekursionsformel erinnert stark an die Fibonacci-Folge. Man kann auch folgendes schreiben.
    \[\binom{u_{n+1}}{g_{n+1}}=\left(\begin{array}05 & 5\\5 & 0\end{array}\right)\binom{u_n}{g_n}\] bzw.
    \[\binom{u_{n}}{g_{n}}=\left(\begin{array}05 & 5\\5 & 0\end{array}\right)^{n-2}\binom{u_2}{g_2} = 5^{n-1}\left(\begin{array}01 & 1\\1 & 0\end{array}\right)^{n-2}\binom{9}{5},~n\geq2\] Die Einträge von \(\left(\begin{array}01 & 1\\1 & 0\end{array}\right)^{n-2}\) sind die Folgeglieder der Fibonacci-Folge, soweit ich mich erinnere.
    Bildet man in obiger Tabelle \((u_n+g_n)/5^{n-1}\), so ergibt das
    n	u_n	g_n	u_n+g_n (u_n+g_n)/5^(n-1)
    1	5	5	10	10
    2	45	25	70	14
    3	350	225	575	23
    4	2875	1750	4625	37
    5	23125	14375	37500	60
    6	187500	115625	303125	97
    7	1515625	937500	2453125	157
    Die letzte Spalte gehorcht (ab n=2) tatsächlich dem Bildungsgesetz der Fibonacci-Folge.

    \(\endgroup\)


      Profil  Quote  Link auf diesen Beitrag Link
    Diophant
    Senior Letzter Besuch: in der letzten Woche
    Dabei seit: 18.01.2019
    Mitteilungen: 1891
    Aus: Rosenfeld, BW
    Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, eingetragen 2019-09-21 19:03

    \(\begingroup\)\( \newcommand{\ba}{\begin{aligned}} \newcommand{\ea}{\end{aligned}} \newcommand{\bpm}{\begin{pmatrix}} \newcommand{\epm}{\end{pmatrix}} \newcommand{\bc}{\begin{cases}} \newcommand{\ec}{\end{cases}}\)
    Hallo StrgAltEntf,

    das ist freilich ein genialer Ansatz*. Ich habe kurz gebraucht, um das mit dem Startvektor und der Fünfer-Potenz zu verstehen, aber ich kann das jetzt komplett nachvollziehen.

    * Mit den Fibonacci-Zahlen und deiner Matrix ist es ja so, dass

    \[\bpm 1&1\\1&0\epm^n=\bpm f_{n+1}&f_n\\f_n&f_{n-1}\epm\]
    gilt.


    Gruß, Diophant
    \(\endgroup\)


      Profil  Quote  Link auf diesen Beitrag Link
    StrgAltEntf
    Senior Letzter Besuch: in der letzten Woche
    Dabei seit: 19.01.2013
    Mitteilungen: 5161
    Aus: Milchstraße
    Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, eingetragen 2019-09-21 20:52

    \(\begingroup\)\( \newcommand{\ba}{\begin{aligned}} \newcommand{\ea}{\end{aligned}} \newcommand{\bpm}{\begin{pmatrix}} \newcommand{\epm}{\end{pmatrix}} \newcommand{\bc}{\begin{cases}} \newcommand{\ec}{\end{cases}}\)
    2019-09-21 19:03 - Diophant in Beitrag No. 17 schreibt:
    Mit den Fibonacchi-Zahlen und deiner Matrix ist es ja so, dass

    \[\bpm 1&1\\1&0\epm^n=\bpm f_{n+1}&f_n\\f_n&f_{n-1}\epm\]
    gilt.

    Okay, damit kommen wir dann weiter. Um die Sache noch etwas zu vereinfachen, nehmen wir die Zahl 0 aus der Betrachtung heraus, sodass \(u_1=5,g_1=4\). Dann gilt die Rekursionsformel für \(n\geq1\). Außerdem
    \[\binom{u_n}{g_n}=5^{n-1}\bpm 1&1\\1&0\epm^{n-1}\binom54,~n\geq1\] Mit Diophants Formel folgt dann für \(n\geq1\)
    \[u_n+g_n=5^{n-1}(9f_n+5f_{n-1}),\] wobei \(f_0,f_1,f_2,f_3,...=0,1,1,2,...\) die Fibonaccifolge ist.
    \(\endgroup\)


      Profil  Quote  Link auf diesen Beitrag Link
    OlgaBarati
    Aktiv Letzter Besuch: in der letzten Woche
    Dabei seit: 16.11.2018
    Mitteilungen: 178
    Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.19, eingetragen 2019-09-22 01:19


    ....nicht schlecht


    -----------------
    oLGa



      Profil  Quote  Link auf diesen Beitrag Link
    HellsKitchen
    Senior Letzter Besuch: in der letzten Woche
    Dabei seit: 02.01.2012
    Mitteilungen: 241
    Aus: Fürth in Bayern
    Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.20, eingetragen 2019-09-22 13:24


    Ich habe folgende Formeln gefunden:

    Sei \(f_{n,k}\) die Anzahl der k-Untermengen von {1, ..., n},
    die keine aufeinanderfolgende Zahlen enthalten.

    Dann gelten folgende Formeln:

    \(f_{n,k} = \binom{n-k+1}{k}\) und \(\sum\limits_{k} f_{n,k} = F_{n+2}\)
    wobei \(F_{n}\) die n-te Fibonacci Zahl ist.

    Gruß HellsKitchen



      Profil  Quote  Link auf diesen Beitrag Link
    Newmath2012
    Aktiv Letzter Besuch: in der letzten Woche
    Dabei seit: 26.09.2013
    Mitteilungen: 363
    Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.21, vom Themenstarter, eingetragen 2019-09-22 14:58


    Hallo StrgAltEnt,
    du hast natürlich Recht!
    Das bedeutet, bei der Frage mit den ungeraden Nachbarn ist es egal, ob man von einer Dezimaldarstellung mit führenden 0en oder einer ohne ausgeht, und bei der Frage mit geraden Nachbarn kommt man bei beiden Fragestellungen auf unterschiedliche Ergebnisse, richtig?

    Was ist denn die üblichere Variante - dass man unter Dezimaldarstellung versteht, dass die 0en als Platzhalter dabei sind oder nicht?

    (Olga Barati und Diophant haben das ja schon diskutiert, aber ich würde gernen noch wissen, um ich das Wesentliche daran richtig verstanden habe. ;) )

    EDIT: Ich verstehe in deinen Ausführungen die Spalte "kumuliert" leider nicht. Was meinst du damit?



      Profil  Quote  Link auf diesen Beitrag Link
    Newmath2012
    Aktiv Letzter Besuch: in der letzten Woche
    Dabei seit: 26.09.2013
    Mitteilungen: 363
    Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.22, vom Themenstarter, eingetragen 2019-09-22 14:59


    Hallo Diophant,

    den Weg mit der Siebformeln habe ich im verlinkten Thread am Ende beschrieben.




      Profil  Quote  Link auf diesen Beitrag Link
    Diophant
    Senior Letzter Besuch: in der letzten Woche
    Dabei seit: 18.01.2019
    Mitteilungen: 1891
    Aus: Rosenfeld, BW
    Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.23, eingetragen 2019-09-22 15:05


    Hallo,

    ich antworte mal 'stellvertretend'.

    2019-09-22 14:58 - Newmath2012 in Beitrag No. 21 schreibt:
    Das bedeutet, bei der Frage mit den ungeraden Nachbarn ist es egal, ob man von einer Dezimaldarstellung mit führenden 0en oder einer ohne ausgeht, und bei der Frage mit geraden Nachbarn kommt man bei beiden Fragestellungen auf unterschiedliche Ergebnisse, richtig?

    Genau so ist es.
     
    2019-09-22 14:58 - Newmath2012 in Beitrag No. 21 schreibt:
    Was ist denn die üblichere Variante - dass man unter Dezimaldarstellung versteht, dass die 0en als Platzhalter dabei sind oder nicht?

    Allgemein schreibt man keine führenden Nullen, oder hättest du das schon einmal irgendwo gesehen?  wink

    Einen Kontext, in dem das jedoch der Fall ist, nämlich Zahlenschlösser, hat OlgaBarati ja in Beitrag #9 schon erwähnt.

    2019-09-22 14:59 - Newmath2012 in Beitrag No. 22 schreibt:
    den Weg mit der Siebformeln habe ich im verlinkten Thread am Ende beschrieben.

    Ja, ich war noch nicht dazugekommen, mir das anzusehen (sorry). Aber das ist natürlich dann von allen Varianten die einfachste.  smile

    Für uns war es hier jedenfalls eine schöne Spielwiese.  biggrin


    Gruß, Diophant



      Profil  Quote  Link auf diesen Beitrag Link
    StrgAltEntf
    Senior Letzter Besuch: in der letzten Woche
    Dabei seit: 19.01.2013
    Mitteilungen: 5161
    Aus: Milchstraße
    Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.24, eingetragen 2019-09-22 15:56


    2019-09-22 14:58 - Newmath2012 in Beitrag No. 21 schreibt:
    EDIT: Ich verstehe in deinen Ausführungen die Spalte "kumuliert" leider nicht. Was meinst du damit?

    Das heißt so viel wie aufsummiert. Man möchte ja die Anzahl aller Zahlen mit einer bestimmten Eigenschaft bestimmen, die kleiner als 10000 sind. Dazu bestimmt man dann die Anzahl der ein-, zwei-, drei- und vier-stelligen Zahlen und summiert die Anzahlen. Hier: 5280 = 10 + 70 + 575 + 4625

    Zu den führenden Nullen:
    Man hat ja den schöne Theorem, dass sich jede ganze Zahl eindeutig im Dezimalsystem darstellen lässt. Wenn man führende Nullen zulässt, hätte man das Theorem nicht mehr. (Aus ähnlichen Gründen zählt man 1 nicht zu den Primzahlen.)



      Profil  Quote  Link auf diesen Beitrag Link
    StrgAltEntf
    Senior Letzter Besuch: in der letzten Woche
    Dabei seit: 19.01.2013
    Mitteilungen: 5161
    Aus: Milchstraße
    Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.25, eingetragen 2019-09-22 18:28


    Hallo HellsKitchen,

    2019-09-22 13:24 - HellsKitchen in Beitrag No. 20 schreibt:
    \(\sum\limits_{k} f_{n,k} = F_{n+2}\)

    Eine nette Formel! Ist sie für unser Problem nützlich?



      Profil  Quote  Link auf diesen Beitrag Link
    Newmath2012
    Aktiv Letzter Besuch: in der letzten Woche
    Dabei seit: 26.09.2013
    Mitteilungen: 363
    Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.26, vom Themenstarter, eingetragen 2019-09-23 17:48


    Hallo Diophant und StrgAltEntf,

    vielen Dank für euere Hilfe! Es ist mir nun alles klar. :)



      Profil  Quote  Link auf diesen Beitrag Link
    HellsKitchen
    Senior Letzter Besuch: in der letzten Woche
    Dabei seit: 02.01.2012
    Mitteilungen: 241
    Aus: Fürth in Bayern
    Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.27, eingetragen 2019-09-25 11:30


    Hallo StrgAltEntf,

    2019-09-22 18:28 - StrgAltEntf in Beitrag No. 25 schreibt:

    2019-09-22 13:24 - HellsKitchen in Beitrag No. 20 schreibt:
    \(\sum\limits_{k} f_{n,k} = F_{n+2}\)

    Eine nette Formel! Ist sie für unser Problem nützlich?

    Sie ist in der Tat nützlich.

    Im allgemeinen n-stelligen Fall lautet die Lösung nämlich: \(5^n * F_{n+2}\), dass kann man
    mit den beiden Formeln in No. 20 gut begründen.

    Für n = 4 speziell: \(5^4 * F_6 = 625 * 8 = 5000\)

    Gruß HellsKitchen



      Profil  Quote  Link auf diesen Beitrag Link
    StrgAltEntf
    Senior Letzter Besuch: in der letzten Woche
    Dabei seit: 19.01.2013
    Mitteilungen: 5161
    Aus: Milchstraße
    Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.28, eingetragen 2019-09-25 21:27


    2019-09-25 11:30 - HellsKitchen in Beitrag No. 27 schreibt:
    Im allgemeinen n-stelligen Fall lautet die Lösung nämlich: \(5^n * F_{n+2}\), dass kann man
    mit den beiden Formeln in No. 20 gut begründen.

    Für n = 4 speziell: \(5^4 * F_6 = 625 * 8 = 5000\)

    Ach so, vielen Dank smile

    Ich hatte nicht bemerkt, dass du dich auf die ursprüngliche Aufgabe (mit den ungeraden Ziffern) beziehst. Das ist wirklch eine schöne Begründung und ein interessanter Zusammenhang. (Und die Formel ist selbstverständlich eleganter als für den "geraden Fall".)

    Grüße
    StrgAltEntf



      Profil  Quote  Link auf diesen Beitrag Link
    Newmath2012 hat die Antworten auf ihre/seine Frage gesehen.
    Newmath2012 hat selbst das Ok-Häkchen gesetzt.
    Neues Thema [Neues Thema]  Druckversion [Druckversion]

     


    Wechsel in ein anderes Forum:
     Suchen    
     
    All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
    This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
    Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
    Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
    [Seitenanfang]