A089378 -id:A089378 - cp's OEIS frontend

A049611 a(n) = T(n,2), array T as in A049600.

0, 1, 4, 13, 38, 104, 272, 688, 1696, 4096, 9728, 22784, 52736, 120832, 274432, 618496, 1384448, 3080192, 6815744, 15007744, 32899072, 71827456, 156237824, 338690048, 731906048, 1577058304, 3388997632, 7264534528, 15535702016

Offset: 0

Clark Kimberling

Refer to A089378 and A075729 for the definition of hierarchies, subhierarchies and one-step transitions. - Thomas Wieder, Feb 28 2004
We may ask for the number of one-step transitions (NOOST) between all unlabeled hierarchies of n elements with the restriction that no subhierarchies are allowed. As an example, consider n = 4 and the hierarchy H1 = [[2,2]] with two elements on level 1 and two on level 2. Starting from H1 the hierarchies [[1, 3]], [[2, 1, 1]], [[1, 2, 1]] can be reached by moving one element only, but [[1, 1, 2]] cannot be reached in a one-step transitition. The solution is n = 1, NOOST = 0; n = 2, NOOST = 1; n = 3, NOOST = 4; n = 4, NOOST = 13; n = 5, NOOST = 38; n = 6, NOOST = 104; n = 7, NOOST = 272; n = 8, NOOST = 688; n = 9, NOOST = 1696. This is sequence A049611. - Thomas Wieder, Feb 28 2004
If X_1,X_2,...,X_n are 2-blocks of a (2n+2)-set X then, for n>=1, a(n+1) is the number of (n+2)-subsets of X intersecting each X_i, (i=1,2,...,n). - Milan Janjic, Nov 18 2007
In each composition (ordered partition) of the integer n, circle the first summand once, circle the second summand twice, etc. a(n) is the total number of circles in all compositions of n (that is, add k*(k+1)/2 for each composition into k parts). Note the O.g.f. is B(A(x)) where A(x)= x/(1-x) and B(x)= x/(1-x)^3.
This is the Riordan transform with the Riordan matrix A097805 (of the associated type) of the triangular number sequence A000217. See a Feb 17 2017 comment on A097805. - Wolfdieter Lang, Feb 17 2017

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Robert Davis, Greg Simay, Further Combinatorics and Applications of Two-Toned Tilings, arXiv:2001.11089 [math.CO], 2020.
Milan Janjic, Two Enumerative Functions
M. Janjic, On a class of polynomials with integer coefficients, JIS 11 (2008) 08.5.2.
M. Janjic and B. Petkovic, A Counting Function, arXiv preprint arXiv:1301.4550 [math.CO], 2013. - From _N. J. A. Sloane_, Feb 13 2013
M. Janjic, B. Petkovic, A Counting Function Generalizing Binomial Coefficients and Some Other Classes of Integers, J. Int. Seq. 17 (2014) # 14.3.5.
S. Kitaev, J. Remmel, p-Ascent Sequences, arXiv:1503.00914 [math.CO], 2015.
Sergey Kitaev, J. B. Remmel, A note on p-Ascent Sequences, Preprint, 2016.
Igor Makhlin, Gröbner fans of Hibi ideals, generalized Hibi ideals and flag varieties, arXiv:2003.02916 [math.CO], 2020.
Agustín Moreno Cañadas, Hernán Giraldo, Gabriel Bravo Rios, On the Number of Sections in the Auslander-Reiten Quiver of Algebras of Dynkin Type, Far East Journal of Mathematical Sciences (FJMS), Vol. 101, No. 8 (2017), pp. 1631-1654.
Index entries for linear recurrences with constant coefficients, signature (6,-12,8).

a(n+1)= A055252(n, 0), n >= 0. Row sums of triangle A055249.

Cf. A001793, A058396, A075729, A089378, A000217.

CoefficientList[Series[x (1-x)^2/(1-2x)^3,{x,0,40}],x] (* Harvey P. Dale, Sep 24 2013 *)

concat(0, Vec(x*(1-x)^2/(1-2*x)^3+O(x^99))) \\ Charles R Greathouse IV, Jun 12 2015

G.f.: x*(1-x)^2/(1-2*x)^3.
Binomial transform of quarter squares A002620(n+1): a(n) = Sum_{k=0..n} binomial(n, k)*floor((k+1)^2/4). - Paul Barry, May 27 2003
a(n) = 2^(n-4)*(n^2+5*n+2) - 0^n/8. - Paul Barry, Jun 09 2003
a(n+2) = A001787(n+2) + A001788(n). - Creighton Dement, Aug 02 2005
a(n) = Hyper2F1([-n+1, 3], [1], -1) for n>0. - Peter Luschny, Aug 02 2014
a(n) = Sum_{k=0..n-1} Sum_{j=0..n-1} Sum_{i=0..n-1} binomial(n-1, i+j+k). - Yalcin Aktar, Aug 27 2023

A093694 Number of one-element transitions from the partitions of n to the partitions of n+1 for labeled parts.

Original entry on oeis.org

1, 2, 5, 9, 17, 27, 46, 69, 108, 158, 234, 331, 476, 657, 915, 1244, 1694, 2262, 3029, 3988, 5257, 6844, 8901, 11461, 14749, 18809, 23958, 30304, 38263, 48018, 60167, 74977, 93276, 115509, 142772, 175759, 215991, 264449, 323216, 393772, 478884

Offset: 0

Thomas Wieder, Apr 10 2004

nonn

For the unlabeled case, the number of one-element transitions from the partitions of n to the partitions of n+1 is given by A000070. Example: There are A000070(4) = 12 transitions from n=4 to n=5: [1111] -> [11111], [1111] -> [1112], [112] -> [1112], [112] -> [113], [112] -> [122], [13] -> [113], [13] -> [14], [13] -> [23], [22] -> [23], [22] -> [122], [4] -> [14], [4] -> [5].
a(n) is also the total number of parts in all partitions of the integer n+1 which contain at least one part 1.
More generally, a(n) is also the total number of parts in all partitions of n+k that contain k as a part, if k >= 1. - Omar E. Pol, Sep 25 2013
Also partitions of n into 2 sorts of parts where all parts of the first sort precede all parts of the second sort; see example. [Joerg Arndt, Apr 28 2013]
Number of vertical elements in the structure of A225610. - Omar E. Pol, Aug 01 2013

			In the labeled case, we have 9 one-element transitions from all partitions of n=3 to the partitions of n+1=4: [1,1,1] -> [1,1,1,1]; [1,1,1] -> [1,1,2]; [1,1,1] -> [1,1,2]; [1,1,1] -> [1,1,2]; [1,2] -> [1,1,2]; [1,2] -> [1,3]; [1,2] -> [2,2]; [3] -> [1,3]; [3] -> [4].
For n = 3 we have the following partitions of 3+1 = 4 which contain at least one part 1: [1111], [112], [13] and these partitions contain 4 + 3 + 2 = 9 = a(3) parts.
There are a(4)=17 partitions of 4 into 2 sorts where all parts of the first sort precede all parts of the second sort. Here p:s stands for "part p of sort s":
01:  [ 1:0  1:0  1:0  1:0  ]
02:  [ 1:0  1:0  1:0  1:1  ]
03:  [ 1:0  1:0  1:1  1:1  ]
04:  [ 1:0  1:1  1:1  1:1  ]
05:  [ 1:1  1:1  1:1  1:1  ]
06:  [ 2:0  1:0  1:0  ]
07:  [ 2:0  1:0  1:1  ]
08:  [ 2:0  1:1  1:1  ]
09:  [ 2:0  2:0  ]
10:  [ 2:0  2:1  ]
11:  [ 2:1  1:1  1:1  ]
12:  [ 2:1  2:1  ]
13:  [ 3:0  1:0  ]
14:  [ 3:0  1:1  ]
15:  [ 3:1  1:1  ]
16:  [ 4:0  ]
17:  [ 4:1  ]
- _Joerg Arndt_, Apr 28 2013

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A000070, A093695, A089378.

main := proc(n::integer) local a,ndxp,ListOfPartitions; with(combinat): with(ListTools): ListOfPartitions:=partition(n-1); a:=0; for ndxp from 1 to nops(ListOfPartitions) do if Occurrences(1, ListOfPartitions[ndxp]) > 0 then a:=a+nops(Flatten(ListOfPartitions[ndxp])); print("ndxp, Flatten(ListOfPartitions[ndxp]):",ndxp, Flatten(ListOfPartitions[ndxp])); print("ndxp, ListOfPartitions[ndxp], a:",ndxp, ListOfPartitions[ndxp],a); # End of if-clause *** Occurrences(1, ListOfPartitions[ndxp]) *** fi; end do; print("n, a(n):",n,a); end proc;
##
b:= proc(n,i) option remember; local x, y;
      if n<=0 or i=0 then [0, 0]
    elif i=1 then [1, n]
    else x:= b(n, i-1);
         y:= b(n-i, i);
         [x[1]+y[1], x[2]+y[2]+y[1]]
      fi
    end:
