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

Author

Clark Kimberling

Keywords

• nonn
• easy

Comments

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

Links

• 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).

Crossrefs

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

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

Programs

Mathematica

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

PARI

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

Formula

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