A005683 -id:A005683 - cp's OEIS frontend

A034851 Rows of Losanitsch's triangle T(n, k), n >= 0, 0 <= k <= n.

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 4, 2, 1, 1, 3, 6, 6, 3, 1, 1, 3, 9, 10, 9, 3, 1, 1, 4, 12, 19, 19, 12, 4, 1, 1, 4, 16, 28, 38, 28, 16, 4, 1, 1, 5, 20, 44, 66, 66, 44, 20, 5, 1, 1, 5, 25, 60, 110, 126, 110, 60, 25, 5, 1, 1, 6, 30, 85, 170, 236, 236, 170, 85, 30, 6, 1, 1, 6, 36, 110, 255

Offset: 0

N. J. A. Sloane

Sometimes erroneously called "Lossnitsch's triangle". But the author's name is Losanitsch (I have seen the original paper in Chem. Ber.). This is a German version of the Serbian name Lozanic. - N. J. A. Sloane, Jun 29 2008
For n >= 3, a(n-3,k) is the number of series-reduced (or homeomorphically irreducible) trees which become a path P(k+1) on k+1 nodes, k >= 0, when all leaves are omitted (see illustration). Proof by Pólya's enumeration theorem. - Wolfdieter Lang, Jun 08 2001
The number of ways to put beads of two colors in a line, but take symmetry into consideration, so that 011 and 110 are considered the same. - Yong Kong (ykong(AT)nus.edu.sg), Jan 04 2005
Alternating row sums are 1,0,1,0,2,0,4,0,8,0,16,0,... - Gerald McGarvey, Oct 20 2008
The triangle sums, see A180662 for their definitions, link Losanitsch's triangle A034851 with several sequences, see the crossrefs. We observe that the Ze3 and Ze4 sums link Losanitsch's triangle with A005683, i.e., R. K. Guy's Twopins game. - Johannes W. Meijer, Jul 14 2011
T(n-(L-1)k, k) is the number of ways to cover an n-length line by exactly k L-length segments excluding symmetric covers. For L=2 it is corresponds to A102541, for L=3 to A228570 and for L=4 to A228572. - Philipp O. Tsvetkov, Nov 08 2013
Also the number of equivalence classes of ways of placing k 1 X 1 tiles in an n X 1 rectangle under all symmetry operations of the rectangle. - Christopher Hunt Gribble, Feb 16 2014
T(n, k) is the number of non-isomorphic outer planar graphs of order n+3, size n+3+k, and maximum degree k+2. - Christian Barrientos, Oct 18 2018
From Álvar Ibeas, Jun 01 2020: (Start)
T(n, k) is the sum of even-degree coefficients of the Gaussian polynomial [n, k]_q. The area below a NE lattice path between (0,0) and (k, n-k) is even for T(n, k) paths and odd for A034852(n, k) of them.
For a (non-reversible) string of k black and n-k white beads, consider the minimum number of bead transpositions needed to place the black ones to the left and the white ones to the right (in other words, the number of inversions of the permutation obtained by labeling the black beads by integers 1,...,k and the white ones by k+1,...,n, in the same order they take on the string). It is even for T(n, k) strings and odd for A034852(n, k) cases.
(End)
Named after the Serbian chemist, politician and diplomat Simeon Milivoje "Sima" Lozanić (1847-1935). - Amiram Eldar, Jun 10 2021
T(n, k) is the number of caterpillars with a perfect matching, with 2n+2 vertices and diameter 2n-1-k. - Christian Barrientos, Sep 12 2023

			Triangle begins
  1;
  1,  1;
  1,  1,  1;
  1,  2,  2,  1;
  1,  2,  4,  2,  1;
  1,  3,  6,  6,  3,  1;
  1,  3,  9, 10,  9,  3,  1;
  1,  4, 12, 19, 19, 12,  4,  1;
  1,  4, 16, 28, 38, 28, 16,  4,  1;
  1,  5, 20, 44, 66, 66, 44, 20,  5,  1;

