|
%I #90 Oct 15 2023 09:26:31
%S 1,1,1,2,2,4,5,8,10,16,20,31,39,55,71,100,125,173,218,291,366,483,600,
%T 784,971,1244,1538,1957,2395,3023,3693,4605,5604,6942,8397,10347,
%U 12471,15235,18309,22267,26619,32219,38414,46216,54941,65838,77958,93076,109908
%N Number of complete partitions of n.
%C A partition of n is complete if every number 1 to n can be represented as a sum of parts of the partition. This generalizes perfect partitions, where the representation for each number must be unique.
%C A partition is complete iff each part is no more than 1 more than the sum of all smaller parts. (This includes the smallest part, which thus must be 1.) - _Franklin T. Adams-Watters_, Mar 22 2007
%C For n > 0: a(n) = sum of n-th row in A261036 and also a(floor(n/2)) = A261036(n,floor((n+1)/2). - _Reinhard Zumkeller_, Aug 08 2015
%C a(n+1) is the number of partitions of n such that each part is no more than 2 more than the sum of all smaller parts (generalizing Adams-Watters's criterion). Bijection: each partition counted by a(n+1) must contain a 1, removing that gives a desired partition of n. - _Brian Hopkins_, May 16 2017
%C A partition (x_1, ..., x_k) is complete if and only if 1, x_1, ..., x_k is a "regular sequence" (see A003513 for definition). As a result, the number of complete partitions with n parts is given by A003513(n+1). - _Nathaniel Johnston_, Jun 29 2023
%H Alois P. Heinz, <a href="/A126796/b126796.txt">Table of n, a(n) for n = 0..10000</a> (first 301 terms from David W. Wilson)
%H George E. Andrews, George Beck, and Brian Hopkins, <a href="https://doi.org/10.1007/s00026-019-00476-1">On a Conjecture of Hanna Connecting Distinct Part and Complete Partitions</a>, Annals of Comb., 24(2020), pp. 217-224.
%H George Beck and Shane Chern, <a href="https://arxiv.org/abs/2108.04363">Reciprocity between partitions and compositions</a>, arXiv:2108.04363 [math.CO], 2021.
%H Nathaniel Johnston and Sarah Plosker, <a href="https://arxiv.org/abs/2308.15611">Laplacian {-1,0,1}- and {-1,1}-diagonalizable graphs</a>, arXiv:2308.15611 [math.CO], 2023.
%H SeungKyung Park, <a href="http://www.fq.math.ca/Scanned/36-4/park.pdf">Complete Partitions</a>, Fibonacci Quarterly, Vol. 36 (1998), pp. 354-360.
%F G.f.: 1 = Sum_{n>=0} a(n)*x^n*Product_{k=1..n+1} (1-x^k). - _Paul D. Hanna_, Mar 08 2012
%F a(n) ~ exp(Pi*sqrt(2*n/3)) / (4*sqrt(3)*n) * (1 - (sqrt(3/2)/Pi + 25*Pi/(24*sqrt(6))) / sqrt(n) + (25/16 - 1679*Pi^2/6912)/n). - _Vaclav Kotesovec_, May 24 2018, extended Nov 02 2019
%F a(n) = A000041(n) - A365924(n). - _Gus Wiseman_, Oct 14 2023
%e There are a(5) = 4 complete partitions of 5:
%e [1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 2, 2], and [1, 1, 3].
%e G.f.: 1 = 1*(1-x) + 1*x*(1-x)*(1-x^2) + 1*x^2*(1-x)*(1-x^2)*(1-x^3) + 2*x^3*(1-x)*(1-x^2)*(1-x^3)*(1-x^4) + 2*x^4*(1-x)*(1-x^2)*(1-x^3)*(1-x^4)*(1-x^5) + ...
%e From _Gus Wiseman_, Oct 14 2023: (Start)
%e The a(1) = 1 through a(8) = 10 partitions:
%e (1) (11) (21) (211) (221) (321) (421) (3221)
%e (111) (1111) (311) (2211) (2221) (3311)
%e (2111) (3111) (3211) (4211)
%e (11111) (21111) (4111) (22211)
%e (111111) (22111) (32111)
%e (31111) (41111)
%e (211111) (221111)
%e (1111111) (311111)
%e (2111111)
%e (11111111)
%e (End)
%p isCompl := proc(p,n) local m,pers,reps,f,lst,s; reps := {}; pers := combinat[permute](p); for m from 1 to nops(pers) do lst := op(m,pers); for f from 1 to nops(lst) do s := add( op(i,lst),i=1..f); reps := reps union {s}; od; od; for m from 1 to n do if not m in reps then RETURN(false); fi; od; RETURN(true); end: A126796 := proc(n) local prts, res,p; prts := combinat[partition](n); res :=0; for p from 1 to nops(prts) do if isCompl(op(p,prts),n) then res := res+1; fi; od; RETURN(res); end: for n from 1 to 40 do printf("%d %d ",n,A126796(n)); od; # _R. J. Mathar_, Feb 27 2007
%p # At the beginning of the 2nd Maple program replace the current 15 by any other positive integer n in order to obtain a(n). - _Emeric Deutsch_, Mar 04 2007
%p with(combinat): a:=proc(n) local P,b,k,p,S,j: P:=partition(n): b:=0: for k from 1 to numbpart(n) do p:=powerset(P[k]): S:={}: for j from 1 to nops(p) do S:=S union {add(p[j][i],i=1..nops(p[j]))} od: if nops(S)=n+1 then b:=b+1 else b:=b: fi: od: end: seq(a(n),n=1..30); # _Emeric Deutsch_, Mar 04 2007
%p with(combinat): n:=15: P:=partition(n): b:=0: for k from 1 to numbpart(n) do p:=powerset(P[k]): S:={}: for j from 1 to nops(p) do S:=S union {add(p[j][i],i=1..nops(p[j]))} od: if nops(S)=n+1 then b:=b+1 else b:=b: fi: od: b; # _Emeric Deutsch_, Mar 04 2007
%t T[n_, k_] := T[n, k] = If[k <= 1, 1, If[n < 2k-1, T[n, Floor[(n+1)/2]], T[n, k-1] + T[n-k, k]]];
%t a[n_] := T[n, Floor[(n+1)/2]];
%t Table[a[n], {n, 0, 50}] (* _Jean-François Alcover_, Apr 11 2017, after _Franklin T. Adams-Watters_ *)
%t nmz[y_]:=Complement[Range[Total[y]], Total/@Subsets[y]]; Table[Length[Select[IntegerPartitions[n], nmz[#]=={}&]],{n,0,15}] (* _Gus Wiseman_, Oct 14 2023 *)
%o (PARI) {T(n,k)=if(k<=1,1,if(n<2*k-1,T(n,floor((n+1)/2)),T(n,k-1)+T(n-k,k)))}
%o {a(n)=T(n,floor((n+1)/2))} /* If modified to save earlier results, this would be efficient. */ /* _Franklin T. Adams-Watters_, Mar 22 2007 */
%o (PARI) /* As coefficients in g.f.: */
%o {a(n)=local(A=[1,1]);for(i=1,n+1,A=concat(A,0);A[#A]=polcoeff(1-sum(m=1,#A,A[m]*x^m*prod(k=1,m,1-x^k +x*O(x^#A))),#A) );A[n+1]}
%o for(n=0,50,print1(a(n),",")) /* _Paul D. Hanna_, Mar 06 2012 */
%o (Haskell)
%o import Data.MemoCombinators (memo3, integral, Memo)
%o a126796 n = a126796_list !! n
%o a126796_list = map (pMemo 1 1) [0..] where
%o pMemo = memo3 integral integral integral p
%o p _ _ 0 = 1
%o p s k m
%o | k > min m s = 0
%o | otherwise = pMemo (s + k) k (m - k) + pMemo s (k + 1) m
%o -- _Reinhard Zumkeller_, Aug 07 2015
%Y Cf. A002033, A003513, A209405, A261036, A286929, A286097.
%Y For parts instead of sums we have A000009 (sc. coverings), ranks A055932.
%Y The strict case is A188431, complement A365831.
%Y These partitions have ranks A325781.
%Y First column k = 0 of A365923.
%Y The complement is counted by A365924, ranks A365830.
%Y Cf. A000041, A018818, A046663, A047967, A276024, A304792, A325799, A365543, A365658, A365918, A365921.
%K nonn,nice
%O 0,4
%A _Brian Hopkins_, Feb 20 2007
%E More terms from _R. J. Mathar_, Feb 27 2007
%E More terms from _Emeric Deutsch_, Mar 04 2007
%E Further terms from _Franklin T. Adams-Watters_ and _David W. Wilson_, Mar 22 2007
|
