Re: Mathematica für symbolische kombinatorische (Un)gleichungen

[Udo und Susanne Krause <su.krause@XXXXXXX.ch>]

Hallo Andreas,

das erste Problem löst man mit Annahmen:

In[22] := FullSimplify[Sum[Binomial[n, k]*Binomial[n, r - k], {k, 0, n}],
 {n > 0, n \[Element] Integers, r > 0, r \[Element] Integers}]

Out[22]= (2*n)!/(r!*Gamma[1 + 2*n - r])

Wenn Mma dann noch etwas über das Argument der letzten Gammafunktion 
gesagt bekommt:

In[26]:= FullSimplify[Sum[Binomial[n, k]*Binomial[n, r - k], {k, 0, n}],
 {n > 0, n \[Element] Integers, r > 0, r <= n, r \[Element] Integers}]

Out[26]= (2*n)!/((2*n - r)!*r!)

haben Sie es geschafft. Das zweite Problem ist viel schwieriger, das 
Paket InqualitySolve können Sie nur anwenden, wenn die Bedingungen 
polynomial ausgedrückt werden können, m.a.W.:

In[27]:= << "Algebra`InequalitySolve`"

In[28]:= InequalitySolve[Sum[Binomial[n, k], {k, 0, r}] < 2^n - 1, r]

From In[28]:=
InequalitySolve::npi:A nonpolynomial equation or inequality encountered. 
The solution set may be incorrect.

From In[28]:="InequalitySolve[<skip>, r] is not a formula constructed 
with univariate polynomial equations and inequalities in r."

Out[28]=
InequalitySolve[2^n - (n*Gamma[n]*Hypergeometric2F1[1, 1 - n + r, 2 + r, 
-1])/
    (Gamma[n - r]*Gamma[2 + r]) < -1 + 2^n, r]

die hypergeometrischen Funktionen sind i. A. nicht algebraisch, also 
müssten Sie nach algebraischen Ausdrücken für die zu prüfenden 
Ungleichungen suchen, d.h. nach Werten an speziellen Argumenten  etc., 
wenn Sie InequalitySolve nützlich anwenden wollten.

Ein anderer Weg kann die vollständige Induktion sein. Man prüft die 
Ungleichhung für einen übersichtlichen Startwert (n = 3) und führt unter 
der Annahme, dass die Ungleichung für n gilt, den Induktionsschritt nach 
n + 1 aus.

Bei 2 unabhängigen Variablen kann man ein graphisches Experiment machen:
ListDensityPlot[Table[If[r <= n, If[Sum[Binomial[n, k], {k, 0, r}] < 2^n 
- 1, 1, 0], -1], {n, 1, 40}, {r, 0, 40}]]

Mit den besten Grüssen
Udo.

wendemu wrote:

> Hallo, 
>
> vielleicht kann jemand helfen.
> Ich benutze Version 5.0 für das folgende Problem:
>
> FullSimplify[Sum[Binomial[n, k] * Binomial[n, r - k], {k, 0, n}]]
>
> ergibt
>
> Out[45]=
> Gamma[1 + 2 n]/
> ( Gamma[1 + 2 n - r] Gamma[1 + r] )
>
>
> Allerdings ist bekannt, dass, mit n und r nicht-negative integers,
> das obige ergeben müsste:
>
> Binomial[2*n, r].
>
> Wie kriege ich Mathematica dazu, das Resultat in diesem Fall 
> nicht in Gamma-Funktionen  anzugeben?
>
>
> Mathematica KANN das Resultat Binomial[2*n, r] erzeugen (aber dazu 
> müsste ich es vorher wissen, was ich natürlich normalerweise nicht tue),
> denn
>
> FullSimplify[Sum[Binomial[n, k] * Binomial[n, r - k], {k, 0, n}] -
> Binomial[2*n, r] ]
>
> ergibt
>
> 0
>
> wie gewünscht.
>
> Meine zweite Frage:
>
> Wie finde ich heraus, ob kombinatorische Ungleichungen wahr oder falsch sind?
> Also z.B. 
>
>
> Sum[Binomial[n, k], {k, 0, r}] < 2^n -1
> ist wahr  für r < n-1.
>
> Gibt es Mathematica Kommandos, die dieses Rultat 
> produzieren?
>
> Vielen Dank,
>
>
> Andreas
>