# Restricted Integer Partitions

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

Tip: Pk(n) = Pk(n−k) + Pk−1(n−1), with initial values p0(0) = 1 and pk(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

• You should clearly state that this is code-golf, even though it's tagged. – Mr. Xcoder Jul 26 '17 at 14:01
• Can someone link to the OEIS for this (I assume there is one with the number of partition sequences we've been running into on the CnR OEIS post) – Stephen Jul 26 '17 at 14:03
• I think the last test case should be 8 – H.PWiz Jul 26 '17 at 14:12
• I agree with H.PWiz that the last testcase should be 8 instead of 7. – Erik the Outgolfer Jul 26 '17 at 14:19
• A008284 – miles Jul 26 '17 at 14:26

# Pyth, 97 6 bytes

-1 byte thanks to Erik the Outgolfer!

/lM./E


Try it online!

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

# 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 p0(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.

# Jelly, 6 bytes

œċS€ċ⁸


Try it online!

• Ah ha, of course! – Jonathan Allan Jul 26 '17 at 14:31

# Python 2, 615551 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!

• This breaks on the last test case of 10, 3. Too much recursion – jkelm Jul 26 '17 at 14:18
• (n>0and k>0) -> n>0<k – Erik the Outgolfer Jul 26 '17 at 14:19
• Also you can do +(n==k) instead of [0,1][n==k]. – Erik the Outgolfer Jul 26 '17 at 14:23
• You don't need the space in or +. – Erik the Outgolfer Jul 26 '17 at 14:26
• 50 bytes, replace n>0<k and with n*k>0and – Mr. Xcoder Jul 26 '17 at 14:46

# 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

• Of course. I knew there was a builtin. – Matthew Roh Jul 26 '17 at 14:17
• A Mathematica Simplified port would save a 13 bytes here I believe (Length->Len1 and IntegerPartitions -> Int7 – Jonathan Allan Jul 26 '17 at 14:44
• @JonathanAllan I'm actually making a super-short version of this. Hopefully I can finish it by the end of the month – JungHwan Min Jul 26 '17 at 16:50

# JavaScript (ES6), 4240 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>

# 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

• Honestly I'm surprised MATL doesn't have an "integer partition" builtin or something. – Erik the Outgolfer Jul 26 '17 at 14:25
• @Sanchises It should be working now. Thanks for telling me! – Luis Mendo Jul 26 '17 at 19:14
• No problem. I was just playing with it to understand your method (which is generally easier for small cases) when I ran into the error. – Sanchises Jul 26 '17 at 20:22

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


Try it online!

n&0=0^n
n&k=sum$map(&(k-1))[n-1,n-k-1..0]  Try it online! An alternate recurrence. # 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! # Jelly, 13 bytes I have a feeling know this basic approach won't be the golfiest! RŒṖL€€Ṣ€QṀ€=S  Try it online! • Yeah it isn't (see my Jelly answer at the far bottom). – Erik the Outgolfer Jul 26 '17 at 14:29 • Oh no Code bowling – Matthew Roh Jul 26 '17 at 14:30 • @EriktheOutgolfer If it works why is it deleted? – Jonathan Allan Jul 26 '17 at 14:30 • @Jonathan refresh – Matthew Roh Jul 26 '17 at 14:31 • @JonathanAllan It was deleted before a test case was fixed. – Erik the Outgolfer Jul 26 '17 at 14:32 # 05AB1E, 9 bytes L²ã€{ÙO¹¢  Try it online! # CJam, 18 bytes {_,:)@m*:$_&::+e=}


Try it online!

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

# 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!

# C (gcc), 41 bytes

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


Try it online!

# 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.