A017907 -id:A017907 - cp's OEIS frontend

A220122 Number A(n,k) of tilings of a k X n rectangle using integer-sided rectangular tiles of area k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 2, 2, 5, 1, 1, 1, 1, 1, 3, 3, 8, 1, 1, 1, 1, 2, 1, 9, 4, 13, 1, 1, 1, 1, 1, 4, 1, 16, 6, 21, 1, 1, 1, 1, 2, 1, 7, 2, 35, 9, 34, 1, 1, 1, 1, 1, 3, 1, 13, 3, 65, 13, 55, 1, 1, 1, 1, 2, 2, 9, 1, 46, 4, 143, 19, 89, 1, 1

Offset: 0

Alois P. Heinz, Dec 05 2012

Row n gives: 1 followed by period A003418(n): (1, A000045(n+1), ...) repeated; offset 0.

			A(4,4) = 9, because there are 9 tilings of a 4 X 4 rectangle using integer-sided rectangular tiles of area 4:
._._._._.  ._______.  .___.___.  ._.___._.  ._______.
| | | | |  |_______|  |   |   |  | |   | |  |_______|
| | | | |  |_______|  |___|___|  | |___| |  |   |   |
| | | | |  |_______|  |   |   |  | |   | |  |___|___|
|_|_|_|_|  |_______|  |___|___|  |_|___|_|  |_______|
._._.___.  ._______.  .___._._.  .___.___.
| | |   |  |_______|  |   | | |  |   |   |
| | |___|  |_______|  |___| | |  |___|___|
| | |   |  |   |   |  |   | | |  |_______|
|_|_|___|  |___|___|  |___|_|_|  |_______|
Square array A(n,k) begins:
1, 1,  1,  1,   1, 1,    1, 1,    1,  1,   1, ...
1, 1,  1,  1,   1, 1,    1, 1,    1,  1,   1, ...
1, 1,  2,  1,   2, 1,    2, 1,    2,  1,   2, ...
1, 1,  3,  2,   3, 1,    4, 1,    3,  2,   3, ...
1, 1,  5,  3,   9, 1,    7, 1,    9,  3,   5, ...
1, 1,  8,  4,  16, 2,   13, 1,   16,  4,   9, ...
1, 1, 13,  6,  35, 3,   46, 1,   35,  6,  15, ...
1, 1, 21,  9,  65, 4,   88, 2,   65,  9,  26, ...
1, 1, 34, 13, 143, 5,  209, 3,  250, 13,  44, ...
1, 1, 55, 19, 281, 6,  473, 4,  495, 37,  75, ...
1, 1, 89, 28, 590, 8, 1002, 5, 1209, 64, 254, ...

Alois P. Heinz, Antidiagonals n = 0..32, flattened

Columns k=0+1, 2-11, 13 give: A000012, A000045(n+1), A000930, A220123, A003520, A220124, A005709, A220125, A220126, A220127, A017905(n+11), A017907(n+13).
Rows n=0+1, 2-10 give: A000012, A040001, A220128, A220129, A220130, A220131, A220132, A220133, A220134, A220135.
Main diagonal gives: A182106.

b:= proc(n, l) option remember; local i, k, m, s, t;
      if max(l[])>n then 0 elif n=0 or l=[] then 1
    elif min(l[])>0 then t:=min(l[]); b(n-t, map(h->h-t, l))
    else for k do if l[k]=0 then break fi od; s, m:=0, nops(l);
         for i from k to m while l[i]=0 do if irem(m, 1+i-k, 'q')=0
           and q<=n then s:= s+ b(n, [l[j]$j=1..k-1, q$j=k..i,
           l[j]$j=i+1..m]) fi od; s
      fi
    end:
A:= (n, k)-> b(n, [0$k]):
seq(seq(A(n, d-n), n=0..d), d=0..14);

b[n_, l_] := b[n, l] = Module[{i, k, m, s, t}, Which[Max[l] > n, 0, n == 0 || l == {}, 1, Min[l] > 0, t = Min[l]; b[n-t, l-t], True, k = Position[l, 0, 1][[1, 1]]; {s, m} = {0, Length[l]}; For[ i = k , i <= m && l[[i]] == 0, i++, If[Mod[m, 1+i-k ] == 0 && (q = Quotient[m, 1+i-k]) <= n, s = s+b[n, Join[ l[[1 ;; k-1]], Array[q &, i-k+1], l[[i+1 ;; m]] ]]]]; s]]; a[n_, k_] := b[n, Array[0&, k]]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Dec 19 2013, translated from Maple *)

For prime p column p has g.f.: 1/(1-x-x^p) or a_p(n) = Sum_{j=0..floor(n/p)} C(n-(p-1)*j,j).

A141539 Square array A(n,k) of numbers of length n binary words with at least k "0" between any two "1" digits (n,k >= 0), read by antidiagonals.

Original entry on oeis.org

