# Challenge

Let's imagine an N-tuple of integers between 0 and M inclusive, and let's call it F.

There are (M + 1) ** N possible Fs in total.

How many such Fs satisfy all of the following inequalities (index is one-based)?

• F[n] + F[n+1] <= M for 1 <= n < N
• F[N] + F <= M

Write a program or function that takes two positive integers N and M and outputs the answer in any convenient form.

## Test Cases

(N,M) => Answer

(1,1) => 1
(2,1) => 3
(3,1) => 4
(4,1) => 7

(1,2) => 2
(2,2) => 6
(3,2) => 11
(4,2) => 26

(10,3) => 39175
(10,4) => 286555
(10,5) => 1508401

(25,3) => 303734663372
(25,4) => 43953707972058
(25,5) => 2794276977562073

(100,3) => 8510938110502117856062697655362747468175263710
(100,4) => 3732347514675901732382391725971022481763004479674972370
(100,5) => 60964611448369808046336702581873778457326750953325742021695001


## Explanation

M (max value of element) = 1

F + F <= 1; F = 
(1,1) => 1

F + F <= 1; F = [0,0], [0,1], [1,0]
(2,1) => 3

F = [0,0,0], [0,0,1], [0,1,0], [1,0,0]
(3,1) => 4

F = [0,0,0,0], [0,0,0,1], [0,0,1,0], [0,1,0,0], [0,1,0,1], [1,0,0,0], [1,0,1,0]
(4,1) => 7

---

M = 2

F + F <= 2; F = , 
(1,2) => 2

F = [0,0], [0,1], [0,2], [1,0], [1,1], [2,0]
(2,2) => 6

F = [0,0,0], [0,0,1], [0,0,2], [0,1,0], [0,1,1], [0,2,0], [1,0,0], [1,0,1],
[1,1,0], [1,1,1], [2,0,0]
(3,2) => 11

(4,2) => 26 (left as exercise for you)


# Rules

• This is a challenge. The time complexity of your code should be polynomial in M and N (e.g. you can't generate all (M + 1) ** N tuples and then check for the condition). Please explain your approach in your submission.
• Standard rules apply. The shortest answer in bytes wins.

# Python with numpy, 59 bytes

lambda M,N:trace(mat(tri(M+1)[::-1])**N)
from numpy import*


Try it online!

Uses matrix multiplication to count paths. If float precision is an issue, the mat could specify mat(...,int).

• Using mat(...,int) does not seem to work for the n=100 cases. The method is correct (using sympy to sum the powers of the roots of the characteristic polynomial does work, for example), but numpy goes wrong somewhere as the numbers increase (maybe it's the ** power operator?) – Jonathan Allan May 8 '18 at 2:14

# Pyth, 27 bytes

.N?Ys:RTtYh-QNgQ+NTs:Rdtszh


Demonstration

Expects input in the format:

M
N


This is classic dynamic programming, over the left end of the values set so far, the right end, and the current size of the gap.

How it works, in pseudocode/Python:

.N          | define memoized fill(left, right, gap):
?           | if cap > 0 then
s:RTtY      | sum(fill(i, right, gap - 1)
h-QN        |     for i in range(M - left + 1))
gQ+NT       | else M >= left + right
| output:
s:Rdtsz     | sum(fill(i, i, N - 1)
h           |     for i in range(M + 1))


Q is used for M, z is used for N, : is fill, N is left, T is right, Y is gap.

# MATL, 13 12 bytes

Q:&>~PiY^Xds


Try it online! This is a direct translation of xnor's Python answer and my first MATL answer, so it's most likely not optimal. E.g. there is likely a shorter way to get an upper-left triangular matrix of ones than t&lYRP. Edit: And it turns out there is, namely :&>~P. Thanks to Luis Mendo for -1 byte!

               M is the first input and N the second
Q:             increment M and generate range from 1 to M+1
&>           compare vector element wise with itself with greater-than function
results in a upper-right triangular matrix
~          inverse to get lower-left triangular matrix
P         flip rows to get upper-left triangular matrix
i        input N
Y^      take the matrix to the power of N
Xds   compute the sum of the main diagonal

• @LuisMendo Thanks! Though it's only one byte or is there something else which can be dropped? – Laikoni May 10 '18 at 14:16
• No, that's it, I can't count :-D – Luis Mendo May 10 '18 at 14:56

# Stax, 17 bytes

°(√&╒íÆ½╨⌂'├╖▼1_Z


Run and debug it

Unpacked, ungolfed, and commented, it looks like this.

^1](    [1, 0, ... 0] with M zeroes
:)      get all rotations of the array
{       begin block
{:+rm map each array to reverse(prefixSums(arr))
},v*    execute preceding block N-1 times
F       for each array, execute the rest of the program
iT    remove the last i elements from the array, where i is the iteration index
F+    add the remaining elements to the running total
implicitly print output


Run this one

# R, 72 bytes

function(M,N)sum(diag(Reduce(%*%,rep(list(outer(0:M,0:M,"+")<=M),N))))


Try it online!

Ports xnor's approach.

Fails for larger test cases as R only has 32-bit integer support (they get cast to double once the max int value is reached), so using gmp or another arbitrary precision arithmetic library would be required.

Strangely, R lacks a matrix power operator, as ^ always applies elementwise.

• Actually, there is a properly implemented %^% operator in package expm that would allow for -5 bytes, but unfortunately, it is not available on TIO (I had to test locally). – Kirill L. May 11 '18 at 10:36
• @KirillL. yeah, I had considered that but I think I'll stick with my base R response. Also you can golf that down to 60 bytes by not loading in the whole package: function(M,N)sum(diag(expm::%^%(outer(0:M,0:M,"+")<=M,N))) – Giuseppe May 11 '18 at 13:47

# APL (Dyalog Unicode), 31 25 bytes

+/1 1⍉+.×⍣(⎕-1)⍨⌽∘.≤⍨⍳1+⎕


Try it online!

A full program which takes N, then M as inputs.

Follows the same algorithm as xnor's Python solution.

-6 bytes from Bubbler.

• {x+.×⍵}⍣(...) → x+.×⍣(...), then x+.×⍣(...)⊢x←... → +.×⍣(...)⍨ to get 25 bytes. – Bubbler Feb 9 at 6:37
• Should've spotted that. Thanks! – Razetime Feb 9 at 7:51