Jumlah perkiraan

16

Tugas

Diberikan 2 bilangan bulat positif ndan k, di mana n > k, mengeluarkan jumlah dugaan dari satu set nelemen yang dapat dibedakan menjadi satu set kelemen yang dapat dibedakan.

Definisi

Fungsi f: S → T disebut surjeksi jika untuk setiap t∈T ada s suchS sehingga f (s) = t.

Contoh

Kapan n=3dan k=2, outputnya adalah 6, karena ada 6dugaan dari {1,2,3}ke {1,2}:

  1. 1↦1, 2↦1, 3↦2
  2. 1↦1, 2↦2, 3↦1
  3. 1↦1, 2↦2, 3↦2
  4. 1↦2, 2↦1, 3↦1
  5. 1↦2, 2↦1, 3↦2
  6. 1↦2, 2↦2, 3↦1

testcases

n k output
5 3 150
8 4 40824
9 8 1451520

Referensi

Mencetak gol

Ini adalah . Jawabannya terpendek dalam byte menang.

Celah standar berlaku.

bocor Nun
sumber
11
Definisi surjection akan menyenangkan.
Stewie Griffin
3
Apakah disengaja bahwa n tidak dapat menyamai k ?
Dennis
1
@Dennis Saya ingin mengecualikan setiap kemungkinan tepi dari tantangan saya
Leaky Nun
3
Itu sepertinya kasus tepi penting untuk dimasukkan. Dugaan saya adalah bahwa sebagian besar jawaban yang bekerja untuk n> k juga akan bekerja untuk n == k tetapi mungkin memungkinkan untuk bermain golf secara licik di suatu tempat
dylnan
@ siapa pun yang memilih untuk menutup apa alasan Anda?
dylnan

Jawaban:

5

Jelly , 5 4 byte

ṗṬML

Ini adalah solusi brute force O (k n ) .

Cobalah online!

Bagaimana itu bekerja

ṗṬML  Main link. Left argument: k. Right argument: n.

ṗ     Cartesian power; yield the list of all n-tuples over {1, ..., k}.
      Each tuple represents a (not necessarily surjective) function from
      {1, ..., n} to {1, ..., k}.
 Ṭ    Apply the "untruth" atom to each tuple.
      Ṭ maps a list of indices to an array with 1's at those indices, and exactly
      as many zeroes as needed to build the array.
      Examples:
           [1, 2, 3, 3, 3] -> [1, 1, 1]
           [1, 3, 5]       -> [1, 0, 1, 0, 1]
           [2, 6, 2, 4, 4] -> [0, 1, 0, 1, 0, 1]
  M   Yield all indices of maximal elements, i.e., all indices of [1] * k.
   L  Take the length.
Dennis
sumber
4

Haskell , 48 byte

s(_,1)=1
s(1,_)=0
s(m,n)=n*(s(m-1,n-1)+s(m-1,n))

Cobalah online!

Mengapa surjection diperhitungkan s(m,n)=n*s(m-1,n-1)+n*s(m-1,n)?

untuk memanen ngambar, saya juga bisa

  • memeras [m]ciptaan singleton ke salah satu nbatas di sekitar n-1kelompok
  • atau tambahkan yang baru mke salah satu ngrup yang sudah ada[1..m-1]

Haskell , 38 byte

m#n|n<2=1|m<2=0|o<-m-1=n*(o#(n-1)+o#n)

Cobalah online!

Roman Czyborra
sumber
2
38 byte dengan menggunakan operator infiks: Coba online!
Laikoni
4

Lean , 66 byte

def s:_->nat->nat|(m+1)(n+1):=(n+1)*(s m n+s m(n+1))|0 0:=1|_ _:=0

Cobalah online!


Bukti kebenaran

Cobalah online!


Penjelasan

Mari kita ungolf fungsinya:

def s : nat->nat->nat
| (m+1) (n+1) := (n+1)*(s m n + s m (n+1))
| 0     0     := 1
| _     _     := 0

Fungsi ini ditentukan oleh pencocokan pola dan rekursi, yang keduanya memiliki dukungan bawaan.

