login
Search: a076276 -id:a076276
     Sort: relevance | references | number | modified | created      Format: long | short | data
Number of emergent parts in all partitions of n.
+10
26
0, 0, 0, 0, 1, 1, 4, 4, 10, 12, 22, 27, 47, 56, 89, 112, 164, 205, 294, 364, 505, 630, 845, 1052, 1393, 1719, 2235, 2762, 3533, 4343, 5506, 6730, 8443, 10296, 12786, 15531, 19161, 23161, 28374, 34201, 41621, 49975, 60513, 72385, 87200, 103999, 124670, 148209
OFFSET
0,7
COMMENTS
Here the "emergent parts" of the partitions of n are defined to be the parts (with multiplicity) of all the partitions that do not contain "1" as a part, removed by one copy of the smallest part of every partition. Note that these parts are located in the head of the last section of the set of partitions of n.
Also, here the "filler parts" of the partitions of n are defined to be the parts of the last section of the set of partitions of n that are not the emergent parts.
For n >= 4, length of row n of A183152. - Omar E. Pol, Aug 08 2011
Also total number of parts of the regions that do not contain 1 as a part in the last section of the set of partitions of n (cf. A083751, A187219). - Omar E. Pol, Mar 04 2012
FORMULA
a(n) = A138135(n) - A002865(n), n >= 1.
From Omar E. Pol, Oct 21 2011: (Start)
a(n) = A006128(n) - A006128(n-1) - A000041(n), n >= 1.
a(n) = A138137(n) - A000041(n), n >= 1. (End)
a(n) = A076276(n) - A006128(n-1), n >= 1. - Omar E. Pol, Oct 30 2011
EXAMPLE
For n = 6 the partitions of 6 contain four "emergent" parts: (3), (4), (2), (2), so a(6) = 4. See below the location of the emergent parts.
6
(3) + 3
(4) + 2
(2) + (2) + 2
5 + 1
3 + 2 + 1
4 + 1 + 1
2 + 2 + 1 + 1
3 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1
For a(10) = 22 see the link for the location of the 22 "emergent parts" (colored yellow and green) and the location of the 42 "filler parts" (colored blue) in the last section of the set of partitions of 10.
MAPLE
b:= proc(n, i) option remember; local t, h;
if n<0 then [0, 0, 0]
elif n=0 then [0, 1, 0]
elif i<2 then [0, 0, 0]
else t:= b(n, i-1); h:= b(n-i, i);
[t[1]+h[1]+h[2], t[2], t[3]+h[3]+h[1]]
fi
end:
a:= n-> b(n, n)[3]:
seq (a(n), n=0..50); # Alois P. Heinz, Oct 21 2011
MATHEMATICA
b[n_, i_] := b[n, i] = Module[{t, h}, Which[n<0, {0, 0, 0}, n == 0, {0, 1, 0}, i<2 , {0, 0, 0}, True, t = b[n, i-1]; h = b[n-i, i]; Join [t[[1]] + h[[1]] + h[[2]], t[[2]], t[[3]] + h[[3]] + h[[1]] ]]]; a[n_] := b[n, n][[3]]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Jun 18 2015, after Alois P. Heinz *)
KEYWORD
nonn,easy
AUTHOR
Omar E. Pol, Nov 29 2010
STATUS
approved
a(n) = a(n-1) + n * a(n-2), where a(1) = 1, a(2) = 2.
(Formerly M1449 N0573)
+10
7
1, 2, 5, 13, 38, 116, 382, 1310, 4748, 17848, 70076, 284252, 1195240, 5174768, 23103368, 105899656, 498656912, 2404850720, 11879332048, 59976346448, 309442319456, 1628921941312, 8746095288800, 47840221880288, 266492604100288, 1510338372987776
OFFSET
1,2
COMMENTS
a(n) is the number of set partitions of [n] in which the block containing 1 is of length <= 3 and all other blocks are of length <= 2. Example: a(4)=13 counts all 15 partitions of [4] except 1234 and 1/234. - David Callan, Jul 22 2008
Empirical: a(n) is the sum of the entries in the second-last row of the lower-triangular matrix of coefficients giving the expansion of degree-(n+1) complete homogeneous symmetric functions in the Schur basis of the algebra of symmetric functions. - John M. Campbell, Mar 18 2018
REFERENCES
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 86 (divided by 2).
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
R. K. Guy, The Second Strong Law of Small Numbers, Math. Mag, 63 (1990), no. 1, 3-20. [Annotated scanned copy]
FORMULA
a(n) = (1/2)*A000085(n+1).
E.g.f.: (1/2)*( (1+x)*exp(x + x^2/2) - 1). - Vladeta Jovovic, Nov 04 2003
Given e.g.f. y(x), then 0 = y'(x) * (1+x) - (y(x)+1/2) * (2+2*x+x^2) = 1 - y''(x) + y'(x)*(1 + x) + 2*y(x). - Michael Somos, Jan 23 2018
0 = +a(n)*(+a(n+1) +a(n+2) -a(n+3)) +a(n+1)*(-a(n+1) +a(n+2)) for all n>0. - Michael Somos, Jan 23 2018
a(n) ~ n^((n+1)/2) / (2^(3/2) * exp(n/2 - sqrt(n) + 1/4)) * (1 + 19/(24*sqrt(n))). - Vaclav Kotesovec, Apr 01 2018
EXAMPLE
G.f. = x + 2*x + 5*x^2 + 13*x^3 + 38*x^4 + 116*x^5 + 382*x^6 + 1310*x^7 + ... - Michael Somos, Jan 23 2018
MAPLE
a := proc(n) option remember: if n = 1 then 1 elif n = 2 then 2 elif n >= 3 then procname(n-1) +n*procname(n-2) fi; end:
seq(a(n), n = 1..100); # Muniru A Asiru, Jan 25 2018
MATHEMATICA
RecurrenceTable[{a[1]==1, a[2]==2, a[n]==a[n-1]+n a[n-2]}, a, {n, 30}] (* Harvey P. Dale, Apr 21 2012 *)
(* Programs from Michael Somos, Jan 23 2018 *)
a[n_]:= With[{m=n+1}, If[m<2, 0, Sum[(2 k-1)!! Binomial[m, 2 k], {k, 0, m/2}]/2]];
a[n_]:= With[{m=n+1}, If[m<2, 0, HypergeometricU[-m/2, 1/2, -1/2] / (-1/2)^(m/2)/2]];
a[n_]:= With[{m=n+1}, If[m<2, 0, HypergeometricPFQ[{-m/2, (1-m)/2}, {}, 2]/2]];
a[n_]:= If[ n<1, 0, n! SeriesCoefficient[Exp[x+x^2/2]*(1+x)/2, {x, 0, n}]]; (* End *)
Fold[Append[#1, #1[[-1]] + #2 #1[[-2]]] &, {1, 2}, Range[3, 26]] (* Michael De Vlieger, Jan 23 2018 *)
PROG
(PARI) {a(n) = if( n<1, 0, n! * polcoeff( exp( x + x^2/2 + x * O(x^n)) * (1 + x) / 2, n))}; /* Michael Somos, Jan 23 2018 */
(PARI) my(N=30, x='x+O('x^N)); Vec(serlaplace((1/2)*( (1+x)*exp(x + x^2/2) - 1))) \\ Joerg Arndt, Sep 04 2023
(GAP) a:=[1, 2];; for n in [3..10^2] do a[n] := a[n-1] + n*a[n-2]; od; a; # Muniru A Asiru, Jan 25 2018
(Magma) I:=[1, 2]; [n le 2 select I[n] else Self(n-1)+n*Self(n-2): n in [1..30]]; // Vincenzo Librandi, Mar 31 2018
(SageMath)
def A001475_list(prec):
P.<x> = PowerSeriesRing(QQ, prec)
return P( ((1+x)*exp(x+x^2/2) -1)/2 ).egf_to_ogf().list()
a=A001475_list(40); a[1:] # G. C. Greubel, Sep 03 2023
CROSSREFS
KEYWORD
nonn
EXTENSIONS
More terms from Harvey P. Dale, Apr 21 2012
STATUS
approved
Triangle T(n,k) read by rows with q-e.g.f.: 1/Product_{k>0} (1-x^k/faq(k,q)).
+10
4
1, 1, 2, 1, 3, 3, 3, 1, 5, 7, 11, 11, 8, 4, 1, 7, 13, 25, 36, 44, 42, 36, 24, 13, 5, 1, 11, 24, 54, 93, 142, 184, 215, 222, 208, 172, 126, 81, 44, 19, 6, 1, 15, 39, 98, 195, 344, 532, 753, 964, 1150, 1264, 1294, 1226, 1082, 880, 661, 451, 278, 151, 70, 26, 7, 1
OFFSET
0,3
LINKS
Eric Weisstein's World of Mathematics, q-Exponential Function.
Eric Weisstein's World of Mathematics, q-Factorial.
FORMULA
Sum_{k=0..binomial(n,2)} T(n,k)*q^k = Sum_{pi} faq(n,q)/Product_{i=1..n} faq(i,q)^e(i), where pi runs over all nonnegative integer solutions to e(1) + 2*e(2) + ... + n*e(n) = n and faq(i,q) = Product_{j=1..i} (q^j-1)/(q-1), i = 1..n. Sum_{k=0..binomial(n,2)} T(n,k)*exp(2*Pi*I*k/n)) = 1.
Sum_{k=0..binomial(n,2)} (-1)^k*T(n,k) = A152536(n). - Alois P. Heinz, Aug 09 2021
EXAMPLE
Triangle begins:
1;
1;
2, 1;
3, 3, 3, 1;
5, 7, 11, 11, 8, 4, 1;
7, 13, 25, 36, 44, 42, 36, 24, 13, 5, 1;
...
MAPLE
multinomial2q := proc(n::integer, k::integer, nparts::integer)
local lpar , res, constrp;
res := [] ;
if n< 0 or nparts <= 0 then
;
elif nparts = 1 then
if n = k then
return [[n]] ;
end if;
else
for lpar from 0 do
if lpar*nparts > n or lpar > k then
break;
end if;
for constrp in procname(n-nparts*lpar, k-lpar, nparts-1) do
if nops(constrp) > 0 then
res := [op(res), [op(constrp), lpar]] ;
end if;
end do:
end do:
end if ;
return res ;
end proc:
multinomial2 := proc(n::integer, k::integer)
local res, constrp ;
res := [] ;
for constrp in multinomial2q(n, k, n) do
if nops(constrp) > 0 then
res := [op(res), constrp] ;
end if ;
end do:
res ;
end proc:
faq := proc(i, q)
mul((q^j-1)/(q-1), j=1..i) ;
end proc;
A152534 := proc(n, k)
pi := [] ;
for sp from 0 to n do
pi := [op(pi), op(multinomial2(n, sp))] ;
end do;
tqk := 0 ;
for p in pi do
faqe :=1 ;
for i from 1 to nops(p) do
faqe := faqe* faq(i, q)^op(i, p) ;
end do:
tqk := tqk+faq(n, q)/faqe ;
end do;
tqk ;
coeftayl(tqk, q=0, k) ;
end proc:
for n from 1 to 8 do
for k from 0 to binomial(n, 2) do
printf("%d, ", A152534(n, k)) ;
end do;
printf("\n") ;
end do: # R. J. Mathar, Sep 27 2011
# second Maple program:
f:= proc(n) option remember; `if`(n<2, 1, f(n-1)*(q^n-1)/(q-1)) end:
b:= proc(n, i) option remember; simplify(`if`(n=0 or i=1, 1,
add(b(n-i*j, i-1)/f(i)^j, j=0..n/i)))
end:
T:= n-> (p-> seq(coeff(p, q, i), i=0..degree(p)))(simplify(f(n)*b(n$2))):
seq(T(n), n=0..10); # Alois P. Heinz, Aug 09 2021
MATHEMATICA
f[n_] := f[n] = If[n < 2, 1, f[n - 1]*(q^n - 1)/(q - 1)];
b[n_, i_] := b[n, i] = Simplify[If[n == 0 || i == 1, 1,
Sum[b[n - i*j, i - 1]/f[i]^j, {j, 0, n/i}]]];
T[n_] := CoefficientList[Simplify[f[n]*b[n, n]], q];
Table[T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Mar 11 2022, after Alois P. Heinz *)
CROSSREFS
Cf. A005651 (row sums), A000041 (first column), A076276 (second column), A152474, A152536.
T(n,n) gives A346980.
KEYWORD
nonn,tabf
AUTHOR
Vladeta Jovovic, Dec 06 2008
EXTENSIONS
T(0,0)=1 prepended by Alois P. Heinz, Aug 09 2021
STATUS
approved
Number of pairs of partitions of n that are successors in reverse lexicographic order, but incomparable in dominance (natural, majorization) ordering.
+10
3
0, 0, 0, 0, 0, 2, 3, 4, 6, 9, 12, 17, 22, 30, 39, 51, 65, 85, 107, 136, 171, 216, 268, 335, 413, 512, 629, 772, 941, 1151, 1396, 1694, 2046, 2471, 2969, 3569, 4271, 5110, 6093, 7258, 8620, 10235, 12113, 14325, 16902, 19925, 23434, 27540, 32296, 37842, 44260, 51715, 60322, 70306, 81805
OFFSET
1,6
COMMENTS
Empirical: a(n) is the number of zeros in the subdiagonal of the lower-triangular matrix of coefficients giving the expansion of degree-n complete homogeneous symmetric functions in the Schur basis of the algebra of symmetric functions. - John M. Campbell, Mar 18 2018
REFERENCES
Ian G. Macdonald, Symmetric functions and Hall polynomials, Oxford University Press, 1979, pp. 6-8.
EXAMPLE
The successor pair (3,1,1,1) and (2,2,2) are incomparable in dominance ordering, and so are their transposes (4,1,1) and (3,3) and these are the two only pairs for n=6, hence a(6)=2.
MATHEMATICA
Needs["Combinatorica`"];
dominant[par1_?PartitionQ, par2_?PartitionQ]:= Block[{le=Max[Length[par1], Length[par2]], acc},
acc=Accumulate[PadRight[par1, le]]-Accumulate[PadRight[par2, le]]; Which[Min[acc]===0&&Max[acc]>=0, 1, Min[acc]<=0&&Max[acc]===0, -1, True, 0]];
Table[Count[Apply[dominant, Partition[Partitions[n], 2, 1], 1], 0], {n, 40}]
CROSSREFS
KEYWORD
nonn
AUTHOR
Wouter Meeussen, Oct 07 2014
STATUS
approved
A006128(n) mod n.
+10
0
0, 1, 0, 0, 0, 5, 5, 6, 2, 2, 0, 3, 10, 10, 3, 7, 10, 16, 2, 10, 4, 1, 17, 22, 1, 20, 24, 21, 11, 23, 28, 31, 30, 4, 16, 14, 18, 3, 4, 26, 29, 9, 42, 8, 15, 5, 29, 43, 38, 18, 32, 32, 22, 1, 3, 3, 28, 21, 32, 51, 30, 46, 39, 19, 52, 16, 30, 1, 2, 68, 65, 70, 57, 73, 42, 1, 21, 25, 44, 72, 17, 71
OFFSET
1,6
COMMENTS
The remainder of (the total number of parts in all partitions of n) mod n.
EXAMPLE
a(1)=0=1 mod 1. a(2)=1=3 mod 2. a(3)=0=6 mod 3. a(4)=0=12 mod 4. a(5)=0=20 mod 5. a(6)=5=35 mod 6.
CROSSREFS
KEYWORD
nonn
AUTHOR
EXTENSIONS
Edited, a 3 inserted, and extended by R. J. Mathar, Aug 02 2009
STATUS
approved

Search completed in 0.006 seconds