Binomialkoeffizient zu gegebener Zahl finden

30.01.2011, 00:15

Hannc

Binomialkoeffizient zu gegebener Zahl finden

Hallo zusammen,

mich beschäftigt gerade folgendes Problem: Wie kann ich zu einer gegebenen Zahl $\begin{eqnarray*} x\in\mathbb{N} \end{eqnarray*}$ einen passenden Binomialkoeffizienten finden (vorausgesetzt es gibt einen)?

Ein Beispiel zur Veranschaulichung:

Ich suche n und k, so dass $\begin{eqnarray*} {n \choose k} = 6 \end{eqnarray*}$ .

Lösungen dafür wären $\begin{eqnarray*} 4 \choose 2 \end{eqnarray*}$ und $\begin{eqnarray*} 6 \choose 1 \end{eqnarray*}$ bzw. . $\begin{eqnarray*} 6 \choose 5 \end{eqnarray*}$ .

Gehen wir der Einfachheit halber davon aus, dass jeweils das kleinste $\begin{eqnarray*} n \end{eqnarray*}$ gesucht wird, so dass es ein $\begin{eqnarray*} k\in\mathbb{N} \end{eqnarray*}$ gibt mit $\begin{eqnarray*} {n \choose k} = x \end{eqnarray*}$ .

Meine Frage: Gibt es dafür ein systematisches Vorgehen? In entsprechenden Tabellen nachschlagen oder mir per JavaScript die ersten 19 Zeilen des Pascal'schen Dreiecks ausdrucken zu lassen um einen Binomialkoeffizienten zur Zahl 27132 zu finden ist irgendwie... unelegant.

Für Antworten im Voraus vielen Dank!

30.01.2011, 01:02

Math1986

Auf diesen Beitrag antworten »

Es gibt immer die Lösung $\begin{eqnarray*} \binom x1=x \end{eqnarray*}$ Augenzwinkern

Wähle also n=x und k=1, damit wissen wir schonmal dass es immer eine Lösung gibt.

30.01.2011, 09:36

Shortstop

Auf diesen Beitrag antworten »

. Jouh, Rene hat Recht. Sollte so früh keine Beiträge mehr schreiben Wink

30.01.2011, 11:03

René Gruber

Auf diesen Beitrag antworten »

So geschrieben stimmt das natürlich nicht: So ist etwa $\begin{eqnarray*} 2000 < \binom{n}{2} < 3000 \end{eqnarray*}$ für alle $\begin{eqnarray*} n \end{eqnarray*}$ mit $\begin{eqnarray*} 64\leq n\leq 77 \end{eqnarray*}$ .

30.01.2011, 12:51

Hannc

Auf diesen Beitrag antworten »

Zitat:

Original von Math1986
Es gibt immer die Lösung $\begin{eqnarray*} \binom x1=x \end{eqnarray*}$ Augenzwinkern

Wähle also n=x und k=1, damit wissen wir schonmal dass es immer eine Lösung gibt.

Hallo und vielen Dank für die Antwort.

Ok, lassen wir die trivialen Lösungen beiseite. Ich möchte also eine/die Lösung mit möglichst kleinem $\begin{eqnarray*} n \end{eqnarray*}$ finden. Setze ich beispielsweise $\begin{eqnarray*} x=91 \end{eqnarray*}$ , möchte ich als Lösung $\begin{eqnarray*} 14 \choose 2 \end{eqnarray*}$ bzw. $\begin{eqnarray*} 14 \choose 12 \end{eqnarray*}$ erhalten.

Das ganze würde ja prinzipiell 2 Schritte erfordern:

1. Passenden Binomialkoeffizienten finden.
2. Zeigen, dass dies der Bin.Ko. mit kleinstmöglichem $\begin{eqnarray*} n \end{eqnarray*}$ ist, sprich: die Zahl das erste Mal im Pascal'schen Dreieck auftaucht.

Leider bin ich beim Durchforsten des Internet und meiner Büchersammlung auf keinen wirklich brauchbaren Ansatz gestoßen... sollte es ihn geben, versteckt er sich gut oder ich bin blind. verwirrt

Meine bisherigen Versuche haben immer nur einen Spezialfall abgedeckt - z.B. wenn $\begin{eqnarray*} x \end{eqnarray*}$ eine Dreieckszahl ist, die sich bekanntlich als $\begin{eqnarray*} n \choose 2 \end{eqnarray*}$ darstellen lässt. Unklar war mir auch da, ob das wirklich das kleinstmögliche $\begin{eqnarray*} n \end{eqnarray*}$ war...

30.01.2011, 12:57

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von Hannc
Leider bin ich beim Durchforsten des Internet und meiner Büchersammlung auf keinen wirklich brauchbaren Ansatz gestoßen...

Das liegt wahrscheinlich dran, dass das zwar für sich gesehen eine interessante zahlentheoretische Fragestellung ist, die aber darüber hinaus für andere Probleme weitgehend bedeutungslos ist - soweit ich weiß. Was nicht heißen soll, dass man sich nicht damit befassen soll. Augenzwinkern

30.01.2011, 13:30

Mystic

Auf diesen Beitrag antworten »

Ja, es gibt da eine "Top down"-Strategie und eine "Bottom up"-Strategie, je nachdem, ob man bei der Suche nach dem "richtigen" n von oben oder unten zu suchen beginnt... Beide unterscheiden sich grundlegend...

