A264902 -id:A264902 - cp's OEIS frontend

A306343 Number T(n,k) of defective (binary) heaps on n elements with k defects; triangle T(n,k), n>=0, 0<=k<=max(0,n-1), read by rows.

1, 1, 1, 1, 2, 2, 2, 3, 9, 9, 3, 8, 28, 48, 28, 8, 20, 90, 250, 250, 90, 20, 80, 360, 1200, 1760, 1200, 360, 80, 210, 1526, 5922, 12502, 12502, 5922, 1526, 210, 896, 7616, 34160, 82880, 111776, 82880, 34160, 7616, 896, 3360, 32460, 185460, 576060, 1017060, 1017060, 576060, 185460, 32460, 3360

Offset: 0

Alois P. Heinz, Feb 08 2019

A defect in a defective heap is a parent-child pair not having the correct order.
T(n,k) is the number of permutations p of [n] having exactly k indices i in {1,...,n} such that p(i) > p(floor(i/2)).
T(n,0) counts perfect (binary) heaps on n elements (A056971).

			T(4,0) = 3: 4231, 4312, 4321.
T(4,1) = 9: 2413, 3124, 3214, 3241, 3412, 3421, 4123, 4132, 4213.
T(4,2) = 9: 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2431, 3142.
T(4,3) = 3: 1234, 1243, 1324.
(The examples use max-heaps.)
Triangle T(n,k) begins:
    1;
    1;
    1,    1;
    2,    2,     2;
    3,    9,     9,     3;
    8,   28,    48,    28,      8;
   20,   90,   250,   250,     90,    20;
   80,  360,  1200,  1760,   1200,   360,    80;
  210, 1526,  5922, 12502,  12502,  5922,  1526,  210;
  896, 7616, 34160, 82880, 111776, 82880, 34160, 7616, 896;
  ...

Alois P. Heinz, Rows n = 0..190, flattened
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap

Columns k=0-10 give: A056971, A323957, A323958, A323959, A323960, A323961, A323962, A323963, A323964, A323965, A323966.
Row sums give A000142.
T(n,floor(n/2)) gives A306356.
Cf. A001286, A001710, A008292, A038720, A229039, A230056, A264902, A306393.

b:= proc(u, o) option remember; local n, g, l; n:= u+o;
      if n=0 then 1
    else g:= 2^ilog2(n); l:= min(g-1, n-g/2); expand(
         add(add(binomial(j-1, i)*binomial(n-j, l-i)*
         b(i, l-i)*b(j-1-i, n-l-j+i), i=0..min(j-1, l)), j=1..u)+
         add(add(binomial(j-1, i)*binomial(n-j, l-i)*
         b(l-i, i)*b(n-l-j+i, j-1-i), i=0..min(j-1, l)), j=1..o)*x)
      fi
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
seq(T(n), n=0..10);

b[u_, o_] := b[u, o] = Module[{n = u + o, g, l},
     If[n == 0, 1, g := 2^Floor@Log[2, n]; l = Min[g-1, n-g/2]; Expand[
     Sum[Sum[ Binomial[j-1, i]* Binomial[n-j, l-i]*b[i, l-i]*
     b[j-1-i, n-l-j+i], {i, 0, Min[j-1, l]}], {j, 1, u}]+
     Sum[Sum[Binomial[j - 1, i]* Binomial[n-j, l-i]*b[l-i, i]*
     b[n-l-j+i, j-1-i], {i, 0, Min[j-1, l]}], {j, 1, o}]*x]]];
T[n_] := CoefficientList[b[n, 0], x];
T /@ Range[0, 10] // Flatten (* Jean-François Alcover, Feb 17 2021, after Alois P. Heinz *)

T(n,k) = T(n,n-1-k) for n > 0.
Sum_{k>=0} k * T(n,k) = A001286(n).
Sum_{k>=0} (k+1) * T(n,k) = A001710(n-1) for n > 0.
Sum_{k>=0} (k+2) * T(n,k) = A038720(n) for n > 0.
Sum_{k>=0} (k+3) * T(n,k) = A229039(n) for n > 0.
Sum_{k>=0} (k+4) * T(n,k) = A230056(n) for n > 0.

A101334 a(n) = n^n - (n+1)^(n-1).

Original entry on oeis.org

0, 0, 1, 11, 131, 1829, 29849, 561399, 11994247, 287420489, 7642052309, 223394306387, 7123940054219, 246181194216957, 9165811757198641, 365836296342931439, 15584321022199735823, 705800730789742512401, 33866021217511735389485, 1716275655660313589123979

Offset: 0

Jorge Coveiro, Dec 24 2004

nonn

b(n) = n^n mod (n+1)^(n-1)  begins: 0, 0, 1, 11, 6, 533, 13042, 37111, 2428309, ... - Alex Ratushnyak, Aug 06 2012
a(n) is the number of functions f:{1,2,...,n}->{1,2,...,n} with at least one cycle of length >= 2. - Geoffrey Critzer, Jan 11 2013
Number of defective parking functions of length n and at least one defect. - Alois P. Heinz, Aug 18 2017

			a(3) = 3^3 - 4^2 = 27-16 = 11.

Alois P. Heinz, Table of n, a(n) for n = 0..386
Peter J. Cameron, Daniel Johannsen, Thomas Prellberg, and Pascal Schweitzer, Counting Defective Parking Functions, arXiv:0803.0302 [math.CO], 2008.
Luca Ferrari and Francesco Verciani, On the enumeration of permutation-invariant and complete Naples parking functions, arXiv:2411.06876 [math.CO], 2024. See p. 11.

Cf. A000272, A000312, A046065, A264902.

ReplacePart[Table[n^n-(n+1)^(n-1),{n,0,nn}],0,1]  (* Geoffrey Critzer, Jan 11 2013 *)

PARI
```
for(x=1,20,print( x^x-(x+1)^(x-1) ))
```

print([n**n - (n+1)**(n-1) for n in range(33)]) # Alex Ratushnyak, Aug 06 2012

E.g.f.: 1/(1-T(x)) - exp(T(x)) where T(x) is the e.g.f. for A000169. - Geoffrey Critzer, Jan 11 2013
a(n) = Sum_{k>0} A264902(n,k). - Alois P. Heinz, Nov 29 2015
a(n) = A000312(n) - A000272(n+1). - Alois P. Heinz, Aug 18 2017

a(0) prepended by Alex Ratushnyak, Aug 06 2012

A274279 Expansion of e.g.f.: tanh(x*W(x)), where W(x) = LambertW(-x)/(-x).

Original entry on oeis.org

1, 2, 7, 40, 341, 3936, 57107, 992384, 20025385, 459466240, 11804134079, 335571265536, 10456512176189, 354362575314944, 12975301760361163, 510462668072058880, 21472710312090391889, 961728814178702327808, 45692671937666739799799, 2295278998002033651875840, 121545436687537993689631525, 6767130413049423041105231872, 395177438856180565803457658627, 24152146710231984411570685870080

Offset: 1

Paul D. Hanna, Jun 19 2016

nonn

			E.g.f.: A(x) = x + 2*x^2/2! + 7*x^3/3! + 40*x^4/4! + 341*x^5/5! + 3936*x^6/6! + 57107*x^7/7! + 992384*x^8/8! + 20025385*x^9/9! + 459466240*x^10/10! + 11804134079*x^11/11! + 335571265536*x^12/12! +...
such that A(x) = tanh(x*W(x))
where W(x) = LambertW(-x)/(-x) begins
W(x) = 1 + x + 3*x^2/2! + 16*x^3/3! + 125*x^4/4! + 1296*x^5/5! + 16807*x^6/6! + 262144*x^7/7! + 4782969*x^8/8! + 100000000*x^9/9! +...+ (n+1)^(n-1)*x^n/n! +...
and satisfies W(x) = exp(x*W(x)).
Also, A(x) = (W(x)^2 - 1)/(W(x)^2 + 1), where
W(x)^2 = 1 + 2*x + 8*x^2/2! + 50*x^3/3! + 432*x^4/4! + 4802*x^5/5! + 65536*x^6/6! + 1062882*x^7/7! + 20000000*x^8/8! +...+ 2*(n+2)^(n-1)*x^n/n! +...

Paul D. Hanna, Table of n, a(n) for n = 1..200

Cf. A000272, A195136, A238085, A264902, A274278, A277468, A277480.

Rest[CoefficientList[Series[(LambertW[-x]^2 - x^2)/(LambertW[-x]^2 + x^2), {x, 0, 20}], x] * Range[0, 20]!] (* Vaclav Kotesovec, Jun 23 2016 *)
Rest[With[{nmax=30}, CoefficientList[Series[Tanh[-LambertW[-x]], {x,0,nmax}], x]*Range[0, nmax]!]] (* G. C. Greubel, Feb 19 2018 *)

{a(n) = my(W=sum(m=0, n, (m+1)^(m-1)*x^m/m!) +x*O(x^n)); n!*polcoeff(tanh(x*W), n)}
for(n=1, 30, print1(a(n), ", "))

