login
Number of length n words on alphabet {0,1,2,3} which contain all 16 of the 2-letter strings of the alphabet.
1

%I #13 Jun 18 2014 21:37:20

%S 331776,5806080,69672960,675578880,5675235840,42832800000,

%T 297267224832,1927826369280,11821052680704,69152452363584,

%U 388663047288576,2110540207741632,11123834480487936,57120835559901696,286669843226634240,1409843999618778240,6809949521252980992

%N Number of length n words on alphabet {0,1,2,3} which contain all 16 of the 2-letter strings of the alphabet.

%C The expected wait time to see all 16 2-letter subwords is: 3401981586663184695807274256173879732908913569174615510479814304735002007 *1982900192550576041 / (2^3 *3^3 *5^3 *11^2 *13^2 *17 *19 *23 *29 *31 *37 *41 *43 *47 *53 *59 *61 *67 *71 *73 *79 *83 *89 *97 *101 *103 *107 *113 *127 *131 *137 *139 *149 *151 *157 *163 *167 *173 *179 *191 *199 *211 *223 *227 *239 *251) (approximately 55.0688).

%H Alois P. Heinz, <a href="/A244044/b244044.txt">Table of n, a(n) for n = 17..150</a>

%p b:= proc(n, t, s) option remember; `if`(s={}, 4^n, `if`(nops(s)>n,

%p 0, add(b(n-1, j, s minus {4*t+j}), j=0..3)))

%p end:

%p a:= n-> 4*b(n-1, 0, {$0..15}):

%p seq(a(n), n=17..25); # _Alois P. Heinz_, Jun 18 2014

%t abcd=Solve[{aa==uaa(z^2+z(aa+ab+ac+ad)), ab==uab(z^2+z(ba+bb+bc+bd)), ac==uac(z^2+z(ca+cb+cc+cd)),ad==uad(z^2+z(da+db+dc+dd)),ba==uba(z^2+z(aa+ab+ac+ad)), bb==ubb(z^2+z(ba+bb+bc+bd)),bc==ubc(z^2+z(ca+cb+cc+cd)),bd==ubd(z^2+z(da+db+dc+dd)), ca==uca(z^2+z(aa+ab+ac+ad)),cb==ucb(z^2+z(ba+bb+bc+bd)),cc==ucc(z^2+z(ca+cb+cc+cd)), cd==ucd(z^2+z(da+db+dc+dd)),da==uda(z^2+z(aa+ab+ac+ad)),db==udb(z^2+z(ba+bb+bc+bd)), dc==udc(z^2+z(ca+cb+cc+cd)),dd==udd(z^2+z(da+db+dc+dd))},{aa,ab,ac,ad,ba,bb,bc,bd,ca,cb,cc,cd,da,db,dc,dd}];

%t fz[uaa_,uab_,uac_,uad_,uba_,ubb_,ubc_,ubd_,uca_,ucb_,ucc_,ucd_,uda_,udb_,udc_,udd_] =aa+ab+ac+ad+ba+bb+bc+bd+ca+cb+cc+cd+da+db+dc+dd/.abcd//Simplify;

%t t=Map[Total[Map[Apply[fz,#]&,#]]&,Table[Select[Tuples[{0,1},16],Count[#,0]==n&],{n,0,16}]];

%t nn=35;Drop[Flatten[CoefficientList[Series[Sum[(-1)^(i+1)t[[i]],{i,1,16}],{z,0,nn}],z]],17]

%Y Cf. A243862.

%K nonn

%O 17,1

%A Edward Williams and _Geoffrey Critzer_, Jun 17 2014