A000802 - OEIS

%I #40 Nov 19 2024 11:46:23

%S 1,2,4,7,11,19,34,50,82,146,274,529,785,1297,2321,4369,8465,16657,

%T 33041,65809,131344,196880,327952,590096,1114384,2162960,4260112,

%U 8454416,16843024,33620240,67174672,134283536,268501264,536936720,1073807632,2147549456,4295033104

%N Maximal number of states in the minimal deterministic finite automaton accepting a language over a binary alphabet consisting of some words of length n.

%H John Cerkan, <a href="/A000802/b000802.txt">Table of n, a(n) for n = 0..3300</a>

%H J.-M. Champarnaud and J.-E. Pin, <a href="http://dx.doi.org/10.1016/0166-218X(89)90037-1">A maxmin problem on finite automata</a>, Discrete Appl. Math. 23 (1989), no. 1, 91-96.

%F a(n) = Sum_{k=0..n} min(2^k,2^(2^(n-k))-1). - _Sean A. Irvine_, Jun 24 2011

%p a:= n-> add((t-> `if`(t>k, 2^k, 2^t-1))(2^(n-k)), k=0..n):

%p seq(a(n), n=0..36);  # _Alois P. Heinz_, Apr 13 2022

%t a[n_] := Sum[Function[t, If[t > k, 2^k, 2^t-1]][2^(n-k)], {k, 0, n}];

%t Table[a[n], {n, 0, 36}] (* _Jean-François Alcover_, Nov 19 2024, after _Alois P. Heinz_ *)

%o (PARI) a(n) = sum(k=0, n, min(2^k,2^(2^(n-k))-1)) \\ (works while n<29) _Michel Marcus_, May 25 2013

%K nonn

%O 0,2

%A _Jeffrey Shallit_

%E a(34)-a(36) from _Sean A. Irvine_, Jun 23 2011