Thomas Dybdahl Ahle - cp's OEIS frontend

A255192 Triangle of number of connected subgraphs of K(n,n) with m edges.

1, 4, 1, 81, 78, 36, 9, 1, 4096, 8424, 9552, 7464, 4272, 1812, 560, 120, 16, 1, 390625, 1359640, 2696200, 3880300, 4394600, 4059000, 3111140, 1994150, 1070150, 478800, 176900, 53120, 12650, 2300, 300, 25, 1, 60466176, 314452800, 939988800, 2075760000

Offset: 1

Thomas Dybdahl Ahle, Feb 16 2015

m ranges from 2n-1 to n^2.

First column is A068087.

			Triangle begins:
----|------------------------------------------------------------
n\m |  1 2 3 4  5  6    7    8    9   10   11   12  13  14 15 16
----|------------------------------------------------------------
1   |  1
2   |  - - 4 1
3   |  - - - - 81 78   36    9    1
4   |  - - - -  -  - 4096 8424 9552 7464 4272 1812 560 120 16  1

Cf. A005333 (row sums?).

from math import comb as binomial
def f(x, a, b, k):
    if b == k == 0:
        return 1
    if b == 0 or k == 0:
        return 0
    if x == a:
        return sum(binomial(a, n) * f(x, x, b - 1, k - n) for n in range(1, a + 1))
    return sum(binomial(b, n) * f(x, x, n, k2) * f(n, b, a - x, k - k2)
        for n in range(1, b + 1) for k2 in range(0, k + 1) )
def a(n, m):
    return f(1, n, n, m)
for n in range(1, 5):
    print([a(n, m) for m in range(1, n * n + 1)])

Sum(k>=0, T(n,k)*(-1)^k ) = A136126(2*n-1,n-1) = A092552(n+1), alternating row sums.

A239288 Maximal sum of x0 + x0x1 + ... + x0x1...xk over all compositions x0 + ... + xk = n.

Original entry on oeis.org

0, 1, 2, 4, 6, 10, 15, 22, 33, 48, 69, 102, 147, 210, 309, 444, 633, 930, 1335, 1902, 2793, 4008, 5709, 8382, 12027, 17130, 25149, 36084, 51393, 75450, 108255, 154182, 226353, 324768, 462549, 679062, 974307, 1387650, 2037189, 2922924, 4162953, 6111570

Offset: 0

Thomas Dybdahl Ahle, Jun 13 2014

This sequence comes up in the analysis of exact algorithms for maximum independent sets.

			For n = 4 there are three solutions, all summing to 6: 3+3*1, 2+2*1+2*1*1, 2+2*2.
For n = 7 there is only one solution: 2 + 2*2 + 2*2*2 + 2*2*2*1.

Index entries for linear recurrences with constant coefficients, signature (1,0,3,-3).

mulprod := proc(L)
    local i,k ;
    add(mul(op(k,L),k=1..i),i=1..nops(L)) ;
end proc:
A239288 := proc(n)
    a := 0 ;
    for pa in combinat[partition](n) do
        for pe in combinat[permute](pa) do
            f := mulprod(pe) ;
            a := max(a,f) ;
        end do:
    end do:
    return a;
end proc: # R. J. Mathar, Jul 03 2014

a(0) = 0, a(n) = max{k + k*a(n - k) | 1 <= k <= n}.
For n >= 8 the solution becomes cyclic: a(3n + k) = 3 + 3a(3n - 3 + k).
G.f.: -x*(x^2+x+1)*(x^5-2*x^4+2*x^3-x^2-1) / ((x-1)*(3*x^3-1)). - Joerg Arndt

A217595 Number of free n-celled polyominoes without holes and odd side lengths.

Original entry on oeis.org

1, 0, 1, 1, 2, 4, 7, 12, 35, 55, 144, 335, 710, 1791, 4195

Offset: 1

Thomas Dybdahl Ahle, May 28 2013

If you checkerboard color the vertices of the square lattice, a(n) is the number of orthogonal polygons of area n, which alternates between white and black vertices.

			For n=5 the a(5)=2 pentominoes are 'I' and 'X'.

Giovanni Resta, Illustration of a(10) = 55.

a(10) from Giovanni Resta, Jun 06 2013
a(11)-a(12) from Thomas Dybdahl Ahle, Nov 13 2019
a(13)-a(15) from Aurélien Ooms, Nov 14-19 2019

A188816 Triangle read by rows: row n gives (coefficients * (n-1)!) in expansion of pieces k=0..n-1 of the probability mass function for the Irwin-Hall distribution, lowest powers first.

Original entry on oeis.org

1, 0, 1, 2, -1, 0, 0, 1, -3, 6, -2, 9, -6, 1, 0, 0, 0, 1, 4, -12, 12, -3, -44, 60, -24, 3, 64, -48, 12, -1, 0, 0, 0, 0, 1, -5, 20, -30, 20, -4, 155, -300, 210, -60, 6, -655, 780, -330, 60, -4, 625

Offset: 1

Thomas Dybdahl Ahle, Apr 11 2011

This is the probability distribution for the sum of n independent, random variables, each uniformly distributed on [0,1).

			For n = 4, k = 1 (four variables, second piece) the function is the polynomial: 1/6 * (4 - 12x + 12x^2 -3x^3). That gives the subsequence [4, -12, 12, -3].
