{"id":258836,"date":"2026-07-13T16:32:24","date_gmt":"2026-07-13T13:32:24","guid":{"rendered":"https:\/\/1kitap1.com\/en\/discrete-mathematics-kenneth-rosens\/"},"modified":"2026-07-13T16:32:24","modified_gmt":"2026-07-13T13:32:24","slug":"discrete-mathematics-kenneth-rosens","status":"publish","type":"post","link":"https:\/\/1kitap1.com\/en\/discrete-mathematics-kenneth-rosens\/","title":{"rendered":"Discrete Mathematics – Kenneth Rosens"},"content":{"rendered":"
\"<\/figure>\n

The Birthday Problem A famous puzzle asks for the smallest number of people needed in a room so that it is more likely than not that at least two of them have the same day of the year as their birthday. Most people \ufb01nd the answer, which we determine in Example 13, to be surprisingly small.<\/p>\n

After we solve this famous problem, we will show how similar reasoning can be adapted to solve a question about hashing functions. The Birthday Problem What is the minimum number of people who need to be in a room so that the probability that at least two of them have the same birthday is greater than 1\/2? Solution: First, we state some assumptions. We assume that the birthdays of the people in the room are independent.<\/p>\n

Furthermore, we assume that each birthday is equally likely and that there are 366 days in the year. (In reality, more people are born on some days of the year than others, such as days nine months after some holidays including New Year\u2019s Eve, and only leap years have 366 days.) To \ufb01nd the probability that at least two of n people in a room have the same birthday, we \ufb01rst calculate the probability pn that these people all have different birthdays.<\/p>\n

Then, the probability that at least two people have the same birthday is 1\u2013 pn. To compute pn, we consider the birthdays of the n people in some \ufb01xed order. Imagine them entering the room one at a time; we will compute the probability that each successive person entering the room has a birthday different from those of the people already in the room.<\/p>\n

The birthday of the \ufb01rst person certainly does not match the birthday of someone already in the room. The probability that the birthday of the second person is different from that of the \ufb01rst person is 365\/366 because the second person has a different birthday when he or she was born on one of the 365 days of the year other than the day the \ufb01rst person was born. (The assumption that it is equally likely for someone to be born on any of the 366 days of the year enters into this and subsequent steps.)<\/p>\n

The probability that the third person has a birthday different from both the birthdays of the \ufb01rst and second people given that these two people have different birthdays is 364\/366. In general, the probability that the jth person, with 2 \u2264j \u2264366, has a birthday different from the 7 \/ Discrete Probability birthdays of the j \u22121 people already in the room given that these j \u22121 people have different birthdays is 366 \u2212( j \u22121) = 367 \u2212j .<\/p>\n

\n

Published by McGraw-Hill, a business unit of The McGraw-Hill Companies, Inc., 1221 Avenue of the Americas, New York, NY 10020. Copyright \u00a9 2012 by The McGraw-Hill Companies, Inc. All rights reserved. Previous editions \u00a9 2007, 2003, and 1999. No part of this publication may be reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior written consent of The McGraw-Hill Companies, Inc., including, but not limited to, in any network or other electronic storage or transmission, or broadcast for distance learning.<\/p>\n

Some ancillaries, including electronic and print components, may not be available to customers outside the United States. This book is printed on acid-free paper. 1 2 3 4 5 6 7 8 9 0 DOW\/DOW 1 0 9 8 7 6 5 4 3 2 1 ISBN 978-0-07-338309-5 MHID 0-07-338309-0 Vice President & Editor-in-Chief: Marty Lange Editorial Director: Michael Lange Global Publisher: Raghothaman Srinivasan Executive Editor: Bill Stenquist Development Editors: Lorraine K. Buczek\/Rose Kernan Senior Marketing Manager: Curt Reynolds Project Manager: Robin A. Reed Buyer: Sandy Ludovissy Design Coordinator: Brenda A.<\/p>\n

Rolwes Cover painting: Jasper Johns, Between the Clock and the Bed, 1981. Oil on Canvas (72 \u00d7 126 1\/4 inches) Collection of the artist. Photograph by Glenn Stiegelman. Cover Art \u00a9 Jasper Johns\/Licensed by VAGA, New York, NY Cover Designer: Studio Montage, St. Louis, Missouri Lead Photo Research Coordinator: Carrie K.<\/p>\n

Burger Media Project Manager: Tammy Juran Production Services\/Compositor: RPK Editorial Services\/PreTeX, Inc. Typeface: 10.5\/12 Times Roman Printer: R.R. Donnelley All credits appearing on this page or at the end of the book are considered to be an extension of the copyright page. Library of Congress Cataloging-in-Publication Data Rosen, Kenneth H. Discrete mathematics and its applications \/ Kenneth H. Rosen. \u2014 7th ed. p. cm. Includes index. ISBN 0\u201307\u2013338309\u20130 1. Mathematics. 2. Computer science\u2014Mathematics. I. Title. QA39.3.R67 2012 511\u2013dc22 2011011060 www.mhhe.com Contents About the Author vi Preface vii The Companion Website xvi To the Student xvii 1 The Foundations: Logic and Proofs .<\/p>\n

. . . . . . . . . . . . . . . . . . . . . . . .<\/p>\n<\/blockquote>\n

This is a short excerpt from the opening of “” by Unknown, quoted for review and introduction purposes. All rights belong to the copyright holders.<\/em><\/p>\n

\n
\n

Table of Contents<\/p>\nToggle<\/span><\/path><\/svg><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n