Packing Ferrers Shapes

Noga Alon; Miklós Bóna; Joel Spencer

doi:10.1017/S0963548300004223

Packing Ferrers Shapes

Noga Alon, Miklós Bóna, Joel Spencer

Research output: Contribution to journal › Article › peer-review

Abstract

Answering a question of Wilf, we show that, if n is sufficiently large, then one cannot cover an n x p(n) rectangle using each of the p(n) distinct Ferrers shapes of size n exactly once. Moreover, the maximum number of pairwise distinct, non-overlapping Ferrers shapes that can be packed in such a rectangle is only Θ(p(n)/log n).

Original language	English (US)
Pages (from-to)	205-211
Number of pages	7
Journal	Combinatorics Probability and Computing
Volume	9
Issue number	3
DOIs	https://doi.org/10.1017/S0963548300004223
State	Published - 2000

ASJC Scopus subject areas

Theoretical Computer Science
Statistics and Probability
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1017/S0963548300004223

Cite this

@article{24ef17c87f6749599ec0c63b0281b169,

title = "Packing Ferrers Shapes",

abstract = "Answering a question of Wilf, we show that, if n is sufficiently large, then one cannot cover an n x p(n) rectangle using each of the p(n) distinct Ferrers shapes of size n exactly once. Moreover, the maximum number of pairwise distinct, non-overlapping Ferrers shapes that can be packed in such a rectangle is only Θ(p(n)/log n).",

author = "Noga Alon and Mikl{\'o}s B{\'o}na and Joel Spencer",

year = "2000",

doi = "10.1017/S0963548300004223",

language = "English (US)",

volume = "9",

pages = "205--211",

journal = "Combinatorics Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

number = "3",

}

TY - JOUR

T1 - Packing Ferrers Shapes

AU - Alon, Noga

AU - Bóna, Miklós

AU - Spencer, Joel

PY - 2000

Y1 - 2000

N2 - Answering a question of Wilf, we show that, if n is sufficiently large, then one cannot cover an n x p(n) rectangle using each of the p(n) distinct Ferrers shapes of size n exactly once. Moreover, the maximum number of pairwise distinct, non-overlapping Ferrers shapes that can be packed in such a rectangle is only Θ(p(n)/log n).

AB - Answering a question of Wilf, we show that, if n is sufficiently large, then one cannot cover an n x p(n) rectangle using each of the p(n) distinct Ferrers shapes of size n exactly once. Moreover, the maximum number of pairwise distinct, non-overlapping Ferrers shapes that can be packed in such a rectangle is only Θ(p(n)/log n).

UR - http://www.scopus.com/inward/record.url?scp=0442311731&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0442311731&partnerID=8YFLogxK

U2 - 10.1017/S0963548300004223

DO - 10.1017/S0963548300004223

M3 - Article

AN - SCOPUS:0442311731

SN - 0963-5483

VL - 9

SP - 205

EP - 211

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

IS - 3

ER -

Packing Ferrers Shapes

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this