tło

Wielomian Sidi stopnia n - lub (n + 1) ^th wielomian Sidi - jest zdefiniowany następująco.

Wielomiany Sidi mają kilka interesujących właściwości, ale i ich współczynniki. Te ostatnie tworzą sekwencję OEIS A075513 .

Zadanie

Napisz pełny program lub funkcję, która przy nieujemnej liczbie całkowitej n drukuje lub zwraca bezwzględną sumę współczynników wielomianu Sidi stopnia n , to znaczy

Sumy te tworzą sekwencję OEIS A074932 .

Jeśli wolisz indeksowanie na podstawie 1, możesz zamiast tego wziąć dodatnią liczbę całkowitą n i obliczyć bezwzględną sumę współczynników n- ^tego wielomianu Sidi.

Ponieważ jest to gra w golfa , kod musi być możliwie jak najkrótszy. Obowiązują wszystkie standardowe zasady.

Przypadki testowe (oparte na 0)

 n           Σ

 0           1
 1           3
 2          18
 3         170
 4        2200
 5       36232
 6      725200
 7    17095248
 8   463936896
 9 14246942336

Przypadki testowe (oparte na 1)

 n           Σ

 1           1
 2           3
 3          18
 4         170
 5        2200
 6       36232
 7      725200
 8    17095248
 9   463936896
10 14246942336

05AB1E , 10 bajtów

Ý©¹c®>¹m*O

Wykorzystuje kodowanie CP-1252 . Wypróbuj online!

Python 2 , 43 bajty

f=lambda n,k=1:k/n or n*f(n,k+1)+k*f(n-1,k)

Wypróbuj online!

Inne podejście

Od kiedy opublikowałem to wyzwanie, starałem się znaleźć rekurencyjne rozwiązanie tego problemu. Chociaż nie udało mi się użyć wyłącznie długopisu i papieru, udało mi się przekształcić formułę w golfa w praktyczny problem - przynajmniej w przypadku niektórych definicji praktycznych - co ułatwiło analizę.

Wyobraź sobie teleturniej za pomocą k + m kandydatami na który działa w następujący sposób.

W rundzie 1 wszyscy kandydaci muszą wykonać określone zadanie tak szybko, jak to możliwe. Do k kandydatów, które realizują zadania najszybszym wygrać 1 k $ (jeden kilodollar) każda i przejść do 3 rundzie.

W drugiej rundzie m pozostałych kandydatów otrzymuje drugą szansę na dołączenie do drugiego k . Każdemu kandydatowi zadawane jest pytanie. Jeśli odpowiedzą poprawnie na pytanie, wygrają 1 tys. $ I przejdą do rundy 3. Jeśli jednak nie odpowiedzą na pytanie, zostaną wyeliminowani z gry. Oznacza to, że runda 3 będzie miała wartość od k do k + m kandydatów, w zależności od liczby osób, które odpowiedzą na ich pytania.

Runda składa się z 3 m więcej konkursów, które są podobne do okrągły 1. W każdym konkursie, uczestnicy mają do wykonania określonego zadania. W przeciwieństwie do pierwszej rundy tylko jeden kandydat otrzymuje nagrodę, ale wszyscy kandydaci mogą wziąć udział w następnym konkursie. Każdy konkurs płaci dwa razy więcej niż konkurs przed nim; pierwszy płaci 2 tys. $, a ostatni 2 ^mln $ .

Zauważ, że ponieważ wszystkie nagrody są potęgami dwóch, wiedza o tym, ile wygranych wygrał kandydat, oznacza, że ​​wiemy, czy awansowali do trzeciej rundy i który z konkursów w trzeciej rundzie wygrał.

Załóżmy, że oglądasz teleturniej, a runda 1 już się zakończyła, więc wiesz, którzy k kandydaci osiągnęli już rundę 3, a którzy m utknęli w rundzie 2. Na ile sposobów można rozdzielić pozostałe nagrody pieniężne?

