login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A108917 Number of knapsack partitions of n. 173
1, 1, 2, 3, 4, 6, 7, 11, 12, 17, 19, 29, 25, 41, 41, 58, 56, 84, 75, 117, 99, 149, 140, 211, 172, 259, 237, 334, 292, 434, 348, 547, 465, 664, 588, 836, 681, 1014, 873, 1243, 1039, 1502, 1224, 1822, 1507, 2094, 1810, 2605, 2118, 3038, 2516 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

A knapsack partition is a partition such that for every integer there is at most one way to write it as a sum of a subset of the parts of the partition.

Equivalently, a knapsack partition of n is a multiset of positive integers summing to n such that every distinct submultiset has a different sum. - Gus Wiseman, Oct 03 2015

LINKS

Vladimir A. Shlyk, Table of n, a(n) for n=0..165 [Terms 51 through 165 were computed by V. A. Shlyk and A. S. Vroublevski with sporadic use of the Polymake program, May 20 2012]

R. Ehrenborg and M. Readdy, The Mobius function of partitions with restricted block sizes, Advances in Applied Mathematics, Volume 39, Issue 3, September 2007, Pages 283-292.

Vladimir A. Shlyk, Number of Vertices of the Polytope of Integer Partitions and Factorization of the Partitioned Number, arXiv:1805.07989 [math.CO], 2018.

EXAMPLE

a(4) = 4, since there are 5 partitions of 4 (see sequence A000041) and the partition 211 is the only partition of these that is not knapsack since 2=1+1.

The a(5) = 6 knapsack partitions of 5 are {{5},{3,2},{4,1},{2,2,1},{3,1,1},{1,1,1,1,1}}.

MAPLE

g:= proc(n, k) option remember;

# list of pairs [multiset, generator] of knapsack partitions of n with max part k

local res, i, p, p2;

if k = 1 then return [[[n], add(x^i, i=0..n)]] fi;

res:= NULL;

for i from 0 to floor(n/k) do

  for p in procname(n-k*i, k-1) do

     p2:= p[2]*add(x^(k*j), j=0..i);

     if max(coeffs(expand(p2))) <= 1 then

        res:= res, [[op(p[1]), i], p2]

     fi

  od

od;

[res];

end proc:

1, seq(nops(g(n, n)), n=1..60); # Robert Israel, Oct 04 2015

MATHEMATICA

ksQ[ptn_] := UnsameQ @@ Plus @@@ Union[Subsets[ptn]];

ksAll[n_Integer] :=

  ksAll[n] =

   If[n <= 0, {},

    With[{loe = Array[ksAll, n - 1, 1, Join]},

     Union[{{n}},

      Select[Sort[Append[#, n - Plus @@ #], Greater] & /@ loe, ksQ]]]];

ksAll[5](*example*)

Array[Length[ksAll[#]] &, 20](*sequence*) (* Gus Wiseman, Oct 02 2015 *)

CROSSREFS

Cf. A000041, A275972 (strict knapsack partitions).

Sequence in context: A036470 A111243 A203898 * A237667 A325769 A226538

Adjacent sequences:  A108914 A108915 A108916 * A108918 A108919 A108920

KEYWORD

nonn

AUTHOR

Richard Ehrenborg, Jul 20 2005

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 19 00:03 EDT 2021. Contains 343098 sequences. (Running on oeis4.)