{a(n) = my(W = sum(m=0, n, (m+1)^(m-1)*x^m/m!) +x*O(x^n)); n!*polcoeff( (W^2 - 1)/(W^2 + 1), n)}
for(n=1, 30, print1(a(n), ", "))

x='x+O('x^30); Vec(serlaplace(tanh(-lambertw(-x)))) \\ G. C. Greubel, Feb 19 2018

E.g.f.: (W(x)^2 - 1)/(W(x)^2 + 1), where W(x) = LambertW(-x)/(-x) = exp(x*W(x)) = Sum_{n>=0} (n+1)^(n-1)*x^n/n!.
a(n) ~ 4*exp(2) * n^(n-1) / (1+exp(2))^2. - Vaclav Kotesovec, Jun 23 2016
a(n) = Sum_{k=0..n-1} (-1)^k * A264902(n,k). - Alois P. Heinz, Aug 08 2022

A036276 a(n) = A001864(n+1)/2.

Original entry on oeis.org

0, 1, 12, 156, 2360, 41400, 831012, 18832576, 476200944, 13301078400, 406907517500, 13534968927744, 486470108273448, 18790567023993856, 776343673316956500, 34165751933338828800, 1595693034061797583328, 78831769938218360930304, 4107393289066148637198444

Offset: 0

N. J. A. Sloane

