A102366 Number of subsets of {1,2,...,n} in which exactly half of the elements are less than or equal to sqrt(n).

1, 1, 2, 3, 6, 10, 15, 21, 28, 84, 120, 165, 220, 286, 364, 455, 1820, 2380, 3060, 3876, 4845, 5985, 7315, 8855, 10626, 53130, 65780, 80730, 98280, 118755, 142506, 169911, 201376, 237336, 278256, 324632, 1947792, 2324784, 2760681, 3262623, 3838380, 4496388

Offset

0,3

Comments

Also number of subsets of [n] in which exactly half of the elements are squares: a(5) = 10: {}, {1,2}, {1,3}, {1,5}, {2,4}, {3,4}, {4,5}, {1,2,3,4}, {1,2,4,5}, {1,3,4,5}. - Alois P. Heinz, Oct 11 2022

Links

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

Formula

a(n) = Sum_k C(floor(sqrt(n)),k)*C(n-floor(sqrt(n)),k) = A048093(n) + 1 = a(n-1) + A084919(n-1).

a(n) = binomial(n, floor(sqrt(n))). - Paul D. Hanna, Jun 25 2011

Example

a(5) = 10 since the ten subsets of {1,2,3,4,5} are { }, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {1,2, 3,4}, {1,2, 3,5} and {1,2, 4,5}.

Prog

(PARI) {a(n)=if(n<0, 0, binomial(n, sqrtint(n)))} /* Paul D. Hanna */
(PARI) {a(n)=sum(k=0, sqrtint(n), binomial(sqrtint(n), k)*binomial(n-sqrtint(n), k))}

Crossrefs

Cf. A011782 for number of subsets with an even number of elements.

Cf. A000290.

Sequence in context: A215891 A254033 A356314 * A152452 A217741 A074134

Adjacent sequences: A102363 A102364 A102365 * A102367 A102368 A102369

Keyword

nonn

Author

Henry Bottomley, Feb 22 2005

Status

approved