Felix A. Pahl - cp's OEIS frontend

User: Felix A. Pahl

Felix A. Pahl has authored 4 sequences.

A225877 Number of (2n-1)-step self-avoiding paths between two adjacent sites of a 2-dimensional square lattice.

1, 2, 6, 28, 140, 744, 4116, 23504, 137412, 818260, 4945292, 30255240, 187009888, 1166065936, 7325767920, 46326922560, 294658864188, 1883761686216, 12098003064296, 78015400052920, 504955502402148, 3279315915221192, 21361995729759184, 139545638718942960

Offset: 1

Felix A. Pahl, May 19 2013

nonn

For n > 1, a(n) = A010566(n)/4: every self-avoiding open path from P to an adjacent site Q (except the one for n = 1) can be completed to a self-avoiding closed path by adding an edge from Q back to P, and exactly 1/4 of all closed paths through P contain that edge.

Felix A. Pahl, Table of n, a(n) for n = 1..55

A002931 = Cases[Import["https://oeis.org/A002931/b002931.txt", "Table"], {, }][[All, 2]]; a[n_] := n A002931[[n]];
a /@ Range[55] (* Jean-François Alcover, Jan 11 2020 *)

For n>1, a(n) = n*A002931(n) = A010566(n)/4.

A220452 Number of unordered full binary trees with labels from a set of n labels.

Original entry on oeis.org

1, 3, 9, 37, 225, 1881, 19873, 251889, 3712257, 62286625, 1171487361, 24402416193, 557542291969, 13861636770177, 372514645389825, 10759590258589441, 332386419622387713, 10935312198369141249, 381705328034883127297, 14089260601787531469825, 548302210950105933701121

Offset: 1

Felix A. Pahl, Dec 15 2012

a(n) is the size of the population generated by n unrelated ancestors if two individuals produce one descendant together if and only if they are not related.

			For n=3, each of the three pairs of ancestors produces one descendant, and each of these descendants produces one more descendant with the respective remaining ancestor; three ancestors, three first-order descendants and three second-order descendants makes a population of a(3)=9.

Felix A. Pahl, Table of n, a(n) for n = 1..400
Mathematics Stack Exchange, The n immortals problem
V. Kotesovec, Interesting asymptotic formulas for binomial sums, Jun 09 2013

Cf. A001147.

Partial sums of A084262.

import java.math.BigInteger;
public class A220452 {
    public static void main (String [] args) {
        int max = Integer.parseInt (args [0]);
        BigInteger [] doubleFactorials = new BigInteger [max + 1];
        BigInteger [] [] binomialCoefficients = new BigInteger [max + 1] [max + 1];
        doubleFactorials [0] = BigInteger.ONE;
        for (int n = 1;n <= max;n++) {
            binomialCoefficients [n] [0] = BigInteger.ONE;
            BigInteger sum = BigInteger.ZERO;
            for (int k = 1;k <= n;k++) {
                binomialCoefficients [n] [k] = k == n ? BigInteger.ONE : binomialCoefficients [n - 1] [k - 1].add (binomialCoefficients [n - 1] [k]);
                sum = sum.add (binomialCoefficients [n] [k].multiply (doubleFactorials [k - 1]));
            }
            System.out.println (n + " " + sum);
            doubleFactorials [n] = doubleFactorials [n - 1].multiply (BigInteger.valueOf (2 * n - 1));
        }
    }
}

Table[Sum[Binomial[n,k]*(2*k-3)!!, {k, 1, n}], {n, 1, 20}] (* Vaclav Kotesovec, Dec 17 2012 *)

a(n) = Sum_{k=1..n} binomial(n,k)*(2k-3)!!.

a(n) ~ (2n-3)!!*sqrt(e) ~ (2n)!/(n!*2^n*(2n-1))*sqrt(e) ~ n^(n-1)*2^(n-1/2)*exp(1/2-n). - Vaclav Kotesovec, Dec 17 2012

A182106 Number of tilings of an n X n square with rectangles with integer sides and area n.

Original entry on oeis.org

1, 1, 2, 2, 9, 2, 46, 2, 250, 37, 254, 2, 31052, 2, 1480, 896, 306174, 2, 2097506, 2, 6025516, 6638, 59930, 2, 22119057652, 1141, 400776, 1028162, 1205138020, 2, 188380348290, 2

Offset: 0

Felix A. Pahl, Apr 12 2012

Math StackExchange, Dividing a square into equal-sized rectangles.

Diagonal of A220122. - Alois P. Heinz, Dec 07 2012

public class Question130758 {
    final static int maxn = 23;
    static int n;
    static int [] divisors = new int [maxn];
    static int ndivisors;
    static boolean [] [] grid;
    static int count;
    public static void main (String [] args) {
        for (n = 0;n <= maxn;n++) {
            ndivisors = 0;
            for (int divisor = 1;divisor <= n;divisor++)
                if (n % divisor == 0)
                    divisors [ndivisors++] = divisor;
            grid = new boolean [n] [n];
            count = 0;
            recurse (0,0,0);
            System.out.print (count + ",");
        }
        System.out.println ();
    }
    static void recurse (int x,int y,int depth) {
        if (depth == n) {
            count++;
            return;
        }
        while (grid [x] [y])
            if (++x == n) {
                x = 0;
                y++;
            }
        outer:
        for (int k = 0;k < ndivisors;k++) {
            int w = divisors [k];
            int h = n / w;
            if (x + w > n || y + h > n)
                continue;
            for (int i = 0;i < w;i++)
                for (int j = 0;j < h;j++)
                    if (grid [x + i] [y + j])
                        continue outer;
            for (int i = 0;i < w;i++)
                for (int j = 0;j < h;j++)
                    grid [x + i] [y + j] = true;
            recurse (x,y,depth + 1);
            for (int i = 0;i < w;i++)
                for (int j = 0;j < h;j++)
                    grid [x + i] [y + j] = false;
        }
    }
}

a(24)-a(31) from Lars Blomberg, Oct 09 2023

A197458 Number of n X n binary matrices with at most two 1's in each row and column, other entries 0.

Original entry on oeis.org

1, 2, 16, 265, 7343, 304186, 17525812, 1336221251, 129980132305, 15686404067098, 2297230134084416, 400977650310256537, 82188611938415464231, 19536244019455339261970, 5328019975275896220786388, 1651867356348327784988233291, 577522171260292028520919811777

Offset: 0

Felix A. Pahl, Oct 15 2011

nonn

Filling out an n x n square grid with 0's and 1's at math.stackexchange
R. J. Mathar, The number of binary n X m matrices with at most k 1's in each row or column, (2014) Table 2.

Cf. A001499, A002720. Column of A283500.

import java.math.BigInteger;
public class AtMostTwoOnes {
    public static void main (String [] args) {
        for (int n = 0;n <= 40;n++) {
            BigInteger [] [] [] counts = new BigInteger [n + 1] [n + 1] [n + 1]; // counts [m] [k] [l] : number of mxn matrices with k column sums 0, l column sums 1
            for (int k = 0;k <= n;k++)
                for (int l = 0;l <= n;l++)
                    counts [0] [k] [l] = BigInteger.ZERO;
            counts [0] [n] [0] = BigInteger.ONE; // only one 0xn matrix, with all n column sums 0
            for (int m = 1;m <= n;m++) {
                BigInteger [] [] old = counts [m - 1];
                for (int k = 0;k <= n;k++)
                    for (int l = 0;l <= n;l++) {
                        BigInteger sum = BigInteger.ZERO;
                        // new row contains no 1s
                        sum = sum.add (old [k] [l]);
                        // new row contains one 1
                        //   added to column sum 0
                        if (k < n && l > 0)
                            sum = sum.add (old [k + 1] [l - 1].multiply (BigInteger.valueOf (k + 1)));
                        //   added to column sum 1
                        if (l < n)
                            sum = sum.add (old [k] [l + 1].multiply (BigInteger.valueOf (l + 1)));
                        // new row contains two 1s
                        //   added to two column sums 0
                        if (k < n - 1 && l > 1)
                            sum = sum.add (old [k + 2] [l - 2].multiply (BigInteger.valueOf (((k + 2) * (k + 1)) / 2)));
                        //   added to one column sum 0, one column sum 1
                        if (k < n)
                            sum = sum.add (old [k + 1] [l].multiply (BigInteger.valueOf ((k + 1) * l)));
                        //   added to two column sums 1
                        if (l < n - 1)
                            sum = sum.add (old [k] [l + 2].multiply (BigInteger.valueOf (((l + 2) * (l + 1)) / 2)));
                        counts [m] [k] [l] = sum;
                    }
            }
            BigInteger sum = BigInteger.ZERO;
            for (int k = 0;k <= n;k++)
                for (int l = 0;l <= n;l++)
                    sum = sum.add (counts [n] [k] [l]);
            System.out.println (n + " : " + sum);
        }
    }
}

a(n) = Sum_{k=0}^n Sum_{l=0}^{n-k} a(k,l,n,n) where a(k,l,m,n) is the number of binary m X n matrices with at most two 1's per row, k columns with sum 0, l columns with sum 1 and the remaining n - k - l columns with sum 2.

a(k,l,m,n) = a(k,l,m-1,n) +(k+1)*a(k+1,l-1,m-1,n) +(l+1)*a(k,l+1,m-1,n) +(k+1)*2*a(k+2,l-2,m-1,n)/(k+2) +(k+1)*l*a(k+1,l,m-1,n) +(l+1)*2*a(k,l+2,m-1,n)/(l+2).

cp's OEIS Frontend

User: Felix A. Pahl

A225877 Number of (2n-1)-step self-avoiding paths between two adjacent sites of a 2-dimensional square lattice.

Views

Author

Keywords

Comments

Links

Programs

Mathematica

Formula

A220452 Number of unordered full binary trees with labels from a set of n labels.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Java

Mathematica

Formula

A182106 Number of tilings of an n X n square with rectangles with integer sides and area n.

Views

Author

Keywords

Links

Crossrefs

Programs

Java

Extensions

A197458 Number of n X n binary matrices with at most two 1's in each row and column, other entries 0.

Views

Author

Keywords

Links

Crossrefs

Programs

Java

Formula