Displaying 1-10 of 15 results found.
First differences of the binomial transform of the partition numbers ( A000041).
+10
30
1, 1, 3, 8, 21, 54, 137, 344, 856, 2113, 5179, 12614, 30548, 73595, 176455, 421215, 1001388, 2371678, 5597245, 13166069, 30873728, 72185937, 168313391, 391428622, 908058205, 2101629502, 4853215947, 11183551059, 25718677187, 59030344851, 135237134812, 309274516740
COMMENTS
a(n) = A103446(n) for n>=1; here a(0) is set to 1 in accordance with the definition and other important generating functions. Also the number of sequences of compositions ( A133494) with weakly decreasing lengths and total sum n. For example, the a(0) = 1 through a(3) = 8 sequences are: () ((1)) ((2)) ((3))
((11)) ((12))
((1)(1)) ((21))
((111))
((1)(2))
((2)(1))
((11)(1))
((1)(1)(1))
The case of constant lengths is A101509. The case of strictly decreasing lengths is A129519. The case of sequences of partitions is A141199. The case of twice-partitions is A358831. (End)
FORMULA
G.f.: Product_{n>=1} (1-x)^n / ((1-x)^n - x^n).
G.f.: Sum_{n>=0} x^n * (1-x)^(n*(n-1)/2) / Product_{k=1..n} ((1-x)^k - x^k).
G.f.: Sum_{n>=0} x^(n^2) * (1-x)^n / Product_{k=1..n} ((1-x)^k - x^k)^2.
G.f.: exp( Sum_{n>=1} x^n/((1-x)^n - x^n) / n ).
G.f.: exp( Sum_{n>=1} sigma(n) * x^n/(1-x)^n / n ), where sigma(n) is the sum of divisors of n ( A000203). G.f.: Product_{n>=1} (1 + x^n/(1-x)^n)^ A001511(n), where 2^ A001511(n) is the highest power of 2 that divides 2*n. a(n) ~ exp(Pi*sqrt(n/3) + Pi^2/24) * 2^(n-2) / (n*sqrt(3)). - Vaclav Kotesovec, Jun 25 2015
EXAMPLE
G.f.: A(x) = 1 + x + 3*x^2 + 8*x^3 + 21*x^4 + 54*x^5 + 137*x^6 + 344*x^7 +...
The g.f. equals the product:
A(x) = (1-x)/((1-x)-x) * (1-x)^2/((1-x)^2-x^2) * (1-x)^3/((1-x)^3-x^3) * (1-x)^4/((1-x)^4-x^4) * (1-x)^5/((1-x)^5-x^5) * (1-x)^6/((1-x)^6-x^6) * (1-x)^7/((1-x)^7-x^7) *...
and also equals the series:
A(x) = 1 + x*(1-x)/((1-x)-x)^2 + x^4*(1-x)^2/(((1-x)-x)*((1-x)^2-x^2))^2 + x^9*(1-x)^3/(((1-x)-x)*((1-x)^2-x^2)*((1-x)^3-x^3))^2 + x^16*(1-x)^4/(((1-x)-x)*((1-x)^2-x^2)*((1-x)^3-x^3)*((1-x)^4-x^4))^2 +...
MAPLE
b:= proc(n) option remember;
add(combinat[numbpart](k)*binomial(n, k), k=0..n)
end:
a:= n-> b(n)-b(n-1):
MATHEMATICA
Flatten[{1, Table[Sum[Binomial[n-1, k]*PartitionsP[k+1], {k, 0, n-1}], {n, 1, 30}]}] (* Vaclav Kotesovec, Jun 25 2015 *)
PROG
(PARI) {a(n)=sum(k=0, n, (binomial(n, k)-if(n>0, binomial(n-1, k)))*numbpart(k))}
for(n=0, 40, print1(a(n), ", "))
(PARI) {a(n)=local(X=x+x*O(x^n)); polcoeff(prod(k=1, n, (1-x)^k/((1-x)^k-X^k)), n)}
(PARI) {a(n)=local(X=x+x*O(x^n)); polcoeff(sum(m=0, n, x^m*(1-x)^(m*(m-1)/2)/prod(k=1, m, ((1-x)^k - X^k))), n)}
(PARI) {a(n)=local(X=x+x*O(x^n)); polcoeff(sum(m=0, n, x^(m^2)*(1-X)^m/prod(k=1, m, ((1-x)^k - x^k)^2)), n)}
(PARI) {a(n)=local(X=x+x*O(x^n)); polcoeff(exp(sum(m=1, n+1, x^m/((1-x)^m-X^m)/m)), n)}
(PARI) {a(n)=local(X=x+x*O(x^n)); polcoeff(exp(sum(m=1, n+1, sigma(m)*x^m/(1-X)^m/m)), n)}
(PARI) {a(n)=local(X=x+x*O(x^n)); polcoeff(prod(k=1, n, (1 + x^k/(1-X)^k)^valuation(2*k, 2)), n)}
CROSSREFS
Cf. A000041, A000219, A011782, A055887, A063834, A075900, A098407, A101509, A103446, A129519, A141199, A218481.
Number of hierarchical ordered partitions of partitions.
+10
29
1, 1, 3, 7, 17, 38, 87, 191, 421, 911, 1963, 4186, 8885, 18724, 39284, 82005, 170521, 353214, 729290, 1501184, 3081869, 6311404, 12896983, 26301515, 53541702, 108815626, 220824295, 447524559, 905850001, 1831526719
COMMENTS
Consider the "ordered partitions of partitions" as described in A055887. They are produced by introducing separators (a term used by J. Riordan) between the parts of a partition. If a partition has P parts, then it is possible to introduce 1, 2, ... P-1 separators. Let "|" denote such a separator. We just append 1,2,...,P-1 separators to each integer partition of n and subsequently form all permutation of the resulting list (which is composed of parts and separators). There are some rules: If we do not append a separator, then we do not perform any permutation. Furthermore, we do not accept permutations which have a dangling separator in front of the integer parts or past them. E.g. the permutations [|,1,2,3] and [1,2,3,|] are forbidden. Furthermore, sequences of separators as "|,|" are forbidden.
Now we impose a further restriction on the permutations. Consider the elements between two separators. We call their number "occupation number". We just request that the occupation number of a ordered partition is monotonically decreasing (if we start from the left to the right of a permutation written in our notation). If we interpret a separator as a level, then we can speak of a hierarchy. E.g. we do not count [1,|,2,3,|,4] as a hierarchy, but we accept [1,2|,3,4] as a hierarchy. We thus speak of "hierarchically ordered partitions of partitions" for this sequence.
With the generating function f := z -> 1/(mul(1-z^i/mul(1-z^j,j=1..i), i=1..25)); we get the asymptotic expansion using the command equivalent (f(z),z,n);
The result is 3.788561346*exp(-n)^(-log(2)) + O(1/n*exp(-n)^(-log(2))). Let fas := n -> 3.788562346*exp(-n)^(-log(2)); then for n=60 we get fas(60)/ A141199(60)= .4367915009e19/4344507472742893655 = 1.005387846. In short, a(n) is the number of finite sequences of integer partitions with weakly decreasing lengths and total sum n. The case of twice-partitions is A358831. A version choosing compositions is A218482. The strictly decreasing case is A358836. For ordered set partitions we have A005651. For weakly decreasing bigomega see A358335. - Gus Wiseman, Dec 05 2022
FORMULA
G.f.: 1/Product_{i>=1} (1-x^i/Product_{j=1..i} (1-x^j)). - Vladeta Jovovic, Jul 16 2008
EXAMPLE
n=1:
[1]
-------------------------
n=2:
[1, 1],
[1, "|", 1],
[2]]
-------------------------
n=3:
[1, 2],
[1, "|", 1, "|", 1],
[1, 1, 1],
[3],
[2, "|", 1],
[1, 1, "|", 1],
[1, "|", 2]
-------------------------
n=4:
[1, 1, 1, "|", 1],
[1, 1, "|", 1, 1],
[2, 2],
[1, 3],
[1, 1, 1, 1],
[1, 1, 2],
[4],
[1, "|", 1, "|", 1, "|", 1],
[1, 2, "|", 1],
[1, 1, "|", 2],
[1, 1, "|", 1, "|", 1],
[2, "|", 1, "|", 1],
[1, "|", 2, "|", 1],
[1, "|", 1, "|", 2],
[1, "|", 3],
[3, "|", 1],
[2, "|", 2].
MAPLE
A Maple program to generate these "hierarchically ordered partitions of partitions" is available on request.
An asymptotic expansion can be found using the generating function given by Vladeta Jovovic. For that purpose we use the Maple program "equivalent" from Bruno Salvy (http://ago.inria.fr/libraries/libraries.html).
PROG
(PARI) my(N=40, x='x+O('x^N)); Vec(1/prod(k=1, N, 1-x^k/prod(j=1, k, 1-x^j))) \\ Seiichi Manyama, Jan 18 2022
CROSSREFS
Cf. A000041, A000219, A001970, A005651, A063834, A129519, A218482, A358335, A358831, A358836, A358908.
Number of twice-partitions of n into partitions with all different lengths.
+10
16
1, 1, 2, 4, 9, 15, 31, 53, 105, 178, 330, 555, 1024, 1693, 2991, 5014, 8651, 14242, 24477, 39864, 67078, 109499, 181311, 292764, 483775, 774414, 1260016, 2016427, 3254327, 5162407, 8285796, 13074804, 20812682, 32733603, 51717463, 80904644, 127305773, 198134675, 309677802
COMMENTS
A twice-partition of n is a sequence of integer partitions, one of each part of an integer partition of n.
EXAMPLE
The a(1) = 1 through a(5) = 15 twice-partitions:
(1) (2) (3) (4) (5)
(11) (21) (22) (32)
(111) (31) (41)
(11)(1) (211) (221)
(1111) (311)
(11)(2) (2111)
(2)(11) (11111)
(21)(1) (21)(2)
(111)(1) (22)(1)
(3)(11)
(31)(1)
(111)(2)
(211)(1)
(111)(11)
(1111)(1)
MATHEMATICA
twiptn[n_]:=Join@@Table[Tuples[IntegerPartitions/@ptn], {ptn, IntegerPartitions[n]}];
Table[Length[Select[twiptn[n], UnsameQ@@Length/@#&]], {n, 0, 10}]
PROG
(PARI)
seq(n)={ local(Cache=Map());
my(g=Vec(-1+1/prod(k=1, n, 1 - y*x^k + O(x*x^n))));
my(F(m, r, b) = my(key=[m, r, b], z); if(!mapisdefined(Cache, key, &z),
z = if(r<=0||m==0, r==0, self()(m-1, r, b) + sum(k=1, m, my(c=polcoef(g[m], k)); if(!bittest(b, k)&&c, c*self()(min(m, r-m), r-m, bitor(b, 1<<k)))));
mapput(Cache, key, z)); z);
vector(n+1, i, F(i-1, i-1, 0))
CROSSREFS
The version for set partitions is A007837. For sums instead of lengths we have A271619. For constant instead of distinct lengths we have A306319. The case of distinct sums also is A358832. The version for multiset partitions of integer partitions is A358836.
Number of finite sequences of distinct integer partitions with total sum n and weakly decreasing lengths.
+10
11
1, 1, 2, 6, 10, 23, 50, 95, 188, 378, 747, 1414, 2739, 5179, 9811, 18562, 34491, 64131, 118607, 218369, 400196, 731414, 1328069, 2406363, 4346152, 7819549, 14027500, 25090582, 44749372, 79586074, 141214698, 249882141, 441176493, 777107137, 1365801088, 2395427040, 4192702241
EXAMPLE
The a(1) = 1 through a(4) = 10 sequences:
((1)) ((2)) ((3)) ((4))
((11)) ((21)) ((22))
((111)) ((31))
((1)(2)) ((211))
((2)(1)) ((1111))
((11)(1)) ((1)(3))
((3)(1))
((11)(2))
((21)(1))
((111)(1))
MATHEMATICA
ptnseq[n_]:=Join@@Table[Tuples[IntegerPartitions/@comp], {comp, Join@@Permutations/@IntegerPartitions[n]}];
Table[Length[Select[ptnseq[n], UnsameQ@@#&&GreaterEqual@@Length/@#&]], {n, 0, 10}]
PROG
(PARI)
P(n, y) = {1/prod(k=1, n, 1 - y*x^k + O(x*x^n))}
R(n, v) = {[subst(serlaplace(p), y, 1) | p<-Vec(prod(k=1, #v, (1 + y*x^k + O(x*x^n))^v[k] ))]}
seq(n) = {my(g=P(n, y)); Vec(prod(k=1, n, Ser(R(n, Vec(polcoef(g, k, y), -n))) ))} \\ Andrew Howroyd, Dec 31 2022
CROSSREFS
This is the distinct case of A055887 with weakly decreasing lengths. This is the distinct case is A141199. The case of distinct lengths also is A358836. This is the case of A358906 with weakly decreasing lengths. A001970 counts multiset partitions of integer partitions.
A358830 counts twice-partitions with distinct lengths.
A358901 counts partitions with all distinct Omegas.
A358912 counts sequences of partitions with distinct lengths.
A358914 counts twice-partitions into distinct strict partitions.
Number of integer partitions of n whose parts have all different numbers of prime factors ( A001222).
+10
10
1, 1, 1, 2, 2, 2, 3, 4, 4, 5, 5, 7, 9, 8, 9, 11, 11, 15, 16, 16, 18, 20, 22, 26, 28, 31, 32, 36, 40, 45, 46, 46, 50, 59, 64, 70, 75, 78, 83, 89, 94, 108, 106, 104, 120, 137, 142, 147, 150, 161, 174, 190, 200, 220, 226, 224, 248, 274, 274, 287, 301, 320, 340, 351, 361
EXAMPLE
The a(1) = 1 through a(11) = 7 partitions:
(1) (2) (3) (4) (5) (6) (7) (8) (9) (A) (B)
(21) (31) (41) (42) (43) (62) (54) (82) (74)
(51) (61) (71) (63) (91) (65)
(421) (431) (81) (451) (83)
(621) (631) (92)
(A1)
(821)
MATHEMATICA
Table[Length[Select[IntegerPartitions[n], UnsameQ@@PrimeOmega/@#&]], {n, 0, 60}]
CROSSREFS
The version not counting multiplicity is A358903, weakly decreasing A358902. For equal numbers of prime factors we have A319169, compositions A358911. A358836 counts multiset partitions with all distinct block sizes.
Number of integer compositions of n whose parts all have the same number of prime factors, counted with multiplicity.
+10
9
1, 1, 2, 2, 3, 4, 4, 7, 9, 12, 20, 21, 39, 49, 79, 109, 161, 236, 345, 512, 752, 1092, 1628, 2376, 3537, 5171, 7650, 11266, 16634, 24537, 36173, 53377, 78791, 116224, 171598, 253109, 373715, 551434, 814066, 1201466, 1773425, 2617744, 3864050, 5703840, 8419699
EXAMPLE
The a(1) = 1 through a(8) = 9 compositions:
(1) (2) (3) (4) (5) (6) (7) (8)
(11) (111) (22) (23) (33) (25) (35)
(1111) (32) (222) (52) (44)
(11111) (111111) (223) (53)
(232) (233)
(322) (323)
(1111111) (332)
(2222)
(11111111)
MAPLE
b:= proc(n, i) option remember; uses numtheory; `if`(n=0, 1, add(
(t-> `if`(i<0 or i=t, b(n-j, t), 0))(bigomega(j)), j=1..n))
end:
a:= n-> b(n, -1):
MATHEMATICA
Table[Length[Select[Join @@ Permutations/@IntegerPartitions[n], SameQ@@PrimeOmega/@#&]], {n, 0, 10}]
CROSSREFS
For sequences of partitions see A358905.
Number of integer partitions of n whose parts have all different numbers of distinct prime factors ( A001221).
+10
7
1, 1, 1, 2, 2, 2, 2, 2, 3, 4, 4, 4, 4, 5, 7, 8, 7, 9, 10, 10, 10, 9, 11, 15, 14, 13, 15, 14, 14, 17, 16, 17, 17, 16, 16, 17, 17, 21, 26, 24, 23, 25, 27, 29, 32, 31, 29, 36, 36, 35, 37, 37, 42, 49, 45, 44, 50, 49, 50, 58, 55, 55, 58, 56, 58, 66, 62, 65, 75
EXAMPLE
The a(15) = 8 partitions are: (15), (14,1), (12,3), (12,2,1), (10,5), (10,4,1), (6,9), (8,6,1).
MAPLE
p:= proc(n) option remember; nops(ifactors(n)[2]) end:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<0, 0,
add((t-> `if`(t<i, b(n-j, t), 0))(p(j)), j=1..n)))
end:
a:= n-> b(n$2):
MATHEMATICA
Table[Length[Select[IntegerPartitions[n], UnsameQ@@PrimeNu/@#&]], {n, 0, 30}]
CROSSREFS
Counting prime factors with multiplicity gives A358901. A116608 counts partitions by sum and number of distinct parts.
A358836 counts multiset partitions with all distinct block sizes.
Number of integer compositions of n whose parts have weakly decreasing numbers of prime factors (with multiplicity).
+10
6
1, 1, 2, 3, 5, 8, 12, 19, 29, 44, 68, 100, 153, 227, 342, 509, 759, 1129, 1678, 2492, 3699, 5477, 8121, 12015, 17795, 26313, 38924, 57541, 85065, 125712, 185758, 274431, 405420, 598815, 884465, 1306165, 1928943, 2848360, 4205979, 6210289, 9169540
EXAMPLE
The a(0) = 1 through a(6) = 12 compositions:
() (1) (2) (3) (4) (5) (6)
(11) (21) (22) (23) (33)
(111) (31) (32) (42)
(211) (41) (51)
(1111) (221) (222)
(311) (231)
(2111) (321)
(11111) (411)
(2211)
(3111)
(21111)
(111111)
MATHEMATICA
Table[Length[Select[Join @@ Permutations/@IntegerPartitions[n], GreaterEqual@@PrimeOmega/@#&]], {n, 0, 10}]
CROSSREFS
The strictly decreasing case is A358901.
Number of rectangular twice-partitions of n of type (P,R,P).
+10
6
1, 1, 3, 4, 8, 8, 17, 16, 32, 34, 56, 57, 119, 102, 179, 199, 335, 298, 598, 491, 960, 925, 1441, 1256, 2966, 2026, 3726, 3800, 6488, 4566, 11726, 6843, 16176, 14109, 21824, 16688, 49507, 21638, 50286, 50394, 99408, 44584, 165129, 63262, 208853, 205109, 248150
COMMENTS
A twice-partition of n is a sequence of integer partitions, one of each part of an integer partition of n, so these are twice-partitions of n into partitions with constant lengths and constant sums.
EXAMPLE
The a(1) = 1 through a(5) = 8 twice-partitions:
(1) (2) (3) (4) (5)
(11) (21) (22) (32)
(1)(1) (111) (31) (41)
(1)(1)(1) (211) (221)
(1111) (311)
(2)(2) (2111)
(11)(11) (11111)
(1)(1)(1)(1) (1)(1)(1)(1)(1)
MATHEMATICA
twiptn[n_]:=Join@@Table[Tuples[IntegerPartitions/@ptn], {ptn, IntegerPartitions[n]}];
Table[Length[Select[twiptn[n], SameQ@@Length/@#&&SameQ@@Total/@#&]], {n, 0, 10}]
PROG
(PARI)
P(n, y) = {1/prod(k=1, n, 1 - y*x^k + O(x*x^n))}
seq(n) = {my(u=Vec(P(n, y)-1)); concat([1], vector(n, n, sumdiv(n, d, my(p=u[n/d]); sum(j=1, n/d, polcoef(p, j, y)^d))))} \\ Andrew Howroyd, Dec 31 2022
CROSSREFS
This is the rectangular case of A279787. This is the case of A306319 with constant sums. For distinct instead of constant lengths and sums we have A358832. The version for multiset partitions of integer partitions is A358835.
Number of integer compositions of n whose parts have weakly decreasing numbers of distinct prime factors ( A001221).
+10
6
1, 1, 2, 3, 5, 8, 13, 21, 33, 53, 84, 134, 213, 338, 536, 850, 1349, 2136, 3389, 5367, 8509, 13480, 21362, 33843, 53624, 84957, 134600, 213251, 337850, 535251, 847987, 1343440, 2128372, 3371895, 5341977, 8463051, 13407689, 21241181, 33651507, 53312538, 84460690
EXAMPLE
The a(0) = 1 through a(6) = 13 compositions:
() (1) (2) (3) (4) (5) (6)
(11) (21) (22) (23) (24)
(111) (31) (32) (33)
(211) (41) (42)
(1111) (221) (51)
(311) (222)
(2111) (231)
(11111) (321)
(411)
(2211)
(3111)
(21111)
(111111)
MAPLE
p:= proc(n) option remember; nops(ifactors(n)[2]) end:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<0, 0,
add((t-> `if`(t<=i, b(n-j, t), 0))(p(j)), j=1..n)))
end:
a:= n-> b(n$2):
MATHEMATICA
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], GreaterEqual@@PrimeNu/@#&]], {n, 0, 10}]
CROSSREFS
The strictly decreasing case is A358903. A116608 counts partitions by sum and number of distinct parts.
A334028 counts distinct parts in standard compositions.
A358836 counts multiset partitions with all distinct block sizes.
Search completed in 0.010 seconds
|