A061989 -id:A061989 - cp's OEIS frontend

A079908 Solution to the Dancing School Problem with 3 girls and n+3 boys: f(3,n).

1, 4, 14, 36, 76, 140, 234, 364, 536, 756, 1030, 1364, 1764, 2236, 2786, 3420, 4144, 4964, 5886, 6916, 8060, 9324, 10714, 12236, 13896, 15700, 17654, 19764, 22036, 24476, 27090, 29884, 32864, 36036, 39406, 42980, 46764, 50764, 54986, 59436

Offset: 0

Jaap Spies, Jan 28 2003

The Dancing School Problem: a line of g girls (g>0) with integer heights ranging from m to m+g-1 cm and a line of g+h boys (h>=0) ranging in height from m to m+g+h-1 cm are facing each other in a dancing school (m is the minimal height of both girls and boys).
A girl of height l can choose a boy of her own height or taller with a maximum of l+h cm. We call the number of possible matchings f(g,h).
This problem is equivalent to a rooks problem: The number of possible placings of g non-attacking rooks on a g X g+h chessboard with the restriction i <= j <= i+h for the placement of a rook on square (i,j): f(g,h) = per(B), the permanent of the corresponding (0,1)-matrix B, b(i, j)=1 if and only if i <= j <= i+h
f(g,h) = per(B), the permanent of the (0,1)-matrix B of size g X g+h with b(i,j)=1 if and only if i <= j <= i+h.
For fixed g, f(g,n) is polynomial in n for n >= g-2. See reference.

Michael De Vlieger, Table of n, a(n) for n = 0..10000
Lute Kamstra, Problem 29 in Vol. 5/3, No. 1, Mar 2002, p. 96. See also Vol. 5/3, Nos. 3 and 4.
Jaap Spies, Dancing School Problems, Nieuw Archief voor Wiskunde 5/7 nr. 4, Dec 2006, pp. 283-285.
Jaap Spies, Dancing School Problems, Permanent solutions of Problem 29.
Jaap Spies, Sage program to compute f(g,h).
Jaap Spies, A Bit of Math, The Art of Problem Solving, Jaap Spies Publishers (2019).
Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Cf. A061989, A079909-A079928.

Cf. Essentially the same as A061989.

Join[{1},Array[#^3+3*#&,5!,1]] (* Vladimir Joseph Stephan Orlovsky, Jan 08 2011 *)

concat(1,vector(30,n,n^3+3*n)) \\ Derek Orr, Jun 18 2015

a(n) = max(1, n^3 + 3*n), found by elementary counting.

G.f.: 1+2*x*(2-x+2*x^2)/(1-x)^4. - R. J. Mathar, Nov 19 2007

A061990 Number of ways to place 4 nonattacking queens on a 4 X n board.

Original entry on oeis.org

0, 0, 0, 0, 2, 12, 46, 140, 344, 732, 1400, 2468, 4080, 6404, 9632, 13980, 19688, 27020, 36264, 47732, 61760, 78708, 98960, 122924, 151032, 183740, 221528, 264900, 314384, 370532, 433920, 505148, 584840, 673644, 772232, 881300, 1001568, 1133780, 1278704, 1437132

Offset: 0

Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), May 29 2001

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
V. Kotesovec, Ways of placing non-attacking queens and kings..., part of "Between chessboard and computer", 1996, pp. 204 - 206.
E. Lucas, Recreations mathematiques I, Albert Blanchard, Paris, 1992, p. 231.
Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Cf. A061989.

Join[{0,0,0,0,2,12,46},LinearRecurrence[{5,-10,10,-5,1},{140,344,732,1400,2468},30]] (* Harvey P. Dale, Mar 06 2013 *)
CoefficientList[Series[-2 x^4 (x^3 - x^2 + x + 1) (x^4 + 4 x^2 + 1) / (x-1)^5, {x, 0, 40}], x] (* Vincenzo Librandi, May 02 2013 *)

a(n)=if(n<7,[0, 0, 0, 0, 2, 12, 46][n+1],n^4-18*n^3+139*n^2-534*n+840) \\ Charles R Greathouse IV, Oct 21 2022

G.f.: -2*x^4*(x^3-x^2+x+1)*(x^4+4*x^2+1)/(x-1)^5.
Recurrence: a(n)=5*a(n-1)-10*a(n-2)+10*a(n-3)-5*a(n-4)+a(n-5), n >= 12.
Explicit formula (H. Tarry, 1890): a(n)=n^4-18*n^3+139*n^2-534*n+840, n >= 7.

A061991 Number of ways to place 5 nonattacking queens on a 5 X n board.

Original entry on oeis.org

0, 0, 0, 0, 0, 10, 40, 164, 568, 1614, 3916, 8492, 16852, 31100, 54068, 89428, 141812, 216932, 321700, 464348, 654548, 903532, 1224212, 1631300, 2141428, 2773268, 3547652, 4487692, 5618900, 6969308, 8569588, 10453172, 12656372, 15218500, 18181988, 21592508

Offset: 0

Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), May 31 2001

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
V. Kotesovec, Ways of placing non-attacking queens and kings..., part of "Between chessboard and computer", 1996, pp. 204 - 206.
Index entries for linear recurrences with constant coefficients, signature (6,-15,20,-15,6,-1).

