Restricted Integer Partitions

Question

P_k(n) means the amount of partitions of n into exactly k parts. Given n and k, calculate P_k(n).

Tip: P_k(n) = P_k(n−k) + P_k−1(n−1), with initial values p₀(0) = 1 and p_k(n) = 0 if n ≤ 0 or k ≤ 0. ^[Wiki]

Examples

n    k    Ans
1    1    1
2    2    1
4    2    2
6    2    3
10   3    8

Rules

• General code-golf rules apply.

Answer 1

Swift, 76 73 bytes

func P(_ n:Int,_ k:Int)->Int{return n*k>0 ?P(n-k,k)+P(n-1,k-1):n==k ?1:0}

Try it online!

---

Explanation

How does the code structurally work?

First of all, we define our function P, with two integer parameters n and k, and give it a return type of Int, with this piece of code: func P(_ n:Int,_ k:Int)->Int{...}. The cool trick here is that we tell the compiler to ignore the names of the parameters, with _ followed by a space, which saves us two bytes when we call the function. return is obviously used to return the result of our nested ternary described below.

Another trick I used was n*k>0, which saves us a couple of bytes over n>0&&k>0. If the condition is true (both the integers are still higher than 0), then we recursively call our function with n decremented by k as our new n and k stays the same, and we add the result of P() with n and k decremented by 1. If the condition is not true, we return either 1 or 0 depending on whether n is equal to k.

How does the recursive algorithm work?

We know that the first element of the sequence is p₀(0), and so we check that both integers are positive (n*k>0). If they are not higher than 0, we check if they are equal (n==l ?1:0), here being two cases:

• There is exactly 1 possible partition, and thus we return 1, if the integers are equal.

• There are no partitions if one of them is already 0 and the other is not.

However, if both are positive, we recursively call P twice, adding the results of P(n-k,k) and P(n-1,k-1). And we loop again until n has reached 0.

---

_{* Note: The spaces cannot be removed.}

Answer 2

Pyth, 9 7 6 bytes

^{-1 byte thanks to Erik the Outgolfer!}

/lM./E

Try it online!

Inputs to the program are reversed (i.e. k, n).

Answer 3

Jelly, 6 bytes

œċS€ċ⁸

Try it online!

Answer 4

Python 2, 61 55 51 50 bytes

-10 bytes thanks to Erik the Outgolfer. -1 byte thanks to Mr. Xcoder.

I will say, I did copy the hint from OP and translate it to Python. :P

P=lambda n,k:n*k>0and P(n-k,k)+P(n-1,k-1)or+(n==k)

Try it online!

Answer 5

Mathematica, 33 bytes

Length@IntegerPartitions[#,{#2}]&

here is n x k table

 \k->
 n1  0  0   0   0   0   0   0   0   0  
 |1  1  0   0   0   0   0   0   0   0  
 v1  1  1   0   0   0   0   0   0   0  
  1  2  1   1   0   0   0   0   0   0  
  1  2  2   1   1   0   0   0   0   0  
  1  3  3   2   1   1   0   0   0   0  
  1  3  4   3   2   1   1   0   0   0  
  1  4  5   5   3   2   1   1   0   0  
  1  4  7   6   5   3   2   1   1   0  
  1  5  8   9   7   5   3   2   1   1  

Answer 6

MATL, 14 bytes

y:Z^!S!Xu!Xs=s

Try it online!

Explanation

Consider inputs 6, 2.

y     % Implicitly take the two inputs. Duplicate from below
      % STACK: 6, 2, 6
:     % Range
      % STACK: 6, 2, [1 2 3 4 5 6]
Z^    % Cartesian power
      % STACK: 6, [1 1; 1 2; ... 1 5; 1 6; 2 1; 2 2; ...; 6 6]
!S!   % Sort each row
      % STACK: 6, [1 1; 1 2; ... 1 5; 1 6; 1 2; 2 2; ...; 6 6]
Xu    % Unique rows
      % STACK: 6, [1 1; 1 2; ... 1 5; 1 6; 2 2; ...; 6 6]
!Xs   % Sum of each row, as a row vector
      % STACK: 6, [2 3 ... 6 7 4 ... 12]
=     % Equals, element-wise
      % STACK: [0 0 ... 1  0 0 ... 0]
s     % Sum. Implicitly display
      % STACK: 3

Answer 7

JavaScript (ES6), 42 40 39 bytes

I think this works.

f=(x,y)=>x*y>0?f(x-y,y)+f(--x,--y):x==y

---

Try it

k.value=(
f=(x,y)=>x*y>0?f(x-y,y)+f(--x,--y):x==y
)(i.value=10,j.value=3)
onchange=_=>k.value=f(+i.value,+j.value)

*{font-family:sans-serif}input{margin:0 5px 0 0;width:100px;}#j,#k{width:50px;}

<label for=i>n: </label><input id=i type=number><label for=j>k: </label><input id=j type=number><label for=k>P<sub>k</sub>(n): </label><input id=k readonly>

Answer 8

Haskell, 41 bytes

0#0=1
n#k|n*k>0=(n-k)#k+(n-1)#(k-1)
_#_=0

Try it online!

Answer 9

Pari/GP, 35 bytes

Pari/GP has a built-in for iterating over integer partitions.

n->k->i=0;forpart(x=n,i++,,[k,k]);i

Try it online!

Answer 10

Haskell, 41 bytes

n&0=0^n
n&k=sum$map(&(k-1))[n-1,n-k-1..0]

Try it online!

An alternate recurrence.

Answer 11

Jelly, 13 bytes

I have a feeling know this basic approach won't be the golfiest!

RŒṖL€€Ṣ€QṀ€=S

Try it online!

Answer 12

05AB1E, 9 bytes

L²ã€{ÙO¹¢

Try it online!

Answer 13

CJam, 18 bytes

{_,:)@m*:$_&::+e=}

Try it online!

Expects inputs in reverse, i.e. k n instead of n k.

Answer 14

Scala, 73 bytes

Well this is some easy unreworked use of OP's tip.

k and n are the parameters of my recursive function f. See TIO link for context.

Since this is recursive, should I include function def in byte count?

(k,n)match{case(0,0)=>1
case _ if k<1|n<1=>0
case _=>f(n-k,k)+f(n-1,k-1)}

Try it online!

Answer 15

C (gcc), 41 bytes

f(n,k){n=n*k>0?f(n-k,k)+f(--n,--k):n==k;}

Try it online!

Answer 16

R (+ pryr), 49 bytes

f=pryr::f(`if`(k<1|n<1,!n+k,f(n-k,k)+f(n-1,k-1)))

Which evaluates to the recursive function

function (k, n) 
if (k < 1 | n < 1) !n + k else f(n - k, k) + f(n - 1, k - 1)

(k < 1 | n < 1) checks if any of the initial states are met. !n + k evaluates to TRUE (1) if both n and k are 0, and FALSE (0) otherwise. f(n - k, k) + f(n - 1, k - 1) handles the recursion.