login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A126796 Number of complete partitions of n. 10
1, 1, 1, 2, 2, 4, 5, 8, 10, 16, 20, 31, 39, 55, 71, 100, 125, 173, 218, 291, 366, 483, 600, 784, 971, 1244, 1538, 1957, 2395, 3023, 3693, 4605, 5604, 6942, 8397, 10347, 12471, 15235, 18309, 22267, 26619, 32219, 38414, 46216, 54941, 65838 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

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 in A261036 and also a(floor(n/2))=A261036(n,floor((n+1)/2). - Reinhard Zumkeller, Aug 08 2015

LINKS

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

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

FORMULA

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

EXAMPLE

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

MAPLE

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

PROG

(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

CROSSREFS

Cf. A002033, A188431, A209405.

Cf. A261036.

Sequence in context: A240486 A237871 A027193 * A240451 A206138 A241545

Adjacent sequences:  A126793 A126794 A126795 * A126797 A126798 A126799

KEYWORD

nonn

AUTHOR

Brian Hopkins, Feb 20 2007

EXTENSIONS

More terms from R. J. Mathar, Feb 27 2007

More terms from Emeric Deutsch, Mar 04 2007

Further terms from Franklin T. Adams-Watters and David W. Wilson, Mar 22 2007

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 25 15:14 EDT 2017. Contains 284082 sequences.