Raz wiemy, który z drugiej turze za m kandydatów awansowały do rundy 3, to łatwo obliczyć ewentualne skutki dla tego konkretnego scenariusza. Jeśli j kandydatów awansuje, w rundzie 3 jest łącznie k + j kandydatów, a tym samym k + j możliwych wyników dla każdego konkursu. Przy m pojedynczych konkursach w rundzie 3 daje to (k + j) ^m wyników dla wszystkich m zawodów.

Teraz j może przyjąć dowolną wartość od 0 do m , w zależności od tego, którzy kandydaci odpowiadają poprawnie w rundzie 2. Dla każdej stałej wartości j istnieją ^m C _j różne kombinacje j kandydatów, które mogłyby przejść do rundy 3. Jeśli zadzwonimy całkowitą liczbę możliwych wyników dla k 3 kandydatów rundy i m 2 kandydatów rundy g (m, k) otrzymujemy następującą formułę.

Jeśli naprawimy k = 1 , otrzymamy następujący specjalny przypadek, który stanowi nasze nowe podejście do rozwiązania pierwotnego problemu.

Formuła rekurencyjna

Załóżmy teraz, że zasnąłeś podczas reklam po pierwszej rundzie i obudziłeś się w samą porę, aby zobaczyć, kto wygrał ostatni konkurs w rundzie 3, a tym samym główną nagrodę w ^wysokości 2 ^mln k $ . Nie masz żadnych innych informacji, a nawet łącznej kwoty nagród wygranych przez kandydata. Na ile sposobów można rozdzielić pozostałe nagrody pieniężne?

Jeśli zwycięzca był jednym z m kandydatów drugiej rundy, już teraz musieliśmy awansować do trzeciej rundy . Zatem efektywnie mamy k + 1 kandydatów w rundzie 3, ale tylko m - 1 kandydatów w rundzie 2. Ponieważ znamy zwycięzcę ostatniego konkursu, jest tylko m - 1 konkursów z niepewnymi wynikami, więc jest g (m - 1, k + 1) możliwe wyniki.

Jeśli zwycięzcą jest jeden z k kandydatów, którzy pominęli rundę 2, obliczenia stają się nieco trudniejsze. Jak poprzednio, pozostało tylko m - 1 rund, ale teraz nadal mamy k kandydatów w rundzie 3 i m kandydatów w rundzie 2. Ponieważ liczba kandydatów w rundzie 2 i liczba konkursów w rundzie 3 są różne, możliwe wyniki nie mogą oblicza się za pomocą zwykłego wywołania g . Jednak po tym, jak kandydat z pierwszej rundy 2 odpowiedział - słusznie lub niesłusznie - liczba kandydatów z drugiej rundy ponownie odpowiada m-1 konkursom z 3 rundy. Jeśli kandydat awansuje, jest k + 1 runda 3 kandydatów i tym samym g (m - 1, k + 1)możliwe rezultaty; jeśli kandydat zostanie wyeliminowany, liczba rund 3 kandydatów pozostaje na poziomie k, a możliwe są g (m - 1, k) wyniki. Ponieważ kandydat albo posuwa się naprzód, albo nie, istnieje g (m - 1, k + 1) + g (m - 1, k) możliwe wyniki łączące te dwa przypadki.

Teraz, jeśli dodamy potencjalne wyniki dla wszystkich kandydatów k + m, którzy mogliby wygrać nagrodę główną, wynik musi być zgodny g (m, k) . Jest m 2 zawodników z 2 rundy, które prowadzą do potencjalnych wyników g (m - 1, k + 1) , oraz k 3 zawodników z rundy, które prowadzą do g (m - 1, k + 1) + g (m - 1, k) te. Podsumowując, otrzymujemy następującą tożsamość.

Wraz z podstawą

te dwie formuły całkowicie charakteryzują funkcję g .

Implementacja golfa

Podczas

g=lambda m,k=1:0**m or(m+k)*g(m-1,k+1)+k*g(m-1,k)

(49 bajtów, 0**mdaje 1 raz m spada do 0 ) lub nawet

g=lambda m,k=1:m<1 or(m+k)*g(m-1,k+1)+k*g(m-1,k)

(48 bajtów, zwraca True zamiast 1 ) byłyby poprawnymi rozwiązaniami, wciąż są bajty do zapisania.

