Binomial typ

I matematik är en polynomsekvens , dvs en sekvens av polynom indexerade med icke-negativa heltal ${\textstyle \left\{0,1,2,3,\ldots \right\} }$ där indexet för varje polynom är lika med dess grad , sägs vara av binomial typ om det uppfyller sekvensen av identiteter

$p_{n}(x+y)=\summa _{k=0}^{n}{n \välj k}\,p_{k}(x)\,p_{nk}(y).$

Många sådana sekvenser finns. Uppsättningen av alla sådana sekvenser bildar en Lie-grupp under drift av umbral sammansättning, förklarat nedan. Varje sekvens av binomialtyp kan uttryckas i termer av Bellpolynomen . Varje sekvens av binomial typ är en Sheffer-sekvens (men de flesta Sheffer-sekvenser är inte av binomial typ). Polynomsekvenser sätter på fast fot de vaga 1800-talets föreställningar om umbral kalkyl .

Exempel

• Som en konsekvens av denna definition kan binomialsatsen anges genom att säga att sekvensen $\{x^{n}:n=0,1,2,\ldots \}$ är av binomial typ.
• Sekvensen av " lägre faktoraler " definieras av
  $$(x)_{n}=x(x-1)(x-2)\cdot \cdots \cdot (x-n+1).$$
  (I teorin om specialfunktioner betecknar samma notation övre faktorialer , men denna nuvarande användning är universell bland kombinatorister .) Produkten förstås vara 1 om n = 0, eftersom det i så fall är en tom produkt . Denna polynomsekvens är av binomial typ.
• Likaså de " övre faktorerna "
  $$x^{(n)}=x(x+1)(x+2)\cdot \cdots \cdot (x+n-1)$$
  är en polynomsekvens av binomial typ.
• Abels polynom
  $$p_{n}(x)=x(x-an)^{n-1}$$
  är en polynomsekvens av binomial typ.
• Touchard- polynomen
  $$p_{n}(x)=\summa _{k=1}^{n}S(n,k)x^ {k}$$
  där $S(n,k)$ är antalet partitioner av en uppsättning av storlek $n$ till $k$ disjunkta icke-tomma delmängder, är en polynomsekvens av binomial typ. Eric Temple Bell kallade dessa "exponentiella polynomen" och den termen ses också ibland i litteraturen. Koefficienterna $S(n,k)$ är " Stirlingtal av det andra slaget". Denna sekvens har ett märkligt samband med Poisson-fördelningen : Om $X$ är en slumpvariabel med en Poisson-fördelning med förväntat värde $\lambda$ så är ${\ displaystil E(X^{n})=p_{n}(\lambda )}$ . När $\lambda =1$ ser vi att det ${\displaystyle n}:$ te momentet av Poisson-fördelningen med förväntat värde $1$ är antalet partitioner i en uppsättning av storlek $n$ , kallad $n$ :e klocknumret . Detta faktum om det ${\displaystyle n}:$ te momentet i den specifika Poisson-fördelningen är " Dobinskis formel ".

Karakterisering av deltaoperatorer

Det kan visas att en polynomsekvens { p _n (x) : n = 0, 1, 2, … } är av binomial typ om och endast om alla tre av följande villkor gäller:

• Den linjära transformationen på rymden av polynom i x som kännetecknas av
  $$p_{n}(x)\mapsto np_{n-1}(x)$$
  är skiftekvivariant , och
• ₀ p ( x ) = 1 för alla x , och
• p _n (0) = 0 för n > 0.

(Utståendet att denna operator är skiftekvivariant är detsamma som att säga att polynomsekvensen är en Sheffer-sekvens ; uppsättningen av sekvenser av binomial typ är korrekt inkluderad i uppsättningen av Sheffer-sekvenser.)

Deltaoperatörer

Den linjära transformationen är helt klart en deltaoperator , dvs en skiftekvivariant linjär transformation på rymden av polynom i x som reducerar grader av polynom med 1. De mest uppenbara exemplen på deltaoperatorer är differensoperatorer och differentiering. Det kan visas att varje deltaoperator kan skrivas som en potensserie av formen

$Q=\sum _{n=1}^{\infty }c_{n}D^{n}$

där D är differentiering (observera att den nedre gränsen för summering är 1). Varje deltaoperator Q har en unik sekvens av "grundpolynom", dvs en polynomsekvens som uppfyller

1. $p_{0}(x)=1,$
2. $p_{n}(0)=0\quad {\rm {for\ }}n\geq 1,{\rm {\ och}}$
3. $Qp_{n}(x)=np_{n-1}(x).$

Det visades 1973 av Rota , Kahaner och Odlyzko , att en polynomsekvens är av binomial typ om och endast om den är sekvensen av grundläggande polynom av någon deltaoperator. Därför är detta stycke ett recept för att generera så många polynomsekvenser av binomial typ som man kan önska.

Karakterisering av Bell polynom

För varje sekvens a ₁ , a ₂ , a ₃ , … av skalärer, låt

$p_{n}(x)=\summa _{k=1}^ {n}B_{n,k}(a_{1},\dots,a_{n-k+1})x^{k}$

där B _{n , k} ( a ₁ , …, a _{n − k +1} ) är Bellpolynomet . Då är denna polynomsekvens av binomial typ. Observera att för varje n ≥ 1,

$p_{n}'(0)=a_{n}.$

Här är huvudresultatet av detta avsnitt:

Sats: Alla polynomsekvenser av binomisk typ är av denna form.

Ett resultat i Mullin och Rota, upprepat i Rota, Kahaner och Odlyzko (se referenser nedan) anger att varje polynomsekvens { p _n ( x ) } _n av binomial typ bestäms av sekvensen { p _n ′(0) } _n , men de källorna nämner inte Bell-polynom.

Denna sekvens av skalärer är också relaterad till deltaoperatorn. Låta

$P(t)=\sum _{n=1}^{\infty }{a_{n} \over n!}t^{n}.$

Sedan

$P^{-1}\left({d \over dx}\right)$

är deltaoperatorn för denna sekvens.

Karakterisering av en konvolutionsidentitet

För sekvenser a _n , b _n , n = 0, 1, 2, …, definiera en sorts faltning med

$(a{\mathbin {\diamondsuit }}b)_{n}=\sum _{j=0}^{n}{n \choose j}a_{j}b_{nj}.$

Låt $a_{n}^{k\diamondsuit }$ vara den n :e termen i sekvensen

$\underbrace {a\mathbin {\diamondsuit } \cdots \mathbin {\diamondsuit } a} _{k{\text{ factors}}}.$

₀₀ Sedan för varje sekvens a _i , i = 0, 1, 2, ..., med a = 0, sekvensen definierad av p ( x ) = 1 och

$p_{n}(x)=\sum _{k=1}^{n}{a_{n}^{k\diamondsuit }x^{k} \over k!}\,$

för n ≥ 1, är av binomial typ, och varje sekvens av binomial typ är av denna form.

Karakterisering genom att generera funktioner

Polynomsekvenser av binomial typ är just de vars genererande funktioner är formella (inte nödvändigtvis konvergenta) potensserier av formen

$\sum _{n=0}^{\infty }{p_{n}(x) \over n!}t^{n}=e^{xf(t) )}$

där f ( t ) är en formell potensserie vars konstantled är noll och vars förstagradsterm inte är noll. Det kan visas genom att använda power-serieversionen av Faà di Brunos formel att

$f(t)=\sum _{n=1}^{\infty }{p_{n}\,'(0) \over n!}t^{n}.$

Deltaoperatorn för sekvensen är f ⁻¹ ( D ), så att

$f^{-1}(D)p_{n}(x)=np_{n-1}(x).$

Ett sätt att tänka på dessa genererande funktioner

Koefficienterna i produkten av två formella effektserier

$\sum _{n=0}^{\infty }{a_{n} \over n!}t^{n}$

och

$\sum _{n=0}^{\infty }{b_{n} \over n!}t^{n}$

är

$c_{n}=\summa _{k=0}^{n}{n \choose k}a_{k}b_{nk }$

(se även Cauchy-produkt ). Om vi ​​tänker på x som en parameter som indexerar en familj av sådana potensserier, så säger den binomiala identiteten i själva verket att potensserien indexerad med x + y är produkten av de som indexeras med x och med y . Således x argumentet till en funktion som mappar summor till produkter: en exponentiell funktion

$g(t)^{x}=e^{xf(t)}$

där f ( t ) har formen ovan.

Umbral sammansättning av polynomsekvenser

Uppsättningen av alla polynomsekvenser av binomial typ är en grupp där gruppoperationen är "umbral sammansättning" av polynomsekvenser. Den operationen definieras enligt följande. Antag att { p _n ( x ) : n = 0, 1, 2, 3, ... } och { q _n ( x ): n = 0, 1, 2, 3, ... } är polynomsekvenser, och

$p_{n}(x)=\summa _{k=0}^{n}a_{n,k}\,x^{k}.$

Då är umbralsammansättningen p o q den polynomsekvens vars n: te term är

$(p_{n}\circ q)(x)=\summa _{k=0}^{n }a_{n,k}\,q_{k}(x)$

(nedsänkningen n förekommer i p _n , eftersom detta är n -termen för den sekvensen, men inte i q , eftersom detta hänvisar till sekvensen som helhet snarare än en av dess termer).

Med deltaoperatorn definierad av en potensserie i D enligt ovan, är den naturliga bijektionen mellan deltaoperatorer och polynomsekvenser av binomial typ, även definierade ovan, en gruppisomorfism, där gruppoperationen på potensserier är formell sammansättning av formell potens serier.

Kumulanter och moment

Sekvensen K _n av koefficienter för förstagradstermera i en polynomsekvens av binomisk typ kan betecknas som kumulanterna för polynomsekvensen. Det kan visas att hela polynomsekvensen av binomialtyp bestäms av dess kumulanter, på ett sätt som diskuteras i artikeln med titeln kumulant . Således

$p_{n}'(0)=\kappa _{n}=$ den n :e kumulanten

och

$p_{n}(1)=\mu _{n}'=$ det n :te ögonblicket.

Dessa är "formella" kumulanter och "formella" moment , till skillnad från kumulanter av en sannolikhetsfördelning och moment av en sannolikhetsfördelning.

Låta

$f(t)=\sum _{n=1}^{\infty }{\frac {\kappa _{n}}{n!}}t^{n}$

vara den (formella) kumulantgenererande funktionen. Sedan

$f^{-1}(D)$

är deltaoperatorn associerad med polynomsekvensen, dvs vi har

$f^{-1}(D)p_{n}(x)=np_{n-1}(x).$

Ansökningar

Begreppet binomial typ har tillämpningar inom kombinatorik , sannolikhet , statistik och en mängd andra områden.

Se även

• Lista över faktoriella och binomiska ämnen
• Binomial-QMF (Daubechies wavelet filter)

• G.-C. Rota , D. Kahaner och A. Odlyzko , "Finite Operator Calculus," Journal of Mathematical Analysis and its Applications, vol. 42, nr. 3, juni 1973. Omtryckt i boken med samma titel, Academic Press, New York, 1975.
• R. Mullin och G.-C. Rota, "On the Foundations of Combinatorial Theory III: Theory of Binomial Enumeration," i Graph Theory and Its Applications , redigerad av Bernard Harris, Academic Press, New York, 1970.

Som titeln antyder handlar den andra av ovanstående uttryckligen om tillämpningar för kombinatorisk uppräkning.

• di Bucchianico, Alessandro. Probabilistiska och analytiska aspekter av Umbral Calculus , Amsterdam, CWI , 1997.
• Weisstein, Eric W. "Binomial-Type Sequence" . MathWorld .