A181731 -id:A181731 - cp's OEIS frontend

A105749 Number of ways to use the elements of {1,...,k}, 0 <= k <= 2n, once each to form a sequence of n sets, each having 1 or 2 elements.

1, 2, 14, 222, 6384, 291720, 19445040, 1781750880, 214899027840, 33007837322880, 6290830003852800, 1456812592995513600, 402910665227270323200, 131173228963370155161600, 49656810289225281849907200, 21628258853895305337293568000, 10739534026001485514941587456000

Offset: 0

Robert A. Proctor (www.math.unc.edu/Faculty/rap/), Apr 18 2005

Equivalently, number of sequences of n labeled items such that each item occurs just once or twice. - David Applegate, Dec 08 2008

Also, number of assembly trees for a certain star graph, see Vince-Bona, Theorem 4. - N. J. A. Sloane, Oct 08 2012

			a(2) = 14 = |{ ({1},{2}), ({2},{1}), ({1},{2,3}), ({2,3},{1}), ({2},{1,3}), ({1,3},{2}), ({3},{1,2}), ({1,2},{3}), ({1,2},{3,4}), ({3,4},{1,2}), ({1,3},{2,4}), ({2,4},{1,3}), ({1,4},{2,3}), ({2,3},{1,4}) }|.

Alois P. Heinz, Table of n, a(n) for n = 0..100
Samuele Giraudo and Yannic Vargas, Operads of packed words, quotients, and monomial bases, Proc. 37th Conf. Formal Power Series Alg. Comb., Sém. Lotharingien Combin. (2025) Vol. 93B Art. No. 82. See p. 9.
Robert A. Proctor, Let's Expand Rota's Twelvefold Way for Counting Partitions!, arXiv:math/0606404 [math.CO], 2006-2007.
Andrew Vince and Miklos Bona, The Number of Ways to Assemble a Graph, arXiv preprint arXiv:1204.3842 [math.CO], 2012.
Index entries for related partition-counting sequences

Cf. A001515, A003011, A143990.
Replace "sets" by "lists": A099022.
Column n=2 of A181731.

[(&+[Binomial(n,j)*Factorial(n+j)/2^j: j in [0..n]]): n in [0..30]]; // G. C. Greubel, Sep 26 2023

a:= n-> add(binomial(n, k)*(n+k)!/2^k, k=0..n):
seq(a(n), n=0..20);  # Alois P. Heinz, Jul 21 2012

f[n_]:= Sum[Binomial[n,k]*(n+k)!/2^k, {k,0,n}]; Table[f[n], {n,0,20}]