1, 1, 2, 1, 2, 4, 1, 2, 3, 8, 1, 2, 3, 5, 16, 1, 2, 3, 4, 8, 32, 1, 2, 3, 4, 6, 13, 64, 1, 2, 3, 4, 5, 9, 21, 128, 1, 2, 3, 4, 5, 7, 13, 34, 256, 1, 2, 3, 4, 5, 6, 10, 19, 55, 512, 1, 2, 3, 4, 5, 6, 8, 14, 28, 89, 1024, 1, 2, 3, 4, 5, 6, 7, 11, 19, 41, 144, 2048, 1, 2, 3, 4, 5, 6, 7, 9, 15, 26, 60, 233, 4096

Offset: 0

Alois P. Heinz, Aug 15 2008

A(n,k+1) = A(n,k) - A143291(n,k).
From Gary W. Adamson, Dec 19 2009: (Start)
Alternative method generated from variants of an infinite lower triangle T(n) = A000012 = (1; 1,1; 1,1,1; ...) such that T(n) has the leftmost column shifted up n times. Then take lim_{k->infinity} T(n)^k, obtaining a left-shifted vector considered as rows of an array (deleting the first 1) as follows:
  1, 2, 4, 8, 16, 32, 64, 128, 256, ... = powers of 2
  1, 1, 2, 3,  5,  8, 13,  21,  34, ... = Fibonacci numbers
  1, 1, 1, 2,  3,  4,  6,   9,  13, ... = A000930
  1, 1, 1, 1,  2,  3,  4,   5,   7, ... = A003269
  ... with the next rows A003520, A005708, A005709, ... such that beginning with the Fibonacci row, the succession of rows are recursive sequences generated from a(n) = a(n-1) + a(n-2); a(n) = a(n-1) + a(n-3), ... a(n) = a(n-1) + a(n-k); k = 2,3,4,... Last, columns going up from the topmost 1 become rows of triangle A141539. (End)

			A(4,2) = 6, because 6 binary words of length 4 have at least 2 "0" between any two "1" digits: 0000, 0001, 0010, 0100, 1000, 1001.
Square array A(n,k) begins:
    1,  1,  1,  1,  1,  1,  1,  1, ...
    2,  2,  2,  2,  2,  2,  2,  2, ...
    4,  3,  3,  3,  3,  3,  3,  3, ...
    8,  5,  4,  4,  4,  4,  4,  4, ...
   16,  8,  6,  5,  5,  5,  5,  5, ...
   32, 13,  9,  7,  6,  6,  6,  6, ...
   64, 21, 13, 10,  8,  7,  7,  7, ...
  128, 34, 19, 14, 11,  9,  8,  8, ...

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

Cf. column k=0: A000079, k=1: A000045(n+2), k=2: A000930(n+2), A068921, A078012(n+5), k=3: A003269(n+4), A017898(n+7), k=4: A003520(n+4), A017899(n+9), k=5: A005708(n+5), A017900(n+11), k=6: A005709(n+6), A017901(n+13), k=7: A005710(n+7), A017902(n+15), k=8: A005711(n+7), A017903(n+17), k=9: A017904(n+19), k=10: A017905(n+21), k=11: A017906(n+23), k=12: A017907(n+25), k=13: A017908(n+27), k=14: A017909(n+29).
Main diagonal gives A000027(n+1).
A(2n,n) gives A000217(n+1)
A(3n,n) gives A008778.
A(3n,2n) gives A034856(n+1).
A(2n,3n) gives A005408.
A(2^n-1,n) gives A376697.
See also A143291.

A:= proc(n, k) option remember;
      if k=0 then 2^n
    elif n<=k and n>=0 then n+1
    elif n>0 then A(n-1, k) +A(n-k-1, k)
    else          A(n+1+k, k) -A(n+k, k)
      fi
    end:
seq(seq(A(n, d-n), n=0..d), d=0..15);

a[n_, k_] := a[n, k] = Which[k == 0, 2^n, n <= k && n >= 0, n+1, n > 0, a[n-1, k] + a[n-k-1, k], True, a[n+1+k, k] - a[n+k, k]]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 15}] // Flatten (* Jean-François Alcover, Dec 17 2013, translated from Maple *)

G.f. of column k: x^(-k)/(1-x-x^(k+1)).

A(n,k) = 2^n if k=0, otherwise A(n,k) = n+1 if n<=k, otherwise A(n,k) = A(n-1,k) + A(n-k-1,k).

A329146 Triangle read by rows: T(n,k) is the number of subsets of {1,...,n} such that the difference between any two elements is k or greater, 1 <= k <= n.

Original entry on oeis.org

2, 4, 3, 8, 5, 4, 16, 8, 6, 5, 32, 13, 9, 7, 6, 64, 21, 13, 10, 8, 7, 128, 34, 19, 14, 11, 9, 8, 256, 55, 28, 19, 15, 12, 10, 9, 512, 89, 41, 26, 20, 16, 13, 11, 10, 1024, 144, 60, 36, 26, 21, 17, 14, 12, 11, 2048, 233, 88, 50, 34, 27, 22, 18, 15, 13, 12, 4096, 377, 129