Kami mendefinisikan s(m+1, n+1) = (n+1) * (s(m, n) + s(m, n+1)dan s(0, 0) = 1, yang meninggalkan terbuka s(m+1, 0)dan s(0, n+1), keduanya didefinisikan 0oleh kasus terakhir.

Lean menggunakan sintaks kalkulus lamdba, begitu s m njuga s(m, n).


Sekarang, bukti kebenaran: Saya menyatakannya dalam dua cara:

def correctness : ∀ m n, fin (s m n) ≃ { f : fin m → fin n // function.surjective f } :=
λ m, nat.rec_on m (λ n, nat.cases_on n s_zero_zero (λ n, s_zero_succ n)) $
λ m ih n, nat.cases_on n (s_succ_zero m) $ λ n,
calc fin (s (nat.succ m) (nat.succ n))
   ≃ (fin (n + 1) × (fin (s m n + s m (n + 1)))) :
  (fin_prod _ _).symm
... ≃ (fin (n + 1) × (fin (s m n) ⊕ fin (s m (n + 1)))) :
  equiv.prod_congr (equiv.refl _) (fin_sum _ _).symm
... ≃ (fin (n + 1) × ({f : fin m → fin n // function.surjective f} ⊕
         {f : fin m → fin (n + 1) // function.surjective f})) :
  equiv.prod_congr (equiv.refl _) (equiv.sum_congr (ih n) (ih (n + 1)))
... ≃ {f // function.surjective f} : s_aux m n

def correctness_2 (m n : nat) : s m n = fintype.card { f : fin m → fin n // function.surjective f } :=
by rw fintype.of_equiv_card (correctness m n); simp

Yang pertama adalah apa yang sebenarnya terjadi: bijection antara [0 ... s(m, n)-1]dan surjections dari [0 ... m-1]ke [0 ... n-1].

Yang kedua adalah bagaimana biasanya dinyatakan, bahwa s(m, n)adalah kardinalitas dari surjections dari [0 ... m-1]ke [0 ... n-1].


Lean menggunakan teori tipe sebagai fondasinya (bukan teori himpunan). Dalam teori tipe, setiap objek memiliki tipe yang melekat padanya. natadalah jenis bilangan asli, dan pernyataan yang 0merupakan bilangan alami dinyatakan sebagai 0 : nat. Kami mengatakan bahwa itu 0adalah tipe nat, dan yang natmemiliki 0sebagai penduduk.

Proposisi (pernyataan / pernyataan) juga tipe: penghuninya adalah bukti proposisi.


  • def: Kami akan memperkenalkan definisi (karena bijection benar-benar fungsi, bukan hanya proposisi).

  • correctness: nama definisi

  • ∀ m n: untuk setiap mdan n(Lean secara otomatis menyimpulkan bahwa tipenya adalah nat, karena apa yang berikut).

  • fin (s m n)adalah jenis bilangan alami yang lebih kecil dari s m n. Untuk membuat penghuni, orang memberikan nomor alami dan bukti bahwa itu lebih kecil dari s m n.

  • A ≃ B: bijection antara jenis Adan jenisnya B. Mengatakan bijection menyesatkan, karena seseorang harus menyediakan fungsi terbalik.

  • { f : fin m → fin n // function.surjective f }jenis surjections dari fin mke fin n. Sintaks ini membangun subtipe dari tipe fin m → fin n, yaitu tipe fungsi dari fin mhingga fin n. Sintaksnya adalah { var : base type // proposition about var }.

  • λ m: ∀ var, proposition / type involving varbenar-benar fungsi yang dibutuhkan varsebagai input, jadi λ mperkenalkan input. ∀ m n,adalah kependekan dari∀ m, ∀ n,

  • nat.rec_on m: lakukan rekursi pada m. Untuk menentukan sesuatu untuk m, menentukan hal untuk 0dan kemudian memberikan hal untuk k, membangun hal untuk k+1. Orang akan melihat bahwa ini mirip dengan induksi, dan memang ini adalah hasil dari korespondensi Gereja-Howard . Sintaksnya adalah nat.rec_on var (thing when var is 0) (for all k, given "thing when k is k", build thing when var is "k+1").

Heh, ini semakin lama dan aku hanya di baris ketiga correctness...

bocor Nun
sumber
3

J , 19 byte

-/@(^~*]!0{])],i.@-

Cobalah online!

Penjelasan

-/@(^~*]!0{])],i.@-  Input: n (LHS), k (RHS)
                  -  Negate k
               i.@   Range [k-1, k-2, ..., 0]
             ]       Get RHS
              ,      Join, forms [k, k-1, ..., 0]
   (        )        Dyad between n (LHS), [k, k-1, ..., 0] (RHS)
           ]           Get RHS
         0{            Select value at index 0
       ]               Get RHS
        !              Binomial coefficient
    ^~                 Raise each in RHS to power of n
      *                Multiply
-/@                  Reduce from right to left using subtraction (forms alternating sum)
mil
sumber
-/@(^~*]!0{])]-i.
FrownyFrog
2

R , 49 byte

function(n,k,j=0:k)((-1)^(k-j)*j^n)%*%choose(k,j)

Cobalah online!

Menerapkan salah satu formula oleh Mario Catalani:

T(n, k) = Sum_{j=0..k} (-1)^(k-j)*j^n*binomial(k, j)

atau secara bergantian:

T(n, k) = Sum_{j=0..k} (-1)^j*binomial(k, j)*(k-j)^n

yang menghasilkan jumlah byte yang sama dalam R.

Giuseppe
sumber
2

Python 2 , 56 53 50 byte

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

Cobalah online!

-3 byte terima kasih kepada H.PWiz.

-3 byte terima kasih kepada Dennis.

  • Jika n<ktidak semua kbisa dipetakan maka tidak ada dugaan. n/k andurus ini.
  • Mengambil f(0,0)=1memberi kita satu-satunya case base bukan nol yang kita butuhkan. 1/k ormencapai ini.
dylnan
sumber
2

Ruby , 46 byte

f=->n,k{k>n ?0:k+n<1?1:k*(f[n-=1,k]+f[n,k-1])}

Cobalah online!

Pendekatan rekursif standar ...

Kirill L.
sumber
2

Brain-Flak , 142 byte

({}<({}()){({}[(())]<<>{({}({})<>)<>}{}>)}{}>)<>{<>(({}<>)<{({}[()]<([])({([{}]()({}))([{}]({}))}{}[{}])>)}{}({}<>)>)<>}<>{}{}{({}<>[{}])<>}<>

Cobalah online!

Ini menggunakan rumus inklusi-pengecualian standar.

Saya tidak bisa menulis penjelasan lengkap saat ini, tapi inilah penjelasan tingkat tinggi:

# Compute k-th row of Pascal's triangle
({}<({}()){({}[(())]<<>{({}({})<>)<>}{}>)}{}>)<>

# Multiply each element by n^j (and reverse to other stack)
{<>(({}<>)<{({}[()]<([])({([{}]()({}))([{}]({}))}{}[{}])>)}{}({}<>)>)<>}

# Compute alternating sum
<>{}{}{({}<>[{}])<>}<>
Nitrodon
sumber
2

Pari / GP , 38 byte

(n,k)->Pol(exp(x+O(x^n))-1)^k*n!\x^n%x

Cobalah online!

Menggunakan rumus oleh Vladimir Kruchinin di OEIS:

E.g.f.: (exp(x)-1)^k = sum T(n,k)x^n/n!
alephalpha
sumber
2

Sekam , 7 byte

#`¦ḣ¹π²

Cobalah online!

Penjelasan

#`¦ḣ¹π²  Inputs: n (²), implicit k (¹)
     π²  Cartesian power of [1..k] to n
#        Count if:
   ḣ¹      Range [1..k]
 `¦        Is a subset
Fyr
sumber
1

05AB1E , 10 byte

sLsãʒêgQ}g

Cobalah online!

Penjelasan

sLsã       # Cartesian product of range(k) repeated n times
    ʒ   }  # Filter by ...
     êgQ   # Connected uniquified length == k  (every item in range(k) appears at least once)
         g # Count
Kaldo
sumber