Cf. A061989, A061990.

CoefficientList[Series[2 x^5 (4 x^11 -11 x^10 + 16 x^9 + 7 x^8 - 32 x^7 + 38 x^6 + 6 x^5 + 8 x^4 - 8 x^3 + 37 x^2 - 10 x + 5) / (x-1)^6, {x, 0, 30}], x] (* Vincenzo Librandi, May 12 2013 *)

G.f.: 2*x^5*(4*x^11 - 11*x^10 + 16*x^9 + 7*x^8 - 32*x^7 + 38*x^6 + 6*x^5 + 8*x^4 - 8*x^3 + 37*x^2 - 10*x + 5)/(x - 1)^6.
Recurrence: a(n) = 6*a(n - 1) - 15*a(n - 2) + 20*a(n - 3) - 15*a(n - 4) + 6*a(n - 5) - a(n - 6), n >= 17.
Explicit formula (V. Kotesovec, 1992): a(n) = n^5 - 30*n^4 + 407*n^3 - 3098*n^2 + 13104*n - 24332, n >= 11.

A061992 Number of ways to place 6 nonattacking queens on a 6 X n board.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 4, 94, 550, 2292, 7552, 21362, 52856, 117694, 241484, 463038, 838816, 1448002, 2398292, 3832374, 5935120, 8941514, 13145292, 18908302, 26670584, 36961170, 50409604, 67758182, 89874912, 117767194, 152596220

Offset: 0

Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), May 31 2001

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Vaclav Kotesovec, Number of ways of placing non-attacking queens and kings on boards of various sizes, part of V. Kotesovec, Between chessboard and computer, 1996, pp. 204 - 206.

Cf. A061989, A061990, A061991.

CoefficientList[Series[-2 x^6 (4 x^17 -12 x^16 + 12 x^15 + 10 x^14 - 10 x^13 + 40 x^12 - 278 x^11 + 677 x^10 - 582 x^9 - 62 x^8 + 654 x^7 - 501 x^6 + 293 x^5 - 46 x^4 + 138 x^3 - 12 x^2 + 33 x + 2) / (x-1)^7, {x, 0, 40}], x] (* Vincenzo Librandi, May 12 2013 *)

G.f.: - 2*x^6*(4*x^17 - 12*x^16 + 12*x^15 + 10*x^14 - 10*x^13 + 40*x^12 - 278*x^11 + 677*x^10 - 582*x^9 - 62*x^8 + 654*x^7 - 501*x^6 + 293*x^5 - 46*x^4 + 138*x^3 - 12*x^2 + 33*x + 2)/(x - 1)^7.
Recurrence: a(n) = 7*a(n - 1) - 21*a(n - 2) + 35*a(n - 3) - 35*a(n - 4) + 21*a(n - 5) - 7*a(n - 6) + a(n - 7), n >= 24.
Explicit formula (V.Kotesovec, 1992): a(n) = n^6 - 45*n^5 + 943*n^4 - 11755*n^3 + 91480*n^2 - 418390*n + 870920, n >= 17.

A061993 Number of ways to place 7 nonattacking queens on a 7 X n board.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 40, 312, 2038, 9632, 37248, 120104, 335010, 835056, 1897702, 3998456, 7907094, 14818300, 26512942, 45562852, 75580634, 121520020, 190031678, 289879092, 432420154, 632159540, 907376502, 1280833348

