Restricted Integer Partitions

Question

P_k(n) means the number 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

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

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 4

Jelly, 6 bytes

œċS€ċ⁸

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

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 7

Haskell, 41 bytes

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

Try it online!

Answer 8

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 9

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 10

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 11

05AB1E, 5 bytes

ÅœIùg

Try it online or verify all test cases.

Explanation:

Ŝ     # Get all lists of positive integers that sum to the first (implicit) 
       # input-integer `n`
   ù   # Only keep the lists with a length equal to
  I    # the second input-integer `k`
    g  # Pop and push the length to get the amount of remaining lists
       # (which is output implicitly as result)

Answer 12

C (gcc), 41 40 bytes

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

Try it online!

Answer 13

Jelly, 13 bytes

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

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

Try it online!

Answer 14

05AB1E, 9 bytes

L²ã€{ÙO¹¢

Try it online!

Answer 15

CJam, 18 bytes

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

Try it online!

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

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.

Answer 17

Scala, 98 bytes

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

k and n are the parameters of my recursive function f.

def f(n:Int,k:Int):Int={(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 18

Vyxal, 5 bytes

ṄvL=∑

Try it Online!

Jelly, 5 bytes

ŒṗẈ=S

Try it online!

Dang it, ninja'd by Kevin because I took the time to get the shortest jelly answer too :p

Exact same approach as the 05ab1e answer, derived independently - both answers get the integer partitions of the first input and then count the number of partitions where the length equals the second input.

Answer 19

Regex 🐇 (Perl/PCRE+(?^=)^RME), 32 28 bytes

^((?^=(\2?x))(\1|^x)x*)+,\2$

Try it on replit.com (RegexMathEngine)

Takes its input in unary, as the lengths of two strings of xs delimited by a ,, specifying \$(n,k)\$. Returns its output as the number of ways the regex can match. (The rabbit emoji indicates this output method. It can yield outputs bigger than the input, and is really good at multiplying.)

This simply enumerates all the partitions. In order to count unordered partitions, it enforces that partitions occur in strictly nondecreasing order. This is accomplished by starting with an arbitrary-sized partition on the first iteration, then increasing it by an arbitrary nonnegative integer on each subsequent iteration. Each iteration increments the counter, which is then compared with \$k\$ at the end.

On each iteration, the size of the partition (arbitrarily chosen) is captured in \1, which is accessed via a nested backreference. The counter is stored in \2. Lookinto is used to ensure there is room to read and increment \2 on each iteration.

^                   # tail = N
(                   # \1 = the following, looping:
    (?^=            # Lookinto; tail = N
        (           # \2 = sum of the following:
            \2?     # previous value of \2 if set, else 0
            x       # 1
        )
    )
    # \1 = the sum of the below items
    (
        \1          # On subsequent iterations, \1
    |
        ^x          # On the first iteration, 1
    )
    x*              # any nonnegative integer
    # \1 = some of the above items
)+                  # Iterate the above as many times as possible, min 1
,                   # Assert tail == 0; tail = K
\2$                 # Assert tail == \2

This uses nested backreferences (supported by Java / Perl / PCRE / .NET), a branch reset group (Perl / PCRE / Python^regex), and a lookinto, a feature just added to RegexMathEngine. The parameterless form of it, (?^=pattern), is equivalent to one of the common uses of variable-length lookbehind, (?<=(?=pattern)^.*) – it allows matching against the entire string, even after the top-level cursor has advanced past the start. It also has a parametrized form, e.g. (?^5=pattern) will match pattern against the current contents of \5.

Regex 🐇 (RME / Perl / PCRE2 _^v10.35+), 36 34 bytes

^((?|(?=.*,(\2x))\1x*|^(x)+))+,\2$

Try it on replit.com (RegexMathEngine)
Try it online! - Perl v5.28.2 / Attempt This Online! - Perl v5.36+
Attempt This Online! - PCRE2 v10.40+
Attempt This Online! - PCRE2 v10.40+ - test cases only

Without lookinto, there's still always room within \$k\$, accesible via lookahead, to count iterations.

Starting with a positive arbitrary-sized partition on the first iteration is done by ^(x)+, which also initializes the counter to \$1\$. On subsequent iterations, \1x* advances by the sum of \1 and any arbitrary nonnegative integer, which also gets captured in \1. At the end, , asserts that the cumulative sum is equal to \$n\$.

To enforce \$k\$ as the number of partitions, it starts by setting \2 \$=1\$ on the first iteration with ^(x)+. On subsequent iterations, (?^=(\2x)) increments \2 by \$1\$. Lookahead is used to avoid not having room for \2\$+1\$ when nearing the end of \$n\$. The Branch Reset Group (?|...|...) allows \2 to be captured/recaptured in these two places.

^                   # tail = N
(                   # \1 = the following, looping:
    (?|             # Branch Reset Group
        # This alternative can only match on iterations after the first, because
        # it unconditionally matches \1 and \2.
        (?=         # Lookahead
            .*,     # tail = K
            (\2x)   # \2 += 1
        )
        \1x*        # \1 += {any nonnegative integer}; tail -= \1
    |
        ^           # Anchor to start, to only match on the first iteration.
        (x)+        # \2 = 1; \1 = {any nonnegative integer}; tail -= \1
    )
)+                  # Iterate the above as many times as possible, min 1
,                   # Assert tail == 0; tail = K
\2$                 # Assert tail == \2

Regex 🐇 (RME / Perl / PCRE2), 50 bytes

^((?=(?(3)(\3)))((?|(?=.*,(\4x))\2x*|^(x)+)))+,\4$

Try it on replit.com (RegexMathEngine)
Try it online! - Perl v5.28.2 / Attempt This Online! - Perl v5.36+
Try it online! - PCRE2 v10.33 / Attempt This Online! - PCRE2 v10.40+
Attempt This Online! - PCRE2 v10.40+ - test cases only

PCRE1, and PCRE2 up to v10.34, automatically makes any capture group atomic if it contains a nested backreference. To work around this, the capture is copied back and forth between \2 and \3 using only forward-declared backreferences.

This would also make the regex compatible with Python^regex and Ruby, but they have no way of doing 🐇 output without source code modifications.

It still doesn't work under PCRE1, probably due to its bug where in certain conditions, captures are not reverted to their earlier values when backtracking: Try it online!

^                      # tail = N
(                      # \1 = the following, looping:
    (?=
        (?(3)(\3))     # If \3 is set, \2 = \3, else leave \2 unset
    )
    (                  # \3 = the following, to avoid a nested backreference
        (?|            # Branch Reset Group
            # This alternative can only match on iterations after the first,
            # because it unconditionally matches \1 and \2.
            (?=
                .*,    # tail = K
                (\4x)  # \4 += 1
            )
            \2x*       # \3 = \2 + {any nonnegative integer}; tail -= \3
        |
            ^          # Anchor to start, to only match on the first iteration.
            (x)+       # \4 = 1; \3 = {any nonnegative integer}; tail -= \3
        )
    )
)+                     # Iterate the above as many times as possible, min 1
,                      # Assert tail == 0; tail = K
\4$                    # Assert tail == \4