login
a(n) = Bell(n+1) - 2^n + 1 + n, where Bell(i) is the i-th Bell number A000110(i).
0

%I #14 Apr 24 2018 14:54:52

%S 1,2,4,11,41,177,820,4020,20900,115473,677557,4211561,27640354,

%T 190891144,1382942176,10480109395,82864804285,682076675105,

%U 5832741942932,51724157711104,474869815108196,4506715736350193,44152005850890065,445958869286416705

%N a(n) = Bell(n+1) - 2^n + 1 + n, where Bell(i) is the i-th Bell number A000110(i).

%C a(n) is the solution to the following combinatorial problem. Given a set S of n labeled elements, find the number of all subsets of S (2^n) plus the number of partitions of any subset T of S into parts which are not all of size 1 nor of size |T|. This implies that a(n) = 2^n + Sum_{m=3..n} (Bell(m)-2) = Bell(n+1) - 2^n + 1 + n, using the standard recurrence for the Bell numbers (Comtet, Eq. (4a)). - _N. J. A. Sloane_, Nov 26 2013

%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 210.

%F Also a(n) = 2^n + Sum_{m=3..n} binomial(n,m)*(Bell(m)-2).

%p with(combinat); [seq(bell(n+1)-2^n+n+1,n=0..30)];

%t Table[BellB[n+1]-2^n+n+1,{n,0,30}] (* _Harvey P. Dale_, Apr 24 2018 *)

%Y Cf. A000110, A144646.

%K nonn

%O 0,2

%A _Jean-Yves Tallet_ and _N. J. A. Sloane_, Jan 24 2009