This is Sum_{all n^(n-2) labeled trees T on n nodes} Sum_{1<=i

a(n) is the total number of all defects in defective parking functions of length n+1. - Alois P. Heinz, Nov 28 2015

With offset 1, a(n) is the number of unordered pairs {f,g} where for some nonempty proper subset S of [n], f:S->S and g:[n]\S->[n]\S. - Geoffrey Critzer, Apr 23 2017

Alois P. Heinz, Table of n, a(n) for n = 0..380
J. Riordan and N. J. A. Sloane, Enumeration of rooted trees by total height, J. Austral. Math. Soc., vol. 10 pp. 278-282, 1969.
Peter Winkler, Mean distance in a tree, in Computational algorithms, operations research and computer science (Burnaby, BC, 1987). Discrete Appl. Math. 27 (1990), no. 1-2, 179-185. [For background information only.]

Cf. A001864, A264902.

Table[Sum[Binomial[n, k] (n - k)^(n - k) k^k, {k, n - 1}]/2, {n, 18}] (* Michael De Vlieger, Apr 24 2017, after Harvey P. Dale at A001864 *)

from math import math
def A036276(n): return sum(comb(n+1,k)*(n+1-k)**(n+1-k)*k**k for k in range(1,(n>>1)+1)) + (comb(n+1,m:=n+1>>1)*m**(n+1)>>1 if n&1 else 0) # Chai Wah Wu, Apr 26 2023

a(n) = Sum_{k>0} k * A264902(n+1,k). - Alois P. Heinz, Nov 28 2015

A140647 Number of car parking assignments of n cars in n spaces, if one car does not park.

Original entry on oeis.org

1, 10, 107, 1346, 19917, 341986, 6713975, 148717762, 3674435393, 100284451730, 2998366140915, 97510068994690, 3428106725444117, 129590070259759042, 5242767731544271343, 226057515078414496898, 10350122253780835777545, 501543984793431059579122

Offset: 2

Jonathan Vos Post, Jul 09 2008

nonn

			a(3) = 10: [1,3,3], [2,2,2], [2,2,3], [2,3,2], [2,3,3], [3,1,3], [3,2,2], [3,2,3], [3,3,1], [3,3,2].

Alois P. Heinz, Table of n, a(n) for n = 2..380
Peter J. Cameron, Daniel Johannsen, Thomas Prellberg and Pascal Schweitzer, Counting Defective Parking Functions

Cf. A000272.

Column k=1 of A264902.

a(n) = 2*(n+2)^(n-1)-(3*n+1)*(n+1)^(n-2). - Vladeta Jovovic, Jul 21 2008
a(n) = 2*A007830(n-1)-A016777(n)*A007830(n-2). - R. J. Mathar, Aug 09 2008
a(n) ~ (2*exp(2) - 3*exp(1)) * n^(n-1). - Vaclav Kotesovec, Aug 19 2017

Extended beyond a(10) by R. J. Mathar, Aug 09 2008

A264903 Number of defective parking functions of length 2n and defect n.

Original entry on oeis.org

1, 1, 23, 1442, 176843, 36046214, 11023248678, 4719570364004, 2693983725947891, 1976997422623843358, 1813499364725872444178, 2033181299894696684493980, 2735368952738645928181452734, 4349180440965667221581315433212, 8067655677482008559181766540571948

Offset: 0

Alois P. Heinz, Nov 28 2015

nonn

			a(2) = 23: [1,4,4,4], [2,4,4,4], [3,3,3,3], [3,3,3,4], [3,3,4,3], [3,3,4,4], [3,4,3,3], [3,4,3,4], [3,4,4,3], [3,4,4,4], [4,1,4,4], [4,2,4,4], [4,3,3,3], [4,3,3,4], [4,3,4,3], [4,3,4,4], [4,4,1,4], [4,4,2,4], [4,4,3,3], [4,4,3,4], [4,4,4,1], [4,4,4,2], [4,4,4,3].

Alois P. Heinz, Table of n, a(n) for n = 0..200
Peter J. Cameron, Daniel Johannsen, Thomas Prellberg, Pascal Schweitzer, Counting Defective Parking Functions, arXiv:0803.0302 [math.CO], 2008

Cf. A264902.

S:= (n, k)-> `if`(k=0, n^n, add(binomial(n, i)*k*
             (k+i)^(i-1)*(n-k-i)^(n-i), i=0..n-k)):
a:= n-> S(2*n, n)-S(2*n, n+1):
seq(a(n), n=0..20);

s[n_, k_] :=  Sum[Binomial[n, i]*k*(k + i)^(i - 1)*(n - k - i)^(n - i), {i, 0, n - k}]; Flatten[{1, Table[s[2*n, n] - s[2*n, n + 1], {n, 1, 20}]}] (* Vaclav Kotesovec, Aug 19 2017 *)
(* constant d *) 4*((1 - r)/(2 - r))^(2 - r)*((1 + r)/r)^r /.FindRoot[(((2 - r)*(1 + r))/((1 - r)*r))^(1 - r^2) == E^2, {r, 1/2}, WorkingPrecision -> 100] (* Vaclav Kotesovec, Aug 19 2017 *)

a(n) = A264902(2n,n).

a(n) ~ c * d^n * n^(2*n), where d = 4 * ((1-r)/(2-r))^(2-r) * ((1+r)/r)^r = 1.37946886318881879639758089832698445354075122787883765455607405487162077... where r = 0.3507604755943619981673674677676002458987390260372260977704596... is the root of the equation (((2-r)*(1+r))/((1-r)*r))^(1-r^2) = exp(2) and c = 0.71338164469811281152311896105657925861924201644973836628479626510877... - Vaclav Kotesovec, Aug 19 2017

A291128 Number of defective parking functions of length n and defect two.

Original entry on oeis.org

1, 23, 436, 8402, 173860, 3924685, 96920092, 2612981360, 76612170196, 2432096760755, 83225580995116, 3056917610828590, 120045033150878404, 5021755110536666777, 223031850751250882620, 10484575680391970139980, 520227143451578652486196, 27175721567427682443046975

Offset: 3

Alois P. Heinz, Aug 18 2017

nonn

Alois P. Heinz, Table of n, a(n) for n = 3..387
Peter J. Cameron, Daniel Johannsen, Thomas Prellberg, Pascal Schweitzer, Counting Defective Parking Functions, arXiv:0803.0302 [math.CO], 2008

Column k=2 of A264902.

S:= (n, k)-> add(binomial(n, i)*k*(k+i)^(i-1)*(n-k-i)^(n-i), i=0..n-k):
a:= n-> S(n, 2)-S(n, 3):
seq(a(n), n=3..23);

S[n_, k_] := Sum[Binomial[n, i]*k*(k+i)^(i-1)*(n-k-i)^(n-i), {i, 0, n-k}];
a[n_] := S[n, 2] - S[n, 3];
Table[a[n], {n, 3, 23}] (* Jean-François Alcover, Aug 20 2018, from Maple *)

a(n) ~ (7*exp(1)/2 - 8*exp(2) + 3*exp(3)) * n^(n-1). - Vaclav Kotesovec, Aug 19 2017

A291129 Number of defective parking functions of length n and defect three.

Original entry on oeis.org

1, 46, 1442, 41070, 1166083, 34268902, 1059688652, 34723442062, 1208687001381, 44701813604150, 1754724115372438, 72987949807322222, 3210789166789472775, 149073947870611952326, 7289995971215959818304, 374726414201304528649678, 20207920615298454956444905

Offset: 4

Alois P. Heinz, Aug 18 2017

nonn

Alois P. Heinz, Table of n, a(n) for n = 4..387
Peter J. Cameron, Daniel Johannsen, Thomas Prellberg, Pascal Schweitzer, Counting Defective Parking Functions, arXiv:0803.0302 [math.CO], 2008.

Column k=3 of A264902.

S:= (n, k)-> add(binomial(n, i)*k*(k+i)^(i-1)*(n-k-i)^(n-i), i=0..n-k):
a:= n-> S(n, 3)-S(n, 4):
seq(a(n), n=4..23);

S[n_, k_] := Sum[Binomial[n, i]*k*(k+i)^(i-1)*(n-k-i)^(n-i), {i, 0, n-k}];
a[n_] := S[n, 3] - S[n, 4];
Table[a[n], {n, 4, 23}] (* Jean-François Alcover, Feb 24 2019, from Maple *)

a(n) ~ (-13*exp(1)/6 + 14*exp(2) - 15*exp(3) + 4*exp(4)) * n^(n-1). - Vaclav Kotesovec, Aug 19 2017

A291130 Number of defective parking functions of length n and defect four.

Original entry on oeis.org

1, 87, 4320, 176843, 6768184, 256059854, 9846223168, 390516805362, 16102219296008, 693122084961945, 31208245366326896, 1470819863019421317, 72549461960461640120, 3743176448672690767272, 201836660477563528892704, 11362223977488695430091444

Offset: 5

Alois P. Heinz, Aug 18 2017

nonn

Alois P. Heinz, Table of n, a(n) for n = 5..386
Peter J. Cameron, Daniel Johannsen, Thomas Prellberg, Pascal Schweitzer, Counting Defective Parking Functions, arXiv:0803.0302 [math.CO], 2008.

Column k=4 of A264902.

S:= (n, k)-> add(binomial(n, i)*k*(k+i)^(i-1)*(n-k-i)^(n-i), i=0..n-k):
a:= n-> S(n, 4)-S(n, 5):
seq(a(n), n=5..23);

S[n_, k_] := Sum[Binomial[n, i]*k*(k+i)^(i-1)*(n-k-i)^(n-i), {i, 0, n-k}];
a[n_] := S[n, 4] - S[n, 5];
Table[a[n], {n, 5, 23}] (* Jean-François Alcover, Feb 24 2019, from Maple *)

a(n) ~ (7*exp(1)/8 - 44*exp(2)/3 + 69*exp(3)/2 - 24*exp(4) + 5*exp(5)) * n^(n-1). - Vaclav Kotesovec, Aug 19 2017

A291131 Number of defective parking functions of length n and defect five.

Original entry on oeis.org

1, 162, 12357, 710314, 36046214, 1735513330, 82324649310, 3930328083098, 191251911975191, 9558232936557458, 492897541966818651, 26298973648144245066, 1454100613639405907108, 83377530695619365120818, 4959049035365905488761452, 305903708967397161238879674

Offset: 6

Alois P. Heinz, Aug 18 2017

nonn

Alois P. Heinz, Table of n, a(n) for n = 6..386
Peter J. Cameron, Daniel Johannsen, Thomas Prellberg, Pascal Schweitzer, Counting Defective Parking Functions, arXiv:0803.0302 [math.CO], 2008.

Column k=5 of A264902.

S:= (n, k)-> add(binomial(n, i)*k*(k+i)^(i-1)*(n-k-i)^(n-i), i=0..n-k):
a:= n-> S(n, 5)-S(n, 6):
seq(a(n), n=6..23);

S[n_, k_] := Sum[Binomial[n, i]*k*(k+i)^(i-1)*(n-k-i)^(n-i), {i, 0, n-k}];
a[n_] := S[n, 5] - S[n, 6];
Table[a[n], {n, 6, 23}] (* Jean-François Alcover, Feb 24 2019, from Maple *)

a(n) ~ (-31*exp(1)/120 + 32*exp(2)/3 - 99*exp(3)/2 + 68*exp(4) - 35*exp(5) + 6*exp(6)) * n^(n-1). - Vaclav Kotesovec, Aug 19 2017

Showing 1-10 of 16 results. Next

cp's OEIS Frontend

A306343 Number T(n,k) of defective (binary) heaps on n elements with k defects; triangle T(n,k), n>=0, 0<=k<=max(0,n-1), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A101334 a(n) = n^n - (n+1)^(n-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A274279 Expansion of e.g.f.: tanh(x*W(x)), where W(x) = LambertW(-x)/(-x).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

A036276 a(n) = A001864(n+1)/2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

Formula

A140647 Number of car parking assignments of n cars in n spaces, if one car does not park.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A264903 Number of defective parking functions of length 2n and defect n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A291128 Number of defective parking functions of length n and defect two.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica