Skip to main content
Bounty Awarded with 200 reputation awarded by Adám
deleted 396 characters in body
Source Link
Bubbler
  • 79.3k
  • 5
  • 162
  • 484

APL (Dyalog Extended), 2020 18 bytes

,(×⌿⍤(×⌿!∘⊂⌹⍥↑⊢⊂⍛\)⌹⊢!⍨\⊢)⍳⍤+ 

Try it online!Try it online!

A tacit dyadic function that takes m and n as left and right arguments respectively. Mainly uses the matrix division built-in to solve the linear equations:

$$ \begin{bmatrix} \binom{1}{1} & \binom{1}{2} & \cdots & \binom{1}{n+m} \\ \binom{2}{1} & \binom{2}{2} & \cdots & \binom{2}{n+m} \\ \vdots & \vdots & \ddots & \vdots \\ \binom{n+m}{1} & \binom{n+m}{2} & \cdots & \binom{n+m}{n+m} \end{bmatrix} \begin{bmatrix} a_1 \\ a_2 \\ \vdots \\ a_{n+m} \end{bmatrix} = \begin{bmatrix} \binom{1}{n} \binom{1}{m} \\ \binom{2}{n} \binom{2}{m} \\ \vdots \\ \binom{n+m}{n} \binom{n+m}{m} \end{bmatrix} \Leftrightarrow Ba = v $$

When \$ B \$ and \$ v \$ are ready, the answer is simply v⌹B. So the main work is to golf the parts to build \$ B \$ and \$ v \$.

How it works

,(×⌿⍤(×⌿!∘⊂⌹⍥↑⊢⊂⍛\)⌹⊢!⍨\⊢)⍳⍤+ ⍝ Left argument: n, Right argument: m ,(  )⍳⍤+ ⍝ Pass [n m] and [1 .. n+m] to the inner function   ⊢⊂⍛!!⍨\⊢ ⍝ Compute the nested array version of B ×⌿⍤(×⌿!∘⊂ \) ⍝ Compute the nested array version of v   ⍥↑  ⍝ Convert both sides to proper matrix/vector   ⍝ Solve the linear equation 

Computing \$ B \$

x!y computes \$ \binom{y}{x} \$.

⊢⊂⍛!!⍨\⊢ ⍝ Left: [n m], Right: [1 .. n+m] ⊢ ⊢ ⍝ Use right argument for both sides (L, R)  ⊂⍛ !⍨\EncloseOuter L,product soby entireflipped Lbinomial:  is mapped to each element of R  For each !pair of l∊L and Computer∊R, binomialcompute r!l or lCr 

The result is a vector of vectors that looks like \$ (\binom{1}{1}, \binom{1}{2}, \cdots, \binom{1}{n+m}), (\binom{2}{1}, \binom{2}{2}, \cdots, \binom{2}{n+m}), \cdots \$. When is applied, each inner vector becomes a row of the matrix \$ B \$.

Computing \$ v \$

×⌿⍤×⌿!∘⊂\ ⍝ Left: [n m], Right: [1 .. n+m]   ∘⊂ ⍝ Enclose right !\  Outer product Computeby binomial  function  ⍝ Result is length-2a nestedmatrix vectorof two rows [U V] ×⌿⍤ ×⌿ ⍝ Reduce by multiply; compute U×V element-wise 

APL (Dyalog Extended), 20 bytes

,(×⌿⍤!∘⊂⌹⍥↑⊢⊂⍛!)⍳⍤+ 

Try it online!

A tacit dyadic function that takes m and n as left and right arguments respectively. Mainly uses the matrix division built-in to solve the linear equations:

$$ \begin{bmatrix} \binom{1}{1} & \binom{1}{2} & \cdots & \binom{1}{n+m} \\ \binom{2}{1} & \binom{2}{2} & \cdots & \binom{2}{n+m} \\ \vdots & \vdots & \ddots & \vdots \\ \binom{n+m}{1} & \binom{n+m}{2} & \cdots & \binom{n+m}{n+m} \end{bmatrix} \begin{bmatrix} a_1 \\ a_2 \\ \vdots \\ a_{n+m} \end{bmatrix} = \begin{bmatrix} \binom{1}{n} \binom{1}{m} \\ \binom{2}{n} \binom{2}{m} \\ \vdots \\ \binom{n+m}{n} \binom{n+m}{m} \end{bmatrix} \Leftrightarrow Ba = v $$

When \$ B \$ and \$ v \$ are ready, the answer is simply v⌹B. So the main work is to golf the parts to build \$ B \$ and \$ v \$.

How it works

,(×⌿⍤!∘⊂⌹⍥↑⊢⊂⍛!)⍳⍤+ ⍝ Left argument: n, Right argument: m ,(  )⍳⍤+ ⍝ Pass [n m] and [1 .. n+m] to the inner function   ⊢⊂⍛!⊢ ⍝ Compute the nested array version of B ×⌿⍤!∘⊂  ⍝ Compute the nested array version of v   ⍥↑  ⍝ Convert both sides to proper matrix/vector   ⍝ Solve the linear equation 

Computing \$ B \$

x!y computes \$ \binom{y}{x} \$.

⊢⊂⍛!⊢ ⍝ Left: [n m], Right: [1 .. n+m] ⊢ ⊢ ⍝ Use right argument for both sides (L, R)  ⊂⍛Enclose L, so entire L is mapped to each element of R  !  Compute binomial 

The result is a vector of vectors that looks like \$ (\binom{1}{1}, \binom{1}{2}, \cdots, \binom{1}{n+m}), (\binom{2}{1}, \binom{2}{2}, \cdots, \binom{2}{n+m}), \cdots \$. When is applied, each inner vector becomes a row of the matrix \$ B \$.