Offset: 1

Gerhard Kirchner, Nov 06 2019

The restriction "the difference between any two elements is k or greater" does not apply to subsets with fewer than two elements.
Therefore T(n,k) = n+1 is valid not only for n=k, but also for n < k. These terms do not occur in the triangular matrix, but they help to simplify formula(3).
T(n,k) is, for 1 <= k <= 16, a subsequence of another sequence:
T(n,1) =  A000079(n)
T(n,2) =  A000045(n+2)
T(n,3) =  A000930(n+2)
T(n,4) =  A003269(n+4)
T(n,5) =  A003520(n+4)
T(n,6) =  A005708(n+5)
T(n,7) =  A005709(n+6)
T(n,8) =  A005710(n+7)
T(n,9) =  A005711(n+7)
T(n,10) = A017904(n+19)
T(n,11) = A017905(n+21)
T(n,12) = A017906(n+23)
T(n,13) = A017907(n+25)
T(n,14) = A017908(n+27)
T(n,15) = A017909(n+29)
T(n,16) = A291149(n+16)
Note the recurrence formula(3) below: T(n,k) = T(n-1,k) + T(n-k,k), n >= 2*k.
As to the corresponding recurrence A..(n) = A..(n-1) + A..(n-k), see definition (1 <= k <= 9) or formula (k=13) or b-files in the remaining cases.

			a(1) = T(1,1) = |{}, {1}| = 2
a(2) = T(2,1) = |{}, {1}, {2}, {1,2}| = 4
a(3) = T(2,2) = |{}, {1}, {2}| = 3
a(4) = T(3,1) = |{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}| = 8
a(5) = T(3,2) = |{}, {1}, {2}, {3}, {1,3}| = 5
etc.
The triangle begins:
   2;
   4,  3;
   8,  5,  4;
  16,  8,  6,  5;
  32, 13,  9,  7,  6;
  ...

Gerhard Kirchner, First 141 rows of T(n,k): Table of n, a(n) for n = 1..10011

Cf. A000079, A000045, A000930, A003269, A003520, A005708, A005709, A005710.

Cf. A005711, A017904, A017905, A017906, A017907, A017908, A017909, A291149.

T(n,k) = sum(j=0, ceil(n/k), binomial(n-(k-1)*(j-1), j)); \\ Andrew Howroyd, Nov 06 2019

Let g(n,k,j) be the number of subsets of {1,...,n} with j elements such that the difference between any two elements is k or greater. Then
(1) T(n,k) = Sum_{j = 0..n} g(n,k,j)
(2) g(n,k,j) = binomial(n-(k-1)*(j-1),j) with the convention binomial(m,j)=0 for j > m
(3) T(n,k) = T(n-1,k) + T(n-k,k), n >= 2*k
or: T(n,k) = n+1 for n <= k and T(n,k) = T(n-1,k) + T(n-k,k) for n > k (see comments).
Formula(1) is evident.
Proof of formula(2):
Let C(n,k,j) be the class of subsets of {1,...,n} with j elements such that the difference between any two elements is k or greater. Let S be one of these subsets and let us write it as a j-tuple (c(1),..,c(j)) with c(i+1)-c(i)>=k, 1<=iIn particular, the number of subsets of C(m,1,j) is binomial(m,j), the basic tuple is (1,...,j) and the generating tuple is (d(1),...,d(j)) with 0 <= d(1) <= ... <= d(j) <= m-j.
With m-j = n-(j-1)*k-1, i.e., m = n-(j-1)*(k-1), the numbers of subsets in C(n,k,j) and C(m,1,j) are equal: g(n,k,j) = binomial(n-(k-1)*(j-1),j) qed
Proof of formula(3):
Using the binomial recurrence binomial(m,j) = binomial(m-1,j) + binomial(m-1,j-1) for m = n-(j-1)*(k-1), we find:
T(n,k) = Sum_{j = 0..n} binomial(n-(k-1)*(j-1),j)
       = Sum_{j = 0..n-1} binomial(n-1-(k-1)*(j-1),j)
          + Sum_{j = 1..n} binomial(n-1-(k-1)*(j-1),j-1)
       = T(n-1,k) + Sum_{j = 0..n-1} binomial(n-1-(k-1)*j,j)
       = T(n-1,k) + Sum_{j = 0..n-k} binomial(n-k-(k-1)*(j-1),j)
       = T(n-1,k) + T(n-k,k) qed
T(n-k,k) must be known in this recurrence, therefore n >= 2*k.
For k <= n < 2*k, formula(1) must be applied.

Showing 1-3 of 3 results.

cp's OEIS Frontend

A220122 Number A(n,k) of tilings of a k X n rectangle using integer-sided rectangular tiles of area k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A141539 Square array A(n,k) of numbers of length n binary words with at least k "0" between any two "1" digits (n,k >= 0), read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A329146 Triangle read by rows: T(n,k) is the number of subsets of {1,...,n} such that the difference between any two elements is k or greater, 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula