login
Cardinality of set of sets of parts of all partitions of n.
33

%I #56 Sep 14 2023 18:06:43

%S 1,1,2,3,5,6,10,12,18,22,30,37,51,61,79,96,124,148,186,222,275,326,

%T 400,473,575,673,811,946,1132,1317,1558,1813,2138,2463,2893,3323,3882,

%U 4461,5177,5917,6847,7818,8994,10251,11766,13334,15281,17309,19732,22307

%N Cardinality of set of sets of parts of all partitions of n.

%C Number of different values of A007947(m) when A056239(m) is equal to n.

%C From _Gus Wiseman_, Sep 11 2023: (Start)

%C Also the number of finite sets of positive integers that can be linearly combined using all positive coefficients to obtain n. For example, the a(1) = 1 through a(7) = 12 sets are:

%C {1} {1} {1} {1} {1} {1} {1}

%C {2} {3} {2} {5} {2} {7}

%C {1,2} {4} {1,2} {3} {1,2}

%C {1,2} {1,3} {6} {1,3}

%C {1,3} {1,4} {1,2} {1,4}

%C {2,3} {1,3} {1,5}

%C {1,4} {1,6}

%C {1,5} {2,3}

%C {2,4} {2,5}

%C {1,2,3} {3,4}

%C {1,2,3}

%C {1,2,4}

%C Cf. A365073, A365311, A365312, A365322, A365380.

%C (End)

%H Alois P. Heinz, <a href="/A088314/b088314.txt">Table of n, a(n) for n = 0..100</a>

%F a(n) = 2^(n-1) - A070880(n). - _Alois P. Heinz_, Feb 08 2019

%F a(n) = A365042(n) + 1. - _Gus Wiseman_, Sep 13 2023

%e The 7 partitions of 5 and their sets of parts are

%e [ #] partition set of parts

%e [ 1] [ 1 1 1 1 1 ] {1}

%e [ 2] [ 2 1 1 1 ] {1, 2}

%e [ 3] [ 2 2 1 ] {1, 2} (same as before)

%e [ 4] [ 3 1 1 ] {1, 3}

%e [ 5] [ 3 2 ] {2, 3}

%e [ 6] [ 4 1 ] {1, 4}

%e [ 7] [ 5 ] {5}

%e so we have a(5) = |{{1}, {1, 2}, {1, 3}, {2, 3}, {1, 4}, {5}}| = 6.

%p list2set := L -> {op(L)};

%p a:= N -> list2set(map( list2set, combinat[partition](N) ));

%p seq(nops(a(n)), n=0..30);

%p # Yogy Namara (yogy.namara(AT)gmail.com), Jan 13 2010

%p b:= proc(n, i) option remember; `if`(n=0, {{}}, `if`(i<1, {},

%p {b(n, i-1)[], seq(map(x->{x[],i}, b(n-i*j, i-1))[], j=1..n/i)}))

%p end:

%p a:= n-> nops(b(n, n)):

%p seq(a(n), n=0..40);

%p # _Alois P. Heinz_, Aug 09 2012

%t Table[Length[Union[Map[Union,IntegerPartitions[n]]]],{n,1,30}] (* _Geoffrey Critzer_, Feb 19 2013 *)

%t (* Second program: *)

%t b[n_, i_] := b[n, i] = If[n == 0, {{}}, If[i < 1, {},

%t Union@Flatten@{b[n, i - 1], Table[If[Head[#] == List,

%t Append[#, i]]& /@ b[n - i*j, i - 1], {j, 1, n/i}]}]];

%t a[n_] := Length[b[n, n]];

%t a /@ Range[0, 40] (* _Jean-François Alcover_, Jun 04 2021, after _Alois P. Heinz_ *)

%t combp[n_,y_]:=With[{s=Table[{k,i},{k,y}, {i,1,Floor[n/k]}]}, Select[Tuples[s], Total[Times@@@#]==n&]];

%t Table[Length[Select[Join@@Array[IntegerPartitions,n], UnsameQ@@#&&combp[n,#]!={}&]], {n,0,15}] (* _Gus Wiseman_, Sep 11 2023 *)

%o (Haskell)

%o a066186 = sum . concat . ps 1 where

%o ps _ 0 = [[]]

%o ps i j = [t:ts | t <- [i..j], ts <- ps t (j - t)]

%o -- _Reinhard Zumkeller_, Jul 13 2013

%o (Python)

%o from sympy.utilities.iterables import partitions

%o def A088314(n): return len({tuple(sorted(set(p))) for p in partitions(n)}) # _Chai Wah Wu_, Sep 10 2023

%Y Cf. A182410.

%Y The complement in subsets of {1..n-1} is A070880(n) = A365045(n) - 1.

%Y The case of pairs is A365315, see also A365314, A365320, A365321.

%Y A116861 and A364916 count linear combinations of strict partitions.

%Y A179822 and A326080 count sum-closed subsets.

%Y A326083 and A124506 appear to count combination-free subsets.

%Y A364914 and A365046 count combination-full subsets.

%Y Cf. A000009, A007865, A088528, A088809, A093971, A326020, A364272, A364534, A365043, A364350.

%K easy,nonn

%O 0,3

%A _Naohiro Nomoto_, Nov 05 2003

%E More terms and clearer definition from _Vladeta Jovovic_, Apr 21 2005