Movatterモバイル変換

0,4

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.

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

For n > 0: a(n) = sum of n-th row inA261036 and also a(floor(n/2)) =A261036(n,floor((n+1)/2)). -Reinhard Zumkeller, Aug 08 2015

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

A partition (x_1, ..., x_k) is complete if and only if 1, x_1, ..., x_k is a "regular sequence" (seeA003513 for definition). As a result, the number of complete partitions with n parts is given byA003513(n+1). -Nathaniel Johnston, Jun 29 2023

Alois P. Heinz,Table of n, a(n) for n = 0..10000 (first 301 terms from David W. Wilson)

George E. Andrews, George Beck, and Brian Hopkins,On a Conjecture of Hanna Connecting Distinct Part and Complete Partitions, Annals of Comb., 24(2020), pp. 217-224.

George Beck and Shane Chern,Reciprocity between partitions and compositions, arXiv:2108.04363 [math.CO], 2021.

Nathaniel Johnston and Sarah Plosker,Laplacian {-1,0,1}- and {-1,1}-diagonalizable graphs, arXiv:2308.15611 [math.CO], 2023.

SeungKyung Park,Complete Partitions, Fibonacci Quarterly, Vol. 36 (1998), pp. 354-360.

G.f.: 1 = Sum_{n>=0} a(n)*x^n*Product_{k=1..n+1} (1-x^k). -Paul D. Hanna, Mar 08 2012

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

a(n) =A000041(n) -A365924(n). -Gus Wiseman, Oct 14 2023

There are a(5) = 4 complete partitions of 5:

[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 2, 2], and [1, 1, 3].

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) + ...

FromGus Wiseman, Oct 14 2023: (Start)

The a(1) = 1 through a(8) = 10 partitions:

(1) (11) (21) (211) (221) (321) (421) (3221)

(111) (1111) (311) (2211) (2221) (3311)

(2111) (3111) (3211) (4211)

(11111) (21111) (4111) (22211)

(111111) (22111) (32111)

(31111) (41111)

(211111) (221111)

(1111111) (311111)

(2111111)

(11111111)

(End)

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

# 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

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

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[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]]];

a[n_] := T[n, Floor[(n+1)/2]];

Table[a[n], {n, 0, 50}] (*Jean-François Alcover, Apr 11 2017, afterFranklin T. Adams-Watters *)

nmz[y_]:=Complement[Range[Total[y]], Total/@Subsets[y]]; Table[Length[Select[IntegerPartitions[n], nmz[#]=={}&]], {n, 0, 15}] (*Gus Wiseman, Oct 14 2023 *)

(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)))}

{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 */

(PARI) /* As coefficients in g.f.: */

{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]}

for(n=0, 50, print1(a(n), ", ")) /*Paul D. Hanna, Mar 06 2012 */

(Haskell)

import Data.MemoCombinators (memo3, integral, Memo)

a126796 n = a126796_list !! n

a126796_list = map (pMemo 1 1) [0..] where

pMemo = memo3 integral integral integral p

p _ _ 0 = 1

p s k m

| k > min m s = 0

| otherwise = pMemo (s + k) k (m - k) + pMemo s (k + 1) m

--Reinhard Zumkeller, Aug 07 2015

Cf.A002033,A003513,A209405,A261036,A286929,A286097.

For parts instead of sums we haveA000009 (sc. coverings), ranksA055932.

The strict case isA188431, complementA365831.

These partitions have ranksA325781.

First column k = 0 ofA365923.

The complement is counted byA365924, ranksA365830.

Cf.A000041,A018818,A046663,A047967,A276024,A304792,A325799,A365543,A365658,A365918,A365921.

Sequence in context:A240486A237871A027193 *A325831A240451A206138

Adjacent sequences:A126793A126794A126795 *A126797A126798A126799

nonn,nice

Brian Hopkins, Feb 20 2007

More terms fromR. J. Mathar, Feb 27 2007

More terms fromEmeric Deutsch, Mar 04 2007

Further terms fromFranklin T. Adams-Watters andDavid W. Wilson, Mar 22 2007

approved