Reinhard Zumkeller, Rows n = 0..100 of triangle, flattened
F. Al-Kharousi, R. Kehinde, and A. Umar, Combinatorial results for certain semigroups of partial isometries of a finite chain, The Australasian Journal of Combinatorics, Vol. 58, No. 3 (2014), pp. 363-375.
Tewodros Amdeberhan, Mahir Bilen Can and Victor H. Moll, Broken bracelets, Molien series, paraffin wax and the elliptic curve of conductor 48, SIAM Journal of Discrete Math., Vol. 25, No. 4 (2011), p. 1843-1859; arXiv preprint, arXiv:1106.4693 [math.CO], 2011. See Theorem 2.8.
Johann Cigler, Some remarks on Rogers-Szegö polynomials and Losanitsch's triangle, arXiv:1711.03340 [math.CO], 2017.
Sahir Gill, Bounds for Region Containing All Zeros of a Complex Polynomial, International Journal of Mathematical Analysis Vol. 12, No. 7 (2018), pp. 325-333.
Stephen G. Hartke and A. J. Radcliffe, Signatures of Strings, Annals of Combinatorics, Vol. 17, No. 1 (March, 2013), pp. 131-150.
Rethinasamy K. Kittappa, Combinatorial enumeration of rectangular kolam designs of the Tamil land, Abstracts Amer. Math. Soc., Vol. 29, No. 1 (2008), p. 24 (Abstract 1035-05-543).
Wolfdieter Lang, Illustration of initial rows of triangle.
S. M. Losanitsch, Die Isomerie-Arten bei den Homologen der Paraffin-Reihe, Chem. Ber. Vol. 30 (1897), pp. 1917-1926.
S. M. Losanitsch, Die Isomerie-Arten bei den Homologen der Paraffin-Reihe, Chem. Ber., Vol. 30 (1897), pp. 1917-1926. (Annotated scanned copy)
Ministry of Foreign Affairs of Serbia, List of the Ministers for Foreign Affairs Since the Forming of the First Government in 1811-Sima Lozanic.
Jesse Pajwani, Herman Rohrbach, and Anna M. Viergever, Compactly supported A^1-Euler characteristics of symmetric powers of cellular varieties, arXiv:2404.08486 [math.AG], 2024. See p. 15.
N. J. A. Sloane, Classic Sequences.
Eric Weisstein's World of Mathematics, Losanitsch's Triangle.
Wikipedia, Sima Lozanic.
Index entries for sequences related to trees

Cf. A007318, A034852, A051159, A055138, A102541, A228570, A228572.
Columns: A008619, A087811, A005993 - A005995, A018210 - A018214, A062136, A141783.
Triangle sums (see the comments): A005418 (Row), A011782 (Related to Row2), A102526 (Related to Kn11, Kn12, Kn13, Kn21, Kn22, Kn23), A005207 (Kn3, Kn4), A005418 (Fi1, Fi2), A102543 (Ca1, Ca2), A192928 (Gi1, Gi2), A005683 (Ze3, Ze4).
Sums of squares of terms in rows equal A211208.

a034851 n k = a034851_row n !! k
a034851_row 0 = [1]
a034851_row 1 = [1,1]
a034851_row n = zipWith (-) (zipWith (+) ([0] ++ losa) (losa ++ [0]))
                            ([0] ++ a204293_row (n-2) ++ [0])
   where losa = a034851_row (n-1)
a034851_tabl = map a034851_row [0..]
-- Reinhard Zumkeller, Jan 14 2012

A034851 := proc(n,k) option remember; local t; if k = 0 or k = n then return(1) fi; if n mod 2 = 0 and k mod 2 = 1 then t := binomial(n/2-1,(k-1)/2) else t := 0; fi; A034851(n-1,k-1)+A034851(n-1,k)-t; end: seq(seq(A034851(n, k), k=0..n), n=0..11);

t[n_?EvenQ, k_?OddQ] := Binomial[n, k]/2; t[n_, k_] := (Binomial[n, k] + Binomial[Quotient[n, 2], Quotient[k, 2]])/2; Flatten[Table[t[n, k], {n, 0, 12}, {k, 0, n}]](* Jean-François Alcover, Feb 07 2012, after PARI *)

{T(n, k) = (1/2) *(binomial(n, k) + binomial(n%2, k%2) * binomial(n\2, k\2))}; /* Michael Somos, Oct 20 1999 */

