23
\$\begingroup\$

Challenge

Given a positive integer \$n\$, count the number of \$n\times n\$ binary matrices (i.e. whose entries are \$0\$ or \$1\$) with exactly two \$1\$'s in each rows and two \$1\$'s in each column.

Here are a few examples of valid matrices for \$n=4\$:

1100        1100        1100        
1100        0011        0110        
0011        1100        0011        
0011        0011        1001        

And here are a few invalid matrices:

1100
0011
0111    <-- three 1's in this row
1100
 ^
 `--- three 1's in this column
1111    <-- four 1's in this row
0011
1100
0000    <-- zero 1's in this row

This sequence is catalogued on OEIS as A001499. Here are a few non-bruteforce ways to compute it (\$a_n\$ denotes the number of valid \$n\times n\$ binary matrices).

  • The recursive formula $$ 2a_n-2n(n-1)a_{n-1}-n(n-1)^2a_{n-2}=0 $$ with base cases \$a_1=0\$, \$a_2=1\$.
  • The explicit formula $$ a_n=\frac{(n!)^2}{4^n}\sum_{i=0}^n\frac{(-2)^i(2n-2i)!}{i!((n-i)!)^2}. $$

You may find other ways to compute this sequence on the OEIS page linked above. To be clear, bruteforcing is a perfectly valid way of solving this challenge.

Rules

As usual in challenges, your task is to write a program/function which does one of the following (consistently across different inputs).

  • Take a positive integer \$n\$ as input and return \$a_n\$ as output. Because of the combinatorial interpretation of this sequence, it has to be \$1\$-indexed (i.e. you are not allowed to take \$n\$ and return \$a_{n+1}\$). If you choose this option, you are not required to handle the input \$n=0\$.
  • Take a positive integer \$n\$ as input and return the list \$[a_1,a_2,\ldots,a_n]\$ as output. Optionally, you may instead choose to return \$[a_0,a_1,\ldots,a_{n-1}]\$ or \$[a_0,a_1,\ldots,a_n]\$, where \$a_0=1\$ (consistent with the combinatorial interpretation). The choice has to be consistent across different inputs.
  • Take no input and return the infinite list/generator \$[a_1,a_2,a_3,\ldots]\$. Optionally, you may instead choose to return \$[a_0,a_1,a_2,\ldots]\$, where \$a_0=1\$.

Your program/function must theoretically work for arbitrarily large inputs, assuming infinite time, memory and integer/floating point precision. In practice, it's ok if if fails because of integer overflow and/or floating point errors.

Scoring

This is , so the shortest code in bytes wins.

Testcases

Input                     Output
 1                             0
 2                             1
 3                             6
 4                            90
 5                          2040
 6                         67950
 7                       3110940
 8                     187530840
 9                   14398171200
10                 1371785398200
11               158815387962000
12             21959547410077200
13           3574340599104475200
14         676508133623135814000
15      147320988741542099484000
\$\endgroup\$

19 Answers 19

16
\$\begingroup\$

J, 41 bytes

1#.*:=1#.2>[:>@~.@,[:+&,&.>/~i.@!<@A.=@i.

Try it online!

A different take on brute force, which handles up to n=6 on TIO.

Since the idea is more interesting than the J mechanics here, I'll explain that.

I could likely save bytes by translating one of the formulas into J, but that seemed less fun.

the idea

  • Generate all n! permutations of the identity matrix. Eg, for n=3:

    ┌─────┬─────┬─────┬─────┬─────┬─────┐
    │1 0 0│1 0 0│0 1 0│0 1 0│0 0 1│0 0 1│
    │0 1 0│0 0 1│1 0 0│0 0 1│1 0 0│0 1 0│
    │0 0 1│0 1 0│0 0 1│1 0 0│0 1 0│1 0 0│
    └─────┴─────┴─────┴─────┴─────┴─────┘
    
  • Create an "addition table" of this list with itself, using matrix addition:

    ┌─────┬─────┬─────┬─────┬─────┬─────┐
    │2 0 0│2 0 0│1 1 0│1 1 0│1 0 1│1 0 1│
    │0 2 0│0 1 1│1 1 0│0 1 1│1 1 0│0 2 0│
    │0 0 2│0 1 1│0 0 2│1 0 1│0 1 1│1 0 1│
    ├─────┼─────┼─────┼─────┼─────┼─────┤
    │2 0 0│2 0 0│1 1 0│1 1 0│1 0 1│1 0 1│
    │0 1 1│0 0 2│1 0 1│0 0 2│1 0 1│0 1 1│
    │0 1 1│0 2 0│0 1 1│1 1 0│0 2 0│1 1 0│
    ├─────┼─────┼─────┼─────┼─────┼─────┤
    │1 1 0│1 1 0│0 2 0│0 2 0│0 1 1│0 1 1│
    │1 1 0│1 0 1│2 0 0│1 0 1│2 0 0│1 1 0│
    │0 0 2│0 1 1│0 0 2│1 0 1│0 1 1│1 0 1│
    ├─────┼─────┼─────┼─────┼─────┼─────┤
    │1 1 0│1 1 0│0 2 0│0 2 0│0 1 1│0 1 1│
    │0 1 1│0 0 2│1 0 1│0 0 2│1 0 1│0 1 1│
    │1 0 1│1 1 0│1 0 1│2 0 0│1 1 0│2 0 0│
    ├─────┼─────┼─────┼─────┼─────┼─────┤
    │1 0 1│1 0 1│0 1 1│0 1 1│0 0 2│0 0 2│
    │1 1 0│1 0 1│2 0 0│1 0 1│2 0 0│1 1 0│
    │0 1 1│0 2 0│0 1 1│1 1 0│0 2 0│1 1 0│
    ├─────┼─────┼─────┼─────┼─────┼─────┤
    │1 0 1│1 0 1│0 1 1│0 1 1│0 0 2│0 0 2│
    │0 2 0│0 1 1│1 1 0│0 1 1│1 1 0│0 2 0│
    │1 0 1│1 1 0│1 0 1│2 0 0│1 1 0│2 0 0│
    └─────┴─────┴─────┴─────┴─────┴─────┘
    
  • Now we note that the valid items are simply those without a 2 anywhere:

    ┌─────┬─────┬─────┬─────┬─────┬─────┐
    │     │     │     │1 1 0│1 0 1│     │
    │     │     │     │0 1 1│1 1 0│     │
    │     │     │     │1 0 1│0 1 1│     │
    ├─────┼─────┼─────┼─────┼─────┼─────┤
    │     │     │1 1 0│     │     │1 0 1│
    │     │     │1 0 1│     │     │0 1 1│
    │     │     │0 1 1│     │     │1 1 0│
    ├─────┼─────┼─────┼─────┼─────┼─────┤
    │     │1 1 0│     │     │     │0 1 1│
    │     │1 0 1│     │     │     │1 1 0│
    │     │0 1 1│     │     │     │1 0 1│
    ├─────┼─────┼─────┼─────┼─────┼─────┤
    │1 1 0│     │     │     │0 1 1│     │
    │0 1 1│     │     │     │1 0 1│     │
    │1 0 1│     │     │     │1 1 0│     │
    ├─────┼─────┼─────┼─────┼─────┼─────┤
    │1 0 1│     │     │0 1 1│     │     │
    │1 1 0│     │     │1 0 1│     │     │
    │0 1 1│     │     │1 1 0│     │     │
    ├─────┼─────┼─────┼─────┼─────┼─────┤
    │     │1 0 1│0 1 1│     │     │     │
    │     │0 1 1│1 1 0│     │     │     │
    │     │1 1 0│1 0 1│     │     │     │
    └─────┴─────┴─────┴─────┴─────┴─────┘
    
  • But these are not necessarily unique. However, after removing dups, we have our answer, which is 6:

    ┌─────┬─────┬─────┬─────┬─────┬─────┐
    │     │     │     │1 1 0│1 0 1│     │
    │     │     │     │0 1 1│1 1 0│     │
    │     │     │     │1 0 1│0 1 1│     │
    ├─────┼─────┼─────┼─────┼─────┼─────┤
    │     │     │1 1 0│     │     │1 0 1│
    │     │     │1 0 1│     │     │0 1 1│
    │     │     │0 1 1│     │     │1 1 0│
    ├─────┼─────┼─────┼─────┼─────┼─────┤
    │     │     │     │     │     │0 1 1│
    │     │     │     │     │     │1 1 0│
    │     │     │     │     │     │1 0 1│
    ├─────┼─────┼─────┼─────┼─────┼─────┤
    │     │     │     │     │0 1 1│     │
    │     │     │     │     │1 0 1│     │
    │     │     │     │     │1 1 0│     │
    ├─────┼─────┼─────┼─────┼─────┼─────┤
    │     │     │     │     │     │     │
    │     │     │     │     │     │     │
    │     │     │     │     │     │     │
    ├─────┼─────┼─────┼─────┼─────┼─────┤
    │     │     │     │     │     │     │
    │     │     │     │     │     │     │
    │     │     │     │     │     │     │
    └─────┴─────┴─────┴─────┴─────┴─────┘
    
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Great answer! Instead of removing dups, could you also divide the number without \$2\$s in half and always get the correct answer? \$\endgroup\$
    – Noodle9
    May 16 at 12:06
  • 1
    \$\begingroup\$ Thanks. Actually, that wouldn't work because for higher numbers (eg, 4) there are repeated elements even among a single side of the diagonal in the matrix. Division by 2 gives you an upper bound though, since you'll always have symmetry across the diagonal. \$\endgroup\$
    – Jonah
    May 16 at 14:57
  • \$\begingroup\$ J903 adds implicit definitions, so you can write {{+-!y}} instead of +@-@!. Normally the overheard isn't worth it, but I think it might shorten your answer enough to be worthwhile here. \$\endgroup\$
    – Hovercouch
    May 17 at 4:29
  • \$\begingroup\$ Thanks, so basically 4 bytes rather than the usual 5 with 3 :''. I'll try reworking it tomorrow. Sadly TIO uses an older version of J, so it wouldn't work there, though it's still legal. \$\endgroup\$
    – Jonah
    May 17 at 4:35
9
\$\begingroup\$

JavaScript (ES6), 36 bytes

Returns the \$n\$th term of the sequence.

f=n=>--n<2?n:-~n*n*(f(n)+n*f(n-1)/2)

Try it online!

How?

We decrement \$n\$ right away in order to use the following 0-indexed form of the recursive formula:

  • \$a_n=n\$ for \$0\le n< 2\$
  • \$a_n=(n+1)\times n\times \left(a_{n-1}+\dfrac{n\times a_{n-2}}{2}\right)\$ for \$n\ge2\$
\$\endgroup\$
3
  • \$\begingroup\$ Impressive. The recursive formula, as written on the last line, is for $a_{n+1}$, right? Since you cannot mention --n on this line. \$\endgroup\$ May 16 at 19:50
  • \$\begingroup\$ @EricDuminil The formula was indeed off by 1. Thanks for catching this. \$\endgroup\$
    – Arnauld
    May 16 at 22:56
  • 2
    \$\begingroup\$ My pleasure. It's probably the first time I understood your answer. :D \$\endgroup\$ May 17 at 6:57
8
\$\begingroup\$

05AB1E, 17 12 bytes

1ÝλsN*;+NN>P

Try it online!

-4 thanks to @ovs, which allowed for another -1

Uses the recursive formula.

1Ý        0-based range from 1, pushes [0,1]
λ         recursive context
 s        swap the implicit a(n-1),a(n-2) to a(n-2),a(n-1)
 N*       n*a(n-2)
 ;        /2
 +        +a(n-1)
 NN>      n,(n+1)
 P        product of all elements in stack, (n*a(n-2)/2+a(n-1))*n*(n+1)
\$\endgroup\$
2
  • \$\begingroup\$ You don't need the closing } at the end. And pairing a(n-1) and a(n-2) and multiplying both with NN>* at once saves another byte: tio.run/##yy9OTMpM/f/f8PDcc7sfNcwK8vOz09JK8NOy1v7/HwA \$\endgroup\$
    – ovs
    May 15 at 11:31
  • \$\begingroup\$ And you can rewrite this using (a(n-2)*n/2+a(n-1))*n*(n+1): 13 bytes \$\endgroup\$
    – ovs
    May 15 at 11:38
5
\$\begingroup\$

Oasis, 16 12 14 13 11 bytes

àn*t+nn>**T

Try it online!

Uses the recursive formula, a port of the 05AB1E answer.

\$\endgroup\$
5
\$\begingroup\$

Jelly, 15 bytes

²Ø.ṗs€µ;Z§=2Ạ)S

Try it online!

A monadic link taking an integer and returning an integer. Brute forces it.

Explanation

²               | Squared
 Ø.ṗ            | [0,1] Cartesian power of this
    s€          | Split each of these into lists of the original argument in length
      µ         | Start a new monadic chain
             )  | For each of the possible matrices we’ve generated:
       ;Z       | - Append its transpose
         §      | - Sum each list
          =2    | - Equal to 2 (vectorises)
            Ạ   | - All true
              S | Finally, sum to find the number of matrices meeting the criteria

As an alternative, here’s an implementation of the recursive formula:

Jelly, 18 bytes

L,²H$בƲ×Fḣ2S;
Ç¡Ḋ

Try it online!

A full program that takes n via STDIN and returns the first n+1 terms in reverse order. I thought I should be able to shorten it by replacing \nÇ with µ but that’s not working.


Finally, a Jelly translation of @Jonah’s J answer:

Jelly, 15 bytes

=þ`Œ!+þ`ẎQ«Ƒ€1S

Try it online!

\$\endgroup\$
4
\$\begingroup\$

C (gcc), 45 41 bytes

f(n){n=n--<3?n:-~n*n*(f(n)+n*f(n-1)/2.);}

Try it online!

Inputs a positive integer \$n\$ and returns \$a_n\$.

\$\endgroup\$
4
\$\begingroup\$

Factor, 83 76 bytes

:: f ( n! -- m ) n 1 - n! n n 1 > [ n 1 + * n f n n 1 - f 2 / * + * ] when ;

Try it online!

-7 thanks to @Delfad0r

This is a translation of @Arnauld's excellent answer.

This is the first time I've submitted a Factor golf where it was shortest to make a named function. Recursion is so much shorter than other solutions that the mandatory function signature is worth it.

Here are some other solutions I tried first, which ended up being longer:

Brute force, 94 bytes

[ { 0 1 } swap '[ _ selections ] twice [ dup flip [ t [ sum 2 = and ] reduce ] both? ] count ]

Explicit formula, 98 bytes

[| n | n n! sq 4 n ^ / n [0,b] [| i | -2 i ^ 2 n * 2 i * - n! * i n! n i - n! sq * / ] map-sum * ]
\$\endgroup\$
2
  • \$\begingroup\$ I know absolutely nothing about Factor, but why not 76 bytes? \$\endgroup\$
    – Delfad0r
    May 15 at 15:23
  • \$\begingroup\$ @Delfad0r Thanks! \$\endgroup\$
    – chunes
    May 15 at 16:18
3
\$\begingroup\$

APL(Dyalog Extended), 32 bytes SBCS

{+/∧/¨(2=+/,+⌿)¨⍵ ⍵∘⍴¨↓⍉⊤⍳2*×⍨⍵}

Try it on APLgolf!

A dfn submission which takes a single input on the right.

Straight brute force which exceeds workspace size at n=5.

Uses ⎕IO←0 (0 indexing).

-4 bytes from ovs.

Explanation

{+/∧/¨(2=+/,+⌿)¨⍵ ⍵∘⍴¨↓⍉2⊤¯1+⍳2*×⍨⍵}
                                2*×⍨⍵ 2^(n**2)
                            ¯1+⍳        0-range
                          2⊤           convert to base 2 matrix
                        ⍉              transpose
                       ↓                convert to nested list
                ⍵ ⍵∘⍴¨                 reshape each vector to n x n matrix
      (2=+/,+⌿)¨                        2= sums of rows and cols?
   ∧/¨                                 check if all elements of each satisfy that condition
 +/                                    sum

\$\endgroup\$
1
  • \$\begingroup\$ In Extended 2 is the default left argument of . And is there a reason you didn't use ⎕IO←0? \$\endgroup\$
    – ovs
    May 15 at 11:51
3
\$\begingroup\$

Jelly, 15 bytes

⁼þⱮŒ!+þ`ẎḊỊÐṀQL

A monadic Link that accepts \$n\$ and yields \$a_n\$.

Try it online!

How?

Uses Jonah's idea from their J answer.

⁼þⱮŒ!+þ`ẎḊỊÐṀQL - Link: n
   Œ!           - all permutations (of implicit [1..n])
  Ɱ             - map with:
 þ              -   (implicit [1..n]) outer product (permutation) using:
⁼               -     equals?
       `        - use that as both arguments of:
      þ         -   outer product using:
     +          -     addition
        Ẏ       - tighten (to a list of matrices)
         Ḋ      - dequeue (makes the following still work when n=1)
           ÐṀ   - keep those which are maximal under:
          Ị     -   is insignificant (abs(x)<=1?)
             Q  - deduplicate
              L - length
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 49 36 bytes

⊞υ¹⊞υ⁰F⊖N⊞υ×÷×Lυ⊖Lυ²⁺⊗§υ±¹×⊖Lυ§υ±²Iυ

Try it online! Link is to verbose version of code. Outputs the terms a₀..aₙ. Explanation:

⊞υ¹⊞υ⁰F⊖N⊞υ×÷×Lυ⊖Lυ²⁺⊗§υ±¹×⊖Lυ§υ±²Iυ

Start with a₀ and a₁.

F⊖N

Input n and calculate n-1 more terms...

⊞υ×÷×Lυ⊖Lυ²⁺⊗§υ±¹×⊖Lυ§υ±²

... apply the recurrence relation to calculate the next term.

Iυ

Output all the terms.

\$\endgroup\$
6
  • \$\begingroup\$ Quite interesting that you chose the brute force method over the faster and cleaner formula. \$\endgroup\$ May 15 at 9:34
  • \$\begingroup\$ @StackMeter because Charcoal is more focused on ASCII art things, and its math functions are not so developed, so this is a better option \$\endgroup\$
    – wasif
    May 15 at 9:39
  • \$\begingroup\$ @StackMeter I don't have a factorial built-in or recursion, so I tried the brute-force method first. \$\endgroup\$
    – Neil
    May 15 at 9:39
  • 1
    \$\begingroup\$ @StackMeter The explicit formula comes out 10 bytes longer, and also requires floating-point arithmetic, which is unfortunate. \$\endgroup\$
    – Neil
    May 15 at 9:47
  • \$\begingroup\$ @StackMeter I was able to turn the recursive formula into a recurrence relation, thus reducing my byte count from 7² to 6². \$\endgroup\$
    – Neil
    May 15 at 10:00
2
\$\begingroup\$

MATLAB/Octave, 58 bytes

c=0
b=1
n=2;while k=n
n=n+1;
a=n*k*b+n*k*k*c/2
c=b;b=a;end

Use Octave Online to test it yourself! TIO seems to have problems with infinite nature of the script. It uses recursive formula and it's an infinite generator. The following results are printed to the console. It technically works forever but pretty fast falls into limits of floating precision and all new results are infinity. On MATLAB as I checked the results stay precise up to 13th element of the sequence. After that some floating precision errors appear and then they accumulate with each next element.
The scripts throws a warning due to while k=n but it continues to work. If needed to be avoided it can be replaced with while 1 and k=n in next line.

For MATLAB it is also possible to reduce length to 57 bytes with code like that:

c=0
b=1
for n=3:Inf
k=(n-1);a=n*k*b+n*k*k*c/2
c=b;b=a;end

But it doesn't work in Octave due to 3:Inf range.

\$\endgroup\$
2
\$\begingroup\$

Jelly, 15 bytes

’ÑH×+Ñ×ב
’¹ÇỊ?

Try it online!

Uses the recursive formula.

Explanation

’ÑH×+Ñ×ב Auxiliary monadic link, taking (n-1) as the argument
’         Decrement:
                (n-2)
 Ñ        Apply next link:
                a(n-2)
  H       Halve:
                a(n-2) / 2
   ×      Multiply by the argument:
                (n-1) a(n-2) / 2
    +     Add
     Ñ      the next link applied to the argument:
                (n-1) a(n-2) / 2 + a(n-1)
      ×   Multiply by the argument:
                (n-1) ((n-1) a(n-2) / 2 + a(n-1))
       ×  Multiply by
        ‘   the argument incremented:
                n (n-1) ((n-1) a(n-2) / 2 + a(n-1))

