A269343 - OEIS

%I #17 Sep 29 2016 10:09:35

%S 2,3,18,3672,24910877376,7729246189105080794275923648000,

%T 230877401507888187121306798555325965236859153667020902009451728482501547497913534258396672000

%N Sequence that describes an infinite directed graph representing all of the combinations of a two-input logic gate from two starting inputs.

%C This sequence is part of a family of sequences defined by:

%C a(n) = g*( a(n-1)*(a(n-1)-1)/2 ) * ( 1 + g*(Sum_{k=0..n-1} a(k)) ), a(0) = h;

%C where h indicates the starting number of nodes and g represents how many different logic gates (nodes) will compare each pair of nodes.

%C This particular sequence follows g=1, h=2.

%C This sequence originated from exploring g=2, h=3 when I was working on the "three NOTs problem" (the task to design a logic circuit that outputs three complements with only two NOT gates)

%F a(n) = ( a(n-1)*(a(n-1)-1)/2 ) * ( 1 + (Sum_{k=0..n-1} a(k)) ), a(0) = 2.

%e The first term a(0) = 2 represents the two starting nodes.

%e The second term a(1) = 3 (and all terms after) are formed by two parts:

%e [1] the comparison of the two inputs in a(0) yields one node in a(1) (as an AND gate comparing two signals),

%e [2] the comparisons of the one node in a(1) (placed by the first step) with the two nodes in a(0) (all previous nodes) yield two more nodes that are then added to the one node in a(1) giving a(1) = 1 + 2 = 3.

%e The third term a(2) = 18 is formed the same way:

%e [1] the comparison of all nodes in a(1) yields three nodes to be placed in a(2),

%e [2] the comparisons of these three nodes with each of the nodes in a(1) and a(0) yields 3*5 = 15 nodes which are then added to the nodes already in a(2) giving a(2) = 3 + 15 = 18.

%e This compound construction of terms was used to ensure that the logic circuit that is represented by this sequence doesn't contain any duplicate comparisons of the same nodes.

%K nonn

%O 0,1

%A _M Stefan Walker_, Feb 25 2016