T(n, k) = (1/2) * (A007318(n, k) + A051159(n, k)).
G.f. for k-th column (if formatted as lower triangular matrix a(n, k)): x^k*Pe(floor((k+1)/2), x^2)/(((1-x)^(k+1))*(1+x)^(floor((k+1)/2))), where Pe(n, x^2) := Sum_{m=0..floor(n/2)} A034839(n, m)*x^(2*m) (row polynomials of Pascal array even numbered columns). - Wolfdieter Lang, May 08 2001
a(n, k) = a(n-1, k-1) + a(n-1, k) - C(n/2-1, (k-1)/2), where the last term is present only if n is even and k is odd (see Sloane link).
T(n, k) = T(n-2, k-2) + T(n-2, k) + C(n-2, k-1), n > 1.
Let P(n, x, y) = Sum_{m=0..n} a(n, m)*x^m*y^(n-m), then for x > 0, y > 0 we have P(n, x, y) = (x+y)*P(n-1, x, y) for n odd and P(n, x, y) = (x+y)*P(n-1, x, y) - x*y*(x^2+y^2)^((n-2)/2) for n even. - Gerald McGarvey, Feb 15 2005
T(n, k) = T(n-1, k-1) + T(n-1, k) - A204293(n-2, k-1), 0 < k <= n and n > 1. - Reinhard Zumkeller, Jan 14 2012
From Christopher Hunt Gribble, Feb 25 2014: (Start)
It appears that:
T(n,k) = C(n,k)/2,                        n even, k odd;
T(n,k) = (C(n,k) + C(n/2,k/2))/2,         n even, k even;
T(n,k) = (C(n,k) + C((n-1)/2,(k-1)/2))/2, n odd,  k odd;
T(n,k) = (C(n,k) + C((n-1)/2,k/2))/2,     n odd,  k even.
(End)

More terms from James Sellers, May 04 2000

Name edited by Johannes W. Meijer, Aug 26 2013

A254414 Number A(n,k) of tilings of a k X n rectangle using polyominoes of shape I; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 4, 7, 4, 1, 1, 8, 29, 29, 8, 1, 1, 16, 124, 257, 124, 16, 1, 1, 32, 533, 2408, 2408, 533, 32, 1, 1, 64, 2293, 22873, 50128, 22873, 2293, 64, 1, 1, 128, 9866, 217969, 1064576, 1064576, 217969, 9866, 128, 1, 1, 256, 42451, 2078716, 22734496, 50796983, 22734496, 2078716, 42451, 256, 1

Offset: 0

Alois P. Heinz, Jan 30 2015

A polyomino of shape I is a rectangle of width 1.

All columns (or rows) are linear recurrences with constant coefficients. An upper bound on the order of the recurrence is A005683(k+2). This upper bound is exact for at least 1 <= k <= 10. - Andrew Howroyd, Dec 23 2019

			Square array A(n,k) begins:
  1,  1,    1,      1,        1,          1,            1, ...
  1,  1,    2,      4,        8,         16,           32, ...
  1,  2,    7,     29,      124,        533,         2293, ...
  1,  4,   29,    257,     2408,      22873,       217969, ...
  1,  8,  124,   2408,    50128,    1064576,     22734496, ...
  1, 16,  533,  22873,  1064576,   50796983,   2441987149, ...
  1, 32, 2293, 217969, 22734496, 2441987149, 264719566561, ...

Liang Kai, Table of n, a(n) for n = 0..1377 (terms 0..495 from Andrew Howroyd)
Wikipedia, Polyomino

Columns (or rows) k=0-7 give: A000012, A011782, A052961, A254124, A254125, A254126, A254458, A254607.
Main diagonal gives: A254127.
Cf. A005683.

step(v,S)={vector(#v, i, sum(j=1, #v, v[j]*2^hammingweight(bitand(S[i], S[j]))))}
mkS(k)={apply(b->bitand(b,2*b+1), [2^(k-1)..2^k-1])}
T(n,k)={if(k<2, if(k==0||n==0, 1, 2^(n-1)), my(S=mkS(k), v=vector(#S, i, i==1)); for(n=1, n, v=step(v,S)); vecsum(v))} \\ Andrew Howroyd, Dec 23 2019

A331406 Array read by antidiagonals: A(n,m) is the number of ways to place non-adjacent counters on the black squares of a 2n-1 X 2m-1 checker board.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 4, 1, 1, 8, 17, 8, 1, 1, 16, 73, 73, 16, 1, 1, 32, 314, 689, 314, 32, 1, 1, 64, 1351, 6556, 6556, 1351, 64, 1, 1, 128, 5813, 62501, 139344, 62501, 5813, 128, 1, 1, 256, 25012, 596113, 2976416, 2976416, 596113, 25012, 256, 1

Offset: 0

Andrew Howroyd, Jan 16 2020

The array has been extended with A(n,0) = A(0,m) = 1 for consistency with recurrences and existing sequences.
The checker board is such that the black squares are in the corners and adjacent means diagonally adjacent, since the white squares are not included.
Equivalently, A(n,m) is the number of independent sets in the generalized Aztec diamond graph E(L_{2n-1}, L_{2m-1}). The E(L_{2n-1},L_{2m-1}) Aztec diamond is the graph with vertices {(a,b) : 1<=a<=2n-1, 1<=b<=2m-1, a+b even} and edges between (a,b) and (c,d) if and only if |a-b|=|c-d|=1.
All rows (or columns) are linear recurrences with constant coefficients. For n > 0 an upper bound on the order of the recurrence is A005418(n-1), which is the number of binary words of length n up to reflection.
A stronger upper bound on the recurrence order is A005683(n+2). This upper bound is exact for at least 1 <= n <= 10. This bound follows from considerations about which patterns of counters in a row are redundant because they attack the same points in adjacent rows. For example, the pattern of counters 1101101 is equivalent to 1111111 because they each attack all points in the neighboring rows.
It appears that the denominators for the recurrences are the same as those for the rows and columns of A254414. This suggests there is a connection.

			Array begins:
===========================================================
n\m | 0  1    2      3        4          5            6
----+------------------------------------------------------
  0 | 1  1    1      1        1          1            1 ...
  1 | 1  2    4      8       16         32           64 ...
  2 | 1  4   17     73      314       1351         5813 ...
  3 | 1  8   73    689     6556      62501       596113 ...
  4 | 1 16  314   6556   139344    2976416     63663808 ...
  5 | 1 32 1351  62501  2976416  142999897   6888568813 ...
  6 | 1 64 5813 596113 63663808 6888568813 748437606081 ...
  ...
Case A(2,2): the checker board has 5 black squares as shown below.
      __    __
     |__|__|__|
      __|__|__
     |__|  |__|
If a counter is placed on the central square then a counter cannot be placed on the other 4 squares, otherwise counters can be placed in any combination. The total number of arrangements is then 1 + 2^4 = 17, so A(2, 2) = 17.

Andrew Howroyd, Table of n, a(n) for n = 0..860
Eric Weisstein's World of Mathematics, Independent Vertex Set
Wikipedia, Independent set
Z. Zhang, Merrifield-Simmons index of generalized Aztec diamond and related graphs, MATCH Commun. Math. Comput. Chem. 56 (2006) 625-636.

Rows n=0..5 are A000012, A000079, A018902, A254150, A254151, A254152.
Main diagonal is A054867.
Cf. A005418, A005683, A089934, A254414.

step1(v)={vector(#v/2, t, my(i=t-1); sum(j=0, #v-1, if(!bitand(i, bitor(j, j>>1)), v[1+j])))}
step2(v)={vector(#v*2, t, my(i=t-1); sum(j=0, #v-1, if(!bitand(i, bitor(j, j<<1)), v[1+j])))}
T(n,k)={if(n==0||k==0, 1, my(v=vector(2^k, i, 1)); for(i=2, n, v=step2(step1(v))); vecsum(v))}
{ for(n=0, 7, for(k=0, 7, print1(T(n,k), ", ")); print) }

A(n,m) = A(m,n).

cp's OEIS Frontend

A034851 Rows of Losanitsch's triangle T(n, k), n >= 0, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A254414 Number A(n,k) of tilings of a k X n rectangle using polyominoes of shape I; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A331406 Array read by antidiagonals: A(n,m) is the number of ways to place non-adjacent counters on the black squares of a 2n-1 X 2m-1 checker board.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A068930 Number of incongruent ways to tile a 5 X 2n room with 1x2 Tatami mats. At most 3 Tatami mats may meet at a point.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions