A056823 Number of compositions minus number of partitions: A011782(n) - A000041(n).

0, 0, 0, 1, 3, 9, 21, 49, 106, 226, 470, 968, 1971, 3995, 8057, 16208, 32537, 65239, 130687, 261654, 523661, 1047784, 2096150, 4193049, 8387033, 16775258, 33551996, 67105854, 134214010, 268430891, 536865308, 1073734982, 2147475299, 4294957153, 8589922282

Offset: 0

Author

Alford Arnold, Aug 29 2000

Keywords

• easy
• nonn

Comments

Previous name was: Counts members of A056808 by number of factors.

A056808 relates to least prime signatures (cf. A025487)

a(n) is also the number of compositions of n that are not partitions of n. - Omar E. Pol, Jan 31 2009, Oct 14 2013

a(n) is the number of compositions of n into positive parts containing pattern [1,2]. - Bob Selcoe, Jul 08 2014

Examples

			A011782 begins     1 1 2 4 8 16 32 64 128 256 ...;
A000041 begins     1 1 2 3 5  7 11 15  22  30 ...;
so sequence begins 0 0 0 1 3  9 21 49 106 226 ... .
For n = 3 the factorizations are 8=2*2*2, 12=2*2*3, 18=2*3*3 and 30=2*3*5.
a(5) = 9: {[1,1,1,2], [1,1,2,1], [1,1,3], [1,2,1,1], [1,2,2], [1,3,1], [1,4], [2,1,2], [2,3]}. - _Bob Selcoe_, Jul 08 2014
		

Links

• Wikipedia, Permutation pattern
• Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

Crossrefs

Cf. A025487, A056808, A117989.

The version for patterns is A002051.

(1,2)-avoiding compositions are just partitions A000041.

The (1,1)-matching version is A261982.

The version for prime indices is A335447.

(1,2)-matching compositions are ranked by A335485.

Patterns matched by compositions are counted by A335456.

Cf. A011782, A056986, A106356, A144300, A238279, A269134, A333755.

Programs

Maple

a:= n-> ceil(2^(n-1))-combinat[numbpart](n):
seq(a(n), n=0..37);  # Alois P. Heinz, Jan 30 2020

Mathematica

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!GreaterEqual@@#&]],{n,0,10}] (* Gus Wiseman, Jun 24 2020 *)
a[n_] := If[n == 0, 0, 2^(n-1) - PartitionsP[n]];
a /@ Range[0, 37] (* Jean-François Alcover, May 23 2021 *)

Formula

a(n) = A011782(n) - A000041(n).

a(n) = 2*a(n-1) + A117989(n-1). - Bob Selcoe, Apr 11 2014

G.f.: (1 - x) / (1 - 2*x) - Product_{k>=1} 1 / (1 - x^k). - Ilya Gutkovskiy, Jan 30 2020

Extensions

More terms from James Sellers, Aug 31 2000

New name from Joerg Arndt, Sep 02 2013