’¹ÇỊ? Main monadic link, taking n as the argument
’     Decrement: (n-1)
    ? If
   Ị    insignificant: |n-1| ≤ 1
      then
 ¹      identity: (n-1)
      else
  Ç     apply previous link
\$\endgroup\$
2
\$\begingroup\$

R, 52 bytes

f=function(n,k=n-1)"if"(n<3,k,n*k*(f(k)+f(n-2)*k/2))

Try it online!

Using formula from OEIS page: a(n) = n(n-1)/2 [ 2 a(n-1) + (n-1) a(n-2) ] (Bricard)

\$\endgroup\$
2
\$\begingroup\$

Brachylog, 20 bytes

~lṁ{{0|1}ᵐ²\,?+ᵐ=₂}ᶜ

Brute-force solution; times out on TIO with any input higher than 4. Try it online!

Explanation

~l                    Generate a list whose length equals the input
  ṁ                   That list is a square matrix
                      At this point, we have a matrix of indeterminate values
   {              }ᶜ  Count how many ways we can satisfy this predicate:
    {   }ᵐ²            For each value in the matrix:
     0|1                It is either 0 or 1
           \           Transpose the matrix
            ,?         Append the non-transposed version
                       We now have a list of all rows and all columns of the matrix
              +ᵐ       Sum each row/column
                =₂     All the results must equal 2