Nachfolgend der Code in C# für letztere, welcher in dieser Form allerdings nur für n<67 funktioniert , was aber hier auch ausreicht... Es sollte kein Problem sein, ihn bei Bedarf in jede andere C-Sprache zu konvertieren...

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:

using System;
using System.Collections.Generic;

namespace pascal
{
	class Program
	{
		public static void Main(){
			int k=-1,n=0;
			ulong x=27132;			
			List<ulong> p=new List<ulong>{1};
			
			while (n<67) {
				k=p.IndexOf(x);
				if (k>=0) break;
				n++; p.Insert(0,0); 
				for(int i=0;i<p.Count-1;i++) 
					p[i]+=p[i+1];
			}
			
			Console.WriteLine("n={0},k={1}",n,k);
			Console.ReadKey(true);
		}
	}
}

Edit: Aus zahlentheoretischer Sicht - weil René diesen Punkt angesprochen hat -, fällt mir eigentlich jetzt nur ein, dass das in Frage kommende n mindestens so groß sein muss wie die größte Primzahlpotenz, welche in $\begin{eqnarray*} \begin{binom} nk \end{binom} \end{eqnarray*}$ vorkommt. (Vielleicht hätte ich das aber jetzt lieber verschweigen sollen, da es mein obiges Programm obsolet macht! traurig

)

30.01.2011, 20:33

Hannc

Auf diesen Beitrag antworten »

Zitat:

Original von Mystic
Edit: Aus zahlentheoretischer Sicht - weil René diesen Punkt angesprochen hat -, fällt mir eigentlich jetzt nur ein, dass das in Frage kommende n mindestens so groß sein muss wie die größte Primzahlpotenz, welche in $\begin{eqnarray*} \begin{binom} nk \end{binom} \end{eqnarray*}$ vorkommt. (Vielleicht hätte ich das aber jetzt lieber verschweigen sollen, da es mein obiges Programm obsolet macht! traurig

)

Macht es nicht, es hat mich immerhin dazu animiert, mich mal mit Mono und C# zu beschäftigen. Augenzwinkern

30.01.2011, 21:08

Hanc

Auf diesen Beitrag antworten »

Zitat:

Man entschuldige den Doppelpost (edit geht als nicht-registrierter Benutzer natürlich nicht), aber könntest du bitte kurz skizzieren, warum das so ist (stehe gerade auf dem Schlauch)?

30.01.2011, 23:11

Mystic

Auf diesen Beitrag antworten »

Wenn $\begin{eqnarray*} \nu_p(n) \end{eqnarray*}$ ganz allgemein die Vielfachheit bezeichnet, mit der die Primzahl $\begin{eqnarray*} p \end{eqnarray*}$ in der Primfaktorzerlegung einer natürlichen Zahl $\begin{eqnarray*} n > 0 \end{eqnarray*}$ vorkommt, so gilt ja bekanntlich

$\begin{eqnarray*} \nu_p(n!) = \sum_{i=1}^\infty \lfloor \frac n{p^i} \rfloor \end{eqnarray*}$

wobei diese Summe zwar formal unendlich ist, tatsächlich aber nur die Summanden mit $\begin{eqnarray*} i \le r=\lfloor \frac {\ln n}{\ln p} \rfloor \end{eqnarray*}$ Beiträge > 0 liefern... Die anschauliche Bedeutung von r ist dabei, dass $\begin{eqnarray*} p^r \end{eqnarray*}$ die größte Potenz von $\begin{eqnarray*} p \end{eqnarray*}$ ist, für welche noch $\begin{eqnarray*} p^r \le n \end{eqnarray*}$ gilt...

Damit gilt dann

$\begin{eqnarray*} \nu_p\left(\begin{binom} nk \end{binom}\right)=\nu_p\left(\frac{n!}{k!(n-k)!} \right)= \sum_{i=1}^r ( \underbrace{\lfloor \frac n{p^i} \rfloor-\lfloor \frac k{p^i} \rfloor-\lfloor \frac {n-k}{p^i} \rfloor}_{\le 1}\ ) \le r \end{eqnarray*}$

und indem man diese letzte Ungleichung zur p-ten Potenz erhebt folgt daraus wegen $\begin{eqnarray*} p^r \le n \end{eqnarray*}$ schließlich die Behauptung...

Edit: Bitte jetzt nicht sagen, du weißt nicht wieso der unterklammerte Ausdruck $\begin{eqnarray*} \le 1 \end{eqnarray*}$ ist, denn ein bißchen was zum selber nachdenken sollte schon noch übrigbleiben... Wink

Edit2: Ja tatsächlich, das sollte man am besten gleich in der Allgemeinheit, wie von René unten angedeutet, beweisen... (Und ich dachte schon, ich bekomme einen Rüffel, weil ich die runden Klammern rund um den den unterklammerten Ausdruck vergessen hatte! Augenzwinkern

)

31.01.2011, 00:04

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von Mystic
Edit: Bitte jetzt nicht sagen, du weißt nicht wieso der unterklammerte Ausdruck $\begin{eqnarray*} \le 1 \end{eqnarray*}$ ist

Verallgemeinert könnte man diese nette kleine Eigenschaft so formulieren:

Für alle reellen Zahlen $\begin{eqnarray*} x,y \end{eqnarray*}$ gilt $\begin{eqnarray*} \lfloor x+y \rfloor - \lfloor x \rfloor - \lfloor y \rfloor \in \{0,1\} \end{eqnarray*}$ . Augenzwinkern

Neue Frage »

Antworten »

Binomialkoeffizient zu gegebener Zahl finden

Verwandte Themen