Steffen Eger - cp's OEIS frontend

User: Steffen Eger

Steffen Eger has authored 5 sequences.

A191588 T(m,n) is the number of ways to split two strings of length m and n, respectively, into the same number of nonempty parts such that at least one of the corresponding parts has length 1 and such that the parts have at most size 2.

1, 1, 1, 0, 2, 3, 0, 1, 3, 7, 0, 0, 3, 7, 13, 0, 0, 1, 6, 17, 27, 0, 0, 0, 4, 14, 36, 61, 0, 0, 0, 1, 10, 35, 77, 133, 0, 0, 0, 0, 5, 25, 81, 173, 287, 0, 0, 0, 0, 1, 15, 65, 183, 387, 633, 0, 0, 0, 0, 0, 6, 41, 161, 421, 857, 1407, 0, 0, 0, 0, 0, 1, 21, 112, 385, 969, 1911, 3121, 0, 0, 0, 0, 0, 0, 7, 63, 294, 918, 2211, 4287, 6943, 0, 0, 0, 0, 0, 0, 1, 28, 182, 742, 2181, 5040, 9619, 15517, 0, 0

Offset: 1

Steffen Eger, Jun 09 2011

Diagonal appears to be A098479. - Joerg Arndt, Jun 09 2011

T(m,n) is the number of lattice paths from (0,0) to (m,n) with steps in {(1,1),(1,2),(2,1)}. - Steffen Eger, Sep 25 2012

			1
1 1
0 2 3
0 1 3 7
0 0 3 7 13
0 0 1 6 17 27
0 0 0 4 14 36 61
0 0 0 1 10 35 77 133
0 0 0 0  5 25 81 173 287
0 0 0 0  1 15 65 183 387 633
0 0 0 0  0  6 41 161 421 857 1407
0 0 0 0  0  1 21 112 385 969 1911 3121
0 0 0 0  0  0  7  63 294 918 2211 4287  6943
0 0 0 0  0  0  1  28 182 742 2181 5040  9619 15517
0 0 0 0  0  0  0   8  92 504 1842 5134 11508 21602 34755
Examples:
For m=3, n=2, we have
  x xx     xx x
  y  y      y y
For m=3, n=3, we have
  x xx     xx x   x x x
  yy y      y yy  y y y
For m=4, n=4, we have
  x xx x   x xx x   xx x x   xx x x   x x xx  x x xx   x x x x
  yy y y   y y yy   y yy y    y y yy  y yy y  yy y y   y y y y

Steffen Eger, On the Number of Many-to-Many Alignments of N Sequences, arXiv:1511.00622 [math.CO], 2015.

Cf. A180091, A185287, A098479 (diagonal).

t[m_, n_] /; m >= n := t[m, n] = Binomial[n, 2n - m] + Sum[Binomial[k, 2k - n]*Binomial[2k - n, 3k - n - m], {k, 2, n-1}]; t[m_, n_] /; m < n := t[m, n]; Table[t[n, m], {n, 1, 14}, {m, 1, n}] // Flatten (* Jean-François Alcover, Jan 07 2013, from formula *)

For m >= n: T(m,n) = C(n,2*n-m) + Sum_{k=2..n-1} C(k,2*k-n)*C(2*k-n,3*k-n-m) (note: C(2*k-n,3*k-n-m) = C(2*k-n,m-k)) where C(n,k) = binomial(n,k) for n >= k and 0 otherwise.

Symmetrically extended by T(n,m) = T(m,n).

A187152 Triangle T(m,n), read by rows: Number of bipartite labeled graphs (V,E) with vertices A={a_1,...,a_m} and B={b_1,...,b_n} where for any vertex in V at most one edge in E is allowed. Additionally, an edge {a_k,b_l} is allowed only when |k-l|<=1.

Original entry on oeis.org

2, 3, 7, 3, 10, 22, 3, 10, 32, 71, 3, 10, 32, 103, 228, 3, 10, 32, 103, 331, 733, 3, 10, 32, 103, 331, 1064, 2356, 3, 10, 32, 103, 331, 1064, 3420, 7573, 3, 10, 32, 103, 331, 1064, 3420, 10993, 24342, 3, 10, 32, 103, 331, 1064, 3420, 10993, 35335, 78243

Offset: 1

Steffen Eger, Mar 06 2011

This also has the obvious corresponding string alignment interpretation where we allow only one-to-one alignments between strings a_1...a_m and b_1...b_n, and additionally demand that aligned characters have a distance of at most 1.

			2;
3 7;
3 10 22;
3 10 32 71;
3 10 32 103 228;
3 10 32 103 331 733;
3 10 32 103 331 1064 2356;
3 10 32 103 331 1064 3420 7573;
3 10 32 103 331 1064 3420 10993 24342;
3 10 32 103 331 1064 3420 10993 35335 78243;
3 10 32 103 331 1064 3420 10993 35335 113578 251498;

Cf. A033505, A030186.

For m >= n:
T(m,n) =
   A030186(m)   if m = n
   A033505(n+1) if m >= n+1
Symmetrically extended by T(n,m)=T(m,n).
Both the diagonal and the off-diagonals follow the recurrence a(n) = 3*a(n-1) + a(n-2) - a(n-3), n >= 3, with different initial conditions; 2,7,22 and 3,10,32, respectively.

A185287 R(m,n) is the number of ways to split two strings x and y of length m and n, respectively, into the same number of nonempty parts such that at least one of the corresponding parts has length 1 and such that the parts of the y string have at most size 2.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 3, 3, 0, 0, 1, 4, 5, 3, 0, 0, 1, 5, 8, 7, 3, 0, 0, 1, 6, 12, 13, 7, 0, 0, 0, 1, 7, 17, 22, 16, 6, 0, 0, 0, 1, 8, 23, 35, 32, 17, 4, 0, 0, 0, 1, 9, 30, 53, 58, 39, 14, 0, 0, 0, 0, 1, 10, 38, 77, 98, 80, 40, 10, 0, 0

Offset: 1

Steffen Eger, Feb 20 2011

			1    0    0    0    0    0    0    0    0    0    0    0
1    1    2    0    0    0    0    0    0    0    0    0
1    2    3    3    3    0    0    0    0    0    0    0
1    3    5    7    7    6    4    0    0    0    0    0
1    4    8   13   16   17   14   10    5    0    0    0
1    5   12   22   32   39   40   35   25   15    6    0
1    6   17   35   58   80   95   97   86   65   41   21
1    7   23   53   98  151  201  233  238  213  167  112
1    8   30   77  157  267  392  505  577  587  532  427
1    9   38  108  241  448  718 1013 1273 1436 1458 1333
1   10   47  147  357  720 1250 1912 2612 3217 3590 3640
1   11   57  195  513 1116 2086 3434 5056 6728 8146 9011

Cf. A180091.

r[m_, n_] := Binomial[m-1, n-1] + Sum[ Binomial[k, 2k-n]*Binomial[k+m-n-1, 2k-n-1], {k, 2, n-1}]; r[m_, n_] /; n > 2m-1 = 0; Flatten[ Table[ r[m-k+1, k], {m, 1, 12}, {k, 1, m}]] (* Jean-François Alcover, Nov 07 2011 *)

PARI
```
C(n,k)=if(nJoerg Arndt, Mar 11 2011 */
```

R(m,n) = C(m-1,n-1) + Sum_{k=2..n-1} C(m+k-n-1,2*k-n-1)*C(k,2*k-n).

A183109 Triangle read by rows: T(n,m) = number of n X m binary matrices with no zero rows or columns (n >= 1, 1 <= m <= n).

Original entry on oeis.org

1, 1, 7, 1, 25, 265, 1, 79, 2161, 41503, 1, 241, 16081, 693601, 24997921, 1, 727, 115465, 10924399, 831719761, 57366997447, 1, 2185, 816985, 167578321, 26666530801, 3776451407065, 505874809287625

Offset: 1

Steffen Eger, Feb 01 2011

T(n,m) = T(m,n) is also the number of complete alignments between two strings of sizes m and n, respectively; i.e. the number of complete matchings in a bipartite graph
From Manfred Boergens, Jul 25 2021: (Start)
The matrices in the definition are a superset of the matrices in the comment to A019538 by Manfred Boergens.
T(n,m) is the number of coverings of [n] by tuples (A_1,...,A_m) in P([n])^m with nonempty A_j, with P(.) denoting the power set (corrected for clarity by Manfred Boergens, May 26 2024). For the disjoint case see A019538.
For tuples with "nonempty" dropped see A092477 and A329943 (amendment by Manfred Boergens, Jun 24 2024). (End)

			Triangle begins:
  1;
  1,    7;
  1,   25,    265;
  1,   79,   2161,     41503;
  1,  241,  16081,    693601,    24997921;
  1,  727, 115465,  10924399,   831719761,   57366997447;
  1, 2185, 816985, 167578321, 26666530801, 3776451407065, 505874809287625;
  ...

Indranil Ghosh, Rows 1..50, flattened
Ch. A. Charalambides, A problem of arrangements on chessboards and generalizations, Discrete Mathematics 27.2 (1979): 179-186. (Generalizations.)
D. E. Knuth, Problem 11243, Am. Math. Montly 113 (8) (2006) page 759.
John Riordan and Paul R. Stein, Arrangements on chessboards, Journal of Combinatorial Theory, Series A 12.1 (1972): 72-80. See Table page 78.

Cf. A218695 (same sequence with restriction m<=n dropped).
Cf. A058482 (this gives the general formula, but values only for m=3).
Main diagonal gives A048291.
Column 2 is A058481.
Cf. A019538, A092477, A329943.

A183109 := proc(n,m)
    add((-1)^j*binomial(m,j)*(2^(m-j)-1)^n,j=0..m) ;
end proc:
seq(seq(A183109(n,m),m=1..n),n=1..10) ; # R. J. Mathar, Dec 03 2015

Flatten[Table[Sum[ (-1)^j*Binomial[m, j]*(2^(m - j) - 1)^n, {j, 0, m}], {n, 1, 7}, {m, 1, n}]] (* Indranil Ghosh, Mar 14 2017 *)

tabl(nn) = {for(n=1, nn, for(m = 1, n, print1(sum(j=0, m, (-1)^j*binomial(m, j)*(2^(m - j) - 1)^n),", ");); print(););};
tabl(8); \\ Indranil Ghosh, Mar 14 2017

import math
f = math.factorial
def C(n,r): return f(n)//f(r)//f(n - r)
def T(n,m):
    return sum((-1)**j*C(m,j)*(2**(m - j) - 1)**n for j in range (m+1))
i=1
for n in range(1,21):
    for m in range(1, n+1):
        print(str(i)+" "+str(T(n, m)))
        i+=1 # Indranil Ghosh, Mar 14 2017

T(n,m) = Sum_{j=0..m}(-1)^j*C(m, j)*(2^(m-j)-1)^n.
Recursion: T(m,n) = Sum_{k=1..m} T(k,n-1)*C(m,k)*2^k - T(m,n-1).
From Robert FERREOL, Mar 14 2017: (Start)
T(n,m) = Sum_{i = 0 .. n,j = 0 ..m}(-1)^(n+m+i+j)*C(n,i)*C(m,j)*2^(i*j).
Inverse formula of: 2^(n*m) = Sum_{i = 0 .. n , j = 0 ..m} C(n,i)*C(m,j)*T(i,j). (End)
A019538(j) <= a(j). - Manfred Boergens, Jul 25 2021

A180091 a(m,n) is the number of ways to split two strings of length m and n, respectively, into the same number of nonempty parts such that at least one of the corresponding parts has length 1.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 1, 3, 5, 9, 1, 4, 8, 15, 27, 1, 5, 12, 24, 46, 83, 1, 6, 17, 37, 75, 143, 259, 1, 7, 23, 55, 118, 237, 450, 817, 1, 8, 30, 79, 180, 380, 755, 1429, 2599, 1, 9, 38, 110, 267, 592, 1229, 2421, 4570, 8323

Offset: 1

Steffen Eger, Jan 14 2011

a(m,n) is also the number alignments (between two strings) that satisfy weak monotonicity, completeness, and disjointness.
a(m,n) is also the number of monotone lattice paths from (0,0) to (m,n) with steps in {(1,1),(1,2),(1,3),(1,4),...,(2,1),(3,1),(4,1),...}. - Steffen Eger, Sep 25 2012
From Julien Rouyer, Jun 02 2023: (Start)
a(m-1,n-1) is also the number of strictly increasing functions defined on a part of the m-set {1,...,m} that take values in the n-set {1,...,n} and that can't be extended to a greater part of the m-set to give another strictly increasing function (values for m < n can be obtained by symmetry).
a(m-1,n-1) is also the number of solutions to the problem consisting of connecting, with noncrossing edges, some of m points aligned on a straight line to some of n other points aligned on a parallel straight line (each point is connected at most with one other point), in such a way that no additional noncrossing connection can be added.
A direct combinatorial calculation is possible, but time-consuming if m and n are large. (End)
From Thierry Marchant, Oct 30 2024: (Start)
a(m,n) is also the number of maximal antichains in the product of two chains of length m and n.
a(m,n) is also the number of strict chains in the product of two chains of length m and n (a strict chain P in a product of two chains is a chain such that x,y in P implies x_1 different from y_1 and x_2 different from y_2).
a(m,n) is also the number of walks from (0,0) to (m,n) where unit horizontal (+1,0), vertical (0,+1), and diagonal (+1,+1) steps are permitted but a horizontal step cannot be followed by a vertical step, nor vice versa. (End)

			For m=4, n=3, the 5 possibilities are:
a) X XXX   b) XXX X  c) X XX X  d) XX X X   e) X X XX
   YY Y        Y YY     Y  Y Y     Y  Y Y      Y Y Y
The triangle a(m,n) starts in row m=1 with columns 1 <= n <= m as:
  1;
  1,  1;
  1,  2,  3;
  1,  3,  5,   9;
  1,  4,  8,  15,  27;
  1,  5, 12,  24,  46,   83;
  1,  6, 17,  37,  75,  143,  259;
  1,  7, 23,  55, 118,  237,  450,  817;
  1,  8, 30,  79, 180,  380,  755, 1429,  2599;
  1,  9, 38, 110, 267,  592, 1229, 2421,  4570,  8323;
  1, 10, 47, 149, 386,  899, 1948, 3989,  7804, 14698, 26797;
  1, 11, 57, 197, 545, 1334, 3015, 6412, 12987, 25264, 47491, 86659;
From _Julien Rouyer_, Jun 02 2023: (Start)
There are a(5)=T(3,2)=5 strictly increasing functions defined on a part of {1,2,3} that take values in {1,2} and can't be extended keeping the same properties. The 5 functions are defined by
    f(1)=1, f(2)=2;
    g(1)=1, g(2)=3;
    h(1)=2, h(2)=3;
    i(1)=3;
    j(2)=1. (End)

D. Bouyssou, T. Marchant, and M. Pirlot, About maximal antichains in a product of two chains:A catch-all note, arXiv:2410.16243 [math.CO], 2024. See pp. 1, 3, 16-18.
M. A. Covington, The Number of Distinct Alignments of Two Strings, Journal of Quantitative Linguistics, Vol. 11 (2004), Issue 3, pp. 173-182.
S. Eger, Derivation of sequence [broken link]

Cf. A089071 (third column), A108626 (sums of diagonals).
Main diagonal gives A171155.
Cf. A047080.

A180091 := proc(m,n) a := binomial(m-1,n-1); for k from 2 to n-1 do for l from 1 to k-1 do if k-l-1 >= 0 and k-l-1 <= n-k-1 and l-1 >=0 and l-1 <= m+l-k-1 then a := a+ binomial(k,l)*binomial(n-k-1,k-l-1)*binomial(m+l-k-1,l-1); end if; end do: end do: a; end proc: # R. J. Mathar, Feb 01 2011

# The following program gives T(m,n)=a(m+1,n+1) for any m >= 0 and n >= 0:
def T(m,n):
    if n == 0:
        res = 1
    elif n == 1:
        res = max(m,n)
    elif m < n:
        res = T(n,m)
    else:
        res = 0
        for i in range(1,m+1):
            res += T(m-i,n-1)
        for j in range(2,n+1):
            res += T(m-1,n-j)
    return res # Julien Rouyer, Jun 02 2023

For m >= n: a(m,n) = C(m-1,n-1) + Sum_{k=2..n-1} Sum_{i=1..k-1} C(k,i)*C(n-k-1,k-i-1)*C(m+i-k-1,i-1).
Symmetrically extended to m <= n by a(m,n) = a(n,m).
a(n,n) = A171155(n-1).
a(m,n) = Sum_{i=1..m} a(m-i,n-1) + Sum_{j=2..n} a(m-1,n-j). - Julien Rouyer, Jun 02 2023

cp's OEIS Frontend

User: Steffen Eger

A191588 T(m,n) is the number of ways to split two strings of length m and n, respectively, into the same number of nonempty parts such that at least one of the corresponding parts has length 1 and such that the parts have at most size 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A187152 Triangle T(m,n), read by rows: Number of bipartite labeled graphs (V,E) with vertices A={a_1,...,a_m} and B={b_1,...,b_n} where for any vertex in V at most one edge in E is allowed. Additionally, an edge {a_k,b_l} is allowed only when |k-l|<=1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A185287 R(m,n) is the number of ways to split two strings x and y of length m and n, respectively, into the same number of nonempty parts such that at least one of the corresponding parts has length 1 and such that the parts of the y string have at most size 2.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

A183109 Triangle read by rows: T(n,m) = number of n X m binary matrices with no zero rows or columns (n >= 1, 1 <= m <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A180091 a(m,n) is the number of ways to split two strings of length m and n, respectively, into the same number of nonempty parts such that at least one of the corresponding parts has length 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Python

Formula