Laske summan
\sum_{m=1}^n { m/(m-1)! * \sum_{k=0}^{n-m} { (-1)^k / k! } }
arvo.
Selvennys: Se on siis n:stä riippuva tuplasumma, jossa m käy 1:stä n:ään ja sisäsummassa k käy 0:sta (n-m):ään. Ja summattava termi on
m / (m-1)! * (-1)^k / k!
Vinkki: vastaus on kuinka monta päivää on jouluun.
\sum_{m=1}^n { m/(m-1)! * \sum_{k=0}^{n-m} { (-1)^k / k! } }
arvo.
Selvennys: Se on siis n:stä riippuva tuplasumma, jossa m käy 1:stä n:ään ja sisäsummassa k käy 0:sta (n-m):ään. Ja summattava termi on
m / (m-1)! * (-1)^k / k!
Vinkki: vastaus on kuinka monta päivää on jouluun.
Vastaukset 15
Vanhimmat
Äh. Enpä osaa. Ilmeisesti sisempi summa sievenee, ja jäljelle jää sum_{m=1}^n m*(n-m)/((n-m)!).
2 ehtoota(e)
Tuossa taitaa olla äärellinen määrä rationaalilukuja, jolloin vastaus ei voi olla 2e, koska e on irrationaalinen.
Onhan e:lle sarjakehitelmä sum 1/n! nollasta äärettömiin. On tuo silti kyllä väärin, kunhan heitin vaan koska oli silloin kaksi yötä jouluun...
En saa tuosta kakkosta kun n=1, mutta n=2,3,4 niillä tulee kaikilla summan arvoksi 2. Sen osoittaminen, että siitä eteenpäinkin tulee vierasvoittoja viittaisi idunktiotodistukseen. En edes yritä...
Siinä pitää tarkastella kahden peräkkäisen summan erotusta, joka on siis oltava 0. Erinäisten vaiheiden jälkeen päädytään siihen, että sum(-1)^m/(m!(n-m)!)=oltava 0,
kun m summataan, from 0 to n , ja n on ykköstä suurempi. Tuo ei induktiolla tuota vaikeuksia.
Kun n=2 , sum= ½-1 ½=0
Induktio-oletus: sum(-1)^m/(m!(n-m)!)=0,
Induktioväite sum(-1)^m/(m!(n 1-m)!)=0, kun lavennetaan termillä (n-m)!
tulee 0*(n-m)!/(n 1-m), joka = 0.
Oikea vastaus on 2.
Joo n=1 ei toimi vaan silloin tulee 1.. Olisikin voinut kompana kysyä raja-arvoa, kun n menee äärettömään :D.
Kerrotaan nyt miten päädyin tähän kyseiseen summaan.
----
LEMMA
Kun äärellinen ryhmä G toimii transitiivisesti äärellisellä joukolla X ja x on jokin X:n alkio, niin
|X/Stab(x)| = 1/|G| * summa_{g∈G} |Fix(g)|^2
(vasen puoli siis ratojen määrä x:n Stabiloijan Stab(x) = {g∈G | gx = x} toimiessa X:llä).
----
En ole kylläkään saanut kyseistä lemmaa todistettua. Osaisiko joku neuvoa tuon todistamisessa?
No kuitenkin, lähdin soveltamaan kokeilumielessä tuota Lemmaa symmetrisen ryhmän S_n toiminnalle joukolla X = {1, 2, ..., n} (toimii permutoimalla). Valitaan esim. x = n. Ja huomataan, että Stab(n) tekee kaksi rataa, sillä lopuilla se toimii transitiivisesti (paitsi kun n=1, jolloin muita kuin 1 ei ole). Toisen puolen laskemiseksi vinkkinä: kannattaa etsiä sopivaa kaavaa "rencontres-luvuille".
En ole varma tuosta lemmasta. Menisikö jotenkin Burnsiden lemmalla? Ei taida mennä ainakaan ihan suoraan, kun _Bursidessä ei ole toista potenssia.
Ei kun eikös se ole todistettu osoitteessa https://math.stackexchange.com/questions/2491749/show-rxg-sum-g-in-gfixg2-where-g-x-is-a-transitive-group-and
Hei, tämähän onkin hyvä että löytyi. Itsekin jo etsiskelin mutten löytänyt. Nokkela temppu kirjoittaa |Fix(g)| = summa_{x∈X} δg,y. En olisi itse tuota varmaankaan keksiny, mutta pitääpä pitää tuo mielessä.
Voisikos tuota muuten yrittää korkeammillekin potensseille |Fix(x)|^k?
summa_g |Fix(x)|^k
= summa_{x_1} summa_{x_2}...summa_{x_k} |Stab(x_1) ∩ Stab(x_2)∩...∩Stab(x_k)|
= ... ?
Symmetriselle ryhmälle (recontres-luvut: https://en.wikipedia.org/wiki/Rencontres_numbers ) näyttäisi k:n arvolla 3 summasta tulevan 5 * n!
ja edelleen
k=4 antaa 15 (jaetaan nyt se n! toiselle puolelle),
k=5 antaa 52
k=6 antaa 203
...
(kun otetaan n>=k)
Onkos nämä Bellin luvut?!?
Enpäs tiedä. Suosittelisin kuitenkin, että käyttäisit tuota sivua. Siellä tuntuu olevan paremmin asiantuntijoita kuin Suomi24:llä. Sinne vaan kysymys ja ratkaisuidea niin eiköhän tule alan ammattilaisen vastaus.
En tiedä onko suljettua muotoa olevaa ratkaisua, mutta menetelmä korkeammille potensseille on olemassa. Tuskinpa meneteelmä tuottaa otaksumasi kaavan. Katso https://math.stackexchange.com/questions/2583577/is-there-formulas-for-sum-g-in-g-operatornamefixgn/2583625#2583625
Mutta tuohan onkin hyvä tapa ajatella, että toiminto onkin X^k:lla . Mitä "otaksumaani kaavaa" tarkoitat? Ai, että siitä tulee Bellin luvut? Mutta niinhän siitä juuri tulee, koska S_n:n toiminto {1,2,..,n}:llä onkin juuri n-transitiivinen (se tulee suoraan siitä että permutaatiolla voidaan permutoida miten halutaan. Tätä muotoa määritelmästä en kyllä ollut ennen katsonutkaan: https://groupprops.subwiki.org/wiki/Multiply_transitive_group_action
mutta tuolla se sanotaankin että "The symmetric group on any set is k-transitive for every k.")
Tuonne StackExchage:n kysymykseesi tuli muuten toinenkin ratkaisu (oli tullut juuri kun olin siellä sivulla :D) ja sen kohta c sanoo tuon Bellin luvun. Ensin tullut ratkaisu puhuu pelkästä (kakkostyypin) Stirlingin luvusta, mutta vastaus pitäisi varmaan olla summa näistä eli X:n kaikki mahdolliset ositukset eikä pelkästään n:ään osaan ositukset.
Tarkoitin kaavaa summa_g |Fix(x)|^k
= summa_{x_1} summa_{x_2}...summa_{x_k} |Stab(x_1) ∩ Stab(x_2)∩...∩Stab(x_k)|
Eikös se tule näin (vastaavasti kuin oli tehty ensimmäisessä linkatussa SE-postauksen vastauksessa tapauksessa k=2):
∑_{g∈G} |Fix(g)|^k = ∑_{x1∈X} ∑_ {x2∈X} … ∑_{xk∈X} ∑_{g∈G} ∏_{j=1}^k δg,xj
ja
∑_{g∈G} ∏δg,xj = ∣⋂Stab(xj)∣
Eli kirjoitettaan kukin Fix(g) omana summanaan δg,x:stä yli X:n ja sitten siirretään kaikki viimeisen summan alle ja sinne tulee siis tulo deltoista. Tämä tulohan on (jokaiselle g) 1 silloin ja vain silloin kun jokainen x_j kiinnittää g:n eli siis sen summa yli G:n on stabiloijien leikkauksen koko.
-----------------------------------------------------------------------
Mathjax-koodina jos yllä olevasta ei ota selvää :D
$\DeclareMathOperator{\Stab}{Stab}$
$$\sum\limits_{g \in G} |\textrm{Fix}(g)|^k = \sum\limits_{x_1 \in X} \sum\limits_{x_2 \in X} \dots \sum\limits_{x_k \in X} \sum\limits_{g \in G} \prod_{j=1}^k \delta_{g,x_j}$$
ja
$$ \sum\limits_{g \in G} \prod_{j=1}^k \delta_{g,x_j} = \left|\bigcap_{j=1}^k \Stab(x_j) \right|$$
--------------------------------------------------------------------------------------