Offset: 0

Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Jun 10 2001

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Vaclav Kotesovec, Number of ways of placing non-attacking queens and kings on boards of various sizes, part of V. Kotesovec, Between chessboard and computer, 1996, pp. 204 - 206.
Index entries for linear recurrences with constant coefficients, signature (8,-28,56,-70,56,-28,8,-1).

Cf. A061989, A061990, A061991, A061992.

CoefficientList[Series[2*x^7*(20-4*x+331*x^2-88*x^3+1292*x^4-1356*x^5+2019*x^6 +264*x^7-2857*x^8+6472*x^9-7616*x^10+7462*x^11-7831*x^12+8326*x^13-5672*x^14 +1998*x^15-308*x^16-142*x^17+510*x^18-284*x^19-220*x^20+320*x^21-140*x^22 +24*x^23)/(1-x)^8, {x, 0, 40}], x] (* Vincenzo Librandi, May 12 2013 *)

def p(x): return 20-4*x+331*x^2-88*x^3+1292*x^4-1356*x^5+2019*x^6 +264*x^7-2857*x^8+6472*x^9-7616*x^10+7462*x^11-7831*x^12+8326*x^13-5672*x^14 +1998*x^15-308*x^16-142*x^17+510*x^18-284*x^19-220*x^20+320*x^21-140*x^22 +24*x^23
[( 2*x^7*p(x)/(1-x)^8 ).series(x,n+1).list()[n] for n in (0..40)] # G. C. Greubel, Apr 29 2022

Explicit formula (V. Kotesovec, 1992): a(n) = n^7 - 63*n^6 + 1879*n^5 - 34411*n^4 + 417178*n^3 - 3336014*n^2 + 16209916*n - 36693996, n >= 23.
Recurrence: a(n) = 8*a(n-1) - 28*a(n-2) + 56*a(n-3) - 70*a(n-4) + 56*a(n-5) - 28*a(n-6) + 8*a(n-7) - a(n-8), n >= 31.
G.f.: 2*x^7*(20 - 4*x + 331*x^2 - 88*x^3 + 1292*x^4 - 1356*x^5 + 2019*x^6 + 264*x^7 - 2857*x^8 + 6472*x^9 - 7616*x^10 + 7462*x^11 - 7831*x^12 + 8326*x^13 - 5672*x^14 + 1998*x^15 - 308*x^16 - 142*x^17 + 510*x^18 - 284*x^19 - 220*x^20 + 320*x^21 - 140*x^22 + 24*x^23)/(1 - x)^8.

A172202 Number of ways to place 3 nonattacking kings on a 3 X n board.

Original entry on oeis.org

0, 0, 8, 34, 105, 248, 490, 858, 1379, 2080, 2988, 4130, 5533, 7224, 9230, 11578, 14295, 17408, 20944, 24930, 29393, 34360, 39858, 45914, 52555, 59808, 67700, 76258, 85509, 95480, 106198, 117690, 129983, 143104, 157080, 171938, 187705

Offset: 1

Vaclav Kotesovec, Jan 29 2010

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Vaclav Kotesovec, Number of ways of placing non-attacking queens and kings on boards of various sizes
Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Cf. A047659, A061989, A061996.

[0] cat [(n-2)*(9*n^2-45*n+70)/2: n in [2..50]]; // G. C. Greubel, Apr 29 2022

CoefficientList[Series[x^2*(8+2*x+17*x^2)/(1-x)^4, {x, 0, 50}], x] (* Vincenzo Librandi, May 27 2013 *)
LinearRecurrence[{4,-6,4,-1},{0,0,8,34,105},40] (* Harvey P. Dale, Oct 07 2023 *)

[(1/8)*(n-2)*(9*(2*n-5)^2+55) +17*bool(n==1) for n in (1..50)] # G. C. Greubel, Apr 29 2022

a(n) = (n-2)*(9*n^2 - 45*n + 70)/2, n>=2.
G.f.: x^3*(8+2*x+17*x^2)/(1-x)^4. - Vaclav Kotesovec, Mar 24 2010
E.g.f.: 70 + 17*x + (1/2)*(-140 + 106*x - 36*x^2 + 9*x^3)*exp(x). - G. C. Greubel, Apr 29 2022

More terms from Vincenzo Librandi, May 27 2013

A172212 Number of ways to place 3 nonattacking knights on a 3 X n board.

Original entry on oeis.org

1, 12, 36, 100, 233, 456, 796, 1280, 1935, 2788, 3866, 5196, 6805, 8720, 10968, 13576, 16571, 19980, 23830, 28148, 32961, 38296, 44180, 50640, 57703, 65396, 73746, 82780, 92525, 103008, 114256, 126296, 139155, 152860, 167438, 182916, 199321

Offset: 1

Vaclav Kotesovec, Jan 29 2010

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
V. Kotesovec, Number of ways of placing non-attacking queens and kings on boards of various sizes

Cf. A172134, A061989, A047659, A172202.

CoefficientList[Series[(6 x^6 - 8 x^5 + 2 x^4 + 24 x^3 - 6 x^2 + 8 x + 1) / (x - 1)^4, {x, 0, 50}], x] (* Vincenzo Librandi, May 27 2013 *)

a(n) = (9n^3 - 45n^2 + 122n - 144)/2, n>=4.

G.f.: x*(6*x^6-8*x^5+2*x^4+24*x^3-6*x^2+8*x+1)/(x-1)^4. - Vaclav Kotesovec, Mar 25 2010

A172229 Number of ways to place 3 nonattacking wazirs on a 3 X n board.

Original entry on oeis.org

0, 2, 22, 84, 215, 442, 792, 1292, 1969, 2850, 3962, 5332, 6987, 8954, 11260, 13932, 16997, 20482, 24414, 28820, 33727, 39162, 45152, 51724, 58905, 66722, 75202, 84372, 94259, 104890, 116292, 128492, 141517, 155394, 170150, 185812, 202407, 219962, 238504

Offset: 1

Vaclav Kotesovec, Jan 29 2010

A wazir is a (fairy chess) leaper [0,1].

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
V. Kotesovec, Number of ways of placing non-attacking queens and kings on boards of various sizes
R. J. Mathar, Bivariate generating functions for non-attacking wazirs on rectangular boards, viXra:2404.0122 (2024) Section 3.
Eric Weisstein's World of Mathematics, Grid Graph
Wikipedia, Wazir (chess)

Cf. A172226, A061989.

Column w=3 of A371967.

CoefficientList[Series[x (3 x^3 + 8 x^2 + 14 x + 2) / (x - 1)^4, {x, 0, 50}], x] (* Vincenzo Librandi, May 28 2013 *)

a(n) = (3*n - 5)*(3*n^2 - 8*n + 8)/2, n>=2.

G.f.: x^2*(3*x^3+8*x^2+14*x+2)/(x-1)^4. - Vaclav Kotesovec, Mar 25 2010

A005491 a(n) = n^3 + 3*n + 1.

Original entry on oeis.org

1, 5, 15, 37, 77, 141, 235, 365, 537, 757, 1031, 1365, 1765, 2237, 2787, 3421, 4145, 4965, 5887, 6917, 8061, 9325, 10715, 12237, 13897, 15701, 17655, 19765, 22037, 24477, 27091, 29885, 32865, 36037, 39407, 42981, 46765, 50765, 54987, 59437, 64121, 69045

Offset: 0

N. J. A. Sloane, Simon Plouffe

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Ivan Panchenko, Table of n, a(n) for n = 0..1000
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Earl Glen Whitehead Jr., Stirling number identities from chromatic polynomials, J. Combin. Theory, A 24 (1978), 314-317.
Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Cf. A000578, A001093, A008585, A016777, A061989.

[n^3+3*n+1: n in [0..50]]; // G. C. Greubel, Dec 01 2022

A005491:=(1+z+z**2+3*z**3)/(z-1)**4; # [Conjectured by Simon Plouffe in his 1992 dissertation.]

Table[n^3 + 3 n + 1, {n, 0, 50}] (* or *) LinearRecurrence[{4,-6,4,-1},{1,5,15,37},50] (* Harvey P. Dale, Oct 01 2014 *)

a(n)=n^3+3*n+1 \\ Charles R Greathouse IV, Oct 07 2015

[(n+1)^3 -3*n^2 for n in range(51)] # G. C. Greubel, Dec 01 2022

