Coefficienti di polinomi

[Simo_the_wolf]

Sia $ a_{n,k} $ il coefficiente di $ x^k $ nello sviluppo di $ (1+x+x^2+x^3+ ... + x^k ) ^n $. Dimostrare che:

1- Esistono $ C_1, C_2 $, indipendenti da $ n,k $, tali che $ a_{n,k} \leq C_1 \cdot C_2^{n+k} $

2- Fatto alquanto sorprendente... $ a_{n+1,k} = a_{k+1,n} $

Good luck!!

ps con il primo punto dimostrare che composizione di funzioni analitiche è analitica.

[darkcrystal]

2) Dato che mi interessa solo il coefficiente di $ x^k $ posso aggiungere impunemente termini di grado più alto all'espressione.

In particolare il coefficiente che voglio trovare è uguale al coefficiente di $ x^k $ nello sviluppo di $ (1+x+x^2+...+x^k+\sum_{i > k} x^i)^{n+1} $, che è $ (\frac{1}{1-x})^{n+1} $. Per trovare questo coefficiente basta fare k derivate in zero; la prima fa uscire un fattore n+1, la seconda n+2, e così via, perciò il coefficiente è $ {n+k \choose n} $. Rifacendo il ragionamento per $ a_{k+1,n} $ si trova con poca fantasia lo stesso risultato.

Ora la combinatoria: a me sembra che quel coefficiente sia il numero di modi di scrivere k come somma di esattamente n+1 parti non negative, in cui l'ordine conta, e ci chiediamo se sia uguale al numero di modi di scrivere n in esattamente k+1 parti non negative.
Consideriamo la solita striscia di n+k caselline con n caselle colorate di bianco e k di nero; se pensiamo le caselle bianche come "separatori" e le sequenze consecutive di nere come "parti non negative" otteniamo $ a_{n+1,k} $, mentre se si pensano le nere come separatrici e le bianche come parti si ottiene $ a_{k+1,n} $ (quindi in particolare i coefficienti sono uguali tra loro ed a $ {n+k \choose k} $)

Ciao,
Davide

[Simo_the_wolf]

Uh ok, era molto più semplice di come l'avevo pensato...

[dario2994]

Uh ok, era molto più semplice di come l'avevo pensato...

Infatti mi stavo chiedendo perchè in MNE!
Piccolo rilancio:
Bonus della piccola città: Quale è la migliore costante $C_2$?

[Simo_the_wolf]

Considero:

1) $ \displaystyle \tbinom {n+k}n \leq \sum_{i=0}^{n+k} \tbinom {n+k}i = 2^{n+k} $

2) Sapendo che il binomio centrale è quello maggiore nella serie binomiale:
$ \displaystyle \tbinom {2n}n \geq \frac 1{2n+1} \sum_{i=0}^{2n} \tbinom {2n}i = \frac {2^{2n}}{2n+1} $

Mettendole insieme ottengo precisamente che la migliore costante è $ C_2=2 $