Maximale Anzahl von natürlichzahligen beschränken Vektoren mit konstanter Summe

09.05.2020, 20:23

MdAyq0l

Maximale Anzahl von natürlichzahligen beschränken Vektoren mit konstanter Summe

Für positive natürliche Zahlen $\begin{eqnarray*} i \end{eqnarray*}$ und $\begin{eqnarray*} m \end{eqnarray*}$ , wie groß kann die Menge $\begin{eqnarray*} V \subseteq (\mathbb{Z} \cap [0,m[)^i \end{eqnarray*}$ mit $\begin{eqnarray*} \sum_{j<i} v_j = \sum_{j<i} w_j \end{eqnarray*}$ ( $\begin{eqnarray*} v,w \in V \end{eqnarray*}$ ) werden? (Hier laufen die Indizes zwischen zwsichen 0 und i-1.) Eine triviale obere Schranke ist $\begin{eqnarray*} m^i \end{eqnarray*}$ ; gibt es eine elementar ausdrückbare (vage gesprochen) kleinere obere Schranke?

09.05.2020, 21:07

Leopold

Auf diesen Beitrag antworten »

Die Menge $\begin{align*} V \end{align*}$ ist nicht wohldefiniert. Wenn du Bedingungen an die Elemente $\begin{align*} v \end{align*}$ stellst, dann können diese Bedingungen $\begin{align*} v \end{align*}$ und von $\begin{align*} v \end{align*}$ unabhängige Größen enthalten, aber nicht noch ein weiteres Element $\begin{align*} w \end{align*}$ . Es sei denn, $\begin{align*} w \end{align*}$ spielt die Rolle eines Parameters, dann sollte man aber besser $\begin{align*} V(w) \end{align*}$ schreiben oder dieses zumindest im Text erwähnen.

Es ist übrigens ein falsches Verständnis von mathematischer Fachsprache, wenn man diese verwendet, um einfache Dinge möglichst kompliziert auszudrücken. Im Gegenteil ist die Fachsprache dazu da, um schwierige Dinge einfach auszudrücken.

$\begin{align*} V = \left\{ \, v = \left( v_0, v_1, \ldots, v_{i-1} \right) \ \left| \ \ v_0, v_1, \ldots, v_{i-1} \in \{ 0, 1, 2, \ldots, m-1 \}; \, \ldots \ldots \ \right. \right\} \end{align*}$

Jetzt erkläre noch, durch welche weiteren Eigenschaften du die $\begin{align*} v \end{align*}$ charakterisieren willst. Irgendetwas mit der Koordinatensumme war da noch.

EDIT
Nach Beitrag von HAL habe ich die Indizierung angepaßt. Übrigens wäre hier auch eine halbverbale Beschreibung von $\begin{align*} V \end{align*}$ möglich: $\begin{align*} V \end{align*}$ bestehe aus allen $\begin{align*} i \end{align*}$ -Tupeln $\begin{align*} v = \left(v_0,v_1,\ldots,v_{i-1} \right) \end{align*}$ , deren Koordinaten ganze Zahlen im Bereich von $\begin{align*} 0 \end{align*}$ bis $\begin{align*} m-1 \end{align*}$ (jeweils einschließlich) sind und für die … gilt.

09.05.2020, 21:19

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von MdAyq0l
(Hier laufen die Indizes zwischen zwsichen 0 und i-1.)

Damit ist dann anscheinend doch $\begin{eqnarray*} v=\left(v_0,v_1,\ldots,v_{i-1}\right) \end{eqnarray*}$ gemeint. Ist wirklich lästig, wenn man solche Infos erst zwischen den Zeilen herausklauben muss.

Für vorgegebene Elementsumme $\begin{eqnarray*} n = \sum_{j=0}^{i-1} v_j \end{eqnarray*}$ lautet die Mengenmächtigkeit

$\begin{eqnarray*} f(n):=\left|V(n)\right| = \sum_{k=0}^{\min\left(i,\left\lfloor \frac{n}{m}\right\rfloor\right)} (-1)^k \binom{i}{k} \binom{i+n-km-1}{i-1}\qquad (*) \end{eqnarray*}$ ,

die gute alte Siebformel lässt grüßen. Die Funktion ist symmetrisch $\begin{eqnarray*} f(n) = f(i(m-1)-n) \end{eqnarray*}$ mit Maximum in der Mitte, also bei $\begin{eqnarray*} n^*=\left\lfloor \frac{i(m-1)}{2}\right\rfloor \end{eqnarray*}$ .

Ich bezweifle, dass man die Summe (*) für allgemeine $\begin{eqnarray*} i,m \end{eqnarray*}$ signifikant vereinfachen kann, auch an der Maximumstelle $\begin{eqnarray*} n^* \end{eqnarray*}$ nicht. Aber womöglich habe ich ja Unrecht, also lass dich nicht von meinem Pessimismus abhalten. Augenzwinkern

10.05.2020, 11:21

URL

Auf diesen Beitrag antworten »

Den Fall $\begin{eqnarray*} m-1\geq n \end{eqnarray*}$ könnte man vielleicht separat erwähnen. Dann hat man es mit den Zerlegungen von $\begin{eqnarray*} n \end{eqnarray*}$ in $\begin{eqnarray*} i \end{eqnarray*}$ nichtnegative ganze Zahlen zu tun und HALs allgemeine Formel kollabiert zum bekannten Wert.

10.05.2020, 11:44

HAL 9000

Auf diesen Beitrag antworten »

Anzumerken wäre auch noch die Darstellung als Koeffizienten einer erzeugenden Funktion:

$\begin{eqnarray*} \left(1+x+x^2+\dots+x^{m-1}\right)^i = \sum_{n=0}^{i(m-1)} f(n) x^n \end{eqnarray*}$

11.05.2020, 02:23

MdAyq0l

Auf diesen Beitrag antworten »

Strenggenommen ist eine obere Schranke an $\begin{eqnarray*} \max\bigl\{\lvert V\rvert\ \bigm|\ V\mskip1mu\subseteq\mskip1mu\{z\in \mathbb{N}_{\ge 0}\mid z<m\}^i \,\land\, \forall\,v,w\in V\colon \,\,\,\sum_{j\ \in\ \mathrm{dom}\,v}\!\!\! v_j \,= \!\!\!\sum_{j\ \in\ \mathrm{dom}\,w}\!\!\! w_j\bigr\} \end{eqnarray*}$ als Funktion von $\begin{eqnarray*} m\in\mathbb{N}_{>0} \end{eqnarray*}$ und $\begin{eqnarray*} i\in\mathbb{N}_{\ge 0} \end{eqnarray*}$ gesucht. Die Domäne eines Vektors $\begin{eqnarray*} v \end{eqnarray*}$ ist hierbei die Menge seiner Indizes $\begin{eqnarray*} \mathrm{dom}\,v \end{eqnarray*}$ (ganze Zahlen zwischen $\begin{eqnarray*} 0 \end{eqnarray*}$ und $\begin{eqnarray*} i-1 \end{eqnarray*}$ oder zwischen $\begin{eqnarray*} 1 \end{eqnarray*}$ und $\begin{eqnarray*} i \end{eqnarray*}$ , je nach Gewohnheit des Lesers). Leere Summen evaluieren zu Null. Die gesuchte Funktion soll elementar, insbesondere ohne iterierte Summen oder Produkte, ausdrückbar sein. Die zugelassenen Operationen erwähnte ich nicht ursprünglich, aber nun muss ich es tun, um solche komplizierte Ausdrücke wie von HAL9000 zurückzuweisen, auch wenn sie eine beachtliche Leistung darstellen (großes Lob!). Zugelassen sind streng monoton wachsende Funktionen wie Potenzierung, Fakultät (oder Gammafunktion ab 2), Multiplikation, Addition, Logarithmus, Division durch eine positive Konstante. Zugelassene Konstanten sind positive natürlichzahlige Konstanten, bekannte positive reelle Konstanten (Pi, Eulersche Zahl, Goldener Schnitt, usw.) sowie Brüche davon und alle bereits erwähnten Operationen (Potenzierung, ..., Logarithmus, Division durch eine Konstante). Wenn ihr mehr braucht (z.B. nichtisotone Funktionen wie Binomialkoeffizienten oder Multinomialkoeffizienten oder allgemeine Subtraktion oder Inverse), fragt nach. Iterierte oder rekursive oder nichttriviale Funktionen (große Summe, großes Produkt, Integral usw.) sind unerwünscht.

In meiner ursprünglichen Frage vereinfachte ich den Parameter $\begin{eqnarray*} i \end{eqnarray*}$ zu "positiv"; ich glaube nicht, dass der Unterschied "positiv vs nichtnegativ" eine große Rolle in dieser Frage spielt.

Die gesuchte obere Schranke muss nicht zwingend sehr präzise sein; (kleiner oder gleich) und $\begin{eqnarray*} \mathrm{o}(m^i) \end{eqnarray*}$ (asymptotisch kleiner als $\begin{eqnarray*} m^i \end{eqnarray*}$ ) reicht voll und ganz aus.

11.05.2020, 07:05

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von MdAyq0l
Die zugelassenen Operationen erwähnte ich nicht ursprünglich, aber nun muss ich es tun, um solche komplizierte Ausdrücke wie von HAL9000 zurückzuweisen, auch wenn sie eine beachtliche Leistung darstellen (großes Lob!).

Da bin ich aber gerührt, trotz der vorherigen "Zurückweisung". Big Laugh

Es bleibt dir ja unbenommen, den Wert $\begin{eqnarray*} f(n^*) \end{eqnarray*}$ durch einen einfacheren Ausdruck nach oben abzuschätzen. Ich kann das zunächst nur nach unten: Offenbar ist $\begin{eqnarray*} f(n^*)\geq \frac{m^i}{(m-1)i+1} \end{eqnarray*}$ .

Für große $\begin{eqnarray*} i \end{eqnarray*}$ kann man aus dem Zentralen Grenzwertsatz eine approximative Schätzung für $\begin{eqnarray*} f(n^*) \end{eqnarray*}$ berechnen, das läuft auf $\begin{eqnarray*} f(n^*) \approx m^i\cdot \sqrt{\frac{6}{\pi i(m^2-1)}} \end{eqnarray*}$ hinaus.

Beispiel: $\begin{eqnarray*} m=10,i=100 \end{eqnarray*}$

Da ist $\begin{eqnarray*} f(n^*) = f(450) = 138 \,681 \,178 \,063 \,913 \,146 \,486 \,663 \,255 \,108 \,385 \,891 \,670 \,476 \,531 \,416 \,644 \,888 \,545 \,033 \,078 \,503 \,482 \,282 \,975 \,641 \,730 \,091 \,720 \,919 \,340 \,564 \,340 \approx 1.3868\cdot 10^{98} \end{eqnarray*}$ ,

die Schätzung ergibt $\begin{eqnarray*} m^i\cdot \sqrt{\frac{6}{\pi i(m^2-1)}}\approx 1.3889\cdot 10^{98} \end{eqnarray*}$ , zumindest für diesen Parameterfall also so schlecht nicht.

Zitat:

Original von MdAyq0l
ich glaube nicht, dass der Unterschied "positiv vs nichtnegativ" eine große Rolle in dieser Frage spielt.

Falls sich das auf die Bemerkung von URL bezieht: Es macht schon einen Unterschied, ob man nichtnegative oder nur positive Summanden $\begin{eqnarray*} v_j \end{eqnarray*}$ zulässt. Zumal du selber oben explizit die Werte 0 zugelassen hast, also gibt es hier nun wahrlich kein neues Fass aufzumachen.

11.05.2020, 15:32

MdAyq0l

Auf diesen Beitrag antworten »

Zitat:

... $\begin{eqnarray*} \frac{6}{\pi i (m^2-1)} \end{eqnarray*}$ ...

Division durch $\begin{eqnarray*} i \end{eqnarray*}$ und Subktraktion von 1 sind leider nicht zugelassen...

Zitat:

Falls sich das auf die Bemerkung von URL bezieht: Es macht schon einen Unterschied, ob man nichtnegative oder nur positive Summanden $\begin{eqnarray*} v_j \end{eqnarray*}$ zulässt.

Es bezieht sich darauf, ob man 0 als Wert von $\begin{eqnarray*} i \end{eqnarray*}$ zulässt oder nicht.

11.05.2020, 16:45

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von MdAyq0l
Division durch $\begin{eqnarray*} i \end{eqnarray*}$ und Subktraktion von 1 sind leider nicht zugelassen...

Wieso soll Division durch i nicht zugelassen sein??? Und Wert i=0 ist doch kompletter Unsinn, das bezieht sich dann auf leere Tupel ... was soll das?

Die Asymptotik $\begin{eqnarray*} \frac{f(n^*)}{m^i} \sim i^{-\frac{1}{2}} \end{eqnarray*}$ für $\begin{eqnarray*} i\to\infty \end{eqnarray*}$ ist hier essentiell - das zu "verbieten" ist für mich untragbarer Schwachsinn.

Ehrlich gesagt reicht es mir daher mit deinen Verboten, die für mich jetzt langsam nicht mehr den geringsten Sinn ergeben. Mach mit den bisherigen Ergebnissen, was du willst - ich habe fertig.

11.05.2020, 18:08

MdAyq0l

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000

Zitat:

Original von MdAyq0l
Division durch $\begin{eqnarray*} i \end{eqnarray*}$ und Subktraktion von 1 sind leider nicht zugelassen...

Die Division durch $\begin{eqnarray*} i \end{eqnarray*}$ ist eine antitone Operation, keine isotone, daher ist sie nicht zugelassen. Die Summe über das leere Tupel ist Null.

... gähn ...

Deine Beschimpfungen sind inzwischen so was von abgedroschen und ausgelutsch, dass sie nicht im Ansatz mehr bewegend oder rührend sind, sondern eher die Kriterien von Vokabeln erfüllen, die ich lieber hier nicht in den Mund nehmen möchte. Hab du mal fertig, ich muss mit schimpfenden Kleinkindern wie du nicht weiter reden.

11.05.2020, 18:16

HAL 9000

Auf diesen Beitrag antworten »

Das $\begin{eqnarray*} m^i \end{eqnarray*}$ davor hast du bei der Monotoniebetrachtung hinsichtlich $\begin{eqnarray*} i \end{eqnarray*}$ wohl vergessen? Nur rumnölen, aber nie mitdenken: Wie kann man eine Asymptotik verbieten, die schlicht einfach da ist? Das erinnert an die mittelalterliche Inquisition.

Neue Frage »

Antworten »

Maximale Anzahl von natürlichzahligen beschränken Vektoren mit konstanter Summe

Verwandte Themen