Triangle begins:
  [1];
  [0,1], [2,-1];
  [0,0,1], [-3,6,-2], [9,-6,1];
  ...

Alois P. Heinz, Rows n = 1..32, flattened
Philip Hall, The Distribution of Means for Samples of Size N Drawn from a Population in which the Variate Takes Values Between 0 and 1, All Such Values Being Equally Probable, Biometrika, Vol. 19, No. 3/4. (Dec., 1927), pp. 240-245.
Wikipedia, Irwin-Hall distribution

Differentiation of A188668.

f:= proc(n, k) option remember;
       add((-1)^j * binomial(n, j) * (x-j)^(n-1), j=0..k)
    end:
T:= (n, k)-> seq(coeff(f(n, k), x, t), t=0..n-1):
seq(seq(T(n, k), k=0..n-1), n=1..7);  # Alois P. Heinz, Jul 06 2017

f[n_, k_] := f[n, k] = Sum[(-1)^j Binomial[n, j] (x-j)^(n-1), {j, 0, k}];
T[n_, k_] := Table[Coefficient[f[n, k], x, t], {t, 0, n-1}];
Table[Table[T[n, k], {k, 0, n-1}], {n, 1, 7}] // Flatten (* Jean-François Alcover, Feb 19 2021, after Alois P. Heinz *)

G.f. for piece k in row n: (1/(n-1)!) * Sum_{j=0..k} (-1)^j * C(n,j) * (x-j)^(n-1).

A188668 Triangle read by rows: row n gives (coefficients * n!) in expansion of pieces k=0..n-1 of the cumulative distribution function for the Irwin-Hall distribution, lowest powers first.

Original entry on oeis.org

0, 1, 0, 0, 1, -2, 4, -1, 0, 0, 0, 1, 3, -9, 9, -2, -21, 27, -9, 1, 0, 0, 0, 0, 1, -4, 16, -24, 16, -3, 92, -176, 120, -32, 3, -232, 256, -96, 16, -1, 0, 0, 0, 0, 0, 1, 5, -25, 50, -50, 25, -4, -315, 775, -750, 350, -75, 6, 2115, -3275, 1950, -550, 75, -4, -3005, 3125, -1250, 250, -25, 1

Offset: 1

Thomas Dybdahl Ahle, Apr 07 2011

This is the probability distribution for the sum of n independent, random variables, each uniformly distributed on [0,1).

			For n = 3, k = 2 (three variables, third piece) the distribution is the polynomial: 1/6 * (1*(x-0)^3 - 3*(x-1)^3 + 3*(x-2)^3) = 1/6 * (-21 + 27*x - 9*x^2 + x^3). That gives the subsequence [-21, 27, -9, 1].
Triangle begins:
  [0, 1];
  [0, 0, 1], [-2, 4, -1];
  [0, 0, 0, 1], [3, -9, 9, -2], [-21, 27, -9, 1];
  ...

Alois P. Heinz, Rows n = 1..31, flattened
Philip Hall, The Distribution of Means for Samples of Size N Drawn from a Population in which the Variate Takes Values Between 0 and 1, All Such Values Being Equally Probable, Biometrika, Vol. 19, No. 3/4. (Dec., 1927), pp. 240-245.
Wikipedia, Irwin-Hall distribution

f:= proc(n, k) option remember;
       add((-1)^j * binomial(n, j) * (x-j)^n, j=0..k)
    end:
T:= (n, k)-> seq(coeff(f(n, k), x, t), t=0..n):
seq(seq(T(n, k), k=0..n-1), n=1..7);  # Alois P. Heinz, Apr 09 2011

f[n_, k_] := f[n, k] = Sum[(-1)^j*Binomial[n, j]*(x-j)^n, {j, 0, k}]; T[n_, k_] := Table[Coefficient[f[n, k], x, t], {t, 0, n}]; Table[T[n, k], {n, 1, 7}, { k, 0, n-1}] // Flatten (* Jean-François Alcover, Feb 26 2017, after Alois P. Heinz *)

G.f. for piece k in row n: (1/n!) * Sum_{j=0..k} (-1)^j * C(n,j) * (x-j)^n.

cp's OEIS Frontend

User: Thomas Dybdahl Ahle

A255192 Triangle of number of connected subgraphs of K(n,n) with m edges.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Formula

A239288 Maximal sum of x0 + x0*x1 + ... + x0*x1*...*xk over all compositions x0 + ... + xk = n.

Views

Author

Keywords

Comments

Examples

Links

Programs

Maple

Formula

A217595 Number of free n-celled polyominoes without holes and odd side lengths.

Views

Author

Keywords

Comments

Examples

Links

Extensions

A188816 Triangle read by rows: row n gives (coefficients * (n-1)!) in expansion of pieces k=0..n-1 of the probability mass function for the Irwin-Hall distribution, lowest powers first.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A188668 Triangle read by rows: row n gives (coefficients * n!) in expansion of pieces k=0..n-1 of the cumulative distribution function for the Irwin-Hall distribution, lowest powers first.

Views

Author

Keywords

Comments

Examples

Links

Programs

Maple

Mathematica

Formula

A239288 Maximal sum of x0 + x0x1 + ... + x0x1...xk over all compositions x0 + ... + xk = n.