Jeśli zdefiniujemy funkcję f, która jako pierwszy argument przyjmuje liczbę n kandydatów z 1. rundy zamiast liczby m kandydatów z 2. rundy, tj.

otrzymujemy rekurencyjną formułę

z podstawą

Wreszcie mamy

więc implementacja Pythona

f=lambda n,k=1:k/n or n*f(n,k+1)+k*f(n-1,k)

( k/ndaje 1 raz n = k ) rozwiązuje bieżące zadanie za pomocą indeksowania 1.

Mathematica, 33 32 bajty

Oszczędność jednego bajtu dzięki JungHwan Min .

Binomial[#,r=0~Range~#].(r+1)^#&

Pyth - 13 12 bajtów

Po prostu implementuje formułę bez (-1)^kczęści.

sm*.cQd^hdQh

Pakiet testowy .

MATL , 12 bajtów

t:XnG:QG^*sQ

Dane wejściowe są oparte na 0.

Wypróbuj online!

Wyjaśnienie

Rozważ dane wejściowe 5jako przykład.

t      % Take n implicitly. Duplicate
       % STACK: 5, 5
:      % Range [1 2 ...n]
       % STACK: 5, [1 2 3 4 5]
Xn     % N-choose-k, vectorized
       % STACK: [5 10 10 5 1]
G:Q    % Push [2 3 ... n+1]
       % STACK: [5 10 10 5 1], [2 3 4 5 6]
G^     % Raise to n
       % STACK: [5 10 10 5 1], [32 243 1024 3125 7776]
*      % Multiply, element-wise
       % STACK: [160 2430 10240 15625 7776]
s      % Sum of array
       % STACK: 36231
Q      % Add 1. Display implicitly
       % STACK: 36232

R, 36 bajtów

sum(choose(n<-scan(),0:n)*(0:n+1)^n)

Wektoryzacja R przydaje się tutaj przy stosowaniu formuły.

J , 19 bajtów

+/@((!{:)*>:^{:)@i.

Używa indeksowania opartego na jednym.

Wypróbuj online!

Wyjaśnienie

+/@((!{:)*>:^{:)@i.  Input: integer n
                 i.  Range [0, 1, ..., n-1]
   (           )@    Operate on that range
             {:        Get the last value, n-1
          >:           Increment, range becomes [1, 2, ..., n]
            ^          Exponentiate. [1^(n-1), 2^(n-1), ..., n^(n-1)]
    ( {:)              Get the last value, n-1
     !                 Binomial coefficient. [C(n-1, 0), C(n-1, 1), ..., C(n-1, n-1)]
         *             Multiply
+/@                  Reduce by addition

Maxima, 39 bajtów

f(n):=sum(binomial(n,k)*(k+1)^n,k,0,n);

PARI / GP, 35 bajtów

n->sum(k=0,n,binomial(n,k)*(k+1)^n)

Aksjomat, 39 bajtów

f(n)==sum(binomial(n,i)*(i+1)^n,i=0..n)

kod testowy i wyniki

(35) -> [[i,f(i)] for i in 0..9]
   (35)
   [[0,1], [1,3], [2,18], [3,170], [4,2200], [5,36232], [6,725200],
    [7,17095248], [8,463936896], [9,14246942336]]

Galaretka , 9 bajtów

cR×R‘*ƊS‘

Wypróbuj online!

Jak to działa

cR×R‘*ƊS‘ - Main link. Argument: n (integer)        e.g.   5
 R        - Range from 1 to n                              [1, 2, 3, 4, 5]
c         - Binomial coefficient                           [5, 10, 10, 5, 1]
      Ɗ   - Last three links as a monad:
   R      -   Link 1: Range from 1 to n                    [1, 2, 3, 4, 5]
    ‘     -   Link 2: Increment                            [2, 3, 4, 5, 6]
     *    -   Link 3: To the power of n                    [32, 243, 1024, 3125, 7776]
  ×       - Multiply, pairwise                             [160, 2430, 10240, 15625, 7776]
       S  - Sum                                            36231
        ‘ - Increment                                      36232