Hypercube elements

Question

Write a function or program that outputs the number of each type of element (vertex, edge, face, etc.) of an N-dimensional hypercube.

As an example, the 3 dimensional cube has 1 cell (i.e. 1 3-dimensional cube), 6 faces (i.e. 6 2-dimensional cubes), 12 edges (i.e. 12 2-dimensional cubes) and 8 vertices (i.e. 8 0-dimensional cubes).

More details about Hypercube elements can be found here

You can as well take a look at the following OEIS sequence.

Input

Your code will take as input (via STDIN or a function parameter or similar things) an integer greater or equal to 0, which is the dimension of the hypercube.

Your code has to theoretically work for any input >= 0, disregarding memory and time issues (that is, speed and potential stack overflows are not a problem for your answer if the input is big). Inputs given as test cases will not be above 12.

Output

You will ouput a list of all elements of the hypercube, starting with the "highest dimension" element. For example, for a cube (input = 3), you will output the list [1,6,12,8] (1 cell, 6 faces, 12 edges, 8 vertices).

The format of the list in the output is relatively free, as long as it looks like a list.

You can output the result to STDOUT or return it from a function.

Test cases

Input = 0
Output = [1]

Input = 1
Output = [1,2]

Input = 3
Output = [1,6,12,8]

Input = 10
Output = [1, 20, 180, 960, 3360, 8064, 13440, 15360, 11520, 5120, 1024]

Input = 12
Output = [1, 24, 264, 1760, 7920, 25344, 59136, 101376, 126720, 112640, 67584, 24576, 4096]

Scoring

This is code-golf, so the shortest answer in bytes wins.

Answer 1

J, 13 bytes

[:p.2&^;$&_.5

Inspired by @alephalpha's PARI/GP answer. Try it online with J.js.

Background

By the binomial theorem,

Thus, the output for input n consist precisely of the coefficients of the above polynomial.

Code

[:p.2&^;$&_.5  Monadic verb. Argument: n

        $&_.5  Yield an array of n instances of -0.5.
    2&^        Compute 2^n.
       ;       Link the results to the left and right.
               This specifies a polynomial of n roots (all -0.5)
               with leading term 2^n.  
[:p.           Convert from roots to coefficients.

Answer 2

Samau, 8 5 bytes

Saved 3 bytes thanks to Dennis.

▌2\$ⁿ

Hex dump (Samau uses CP737 encoding):

dd 32 2f 24 fc

Explanation:

▌        read a number
 2\      push the array [1 2]
   $     swap
    ⁿ    take the convolution power

Convolving two vectors is equivalent to multiplying two polynomials. Similarly, taking the n-th convolution power is equivalent to taking the n-th power of a polynomial.

Answer 3

MATL, 8 bytes

1i:"2:X+

Inspired by @alephalpha's PARI/GP answer.

Try it online! (uses Y+ for modern day MATL)

How it works

1        % Push 1.
 i:      % Push [1 ... input].
   "     % Begin for-each loop:
    2:   %   Push [1 2].
      X+ %   Take the convolution product of the bottom-most stack item and [1 2].

Answer 4

MATL, 12 bytes

Q:q"H@^G@Xn*

Try it online

Explanation

         % implicit: input number "n"
Q:q      % generate array[0,1,...,n]
"        % for each element "m" from that array
  H@^    % compute 2^m
  G      % push n
  @      % push m
  Xn     % compute n choose m
  *      % multiply
         % implicit: close loop and display stack contents

Answer 5

Mathematica, 29 bytes

CoefficientList[(1+2x)^#,x]&

My first Mathematica answer! This is a pure function that uses the same approach as Alephalpha's PARI/GP answer. We construct the polynomial (1+2x)^n and get the list of coefficients, listed in order of ascending power (i.e. constant first).

Example usage:

> F := CoefficientList[(1+2x)^#,x]&`
> F[10]
{1,20,180,960,3360,8064,13440,15360,11520,5120,1024}

Answer 6

APL, 15 11 bytes

1,(2*⍳)×⍳!⊢

This is a monadic function train that accepts an integer on the right and returns an integer array.

Explanation, calling the input n:

        ⍳!⊢  ⍝ Get n choose m for each m from 1 to n
       ×     ⍝ Multiply elementwise by
  (2*⍳)      ⍝ 2^m for m from 1 to n
1,           ⍝ Tack 1 onto the front to cover the m=0 case

Try it online

Saved 4 bytes thanks to Dennis!

Answer 7

PARI/GP, 20 15 bytes

n->Vec((x+2)^n)

Answer 8

Jelly, 8 bytes

0rð2*×c@

I should really stop writing Jelly on my phone.

0r            Helper link. Input is n, inclusive range from 0 to n. Call the result r.
  ð           Start a new, dyadic link. Input is r, n.
   2*         Vectorized 2 to the power of r
     ×c@      Vectorized multiply by n nCr r. @ switches argument order.

Try it here.

Answer 9

TI-BASIC, 10 bytes

3^Ansbinompdf(Ans,2/3

Answer 10

CJam (17 14 bytes)

ri_3@#_2+@#\b`

Online demo

This approach uses the ordinary generating function (x + 2)^n. The OEIS mentions (2x + 1)^n, but this question indexes the coefficients in the opposite order. I'm kicking myself for not thinking to reverse the g.f. until I saw Alephalpha's update to the PARI/GP answer which did the same.

The interesting trick in this answer is to use integer powers for the polynomial power operation by operating in a base higher than any possible coefficient. In general, given a polynomial p(x) whose coefficients are all non-negative integers less than b, p(b) is a base-b representation of the coefficients (because the individual monomials don't "overlap"). Clearly (x + 2)^n will have coefficients which are positive integers and which sum to 3^n, so each of them will individually be less than 3^n.

ri     e# Read an integer n from stdin
_3@#   e# Push 3^n to the stack
_2+    e# Duplicate and add 2, giving a base-3^n representation of x+2
@#     e# Raise to the power of n
\b`    e# Convert into a vector of base-3^n digits and format for output

---

Alternative approaches: at 17 bytes

1a{0X$2f*+.+}ri*`

Online demo

or

1a{0X$+_]:.+}ri*`

Online demo

both work by summing the previous row with an offset-and-doubled row (in a similar style to the standard manual construction of Pascal's triangle).

A "direct" approach using Cartesian powers (as opposed to integer powers) for the polynomial power operation, comes in at 24 bytes:

2,rim*{1b_0a*2@#+}%z1fb`

where the map is, unusually, complicated enough that it's shorter to use % than f:

2,rim*1fb_0af*2@f#.+z1fb`

Answer 11

ES6, 71 bytes

n=>[...Array(n+1)].fill(n).map(b=(n,i)=>!i?1:i>n?0:b(--n,i-1)*2+b(n,i))

Simple recursive formula. Each hypercube is created by moving the previous hypercube 1 unit through the Nth dimension. This means that the M-dimensional objects are duplicated at the start and end of the unit, but also the (M-1)-dimensional objects gain an extra dimension, turning into M-dimensional objects. In other words, c(n, m) = c(n - 1, m) * 2 + c(n - 1, m - 1). (The actual submission reverses the parameters so that the formula outputs in the desired order.)

Ingeniously, fill allows map to provide the correct arguments to the recursive function, saving me 6 bytes.

Answer 12

05AB1E, 9 bytes

Code:

WƒNoZNc*,

Explanation:

W          # Push input and store in Z
 ƒ         # For N in range(0, input + 1)
  No       # Compute 2**N
    ZNc    # Compute Z nCr N
       *   # Multiply
        ,  # Pop and print

Uses CP-1252 encoding.

Answer 13

Pyth, 10 9 bytes

.<L.cQdhQ

Uses the nCr algorithm everyone seems to be using.

Answer 14

Octave, 31 bytes

Use the formula from A013609: T(n,k) = 2^k*binomial(n,k).

Try it online!

f=@(n)bincoeff(n,0:n).*2.^(0:n)

Answer 15

Julia, 31 bytes

n->[2^m*binomial(n,m)for m=0:n]

This is a lambda function that accepts an integer and returns an integer array. To call it, assign it to a variable.

For each m from 0 to the input n, we count the number of (n-m)-dimensional hypercubes on the boundary of the parent n-dimensional hypercube. Using the formula on Wikipedia, it's simply 2^m * choose(n, m). The case of m = 0 refers to the n-cube itself, so the output begins with 1 regardless of the input. Edges are given by m = n, vertices by m = n - 1, etc.

Answer 16

J, 11 bytes

(,+2*,~)&0#

Attempt This Online!

(,+2*,~)&0#
          #    constant 1
(      )&0     inner function bound to 0 on the right, repeated n times to 1...
 ,               append 0
   2*,~          prepend 0, and then double each number
  +              elementwise add the two

J, 12 bytes

1|.@p.@;$&_2

A minor variation of Dennis's J solution. Attempt This Online!

(!~*2^])i.,]

A minor variation of Alex A's APL solution. Attempt This Online!

1|.@p.@;$&_2
1      ;$&_2    create an array (1; -2 -2 ... -2)
    p.          construct a polynomial having that many -2s as roots
 |.             reverse it

(!~*2^])i.,]
        i.,]    create an array 0, 1, 2, ..., n
    2^]         2^0, 2^1, ..., 2^n
 !~             nC0, nC1, ..., nCn
   *            elementwise multiply

