cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

A114717 Number of linear extensions of the divisor lattice of n.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 5, 1, 2, 2, 1, 1, 5, 1, 5, 2, 2, 1, 14, 1, 2, 1, 5, 1, 48, 1, 1, 2, 2, 2, 42, 1, 2, 2, 14, 1, 48, 1, 5, 5, 2, 1, 42, 1, 5, 2, 5, 1, 14, 2, 14, 2, 2, 1, 2452, 1, 2, 5, 1, 2, 48, 1, 5, 2, 48, 1, 462, 1, 2, 5, 5, 2, 48, 1, 42, 1, 2, 1, 2452, 2, 2, 2, 14, 1, 2452, 2
Offset: 1

Views

Author

Mitch Harris and Antti Karttunen, Dec 27 2005

Keywords

Comments

Notice that only the powers of the primes determine a(n), so a(12) = a(75) = 5.
For prime powers, the lattice is a chain, so there is 1 linear extension.
a(p^1*q^n) = A000108(n+1), the Catalan numbers.
Alternatively, the number of ways to arrange the divisors of n in such a way that no divisor has any of its own divisors following it. E.g., for 12, the following five arrangements are possible: 1,2,3,4,6,12; 1,2,3,6,4,12; 1,2,4,3,6,12; 1,3,2,4,6,12 and 1,3,2,6,4,12. But 1,2,6,4,3,12 is not possible because 3 divides 6 but follows it. Thus a(12)=5. - Antti Karttunen, Jan 11 2006
For n = p1^r1 * p2^r2, the lattice is a grid (r1+1)*(r2+1), whose linear extensions are counted by ((r1+1)*(r2+1))!/Product_{k=0..r2} (r1+1+k)!/k!. Cf. A060854.

References

  • R. Stanley, Enumerative Combinatorics, Vol. 2, Proposition 7.10.3 and Vol. 1, Sec 3.5 Chains in Distributive Lattices.

Links

Crossrefs

Cf. A060854, A114714, A114715, A114716, A119842.

Programs

  • Maple
    with(numtheory):
b:= proc(s) option remember;
      `if`(nops(s)<2, 1, add(`if`(nops(select(y->
       irem(y, x)=0, s))=1, b(s minus {x}), 0), x=s))
    end:
a:= proc(n) local l, m;
      l:= sort(ifactors(n)[2], (x, y)-> x[2]>y[2]);
      m:= mul(ithprime(i)^l[i][2], i=1..nops(l));
      b(divisors(m) minus {1, m})
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Jun 29 2012
  • Mathematica
    b[s_List] := b[s] = If[Length[s]<2, 1, Sum[If[Length[Select[s, Mod[#, x] == 0 &]] == 1, b[Complement[s, {x}]], 0], {x, s}]]; a[n_] := Module[{l, m}, l = Sort[ FactorInteger[n], #1[[2]] > #2[[2]] &]; m = Product[Prime[i]^l[[i]][[2]], {i, 1, Length[l]}]; b[Divisors[m] // Rest // Most]]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, May 28 2015, after Alois P. Heinz *)

A114715 Number A(n,m) of linear extensions of a 2 X n X m lattice; square array A(n,m), n>=1, m>=1, read by antidiagonals.

Original entry on oeis.org

1, 2, 2, 5, 48, 5, 14, 2452, 2452, 14, 42, 183958, 4877756, 183958, 42, 132, 17454844, 20071150430, 20071150430, 17454844, 132, 429, 1941406508, 129586764260850, 6708527580006468, 129586764260850, 1941406508, 429
Offset: 1

Views

Author

Mitch Harris, Dec 27 2005

Keywords

Examples

			Square array A(n,m) begins:
   1,      2,           5,               14, ...
   2,     48,        2452,           183958, ...
   5,   2452,     4877756,      20071150430, ...
  14, 183958, 20071150430, 6708527580006468, ...

References

  • Stanley, R., Enumerative Combinatorics, Vol. 2, Proposition 7.10.3 and Vol. 1, Sec 3.5 Chains in Distributive Lattices.

Links

Crossrefs

Cf. A000108, A114714, A114716, A114717.
Main diagonal gives A370257.

Programs

  • Maple
    b := proc(l) option remember; local n; n:= nops(l);
      `if`({seq(l[i][], i=1..n)}={0}, 1, add(`if`(l[i][1]>l[i][2] and
       l[i][1]>l[i+1][1], b(subsop(i=[l[i][1]-1, l[i][2]], l)), 0),
       i=1..n-1)+ add(`if`(l[i][2]>l[i+1][2], b(subsop(i=[l[i][1],
       l[i][2]-1], l)), 0), i=1..n-1)+ `if`(l[n][1]>l[n][2],
       b(subsop(n=[l[n][1]-1, l[n][2]], l)), 0)+ `if`(l[n][2]>0,
       b(subsop(n=[l[n][1], l[n][2]-1], l)), 0))
     end:
A:= (n, m)-> `if`(m>=n, b([[m$2]$n]), b([[n$2]$m])):
seq(seq(A(n, d+1-n), n=1..d), d=1..8);  # Alois P. Heinz, Jun 29 2012
  • Mathematica
    b[l_List] := b[l] = With[{n = Length[l]}, If[Union[Table[l[[i]], {i, 1, n}] // Flatten] == {0}, 1, Sum[If[l[[i, 1]] > l[[i, 2]] && l[[i, 1]] > l[[i+1, 1]], b[ReplacePart[l, i -> {l[[i, 1]]-1, l[[i, 2]]}]], 0], {i, 1, n-1}] + Sum[If[l[[i, 2]] > l[[i+1, 2]], b[ReplacePart[l, i -> {l[[i, 1]], l[[i, 2]]-1}]], 0], {i, 1, n-1}] + If[l[[n, 1]] > l[[n, 2]], b[ReplacePart[l, n -> {l[[n, 1]]-1, l[[n, 2]]} ]], 0] + If[l[[n, 2]] > 0, b[ReplacePart[l, n -> {l[[n, 1]], l[[n, 2]]-1}]], 0]]] ; A[n_, m_] := If[m >= n, b[Array[{m, m}&, n]], b[Array[{n, n}&, m]]]; Table[ Table[A[n, d+1-n], {n, 1, d}], {d, 1, 8}] // Flatten (* Jean-François Alcover, Mar 11 2015, after Alois P. Heinz *)

Formula

A(n,1) = A(1,n) = A000108(n).
A(n,2) = A(2,n) = A114714(n).
A(n,3) = A(3,n) = A114716(n).

Extensions

Edited by Alois P. Heinz, Jun 29 2012

A119499 Records in A114717.

Original entry on oeis.org

1, 2, 5, 14, 48, 2452, 183958, 4877756, 17454844, 20071150430, 409158464142, 129586764260850, 269333638458151764, 1868569007661198289216, 326772188939088357313806, 48024472200935599107697461965204, 11653191042139941668276738496190656
Offset: 1

Views

Author

Antti Karttunen, May 26 2006

Keywords

Comments

Term a(10) was taken from A114716(4) (= A114715(3,4) = A114715(4,3)).

Links

Crossrefs

a(n) = A114717(A119500(n)). Subset of A119841.

Programs

  • Mathematica
    b[s_] := b[s] = If[Length[s] < 2, 1, Sum[If[Length[Select[s, Mod[#, x] == 0 &]] == 1, b[Complement[s, {x}]], 0], {x, s}]]; a[n_] := Module[{l, m}, l = Sort[FactorInteger[n], #1[[2]] > #2[[2]] &]; m = Product[Prime[i]^l[[i]][[2]], {i, 1, Length[l]}]; b[Divisors[m] // Rest // Most]]; A119499 = Reap[For[record = 0; k = 1, k < 5000, k++, If[a[k] > record, record = a[k]; Print[k, " ", record]; Sow[record]]]][[2, 1]] (* Jean-François Alcover, Mar 03 2016, after Alois P. Heinz *)

Extensions

a(11)-a(17) from Alois P. Heinz, Aug 06 2012
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.