Computing \$ v \$

×⌿⍤!∘⊂ ⍝ Left: [n m], Right: [1 .. n+m]   ∘⊂ ⍝ Enclose right !  Compute binomial  ⍝ Result is length-2 nested vector [U V] ×⌿⍤  ⍝ Reduce by multiply; compute U×V element-wise 

APL (Dyalog Extended), 20 18 bytes

,((×⌿!\)⌹⊢!⍨\⊢)⍳⍤+ 

Try it online!

A tacit dyadic function that takes m and n as left and right arguments respectively. Mainly uses the matrix division built-in to solve the linear equations:

$$ \begin{bmatrix} \binom{1}{1} & \binom{1}{2} & \cdots & \binom{1}{n+m} \\ \binom{2}{1} & \binom{2}{2} & \cdots & \binom{2}{n+m} \\ \vdots & \vdots & \ddots & \vdots \\ \binom{n+m}{1} & \binom{n+m}{2} & \cdots & \binom{n+m}{n+m} \end{bmatrix} \begin{bmatrix} a_1 \\ a_2 \\ \vdots \\ a_{n+m} \end{bmatrix} = \begin{bmatrix} \binom{1}{n} \binom{1}{m} \\ \binom{2}{n} \binom{2}{m} \\ \vdots \\ \binom{n+m}{n} \binom{n+m}{m} \end{bmatrix} \Leftrightarrow Ba = v $$

When \$ B \$ and \$ v \$ are ready, the answer is simply v⌹B. So the main work is to golf the parts to build \$ B \$ and \$ v \$.

How it works

,((×⌿!\)⌹⊢!⍨\⊢)⍳⍤+ ⍝ Left argument: n, Right argument: m ,( )⍳⍤+ ⍝ Pass [n m] and [1 .. n+m] to the inner function ⊢!⍨\⊢ ⍝ Compute B (×⌿!\) ⍝ Compute v ⌹ ⍝ Solve the linear equation 

Computing \$ B \$

x!y computes \$ \binom{y}{x} \$.

!⍨\⊢ ⍝ Left: [n m], Right: [1 .. n+m] ⊢ ⊢ ⍝ Use right argument for both sides (L, R) !⍨\Outer product by flipped binomial:   For each pair of l∊L and r∊R, compute r!l or lCr 

Computing \$ v \$

×⌿!\ ⍝ Left: [n m], Right: [1 .. n+m] !\  Outer product by binomial function  ⍝ Result is a matrix of two rows [U V] ×⌿ ⍝ Reduce by multiply; compute U×V element-wise 
Source Link
Bubbler
  • 79.3k
  • 5
  • 162
  • 484

APL (Dyalog Extended), 20 bytes

,(×⌿⍤!∘⊂⌹⍥↑⊢⊂⍛!⊢)⍳⍤+ 

Try it online!

A tacit dyadic function that takes m and n as left and right arguments respectively. Mainly uses the matrix division built-in to solve the linear equations:

$$ \begin{bmatrix} \binom{1}{1} & \binom{1}{2} & \cdots & \binom{1}{n+m} \\ \binom{2}{1} & \binom{2}{2} & \cdots & \binom{2}{n+m} \\ \vdots & \vdots & \ddots & \vdots \\ \binom{n+m}{1} & \binom{n+m}{2} & \cdots & \binom{n+m}{n+m} \end{bmatrix} \begin{bmatrix} a_1 \\ a_2 \\ \vdots \\ a_{n+m} \end{bmatrix} = \begin{bmatrix} \binom{1}{n} \binom{1}{m} \\ \binom{2}{n} \binom{2}{m} \\ \vdots \\ \binom{n+m}{n} \binom{n+m}{m} \end{bmatrix} \Leftrightarrow Ba = v $$

When \$ B \$ and \$ v \$ are ready, the answer is simply v⌹B. So the main work is to golf the parts to build \$ B \$ and \$ v \$.

How it works

,(×⌿⍤!∘⊂⌹⍥↑⊢⊂⍛!⊢)⍳⍤+ ⍝ Left argument: n, Right argument: m ,( )⍳⍤+ ⍝ Pass [n m] and [1 .. n+m] to the inner function ⊢⊂⍛!⊢ ⍝ Compute the nested array version of B ×⌿⍤!∘⊂ ⍝ Compute the nested array version of v ⍥↑ ⍝ Convert both sides to proper matrix/vector ⌹ ⍝ Solve the linear equation 

Computing \$ B \$

x!y computes \$ \binom{y}{x} \$.

⊢⊂⍛!⊢ ⍝ Left: [n m], Right: [1 .. n+m] ⊢ ⊢ ⍝ Use right argument for both sides (L, R) ⊂⍛ ⍝ Enclose L, so entire L is mapped to each element of R ! ⍝ Compute binomial 

The result is a vector of vectors that looks like \$ (\binom{1}{1}, \binom{1}{2}, \cdots, \binom{1}{n+m}), (\binom{2}{1}, \binom{2}{2}, \cdots, \binom{2}{n+m}), \cdots \$. When is applied, each inner vector becomes a row of the matrix \$ B \$.

Computing \$ v \$

×⌿⍤!∘⊂ ⍝ Left: [n m], Right: [1 .. n+m] ∘⊂ ⍝ Enclose right ! ⍝ Compute binomial ⍝ Result is length-2 nested vector [U V] ×⌿⍤ ⍝ Reduce by multiply; compute U×V element-wise