Answer 17

Ruby, Rev B 57 bytes

->n{a=[1]+[0]*n
(n*n).downto(n){|i|a[1+j=i%n]+=2*a[j]}
a}

The previous rev only scanned through the used part of the array each time. This rev scans through the entire array on every iteration. This is slower, but it saves bytes. A further byte is saved by using 1 loop to do the job of 2.

Ruby, Rev A 61 bytes

->n{a=[1]+[0]*n
n.times{|i|i.downto(0){|j|a[j+1]+=2*a[j]}}
a}

Starts with a point and iteratively creates the next dimension

In each iteration, each existing element increases in dimensionality and generates 2 new elements of its original dimensionality. For example, for a square in the horizontal plane that is extended vertically to become a cube:

The 1 face becomes a cube and generates 1 pair of faces (1 above, 1 below)

The 4 edges become faces and generate 4 pairs of edges (4 above, 4 below)

The 4 vertices become edges and generate 4 pairs of vertices (4 above, 4 below)

Ungolfed in test program

f=->n{a=[1]+[0]*n                  #make an array with the inital point and space for other dimensions
  n.times{|i|                      #iteratively expand dimension by dimension 
    i.downto(0){|j|a[j+1]+=2*a[j]} #iterating downwards (to avoid interferences) add the 2 new elements generated by each existing element.
  }
a}                                 #return the array

p f[gets.to_i]

Answer 18

JavaScript (Node.js), 44 bytes

f=n=>n?[...f(n-1),i=0].map(v=>i*2+(i=v)):[1]

Try it online!

# JavaScript (Node.js), 51 bytes

f=n=>n?[0,...f(n-1)].map((v,i,e)=>~~e[++i]+v*2):[1]

Try it online!

binomial(n,m)*2^m