[sum(binomial(n,j)*factorial(n+j)//2^j for j in range(n+1)) for n in range(31)] # G. C. Greubel, Sep 26 2023

a(n) = Sum_{k=0..n} C(n,k) * (n+k)! / 2^k.
a(n) = n! * A001515(n).
A003011(n) = Sum_{k=0..n} C(n, k)*a(k).
a(n) = Gamma(n+1)*Hypergeometric2F0([-n, n+1], [], -1/2). - Peter Luschny, Jul 29 2014
a(n) ~ sqrt(Pi) * 2^(n + 1) * n^(2*n + 1/2) / exp(2*n - 1). - Vaclav Kotesovec, Nov 27 2017
From G. C. Greubel, Sep 26 2023: (Start)
a(n) = n*(2*n-1)*a(n-1) + n*(n-1)*a(n-2).
a(n) = e * sqrt(2/Pi) * n! * BesselK(n+1/2, 1).
a(n) = ((2*n)!/2^n) * Hypergeometric1F1(-n, -2*n, 2).
G.f.: (-2/x) * Integrate_{t=0..oo} exp(-t)/((t+1)^2 - 1 - 2/x) dt.
G.f.: e*( exp(-sqrt(1 + 2/x)) * ExpIntegralEi(-1 + sqrt(1 + 2/x)) - exp(sqrt(1 + 2/x)) * ExpIntegralEi(-1 - sqrt(1 + 2/x)) )/sqrt(x^2 + 2*x).
E.g.f.: ((1-x)/x) * Hypergeometric1F1(1, 3/2, -(1-x)^2/(2*x)).
E.g.f.: (1/(1-x))*Hypergeometric2F0([1, 1/2]; []; 2*x/(1-x)^2). (End)

More terms from Robert G. Wilson v, Apr 23 2005

A051708 Number of ways to move a chess rook from the lower left corner to square (n,n), with the rook moving only up or right.

Original entry on oeis.org

1, 2, 14, 106, 838, 6802, 56190, 470010, 3968310, 33747490, 288654574, 2480593546, 21400729382, 185239360178, 1607913963614, 13991107041306, 122002082809110, 1065855419418690, 9327252391907790, 81744134786314410, 717367363052796678, 6303080714967178962

Offset: 1

Joe Keane (jgk(AT)jgk.org)

This sequence arises in connection with mean lengths of ascents and descents in Dyck paths as follows. Let u(n,k) denote the mean length of the k-th ascent taken over all Dyck n-paths (A000108) where it is understood that if a Dyck path has fewer than k ascents, then the length of the k-th ascent is 0. For example, the second ascent in UUDUUUDDDDUD has length 3 and its fourth has length 0. Similarly, let v(n,k) denote the mean length of the k-th descent. Then u(k) := lim_{n->infinity} u(n,k) and v(k) := lim_{n->infinity} v(n,k) both exist. The sequence (u(k)){k>=1} begins 3, 8/3, ... and decreases steadily toward a limit of 2. Analogously, v(k) increases steadily from 4/3 toward the same limit of 2. For all k >= 1, u(k+1) exceeds 2 by the same amount that v(k) falls below 2. The common difference u(k+1) - 2 = 2 - v(k) is a(k+1)/3^(2k-1). Thus the common difference sequence begins 2/3, 14/27, 106/243, ..., for k=1,2,3,... . - _David Callan, Jul 14 2006

Number of ways to partition the 1 X (n-1) grid into triangles, with all vertices on grid points. - Peter Kagey, Nov 30 2018

			G.f. = x + 2*x^2 + 14*x^3 + 106*x^4 + 838*x^5 + 6802*x^6 + 56190*x^7 + ...

Posting to newsgroup rec.puzzles, Dec 03 1999 by Nick Wedd (Nick(AT)maproom.co.uk).

Muniru A Asiru, Table of n, a(n) for n = 1..1000 (first 325 terms from Alois P. Heinz)
Alin Bostan, Calcul Formel pour la Combinatoire des Marches [The text is in English], Habilitation à Diriger des Recherches, Laboratoire d'Informatique de Paris Nord, Université Paris 13, December 2017.
"flawr", (Programming Puzzles & Code Golf Stack Exchange user), Partitioning the grid into triangles
E. Yu Jin and M. E. Nebel, A combinatorial proof of the recurrence for rook paths, Electronic J. Comb. 19 (2012) #P57.
M. Kauers and D. Zeilberger, The Computational Challenge of Enumerating High-Dimensional Rook Walks, arXiv:1011.4671 [math.CO], 2010.
Alexander R. Povolotsky, MathOverflow, Are two formulas related to A051708 equivalent?, 2025.
Nick Webb, Thread in newsgroup rec.puzzles, Dec 03 1999. [Broken link]

Main diagonal of the square array given in A035002.
First differences of (A084771-1)/2.
Cf. A144045, A181728.
Row d=2 of A181731.

a:=[1,2];; for n in [3..25] do a[n]:=((10*n-16)*a[n-1]-(9*n-27)*a[n-2])/(n-1); od; a; # Muniru A Asiru, Nov 30 2018

m:=30; R:=PowerSeriesRing(Rationals(), m); Coefficients(R!( ((x*(1-x))/(Sqrt(1-10*x+9*x^2))+x)/2 )); // G. C. Greubel, Dec 01 2018

a:= proc(n) option remember;
      `if`(n<3, n, ((10*n-16)*a(n-1)-(9*n-27)*a(n-2))/(n-1))
    end:
seq(a(n), n=1..30);  # Alois P. Heinz, Jul 21 2012

CoefficientList[Series[(9*x^2 - Sqrt[9*x^2-10*x+1]*x-x) / (2*(9*x-1)), {x,0,20}],x] // Rest (* Jean-François Alcover, Mar 30 2011, after g.f. given by Ralf Stephan *)
RecurrenceTable[{a[1]==1,a[2]==2,a[n]==((10n-16)a[n-1]-(9n-27)a[n-2])/ (n-1)},a,{n,30}] (* Harvey P. Dale, Sep 28 2013 *)

a(n):=sum(binomial(n-1,n-i)*sum(binomial(k+i,i)*binomial(n-1,n-k),k,0,n),i,0,n); /* Vladimir Kruchinin, Apr 20 2015 */

{a(n) = if( n<1, 0, n--; polcoeff( 1/2 + (1 - x) / (2 * sqrt( 1 - 10*x + 9*x^2 + x * O(x^n) ) ), n ) )} /* Michael Somos, Jan 08 2011 */

a(n) = n--; sum(i=0,n, binomial(n-1, n-i)*sum(k=0, n, binomial(k+i, i)*binomial(n-1, n-k))); \\ Michel Marcus, Apr 20 2015

G.f.: ((x*(1-x))/(sqrt(1-10*x+9*x^2)) + x)/2. - Ralf Stephan, Mar 23 2004; confirmed by Martin J. Erickson, Oct 05 2007
D-finite with recurrence a(1)=1; a(2)=2; a(n) = ((10*n-16)*a(n-1) - (9*n-27)*a(n-2)) / (n-1), for n >= 3. - Martin J. Erickson (erickson(AT)truman.edu), Nov 12 2007
a(n) is asymptotic to (sqrt(2)/27)*9^n/(sqrt(Pi*n)). - Martin J. Erickson, Nov 09 2007
G.f.: A(x) satisfies 2 * x^3 = (1 - 9*x) * A(x) * (A(x) - x). - Michael Somos, Jan 08 2011
a(n+1) = Sum_{i=0..n} (C(n-1,n-i)*Sum_{k=0..n} (C(k+i,i)*C(n-1,n-k))). - Vladimir Kruchinin, Apr 20 2015
a(n) = Sum_{k=0..n} (k+1)*C(n-2,k-1)*hypergeom([2+k,2-n],[2],-1) for n >= 2. - Peter Luschny, Apr 20 2015
a(n) = ((-1)^(n-1) * 4^(n-1)) / (48*(n-1)*n) * ( -(4*(n-1)^2 + 16*(n-1) + 28)*JacobiP(n-2, -2*(n-1)-1, 2, -1/2) + (n+2)*(n-2)*JacobiP(n-3, -2*(n-1), 3, -1/2) ) for n > 1. - Alexander R. Povolotsky, Apr 26 2025

More terms from James Sellers, Dec 08 1999

A144045 Number of paths of a chess Rook in a cube, from (1,1,1) to (n,n,n), where the rook may move in steps that are multiples of (1,0,0), (0,0,1), or (0,0,1).

Original entry on oeis.org

1, 6, 222, 9918, 486924, 25267236, 1359631776, 75059524392, 4223303759148, 241144782230124, 13930829740017132, 812470444305924300, 47760356825349969600, 2826309951801018736800, 168207011284961649886800, 10060178088232285063542768, 604273284101165691102038556

Offset: 1

Martin J. Erickson (erickson(AT)truman.edu), Sep 08 2008

nonn

			a(2)=6 because there are 6 Rook paths from (1,1,1) to (2,2,2).
G.f. = x + 6*x^2 + 222*x^3 + 9918*x^4 + 486924*x^5 + 25267236*x^6 + ...

Alin Bostan, Calcul Formel pour la Combinatoire des Marches [The text is in English], Habilitation à Diriger des Recherches, Laboratoire d'Informatique de Paris Nord, Université Paris 13, December 2017.
M. Kauers and D. Zeilberger, The Computational Challenge of Enumerating High-Dimensional Rook Walks, arXiv:1011.4671 [math.CO], 2010.

Cf. A051708.

Row d=3 of A181731.

a(n) satisfies the recurrence relation a(1) = 1; a(2) = 6; a(3) = 222; a(4) = 9918; a(n) = ((-121 n^3 + 575n^2 - 872n + 412)a(n - 1) + (-475n^3 + 4887n^2 - 16202n + 17448)a(n - 2) + (1746n^3 - 19818n^2 + 75060n - 94896)a(n - 3) + (-1152n^3 + 16128n^2 - 74880n + 115200)a(n - 4))/(-(2n^3 - 8n^2 + 10n - 4)), n>= 5.
G.f.: 1+int(6*hypergeom([1/3, 2/3],[2],27*x*(3*x-2)/(4*x-1)^3)/((4*x-1)*(64*x-1)),x). [Mark van Hoeij, Dec 10 2009]
Asymptotics: a(n) ~ 9*sqrt(3)/(40*Pi*n)*64^(n-1). - Frederic Chyzak, 2010

A181728 The number of paths of a chess rook in a 12D hypercube, from (0..0) to (n..n), where the rook may move in steps that are multiples of (1,0..0), (0,1,0..0), ..., (0..0,1).

Original entry on oeis.org

1, 479001600, 402910665227270323200, 1193980357099103775859825737292800, 6221349234739584150822122029143772173312614400, 44698730304001991182769831137859339764690493418024756096000, 395245742455869432937361185087176756463979731526578123254618890928614400

Offset: 0

Manuel Kauers, Nov 16 2010

nonn

			a(1) = 479001600 because there are 479001600 rook paths from (0..0) to (1..1).

Row d=12 of A181731.

a(6) from Alois P. Heinz, Jul 21 2012

A181749 The number of paths of a chess rook in a 4D hypercube, from (0..0) to (n..n), where the rook may move in steps that are multiples of (1,0..0), (0,1,0..0), ..., (0..0,1).

Original entry on oeis.org

1, 24, 6384, 2306904, 964948464, 439331916888, 211383647188320, 105734905550405400, 54434276297806242480, 28652982232251791825880, 15350736081585866511795024, 8343014042738696079671066904, 4588687856038215036178166258304

Offset: 0

Manuel Kauers, Nov 16 2010

nonn

			a(1) = 24 because there are 24 rook paths from (0..0) to (1..1).

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

Row d=4 of A181731.

a:= proc(n) option remember; `if`(n<4, [1, 24, 6384, 2306904][n+1],
      ((44148546*n^7-417566955*n^6+1582366209*n^5-3082719955*n^4
      +3301523581*n^3-1923587242*n^2+559133416*n-61892160)*(n-1)^2*
      a(n-1) -2*(n-2)*(131501097*n^8-1572004161*n^7+7935973542*n^6
      -21971456652*n^5+36200366619*n^4-35926876063*n^3+20608609302*n^2
      -6086148644*n+688049040)*a(n-2) +(393838614*n^7-4640973051*n^6
      +22263043023*n^5-55659442951*n^4+77029268163*n^3
      -57647348158*n^2+20864000120*n-2733950400)*(n-3)^2*a(n-3)
      -5000*(34983*n^4-138138*n^3+184101*n^2-92498*n+14640)*(n-3)^2*
      (n-4)^3*a(n-4))/ (2*n^3*(464360-1015046*n+808413*n^2
      -278070*n^3+34983*n^4)*(n-1)^2))
    end:
seq(a(n), n=0..20); # Alois P. Heinz, Aug 31 2014

b[l_List] := b[l] = If[Union[l]~Complement~{0} == {}, 1, Sum[Sum[b[Sort[ ReplacePart[l, i -> l[[i]] - j]]], {j, 1, l[[i]]}], {i, 1, Length[l]}]];
a[n_] := b[Array[n&, 4]];
a /@ Range[0, 20] (* Jean-François Alcover, Dec 18 2020, after Alois P. Heinz in A181731 *)

Recursion: see Maple program. - Alois P. Heinz, Aug 31 2014

a(n) ~ 8 * 5^(4*n-1) / (3*sqrt(3) * (Pi*n)^(3/2)). - Vaclav Kotesovec, Sep 03 2014

A181724 The number of paths of a chess rook in a 8D hypercube, from (0..0) to (n..n), where the rook may move in steps that are multiples of (1,0..0), (0,1,0..0), ..., (0..0,1).

Original entry on oeis.org

1, 40320, 214899027840, 2509137924026751360, 41795104403987233709518080, 852847938704373386478865686645120, 19846219244619878972245087341015659057280, 506348195597089273505079176351561351976609740160

Offset: 0

Manuel Kauers, Nov 16 2010

nonn

			a(1) = 40320 because there are 40320 rook paths from (0..0) to (1..1).

Row d=8 of A181731.

A181725 The number of paths of a chess rook in a 9D hypercube, from (0..0) to (n..n), where the rook may move in steps that are multiples of (1,0..0), (0,1,0..0), ..., (0..0,1).

Original entry on oeis.org

1, 362880, 33007837322880, 7408611474125625953280, 2499611266020127048565292881280, 1064141699563485513180737844317706666240, 526577363627345975232160422620146408876598167680, 289514065258843883748159731480148589989905149052842682880

Offset: 0

Manuel Kauers, Nov 16 2010

nonn

			a(1) = 362880 because there are 362880 rook paths from (0..0) to (1..1).

Row d=9 of A181731.

A181726 The number of paths of a chess rook in a 10D hypercube, from (0..0) to (n..n), where the rook may move in steps that are multiples of (1,0..0), (0,1,0..0), ..., (0..0,1).

Original entry on oeis.org

1, 3628800, 6290830003852800, 30306073546461323055916800, 231242270452155338291905203314956800, 2293197130058463838438742129627609575368940800, 26941822036577030394903099245279465611395585827577676800

Offset: 0

Manuel Kauers, Nov 16 2010

nonn

			a(1) = 3628800 because there are 3628800 rook paths from (0..0) to (1..1).

Row d=10 of A181731.

A181727 The number of paths of a chess rook in a 11D hypercube, from (0..0) to (n..n), where the rook may move in steps that are multiples of (1,0..0), (0,1,0..0), ..., (0..0,1).

Original entry on oeis.org

1, 39916800, 1456812592995513600, 166369951631853645510591187200, 31707078596527364069316526441204831526400, 8089435115221815003427192379950659547969112311680000, 2492107900477900258313589438717998843635090670139189341868499200

Offset: 0

Manuel Kauers, Nov 16 2010

nonn

			a(1) = 39916800 because there are 39916800 rook paths from (0..0) to (1..1).

Row d=11 of A181731.

a(6) from Alois P. Heinz, Jul 21 2012

A181750 The number of paths of a chess rook in a 5D hypercube, from (0..0) to (n..n), where the rook may move in steps that are multiples of (1,0..0), (0,1,0..0), ..., (0..0,1).

Original entry on oeis.org

1, 120, 291720, 1085674320, 4927561419120, 25071989721176760, 137401053406474591320, 793279085081986319145120, 4760210822189950253433759120, 29426738284267047709626231969120, 186257720453050086737999575854359760, 1201788369927033696254110199515917069120

Offset: 0

Manuel Kauers, Nov 16 2010

nonn

			a(1) = 120 because there are 120 rook paths from (0..0) to (1..1).

Row d=5 of A181731.

cp's OEIS Frontend

A105749 Number of ways to use the elements of {1,...,k}, 0 <= k <= 2n, once each to form a sequence of n sets, each having 1 or 2 elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

Extensions

A051708 Number of ways to move a chess rook from the lower left corner to square (n,n), with the rook moving only up or right.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

Maxima

PARI

PARI

Formula

Extensions

A144045 Number of paths of a chess Rook in a cube, from (1,1,1) to (n,n,n), where the rook may move in steps that are multiples of (1,0,0), (0,0,1), or (0,0,1).

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A181728 The number of paths of a chess rook in a 12D hypercube, from (0..0) to (n..n), where the rook may move in steps that are multiples of (1,0..0), (0,1,0..0), ..., (0..0,1).

Views

Author

Keywords

Examples

Crossrefs

Extensions

A181749 The number of paths of a chess rook in a 4D hypercube, from (0..0) to (n..n), where the rook may move in steps that are multiples of (1,0..0), (0,1,0..0), ..., (0..0,1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A181724 The number of paths of a chess rook in a 8D hypercube, from (0..0) to (n..n), where the rook may move in steps that are multiples of (1,0..0), (0,1,0..0), ..., (0..0,1).

Views

Author

Keywords

Examples

Crossrefs

A181725 The number of paths of a chess rook in a 9D hypercube, from (0..0) to (n..n), where the rook may move in steps that are multiples of (1,0..0), (0,1,0..0), ..., (0..0,1).

Views

Author

Keywords

Examples

Crossrefs

A181726 The number of paths of a chess rook in a 10D hypercube, from (0..0) to (n..n), where the rook may move in steps that are multiples of (1,0..0), (0,1,0..0), ..., (0..0,1).

Views

Author

Keywords

Examples

Crossrefs

A181727 The number of paths of a chess rook in a 11D hypercube, from (0..0) to (n..n), where the rook may move in steps that are multiples of (1,0..0), (0,1,0..0), ..., (0..0,1).