\$\endgroup\$
1
\$\begingroup\$

Pari/GP, 48 bytes

a(n)=if(n<2,n<1,(n^2-n)*(a(n-1)+(n-1)/2*a(n-2)))

Try it online!

Found it on the OEIS page, just golfed it a bit, uses Recursion

\$\endgroup\$
1
1
\$\begingroup\$

Python 3, 53 bytes

a=lambda n:n<1if n<2else~-n*n*(a(n-1)+(n-1)/2*a(n-2))

Try it online!

-2 thanks to @Neil

Recursive formula, for input 1 it should output False instead of 0

\$\endgroup\$
3
  • 1
    \$\begingroup\$ ~-n*n* is shorter than (n*n-n)*. \$\endgroup\$
    – Neil
    May 15 at 10:04
  • \$\begingroup\$ You can save another two by using ~-n not (n-1), and then another two by removing a= \$\endgroup\$
    – rak1507
    May 15 at 12:43
  • \$\begingroup\$ -1 byte \$\endgroup\$ May 15 at 16:17
1
\$\begingroup\$

Desmos, 51 bytes

a=n-i
f(n)=n!^2/4^n\sum_{i=0}^n(-2)^i(2a)!/(i!a!^2)

Try It On Desmos!

Try It On Desmos!(Prettified)

Desmos doesn't support recursion and has limited ability for loops, so I had to use the explicit formula: $$a_n=\frac{(n!)^2}{4^n}\sum_{i=0}^n\frac{(-2)^i(2n-2i)!}{i!((n-i)!)^2}$$

\$\endgroup\$
1
\$\begingroup\$

Ruby, 41 bytes

f=->n{(w=n*n-=1)<3?n:w*f[n]+w*n*f[n-1]/2}

Try it online!

Using the recursive formula

\$\endgroup\$
0
\$\begingroup\$

Python 3, 195 bytes

def f(n):
  if n<2:
    return 1
  return n*f(n-1)
def o(n):
  if n < 2:
    return 0
  p=0
  r=(f(n)**2)/4
  for i in range(n+1):
    p+=(-2)**i*f(2*n-2*i)/(f(i)*(f(n-i)**2))
  return int(p * r)

Try it online!

Pretty ungolfed, but hey, it's one of the first to use the standard formula, and it can handle up to 75.

\$\endgroup\$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.