a:= n-> b(n+1, n+1)[2]:
seq(a(n), n=0..100);  # Alois P. Heinz, Apr 24 2011

f[n_] := Block[{l = Sort[ Flatten[ IntegerPartitions[n]]]}, Length[l] - Count[l, 1]]; g[n_] := (f[n] + Sum[PartitionsP[k], {k, 0, n}]); Table[ g[n], {n, 0, 40}] (* Robert G. Wilson v, Jul 13 2004 *)
b[n_, i_] := b[n, i] = Module[{x, y}, If[n <= 0 || i == 0, {0, 0}, If[i == 1, {1, n}, x = b[n, i-1]; y = b[n-i, i]; {x[[1]] + y[[1]], x[[2]] + y[[2]] + y[[1]]}]]]; a[n_] := b[n+1, n+1][[2]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Oct 10 2015, after Alois P. Heinz *)

a(n) = numbpart(n) + sum(m=1, n, numdiv(m)*numbpart(n - m)); \\ Indranil Ghosh, Apr 25 2017

from sympy import divisor_count, npartitions
def a(n): return npartitions(n) + sum([divisor_count(m)*npartitions(n - m) for m in range(1, n + 1)]) # Indranil Ghosh, Apr 25 2017

a(n) = Sum_k=1^p(n) (nops(p(k, n)) + 1), where p(n) is the number of partitions of n and nops(p(k, n)) is the number of parts in the k-th partition p(n, k) of n.
a(n) = Sum_k=1^p(n) nops(p(k, n)[subject to: at least one p(l, k, n) = 1]; p(n) = number of partitions of n, p(k, n) = k-th partition, p(l, k, n) = l-th part in the k-th partition p(k, n) of integer n.
G.f.: sum(n>=0, (n+1) * x^n / prod(k=1..n, 1-x^k ) ). - Joerg Arndt, Apr 17 2011
a(n) = A000041(n) + A006128(n). - Omar E. Pol, Aug 01 2013
a(n) ~ exp(Pi*sqrt(2*n/3))*(2*gamma + log(6*n/Pi^2))/(4*Pi*sqrt(2*n)), where gamma is the Euler-Mascheroni constant A001620. - Vaclav Kotesovec, Oct 24 2016

More terms from Robert G. Wilson v, Jul 13 2004

A093695 Number of one-element transitions among partitions of the integer n for unlabeled parts.

Original entry on oeis.org

0, 0, 2, 4, 10, 18, 34, 56, 94, 146, 228, 340, 506, 730, 1050, 1476, 2066, 2844, 3896, 5268, 7090, 9442, 12518, 16454, 21534, 27980, 36210, 46572, 59674, 76056, 96594, 122106, 153852, 193048, 241492, 300974, 374038, 463286, 572304, 704826, 865874, 1060766

Offset: 0

Thomas Wieder, Apr 10 2004

nonn

It appears that a(n) = 2 * A000097(n-2). - George Beck, Sep 05 2014
This was proved as noted at A000097. - George Beck, Jan 11 2025
It appears that a(n) = A135348(n+1) - A000070(n). - Thomas Baruchel, May 12 2018

			In the unlabeled case we have 10 one-element transitions among all partitions of n=4: [1,1,1,1] -> [1,1,2]; [1,1,2] -> [2,2]; [1,1,2] -> [1,3]; [2,2] -> [1,3]; [1,3] -> [4] and [1,1,2] -> [1,1,1,1]; [2,2] -> [1,1,2]; [1,3] -> [1,1,2]; [1,3] -> [2,2]; [4] -> [1,3].
n=5:
partition number p=1 is [1,1,1,1,1], parts d(1,1)=1, d(2,1)=1 contribute 1;
partition number p=2 is [1,1,1,2], parts d(1,1)=1, d(2,2)=1 contribute 1, parts d(1,2)=2, d(4,2)=2 contribute 1;
partition number p=3 is [1,2,2], parts d(1,3)=1, d(2,3)=2 contribute 1, parts d(2,3)=2, d(3,3)=2 contribute 1;
partition number p=4 is [1,1,3], parts d(1,4)=1, d(2,4)=1 contribute 1, parts d(1,4)=1, d(3,4)=3 contribute 1;
partition number p=5 is [2,3], parts d(1,5)=2, d(2,5)=3 contribute 1;
partition number p=6 is [1,4], parts d(1,6)=1, d(2,6)=4 contribute 1;
partition number p=7 is [5], parts d(1,7)=5 contributes 0;
==> a(5)=2*9=18 (factor 2 if we accept up and down transitions).
a(5) = 18 because the 11 partitions of n=5+1=6 have the following sets of parts:
{1} contributes 0, {1, 2} contributes 2, {1, 2} contributes 2,
{2} contributes 0, {1, 3} contributes 2, {1, 2, 3} contributes 6,
{3} contributes 0, {1, 4} contributes 2, {2, 4} contributes 2,
{1, 5} contributes 2, {6} contributes 0,
which gives 0 + 2 + 2 + 0 + 2 + 6 + 0 + 2 + 2 + 2 + 0 = 18.
G.f. = 2*x^2 + 4*x^3 + 10*x^4 + 18*x^5 + 34*x^6 + 56*x^7 + 94*x^8 + ...

Alois P. Heinz, Table of n, a(n) for n = 0..5000

Cf. A093694, A089378.
Cf. A094533.
Column k=2 of triangle A322210.

A093695 := proc(n::integer) local a,ndxp,ListOfPartitions,APartition,PartOfAPartition,SetOfParts, iverbose; with(combinat): iverbose:=1; ListOfPartitions:=partition(n+1); a:=0; for ndxp from 1 to nops(ListOfPartitions) do APartition := ListOfPartitions[ndxp]; SetOfParts := convert(APartition,set); a := a + nops(SetOfParts)^2 - nops(SetOfParts); if iverbose = 1 then print ("ndxp, SetOfParts, nops(SetOfParts)^2 - nops(SetOfParts): ", ndxp,SetOfParts,nops(SetOfParts)^2 - nops(SetOfParts)); fi; # End of do-loop *** ndxp ***. end do; print("n, a(n):",n,a); end proc;
# second Maple program
b:= proc(n, i) option remember; local j, f, g;
      if n=0 then [0]
    elif i=1 then [1]
    else f:= b(n, i-1);
         for j to floor(n/i) do f:= zip((x, y)-> x+y,
             f, `if`(n=i*j, [1], [0, b(n-i*j, i-1)[]]), 0)
         od; f
      fi
    end:
a:= n-> (l-> add(i*(i-1)*l[i], i=1..nops(l)))(b(n+1, n+1)):
seq(a(n), n=0..50);  # Alois P. Heinz, Apr 05 2012

a[n_] := Block[{p = IntegerPartitions[n + 1], l = PartitionsP[n + 1]}, Sum[ Length[ Union[ p[[k]]]]^2 - Length[ Union[ p[[k]] ]], {k, l}]]; Table[ a[n], {n, 0, 40}] (* Robert G. Wilson v, Jul 13 2004, updated by Jean-François Alcover, Jan 29 2014 *)

a(n) = Sum_p=1^P(n) Sum_i=1^D(p) Sum_j=1^D(p) 1 [subject to: i <> j and d(i,p) <= d(j,p) and d(i,p) <> d(i-1,p) (if i > 1) and d(j,i) <> d(j-1,i) (if j > 1 and if d(j-1,p) has given a contribution to the sum) ]; P(n) = number of partitions of n, D(p) = number of parts in partition p, d(i,p) and d(j,p) = parts number i and j in partition p of integer n.
See the corresponding formula for a(n) for the labeled case A094533.
a(n) = Sum_i=1^P(n+1) S(i, n+1)^2 - S(i, n+1), where P(n+1) is the number of integer partitions of n+1 and S(i, n+1) is the number of parts in the set of parts of the i-th partition of n+1. (E.g. the partition [1111233] has the set of parts {1, 2, 3} and would contribute 3^2 - 3 = 6 to the sum.)
G.f.: 2*x^2 / (x^3-x^2-x+1) * Product_{m>=1} (1/(1-x^m))  (conjectured). - Thomas Baruchel, May 12 2018

More terms from Robert G. Wilson v, Jul 13 2004

cp's OEIS Frontend

A049611 a(n) = T(n,2), array T as in A049600.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A093694 Number of one-element transitions from the partitions of n to the partitions of n+1 for labeled parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A093695 Number of one-element transitions among partitions of the integer n for unlabeled parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions