login
Length of longest chain of nonempty proper subsemigroups of the symmetric inverse monoid.
4

%I #30 May 16 2016 03:05:09

%S 1,6,25,116,722,5956,59243,667500,8296060,112406158,1648441865,

%T 26016230581,439698829588,7923291500266,151636272041063,

%U 3071397457222772,65637064987470128,1475783903907314842,34822081020977308581,860290584362463964031,22206678791494395506940,597775158911764084886982,16751152450234618859184419,487867395080603697285978385,14745549219503008426659528806

%N Length of longest chain of nonempty proper subsemigroups of the symmetric inverse monoid.

%H Gheorghe Coserea, <a href="/A227914/b227914.txt">Table of n, a(n) for n = 1..200</a>

%H P. J. Cameron, M. Gadouleau, J. D. Mitchell, Y. Peresse, <a href="http://arxiv.org/abs/1501.06394">Chains of subsemigroups</a>, arXiv preprint arXiv:1501.06394 [math.GR], 2015.

%H O. Ganyushkin and I. Livinsky, <a href="http://www.mathnet.ru/links/b418d2ec0c8ec6acf4ff400ce89e9105/adm129.pdf">Length of the inverse symmetric semigroup</a>, Algebra Discrete Math., 12 (2011) 64-71.

%t a[ n_] := Sum[ Binomial[ n, k] (Ceiling[3 k/2] - Total[IntegerDigits[ k, 2]] + 1) + Binomial[ Binomial[ n, k], 2] k! - 1, {k, n}]; (* _Michael Somos_, Feb 25 2014 *)

%o (PARI)

%o A007238(n) = ceil(3*n/2) - hammingweight(n) - 1;

%o a(n) = { sum(i = 1, n+1, my(Ni = binomial(n, i-1));

%o Ni * (A007238(i-1) + 2) + Ni*(Ni-1)/2 * (i-1)! - 1) };

%o vector(25, n, a(n)) \\ _Gheorghe Coserea_, May 15 2016

%Y Cf. A007238.

%K nonn

%O 1,2

%A _James Mitchell_, Oct 13 2013