a(0)=1, a(1)=5, a(2)=15, a(3)=37, a(n)=4*a(n-1)-6*a(n-2)+4*a(n-3)-a(n-4). - Harvey P. Dale, Oct 01 2014
From G. C. Greubel, Dec 01 2022: (Start)
E.g.f.: (1 + 4*x + 3*x^2 + x^3)*exp(x).
a(n) = A000578(n) + A016777(n) = A001093(n) + A008585(n). (End)

More terms from Harvey P. Dale, Oct 01 2014

A117938 Triangle, columns generated from Lucas Polynomials.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 1, 3, 6, 4, 1, 4, 11, 14, 7, 1, 5, 18, 36, 34, 11, 1, 6, 27, 76, 119, 82, 18, 1, 7, 38, 140, 322, 393, 198, 29, 1, 8, 51, 234, 727, 1364, 1298, 478, 47, 1, 9, 66, 364, 1442, 3775, 5778, 4287, 1154, 76, 1, 10, 83, 536, 2599, 8886, 19602, 24476, 14159, 2786, 123

Offset: 1

Gary W. Adamson, Apr 03 2006

Companion triangle using Fibonacci polynomial generators = A073133. Inverse binomial transforms of the columns defines rows of A117937 (with some adjustments of offset).

A309220 is another version of the same triangle (except it omits the last diagonal), and perhaps has a clearer definition. - N. J. A. Sloane, Aug 13 2019

			First few rows of the triangle are:
  1;
  1, 1;
  1, 2,  3;
  1, 3,  6,   4;
  1, 4, 11,  14,   7;
  1, 5, 18,  36,  34,  11;
  1, 6, 27,  76, 119,  82,  18;
  1, 7, 38, 140, 322, 393, 198, 29;
  ...
For example, T(7,4) = 76 = f(4), x^3 + 3*x = 64 + 12 = 76.

G. C. Greubel, Rows n = 1..50 of the triangle, flattened

Cf. A104509, A114525, A117936, A117937, A118980, A118981, A309220.

Cf. A000204 (diagonal), A059100 (column 3), A061989 (column 4).

Lucas := proc(n,x) # see A114525
    option remember;
    if  n=0 then
        2;
    elif n =1 then
        x ;
    else
        x*procname(n-1,x)+procname(n-2,x) ;
    end if;
    expand(%) ;
end proc:
A117938 := proc(n::integer,k::integer)
    if k = 1 then
        1;
    else
        subs(x=n-k+1,Lucas(k-1,x)) ;
    end if;
end proc:
seq(seq(A117938(n,k),k=1..n),n=1..12) ; # R. J. Mathar, Aug 16 2019

T[n_, k_]:= LucasL[k-1, n-k+1] - Boole[k==1];
Table[T[n, k], {n, 12}, {k, n}]//Flatten (* G. C. Greubel, Oct 28 2021 *)

def A117938(n,k): return 1 if (k==1) else round(2^(1-k)*( (n-k+1 + sqrt((n-k)*(n-k+2) + 5))^(k-1) + (n-k+1 - sqrt((n-k)*(n-k+2) + 5))^(k-1) ))
flatten([[A117938(n,k) for k in (1..n)] for n in (1..12)]) # G. C. Greubel, Oct 28 2021

Columns are f(x), x = 1, 2, 3, ..., of the Lucas Polynomials: (1, defined different from A034807 and A114525); (x); (x^2 + 2); (x^3 + 3*x); (x^4 + 4*x^2 + 2); (x^5 + 5*x^3 + 5*x); (x^6 + 6*x^4 + 9*x^2 + 2); (x^7 + 7*x^5 + 14*x^3 + 7*x); ...

Terms a(51) and a(52) corrected by G. C. Greubel, Oct 28 2021

cp's OEIS Frontend

A079908 Solution to the Dancing School Problem with 3 girls and n+3 boys: f(3,n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A061990 Number of ways to place 4 nonattacking queens on a 4 X n board.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A061991 Number of ways to place 5 nonattacking queens on a 5 X n board.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A061992 Number of ways to place 6 nonattacking queens on a 6 X n board.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A061993 Number of ways to place 7 nonattacking queens on a 7 X n board.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

SageMath

Formula

A172202 Number of ways to place 3 nonattacking kings on a 3 X n board.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

Extensions

A172212 Number of ways to place 3 nonattacking knights on a 3 X n board.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A172229 Number of ways to place 3 nonattacking wazirs on a 3 X n board.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica