Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Frage zur Folge A144332 7,14,11,3,11,30,35,19
Autor
Universität/Hochschule Frage zur Folge A144332 7,14,11,3,11,30,35,19
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1842
  Themenstart: 2022-08-21

Frage zur OEIS Folge A144332 Dort steht einfach A144328 * A007318 aber keine weiteren Infos (untypisch für OEIS!). Egal was man versucht, mit "Multiplikation" kommt man nicht auf diese Zahlen: https://matheplanet.com/matheplanet/nuke/html/uploads/b/47407_Folge.PNG Schon die Betrachtung der "19" kann wegen Primzahl nur durch Multiplikation mit 1 entstehen. Selbst Offsetverschiebungen der A144328 (bis 19/1 daraus wird) funktionieren nicht... Auch Interpretation des "*" als "Dot-Produkt" von Blöcken ergibt \sourceon nameDerSprache 1, 2, 5, 13, 33, 81, 193, 449, 1025,... \sourceoff was völlig anderes. Die angeblich beteiligte Binomial-Folge A007318 hat keine 19! Auch Blockschreibweise hilft nicht weiter: \sourceon A007318 in Block-Form-Schreibweise {1},{1,1},{1,2,1},{1,3,3,1},{1,4,6,4,1},{1,5,10,10,5,1},{1,6,15,20,15,6,1},{1,7,21,35,35,21,7,1},{1,8,28,56,70,56,28,8,1},{1,9,36,84,126,126,84,36,9,1},... \sourceoff Ich hätte zwar einen komplizierten langen Algorithmus für die Folge, aber der würde hier nur verwirren. Was läuft da zwischen Zahlen & Algorithmus schief? Schreibfehler?


   Profil
zippy
Senior Letzter Besuch: im letzten Monat
Dabei seit: 24.10.2018
Mitteilungen: 4179
  Beitrag No.2, eingetragen 2022-08-21

\quoteon(2022-08-21 14:06 - hyperG im Themenstart) Egal was man versucht, mit "Multiplikation" kommt man nicht auf diese Zahlen \quoteoff Das ist einfach die Multiplikation von Matrizen:$$ \begin{pmatrix} 1\\ 2&1\\ 4&5&2\\ 7&14&11&3\\ 11&30&35&19&4\\ 16&55&85&69&29&5\\ 22&91&175&189&119&41&6\\ 29&140&322&434&364&188&55&7\\ \end{pmatrix} = \begin{pmatrix} 1\\ 1&1\\ 1&1&2\\ 1&1&2&3\\ 1&1&2&3&4\\ 1&1&2&3&4&5\\ 1&1&2&3&4&5&6\\ 1&1&2&3&4&5&6&7\\ \end{pmatrix} \cdot \begin{pmatrix} 1\\ 1&1\\ 1&2&1\\ 1&3&3&1\\ 1&4&6&4&1\\ 1&5&10&10&5&1\\ 1&6&15&20&15&6&1\\ 1&7&21&35&35&21&7&1\\ \end{pmatrix} $$--zippy


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1842
  Beitrag No.3, vom Themenstarter, eingetragen 2022-08-21

\quoteon(2022-08-21 14:23 - Buri in Beitrag No. 1) Hi hyperG, deine A007318 in Blockschreibweise ist doch das Pascalsche Dreieck aus den Binomialkoeffizienten. Gruß Buri \quoteoff Das ist ja alles bekannt und steht schon auf der Seite selbst. Das "Triangle read by rows" ist noch unklar. Deshalb hier mal die "Dreieck-Schreibweise" (triangle) dieser 3 Folgen: \sourceon A144328 * A007318 = A144332 1; A144328 1, 1; 1, 1, 2; 1, 1, 2, 3; 1, 1, 2, 3, 4; 1, 1, 2, 3, 4, 5; 1, 1, 2, 3, 4, 5, 6; "*" Algorithmus ?? +1 A007318 alternierend negiert mit (-1)^(k + n) -1 +1 +1 -2 ,+1 -1 +3 ,-3 +1 +1 -4 ,+6 -4, +1 -1, 5,-10,10, -5, 1 = 1; A144332 2, 1 4, 5, 2; 7, 14, 11, 3; 11, 30, 35, 19, 4; 16, 55, 85, 69, 29, 5; 22, 91, 175, 189, 119, 41, 6; 29, 140, 322, 434, 364, 188, 55, 7; \sourceoff [Die Antwort wurde nach Beitrag No.1 begonnen.]


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1842
  Beitrag No.4, vom Themenstarter, eingetragen 2022-08-21

\quoteon(2022-08-21 17:22 - zippy in Beitrag No. 2) \quoteon(2022-08-21 14:06 - hyperG im Themenstart) Egal was man versucht, mit "Multiplikation" kommt man nicht auf diese Zahlen \quoteoff Das ist einfach die Multiplikation von Matrizen:$$ \begin{pmatrix} 1\\ 2&1\\ 4&5&2\\ 7&14&11&3\\ 11&30&35&19&4\\ 16&55&85&69&29&5\\ 22&91&175&189&119&41&6\\ 29&140&322&434&364&188&55&7\\ \end{pmatrix} = \begin{pmatrix} 1\\ 1&1\\ 1&1&2\\ 1&1&2&3\\ 1&1&2&3&4\\ 1&1&2&3&4&5\\ 1&1&2&3&4&5&6\\ 1&1&2&3&4&5&6&7\\ \end{pmatrix} \cdot \begin{pmatrix} 1\\ 1&1\\ 1&2&1\\ 1&3&3&1\\ 1&4&6&4&1\\ 1&5&10&10&5&1\\ 1&6&15&20&15&6&1\\ 1&7&21&35&35&21&7&1\\ \end{pmatrix} $$--zippy \quoteoff Ah, danke zippy. War also doch das von mir vermutete "Dot-Produkt". Nur hatte ich 1-Dimensionale Matritzen mit variabler Länge angenommen. Hier sind es aber zweidimensionele Arrays mit Rest-Auffüllung mit 0 für konst. Länge eines zu betrachtenden Blockes: Die Null-Aufgefüllten 2-D-Arrays können z.B. in Mathematica mit "." berechnet werden: \sourceon mathematica max=11; A144328N = Table[Which[n < 1, 1, n > m, 0, n > 0 && n <= m, n], {m, 0, max}, {n, 0, max}]; A007318N = Table[If[k <= n, Binomial[n, k], 0], {n, 0, max}, {k, 0, max}] ; A144328N.A007318N; TraditionalForm[%] Out: 1 0 0 0 0 0 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 4 5 2 0 0 0 0 0 0 0 0 0 7 14 11 3 0 0 0 0 0 0 0 0 11 30 35 19 4 0 0 0 0 0 0 0 16 55 85 69 29 5 0 0 0 0 0 0 22 91 175 189 119 41 6 0 0 0 0 0 29 140 322 434 364 188 55 7 0 0 0 0 37 204 546 882 924 636 279 71 8 0 0 0 46 285 870 1638 2058 1770 1035 395 89 9 0 0 56 385 1320 2838 4158 4290 3135 1595 539 109 10 0 67 506 1925 4653 7788 9372 8217 5225 2354 714 131 11 \sourceoff Dann alle Nullen entfernen und die Zeilen hintereinander schreiben ... Man muss also schon vor Berechnungsstart die Länge definieren und kann nicht: a) nachträglich rekursiv erweitern b) explizit einzelne "Punkte" berechnen Dieser lange Algorithmus steckt also hinter dem "*"!!! https://matheplanet.com/matheplanet/nuke/html/images/forum/subject/rotate.gif


   Profil
zippy
Senior Letzter Besuch: im letzten Monat
Dabei seit: 24.10.2018
Mitteilungen: 4179
  Beitrag No.5, eingetragen 2022-08-21

\quoteon(2022-08-21 18:08 - hyperG in Beitrag No. 4) Hier sind es aber zweidimensionele Arrays mit Rest-Auffüllung mit 0 für konst. Länge eines zu betrachtenden Blockes: \quoteoff Die Zahlen sind halt genau so anzuordnen, wie sie auf OEIS unter "EXAMPLE" auch dargestellt werden. \quoteon(2022-08-21 18:08 - hyperG in Beitrag No. 4) Man muss also schon vor Berechnungsstart die Länge definieren und kann nicht: a) nachträglich rekursiv erweitern b) explizit einzelne "Punkte" berechnen \quoteoff Das scheinen mir jetzt eher Einschränkungen deiner Umsetzung in Mathematica als prinzipielle Probleme zu sein. \quoteon(2022-08-21 18:08 - hyperG in Beitrag No. 4) Dieser lange Algorithmus steckt also hinter dem "*"!!! \quoteoff Es bleibt eine Matrix-Multiplikation.


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1842
  Beitrag No.6, vom Themenstarter, eingetragen 2022-08-21

\quoteon(2022-08-21 18:40 - zippy in Beitrag No. 5) \quoteon(2022-08-21 18:08 - hyperG in Beitrag No. 4) Dieser lange Algorithmus steckt also hinter dem "*"!!! \quoteoff Es bleibt eine Matrix-Multiplikation. \quoteoff Ich verstehe ja, dass DU (und der Ersteller) das verstanden haben, aber man kann doch nicht innerhalb der selben OEIS-Internetseiten erwarten, dass jeder Mensch sofort trotz GLEICHER Schreibweise den großen Algorithmus-Unterschied zwischen: \sourceon nameDerSprache A005443 = A000142*A000045 gemeint ist Algorithmus A005443[n]= Fakultät[n] * Fibonacci[n] \sourceoff und \sourceon nameDerSprache A144332 = A144328 * A007318 gemeint ist hier NICHT A144332[n]= A144328[n] * A007318[n] sondern ToTriangleMatrixWithNulls[A144328].ToTriangleMatrixWithNulls[A007318] dann MatrixTo1D_Array dann Delete_Nulls \sourceoff erkennt. (OK, das "dann MatrixTo1D_Array dann Delete_Nulls" wird bei OEIS meist weggelassen) Außerdem gibt es zig Algorithmen, wie man aus einer Liste (1D-Array mit n Feldern) eine k*m-Matrix machen kann. Normalerweise ist k*m=n. Hier jedoch nicht (habe es mit Funktion ToTriangleMatrixWithNulls versucht zu beschreiben).


   Profil
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 1608
Wohnort: Deutschland
  Beitrag No.6, eingetragen 2022-08-21

Hallo hyperG, Dreiecksmatrizen haben ja zum Teil besondere Eigenschaften, und die beiden zugrunde liegenden Einzelfolgen gehorchen einem festen Algorithmus. Multipliziert ergibt sich dann wieder eine (untere) Dreiecksmatrix, so wie Du sie bis zu einer bestimmten Dimension angegeben hast: \quoteon(2022-08-21 18:08 - hyperG in Beitrag No. 4) \sourceon 1 0 0 0 0 0 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 4 5 2 0 0 0 0 0 0 0 0 0 7 14 11 3 0 0 0 0 0 0 0 0 11 30 35 19 4 0 0 0 0 0 0 0 16 55 85 69 29 5 0 0 0 0 0 0 22 91 175 189 119 41 6 0 0 0 0 0 29 140 322 434 364 188 55 7 0 0 0 0 37 204 546 882 924 636 279 71 8 0 0 0 46 285 870 1638 2058 1770 1035 395 89 9 0 0 56 385 1320 2838 4158 4290 3135 1595 539 109 10 0 67 506 1925 4653 7788 9372 8217 5225 2354 714 131 11 \sourceoff \quoteoff Was mir an dieser Ergebnismatrix zumindest auffällt, ist, dass die erste Spalte sehr einfach konstruiert ist: vom ersten zum zweiten Element muss nur +1 gerechnet werden, vom zweiten zum dritten +2, vom dritten zum vierten +3, vom vierten zum fünften +4, usw. Des Weiteren scheint die Hauptdiagonale nur zu bestehen aus einer 1, gefolgt von der Folge der natürlichen Zahlen (1, 2, 3, 4, 5, usw.). Da drängt sich doch die Frage auf, ob man die Matrixelemente, die sich zwischen der ersten Spalte und der Hauptdiagonale befinden, nicht auch nach einem bestimmten (alternativen) Rechenweg berechnen kann. Dazu bin ich den Weg gegangen, diese "Zwischenelemente" in Abhängigkeit einer Konstante $n$ anzugeben. Damit sieht die 12x12 Ergebnismatrix wie nachfolgend gezeigt aus (sehr große Bilddatei - bitte nicht erschrecken - oder einfach das PDF downloaden), und da sind eindeutig bestimmte Muster erkennbar in den Ausdrücken: \showon Bilddatei \showoff 12x12 Dreiecksergebnismatrix in Abhängigkeit von n als PDF-Datei (pro Seite jeweils eine Matrixspalte) Und jetzt kommt der beste Clou an dieser ganzen Sache: Um die tatsächlichen Werte der Ergebnismatrix zu berechnen, setzt man einfach $n=0$, und schon kommen wieder die gleichen Werte der Matrix heraus, die Du, hyperG, schon berechnet hast und die ich oben zitiert habe. Mit anderen Worten: Die Entstehung der ersten Spalte und der Hauptdiagonale sind trivial, und für die Zwischenelemente kann man versuchen, ob es möglich ist, den Algorithmus in Abhängigkeit von $n$ nachzuprogrammieren, dann kann man ohne erst die Matrizenmultiplikation auszuführen, die Elemente der Ergebnismatrix direkt berechnen. Zumindest kann man sehen, dass der Aufbau der Ausdrücke doch ein gewisses System erkennen lässt. Ob das dann unter dem Strich wirklich einen Zeitvorteil bringt, muss man sehen. Und wie gesagt - das Schöne dabei ist, dass man dann einfach $n=0$ setzen kann. Ich habe diese Darstellung mit $n$ nur deshalb gewählt, um ein System hinter den Ausdrücken erkennbar zu machen, d. h. die einzelnen $n$ kann man sich auch wegdenken, um zu verstehen, welche Ausdrücke entstehen. Und um dann z. B. das $k$-te Array-Element direkt aus der i,j-Ergebnismatrix zu bekommen, ohne das Array selbst zu erzeugen, kann folgender Algorithmus verwendet werden: \sourceon Mathematica (Array-Index k in Matrix-Indizes i,j umwandeln) k2ij[k_] := Module[{i, s}, i = 0; s = 0; While[s < k, i = i + 1; s = s + i]; Return[{i, k - Sum[z, {z, 1, (i - 1)}]}]] (* z. B.: *) k2ij[4] (* liefert 3,1 *) k2ij[17] (* liefert 6,2 *) k2ij[26] (* liefert 7,5 *) k2ij[42] (* liefert 9,6 *) k2ij[60] (* liefert 11,5 *) \sourceoff Somit entfällt dann auch die mühsame Umwandlung der Matrix in ein Array. Beispiel: Um das 42. Array-Element zu erhalten, muss lediglich der Ausdruck $\frac{1}{24}(n+1)(n+2)(n+3)(n+4)(n+5)+\frac{1}{20}(n+2)(n+3)(n+4)(n+6)(n+5)+$ $\frac{7}{120}(n+3)(n+4)(n+6)(n+7)(n+5)+\frac{1}{15}(n+4)(n+6)(n+7)(n+8)(n+5)$ für $n=0$ berechnet werden, was 636 ergibt (Ausdruck vergleiche obige Bilddatei bzw. PDF-Dokument in Matrix Zeile 9, Spalte 6, und Ergebnis vergleiche obige zitierte Ergebnismatrix von hyperG). Ansonsten muss NICHTS berechnet werden(, sofern man es schafft, die Ausdrücke in Abhängigkeit von $n$ für die Matrixfelder zwischen der ersten Spalte und der Hauptdiagonale bis in die Unendllichkeit zu verallgemeinern - aber wie gesagt, das Muster müsste eigentlich herauszufinden sein, ggf. durch Betrachtung noch größerer Matrix-Dimensionen). Es entfallen dann sowohl die Matrixmultiplikation als auch die Array-Erzeugung. Jedes Array-Element kann dann über eine direkte Formel berechnet werden. LG Primentus


   Profil
zippy
Senior Letzter Besuch: im letzten Monat
Dabei seit: 24.10.2018
Mitteilungen: 4179
  Beitrag No.7, eingetragen 2022-08-22

\quoteon(2022-08-21 22:19 - Primentus in Beitrag No. 6) Um das 42. Array-Element zu erhalten, muss lediglich der Ausdruck $\frac{1}{24}(n+1)(n+2)(n+3)(n+4)(n+5)+\frac{1}{20}(n+2)(n+3)(n+4)(n+6)(n+5)+$ $\frac{7}{120}(n+3)(n+4)(n+6)(n+7)(n+5)+\frac{1}{15}(n+4)(n+6)(n+7)(n+8)(n+5)$ für $n=0$ berechnet werden, was 636 ergibt \quoteoff Ist das jetzt einfacher als die direkte Matrix-Multiplikation $ 5\cdot{5\choose0}+ 6\cdot{6\choose1}+ 7\cdot{7\choose2}+ 8\cdot{8\choose3}=636$ ?


   Profil
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 1608
Wohnort: Deutschland
  Beitrag No.8, eingetragen 2022-08-22

Hallo zippy, ja ok, ich sehe gerade - durch die vielen Nullen kürzt sich tatsächlich einiges weg, so dass für das 42. Array-Element nur noch 4 Summanden übrig bleiben. Ich habe jedoch an Matrizen der Größe 1000x1000 oder mehr gedacht, aber dabei vielleicht übersehen, dass wenn man das $k$-te (hier $42$) Array-Element an Position $i,j$ (hier $9, 6$) in der Ergebnismatrix ermitteln möchte, man nicht unbedingt die komplette Matrizenmultiplikation durchführen muss, sondern lediglich die $i$-te Zeile der Matrix OEIS A144328 mit der $j$-ten Spalte der Matrix OEIS A007318 multiplizieren muss. Dann ist der Aufwand natürlich deutlich geringer als ich es anfangs gesehen habe. Aber um das zum gegebenen bzw. gewünschten $k$ gehörige $i,j$ zu ermitteln, um überhaupt zu wissen, welche Zeile und Spalte multipliziert werden müssen, ist meine k2ij-Funktion ja ganz nützlich. LG Primentus


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1842
  Beitrag No.9, vom Themenstarter, eingetragen 2022-08-22

\quoteon(2022-08-21 22:19 - Primentus in Beitrag No. 6) ... kann man versuchen, ob es möglich ist, den Algorithmus in Abhängigkeit von n nachzuprogrammieren \quoteoff hört sich sehr kompliziert an. Hier die kurze Formel, die mir bei OEIS fehlte komprimiert auf 1 Zeile: \sourceon mathematica max=Ceiling[(Sqrt[1 + 8 gewuenschteArraygroesse] - 1)/2]-1; DeleteCases[Flatten[Table[Which[n < 1, 1, n > m, 0, n > 0 && n <= m, n], {m, 0, max},{n, 0,max}].Table[If[k <= n, Binomial[n, k], 0], {n, 0, max}, {k, 0, max}]], 0] \sourceoff Bei OEIS ist das max meist als Beispielkonstante angegeben, so dass nur noch 1 Zeile überbleibt.


   Profil
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 1608
Wohnort: Deutschland
  Beitrag No.10, eingetragen 2022-08-23

\quoteon(2022-08-22 23:21 - hyperG in Beitrag No. 9) \sourceon mathematica max=Ceiling[(Sqrt[1 + 8 gewuenschteArraygroesse] - 1)/2]-1; \sourceoff \quoteoff Hallo hyperG, ja, das ist im wesentlichen eine Art Umkehrfunktion zur Dreieckszahlberechnung. Diese Formel ist natürlich auch sehr nützlich! LG Primentus


   Profil

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-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. 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]