login
Triangle read by rows: T(n,k) = number of k-part order-consecutive partition of {1,2,...,n} (1 <= k <= n).
13

%I #70 Aug 15 2024 03:34:47

%S 1,1,2,1,5,4,1,9,16,8,1,14,41,44,16,1,20,85,146,112,32,1,27,155,377,

%T 456,272,64,1,35,259,833,1408,1312,640,128,1,44,406,1652,3649,4712,

%U 3568,1472,256,1,54,606,3024,8361,14002,14608,9312,3328,512,1,65,870,5202

%N Triangle read by rows: T(n,k) = number of k-part order-consecutive partition of {1,2,...,n} (1 <= k <= n).

%C Generalized Riordan array (1/(1-x), x/(1-x) + x*dif(x/1-x),x)). - _Paul Barry_, Dec 26 2007

%C Reversal of A117317. - _Philippe Deléham_, Feb 11 2012

%C Essentially given by (1, 0, 1/2, 1/2, 0, 0, 0, 0, 0, 0, 0, ...) DELTA (0, 2, 0, 0, 0, 0, 0, 0, 0, ...) where DELTA is the operator defined in A084938. - _Philippe Deléham_, Feb 11 2012

%C This sequence is given in the Strehl presentation with the o.g.f. (1-z)/[1-2(1+t)z+(1+t)z^2], with offset 0, along with a recursion relation, a combinatorial interpretation, and relations to Hermite and Laguerre polynomials. Note that the o.g.f. is related to that of A049310. - _Tom Copeland_, Jan 08 2017

%C From _Gus Wiseman_, Mar 06 2020: (Start)

%C T(n,k) is also the number of unimodal length-n sequences covering an initial interval of positive integers with maximum part k, where a sequence of integers is unimodal if it is the concatenation of a weakly increasing and a weakly decreasing sequence. For example, the sequences counted by row n = 4 are:

%C (1111) (1112) (1123) (1234)

%C (1121) (1132) (1243)

%C (1122) (1223) (1342)

%C (1211) (1231) (1432)

%C (1221) (1232) (2341)

%C (1222) (1233) (2431)

%C (2111) (1321) (3421)

%C (2211) (1322) (4321)

%C (2221) (1332)

%C (2231)

%C (2311)

%C (2321)

%C (2331)

%C (3211)

%C (3221)

%C (3321)

%C (End)

%C T(n,k) is the number of hexagonal directed-column convex polyominoes of area n with k columns (see Baril et al. at page 9). - _Stefano Spezia_, Oct 14 2023

%H Reinhard Zumkeller, <a href="/A056242/b056242.txt">Rows n = 1..125 of table, flattened</a>

%H Jean-Luc Baril, José L. Ramírez, and Fabio A. Velandia, <a href="http://jl.baril.u-bourgogne.fr/hexbij.pdf">Bijections between Directed-Column Convex Polyominoes and Restricted Compositions</a>, September 29, 2023.

%H Tyler Clark and Tom Richmond, <a href="http://people.wku.edu/tom.richmond/Papers/CountConvexTopsFTOsets.pdf">The Number of Convex Topologies on a Finite Totally Ordered Set</a>, 2013, Involve, Vol. 8 (2015), No. 1, 25-32.

%H F. K. Hwang and C. L. Mallows, <a href="http://dx.doi.org/10.1016/0097-3165(95)90097-7">Enumerating nested and consecutive partitions</a>, J. Combin. Theory Ser. A 70 (1995), no. 2, 323-333.

%H Finn Bjarne Jost, <a href="https://arxiv.org/abs/2307.15825">Tautological Intersection Numbers and Order-Consecutive Partition Sequences</a>, arXiv:2307.15825 [math.CO], 2023. See p. 9.

%H V. Strehl, <a href="http://www.emis.de/journals/SLC/wpapers/s71vortrag/strehl.pdf">Combinatoire rétrospective et créative</a>, an on-line presentation, slide 36, SLC 71, Bertinoro,, September 18, 2013.

%H Volker Strehl, <a href="http://www.mat.univie.ac.at/~slc/wpapers/s76strehl.html">Lacunary Laguerre Series from a Combinatorial Perspective</a>, Séminaire Lotharingien de Combinatoire, B76c (2017).

%F The Hwang and Mallows reference gives explicit formulas.

%F T(n,k) = Sum_{j=0..k-1} (-1)^(k-1-j)*binomial(k-1, j)*binomial(n+2j-1, 2j) (1<=k<=n); this is formula (11) in the Huang and Mallows reference.

%F T(n,k) = 2*T(n-1,k) + 2*T(n-1,k-1) - T(n-2,k) - T(n-2,k-1), T(1,1) = 1, T(2,1) = 1, T(2,2) = 2. - _Philippe Deléham_, Feb 11 2012

%F G.f.: -(-1+x)*x*y/(1-2*x-2*x*y+x^2*y+x^2). - _R. J. Mathar_, Aug 11 2015

%e Triangle begins:

%e 1;

%e 1, 2;

%e 1, 5, 4;

%e 1, 9, 16, 8;

%e 1, 14, 41, 44, 16;

%e 1, 20, 85, 146, 112, 32;

%e 1, 27, 155, 377, 456, 272, 64;

%e 1, 35, 259, 833, 1408, 1312, 640, 128;

%e 1, 44, 406, 1652, 3649, 4712, 3568, 1472, 256;

%e T(3,2)=5 because we have {1}{23}, {23}{1}, {12}{3}, {3}{12} and {2}{13}.

%e Triangle (1, 0, 1/2, 1/2, 0, 0, 0, ...) DELTA (0, 2, 0, 0, 0, ...) begins:

%e 1;

%e 1, 0;

%e 1, 2, 0;

%e 1, 5, 4, 0;

%e 1, 9, 16, 8, 0;

%e 1, 14, 41, 44, 16, 0;

%e 1, 20, 85, 146, 112, 32, 0;

%e 1, 27, 155, 377, 456, 272, 64, 0;

%p T:=proc(n,k) if k=1 then 1 elif k<=n then sum((-1)^(k-1-j)*binomial(k-1,j)*binomial(n+2*j-1,2*j),j=0..k-1) else 0 fi end: seq(seq(T(n,k),k=1..n),n=1..12);

%t rows = 11; t[n_, k_] := (-1)^(k+1)*HypergeometricPFQ[{1-k, (n+1)/2, n/2}, {1/2, 1}, 1]; Flatten[ Table[ t[n, k], {n, 1, rows}, {k, 1, n}]](* _Jean-François Alcover_, Nov 17 2011 *)

%o (Haskell)

%o a056242 n k = a056242_tabl !! (n-1)!! (k-1)

%o a056242_row n = a056242_tabl !! (n-1)

%o a056242_tabl = [1] : [1,2] : f [1] [1,2] where

%o f us vs = ws : f vs ws where

%o ws = zipWith (-) (map (* 2) $ zipWith (+) ([0] ++ vs) (vs ++ [0]))

%o (zipWith (+) ([0] ++ us ++ [0]) (us ++ [0,0]))

%o -- _Reinhard Zumkeller_, May 08 2014

%Y Row sums are A007052.

%Y Column k = n - 1 is A053220.

%Y Ordered set-partitions are A000670.

%Y Cf. A001523, A049310, A072704, A084938, A097805, A117317, A227038, A328509, A332294, A332673, A332724, A332872.

%K nonn,tabl,easy,nice

%O 1,3

%A _Colin Mallows_, Aug 23 2000