# Table of Contents - [Navigation - Advanced URI Documentation - Obsidian Publish](#navigation-advanced-uri-documentation-obsidian-publish) - [Obsidian Publish](#obsidian-publish) - [File identifiers - Advanced URI Documentation - Obsidian Publish](#file-identifiers-advanced-uri-documentation-obsidian-publish) - [Frontmatter - Advanced URI Documentation - Obsidian Publish](#frontmatter-advanced-uri-documentation-obsidian-publish) - [Bank Departments - roadmap - Obsidian Publish](#bank-departments-roadmap-obsidian-publish) - [Business Data Model - new - roadmap - Obsidian Publish](#business-data-model-new-roadmap-obsidian-publish) - [Business Data Model - roadmap - Obsidian Publish](#business-data-model-roadmap-obsidian-publish) - [Discutie cu Ruxandraa - roadmap - Obsidian Publish](#discutie-cu-ruxandraa-roadmap-obsidian-publish) - [BT - Data Map for Key Managerial Roles - roadmap - Obsidian Publish](#bt-data-map-for-key-managerial-roles-roadmap-obsidian-publish) - [Binomial coefficient - Discrete Structures for Computer Science - Obsidian Publish](#binomial-coefficient-discrete-structures-for-computer-science-obsidian-publish) - [Unknown](#unknown) - [Unknown](#unknown) - [Unknown](#unknown) - [Unknown](#unknown) - [Unknown](#unknown) - [Unknown](#unknown) - [Unknown](#unknown) - [Unknown](#unknown) - [Unknown](#unknown) - [Unknown](#unknown) - [Unknown](#unknown) - [Unknown](#unknown) - [Unknown](#unknown) - [Unknown](#unknown) - [Unknown](#unknown) - [Unknown](#unknown) - [Unknown](#unknown) - [Unknown](#unknown) - [Unknown](#unknown) - [Unknown](#unknown) - [Unknown](#unknown) - [Unknown](#unknown) - [Unknown](#unknown) - [Unknown](#unknown) - [Unknown](#unknown) - [Unknown](#unknown) - [Unknown](#unknown) - [Unknown](#unknown) - [Unknown](#unknown) - [Unknown](#unknown) - [Unknown](#unknown) - [Unknown](#unknown) - [Factorial - Discrete Structures for Computer Science - Obsidian Publish](#factorial-discrete-structures-for-computer-science-obsidian-publish) - [Additive principle - Discrete Structures for Computer Science - Obsidian Publish](#additive-principle-discrete-structures-for-computer-science-obsidian-publish) - [k-Permutation - Discrete Structures for Computer Science - Obsidian Publish](#k-permutation-discrete-structures-for-computer-science-obsidian-publish) - [Permutation - Discrete Structures for Computer Science - Obsidian Publish](#permutation-discrete-structures-for-computer-science-obsidian-publish) - [License plate problem - Discrete Structures for Computer Science - Obsidian Publish](#license-plate-problem-discrete-structures-for-computer-science-obsidian-publish) - [Multiplicative principle - Discrete Structures for Computer Science - Obsidian Publish](#multiplicative-principle-discrete-structures-for-computer-science-obsidian-publish) - [Dots and dividers - Discrete Structures for Computer Science - Obsidian Publish](#dots-and-dividers-discrete-structures-for-computer-science-obsidian-publish) - [Lattice paths - Discrete Structures for Computer Science - Obsidian Publish](#lattice-paths-discrete-structures-for-computer-science-obsidian-publish) - [Recurrence relation - Discrete Structures for Computer Science - Obsidian Publish](#recurrence-relation-discrete-structures-for-computer-science-obsidian-publish) - [Recursion - Discrete Structures for Computer Science - Obsidian Publish](#recursion-discrete-structures-for-computer-science-obsidian-publish) - [Principle of Inclusion and Exclusion - Discrete Structures for Computer Science - Obsidian Publish](#principle-of-inclusion-and-exclusion-discrete-structures-for-computer-science-obsidian-publish) - [Binary digits and bitstrings - Discrete Structures for Computer Science - Obsidian Publish](#binary-digits-and-bitstrings-discrete-structures-for-computer-science-obsidian-publish) - [Subset - Discrete Structures for Computer Science - Obsidian Publish](#subset-discrete-structures-for-computer-science-obsidian-publish) - [Complete graph - Discrete Structures for Computer Science - Obsidian Publish](#complete-graph-discrete-structures-for-computer-science-obsidian-publish) - [Graph - Discrete Structures for Computer Science - Obsidian Publish](#graph-discrete-structures-for-computer-science-obsidian-publish) - [Mathematical induction - Discrete Structures for Computer Science - Obsidian Publish](#mathematical-induction-discrete-structures-for-computer-science-obsidian-publish) - [Intersection - Discrete Structures for Computer Science - Obsidian Publish](#intersection-discrete-structures-for-computer-science-obsidian-publish) - [Characteristic root method - Discrete Structures for Computer Science - Obsidian Publish](#characteristic-root-method-discrete-structures-for-computer-science-obsidian-publish) - [Addition in binary - Discrete Structures for Computer Science - Obsidian Publish](#addition-in-binary-discrete-structures-for-computer-science-obsidian-publish) - [Sequence - Discrete Structures for Computer Science - Obsidian Publish](#sequence-discrete-structures-for-computer-science-obsidian-publish) - [Solution to a recurrence relation - Discrete Structures for Computer Science - Obsidian Publish](#solution-to-a-recurrence-relation-discrete-structures-for-computer-science-obsidian-publish) - [Base 10 representation - Discrete Structures for Computer Science - Obsidian Publish](#base-10-representation-discrete-structures-for-computer-science-obsidian-publish) - [Base 16 representation - Discrete Structures for Computer Science - Obsidian Publish](#base-16-representation-discrete-structures-for-computer-science-obsidian-publish) - [Base conversion algorithm - Discrete Structures for Computer Science - Obsidian Publish](#base-conversion-algorithm-discrete-structures-for-computer-science-obsidian-publish) - [Cardinality - Discrete Structures for Computer Science - Obsidian Publish](#cardinality-discrete-structures-for-computer-science-obsidian-publish) - [Cartesian product - Discrete Structures for Computer Science - Obsidian Publish](#cartesian-product-discrete-structures-for-computer-science-obsidian-publish) - [Function - Discrete Structures for Computer Science - Obsidian Publish](#function-discrete-structures-for-computer-science-obsidian-publish) - [Base 2 representation - Discrete Structures for Computer Science - Obsidian Publish](#base-2-representation-discrete-structures-for-computer-science-obsidian-publish) - [Set - Discrete Structures for Computer Science - Obsidian Publish](#set-discrete-structures-for-computer-science-obsidian-publish) - [Codomain - Discrete Structures for Computer Science - Obsidian Publish](#codomain-discrete-structures-for-computer-science-obsidian-publish) - [Bijective - Discrete Structures for Computer Science - Obsidian Publish](#bijective-discrete-structures-for-computer-science-obsidian-publish) - [Adjacent - Discrete Structures for Computer Science - Obsidian Publish](#adjacent-discrete-structures-for-computer-science-obsidian-publish) - [Clique number - Discrete Structures for Computer Science - Obsidian Publish](#clique-number-discrete-structures-for-computer-science-obsidian-publish) - [Chromatic index - Discrete Structures for Computer Science - Obsidian Publish](#chromatic-index-discrete-structures-for-computer-science-obsidian-publish) - [Chromatic number - Discrete Structures for Computer Science - Obsidian Publish](#chromatic-number-discrete-structures-for-computer-science-obsidian-publish) - [Bipartite graph - Discrete Structures for Computer Science - Obsidian Publish](#bipartite-graph-discrete-structures-for-computer-science-obsidian-publish) - [Brooks' Theorem - Discrete Structures for Computer Science - Obsidian Publish](#brooks-theorem-discrete-structures-for-computer-science-obsidian-publish) --- # Navigation - Advanced URI Documentation - Obsidian Publish [](https://publish.obsidian.md/advanced-uri-doc/Home) [Advanced URI Documentation](https://publish.obsidian.md/advanced-uri-doc/Home) [Home](https://publish.obsidian.md/advanced-uri-doc/Home) [Installing](https://publish.obsidian.md/advanced-uri-doc/Installing) [Getting started](https://publish.obsidian.md/advanced-uri-doc/Getting+started) Concepts Actions [Actions](https://publish.obsidian.md/advanced-uri-doc/Actions/Actions) [Navigation](https://publish.obsidian.md/advanced-uri-doc/Actions/Navigation) [Writing](https://publish.obsidian.md/advanced-uri-doc/Actions/Writing) [Commands](https://publish.obsidian.md/advanced-uri-doc/Actions/Commands) [Bookmarks](https://publish.obsidian.md/advanced-uri-doc/Actions/Bookmarks) [Frontmatter](https://publish.obsidian.md/advanced-uri-doc/Actions/Frontmatter) [Search](https://publish.obsidian.md/advanced-uri-doc/Actions/Search) [Settings navigation](https://publish.obsidian.md/advanced-uri-doc/Actions/Settings+navigation) [Miscellaneous](https://publish.obsidian.md/advanced-uri-doc/Actions/Miscellaneous) [Canvas](https://publish.obsidian.md/advanced-uri-doc/Actions/Canvas) Tips External i18n [](https://publish.obsidian.md/advanced-uri-doc/Home) [Advanced URI Documentation](https://publish.obsidian.md/advanced-uri-doc/Home) Navigation ========== Tip Use the [view mode](https://publish.obsidian.md/advanced-uri-doc/Concepts/Navigation+Parameters#view-mode) parameter to e.g. switch between reading and live preview mode. Tip Use the [open mode](https://publish.obsidian.md/advanced-uri-doc/Concepts/Navigation+Parameters#open-mode) parameter to open the file always in a new tab or in a new window. | / | parameters | explanation | | | --- | --- | --- | --- | | load workspace | workspace | Opens the workspace called `workspace` | | | copy URI for current workspace | workspace, clipboard=true | Set any non-empty value to `workspace` and `clipboard=true` to copy the URI for the current workspace | | | save current workspace | saveworkspace=true | Saves the current workspace. (Can be combined with `workspace` to open a new workspace afterwards) | | | file | | Opens file | | | line and/or column in file | , line, column | Opens `column` in `line` in file (1 indexed) | | | offset in file | , offset | Sets the cursor at `offset` in file. Offset is the character count from the start | | | heading in file | , heading | Opens the `heading` in file | | | block reference in file | , block | Opens the `block` in file | | | global block reference | block | Searches the whole vault for that block id and uses that file for | | | settings tab | settingid | Opens a settings tab by id, all plugins are supported. See [here](https://publish.obsidian.md/advanced-uri-doc/Actions/Settings+navigation)
for a list of all available options | | Example Open **workspace** "main": obsidian://adv-uri?vault=&workspace=main Open **heading** "Goal" in "my-file.md" (**Important:** Without syntax, only `Goal`): obsidian://adv-uri?vault=&filepath=my-file&heading=Goal Open **block**\-id "12345" in "my-file.md" (**Important:** Without syntax, only `12345`): obsidian://adv-uri?vault=&filepath=my-file&block=12345 Searches whole vault for **block**\-id "12345". Ideally that block id is unique. (**Important:** Without syntax, only `12345`): obsidian://adv-uri?vault=&block=12345 Links to this page [File identifiers](https://publish.obsidian.md/advanced-uri-doc/Concepts/File+identifiers) [Getting started](https://publish.obsidian.md/advanced-uri-doc/Getting+started) [getting\_started](https://publish.obsidian.md/advanced-uri-doc/i18n/zh-CN/getting_started) [Home](https://publish.obsidian.md/advanced-uri-doc/Home) [index](https://publish.obsidian.md/advanced-uri-doc/i18n/zh-CN/index) [Writing](https://publish.obsidian.md/advanced-uri-doc/Actions/Writing) Navigation Not found This page does not exist Interactive graph On this page [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Obsidian Publish * [Download](https://publish.obsidian.md/download) * [Account](https://publish.obsidian.md/account) * [Sync](https://publish.obsidian.md/sync) * [Publish](https://publish.obsidian.md/publish) * [Pricing](https://publish.obsidian.md/pricing) * [Plugins](https://community.obsidian.md/) * [Enterprise](https://publish.obsidian.md/enterprise) * [Web Clipper](https://publish.obsidian.md/clipper) Learn more * [Help](https://obsidian.md/help/) * [About](https://publish.obsidian.md/about) * [Blog](https://publish.obsidian.md/blog) * [Discord](https://discord.gg/obsidianmd) * [Changelog](https://publish.obsidian.md/changelog) * [Community](https://community.obsidian.md/) * [Roadmap](https://publish.obsidian.md/roadmap) * [Security](https://publish.obsidian.md/security) * [Merch store](https://publish.obsidian.md/softwear) * [Privacy](https://publish.obsidian.md/privacy) Give your knowledge a home on the web. ====================================== The easiest way to publish your wiki, knowledge base, documentation, or digital garden. [Create your site](https://publish.obsidian.md/buy/publish) [$8 per month](https://publish.obsidian.md/buy/publish) Features The publishing platform for non-linear thinkers ----------------------------------------------- Obsidian Publish brings your connected notes online. Unique features help readers explore your web of ideas. **Hover previews.** Display a popover preview of the linked page when you hover over it, like Wikipedia. **Graph view.** Visually explore the connections between the pages on your site. **Stacked pages.** Make links open in horizontal panes that you can browse like a stack of pages on a desk. **Backlinks.** Automatically list links to pages that reference the current page you are on. ![Example Obsidian Publish site](https://publish.obsidian.md/images/publish-example-dark.png) ![Example Obsidian Publish site](https://publish.obsidian.md/images/publish-example-dark.png) ![Example Obsidian Publish site](https://publish.obsidian.md/images/publish-example-dark.png) ![Example Obsidian Publish site](https://publish.obsidian.md/images/publish-example-dark.png) Authoring A seamless publishing experience -------------------------------- Publish is built into Obsidian so you can write, collaborate, and publish seamlessly. ![Example of Obsidian Help site powered by Obsidian Publish](https://publish.obsidian.md/images/publish-experience.png) Edit with Markdown Blazing fast text editing built on the simplicity and reliability of Markdown. Collaborate seamlessly Invite your team to collaboratively create and maintain your Publish site. Publish natively Make your changes public in just a few taps, even from your mobile devices. Pricing ------- Host your Obsidian Publish site for one all-inclusive price. If you’re not satisfied, get a refund within 7 days, no questions asked. ### What’s included * Hosting for your site up to 4GB * Priority email support * Customizable theme and domain * SEO and mobile performance Yearly Monthly $8 USD Per site, per month, billed annually $10 USD Per site, per month, billed monthly [Create your site](https://publish.obsidian.md/buy/publish) Site theme /\* Solarized theme \*/ .theme-light { \--background-primary: #FDF6E3; \--background-secondary: #EEE8D5; \--text-normal: #073642; \--text-muted: #586E75; \--text-accent: #248BD2; } .theme-dark { \--background-primary: #002B36; \--background-secondary: #073642; \--text-normal: #93A1A1; \--text-muted: #657B83; \--text-accent: #248BD2; } Site settings Site name Name of your site. Logo Pick an image for your site. Custom URL Define your custom domain. Redirect to your domain Visitors to your site will be redirected. Disallow search engine indexing Prevent search engines from indexing your site. Google Analytics code Configure analytics for your domain. This site is password protected Customization Make it your own ---------------- Obsidian Publish gives you control over the look and feel of your site. It’s easy to create a unique and branded design. **Themes.** The look of your Obsidian Publish site can be fully customized with CSS and Javascript. **Custom domain.** Point your domain name to Obsidian Publish for a more branded experience. **Password protection.** Restrict access to your site with the ability to manage multiple passwords. Performance Built-in performance -------------------- Speed and accessibility are built into every Obsidian Publish site. No configuration required. First-class SEO. Your Publish site is automatically optimized for search engines and social sharing cards. You can even customize metadata with descriptions, slugs, and images, on a page-by-page level. Mobile-friendly. Visitors on mobile devices are treated as first-class citizens, with an experience that’s as intuitive and powerful as it is on the desktop. You can also edit and publish your site from the Obsidian mobile app. Analytics are optional. Obsidian Publish is private by default, but it’s easy to track visits to your site if you choose to. Embed Google Analytics or privacy-friendly tools such as Plausible and Fathom. Accessible by default. Out of the box, Obsidian Publish has a perfect 100% Lighthouse accessibility score. It’s our priority to make your content accessible for all visitors. Explore Publish sites by the Obsidian community ----------------------------------------------- [![Marco Noris](https://publish.obsidian.md/images/publish/marconoris.png) Marco Noris](https://lab.marconoris.com/) [![Emrah](https://publish.obsidian.md/images/publish/emrah.png) Emrah](https://emrah.ca/) [![Stephan Lenvin](https://publish.obsidian.md/images/publish/stephanlenvin-light.png) Stephan Lenvin](https://stephanlevin.blog/) [![Discrete Structures](https://publish.obsidian.md/images/publish/compsci.png) Discrete Structures](https://publish.obsidian.md/discretecs) [![Arkadiusz Lenkiewicz](https://publish.obsidian.md/images/publish/arkadiuszlenkiewicz.png) Arkadiusz Lenkiewicz](https://arkadiuszlenkiewicz.pl/) [![Mister Chad](https://publish.obsidian.md/images/publish/chad.png) Mister Chad](https://mister-chad.com/) Launch your site today ---------------------- Create a Publish site from your notes in just a few minutes. [Create your site](https://publish.obsidian.md/buy/publish) [$8 per month](https://publish.obsidian.md/buy/publish) --- # File identifiers - Advanced URI Documentation - Obsidian Publish [](https://publish.obsidian.md/advanced-uri-doc/Home) [Advanced URI Documentation](https://publish.obsidian.md/advanced-uri-doc/Home) [Home](https://publish.obsidian.md/advanced-uri-doc/Home) [Installing](https://publish.obsidian.md/advanced-uri-doc/Installing) [Getting started](https://publish.obsidian.md/advanced-uri-doc/Getting+started) Concepts [Schema](https://publish.obsidian.md/advanced-uri-doc/Concepts/Schema) [Encoding](https://publish.obsidian.md/advanced-uri-doc/Concepts/Encoding) [File identifiers](https://publish.obsidian.md/advanced-uri-doc/Concepts/File+identifiers) [Navigation Parameters](https://publish.obsidian.md/advanced-uri-doc/Concepts/Navigation+Parameters) Actions Tips External i18n [](https://publish.obsidian.md/advanced-uri-doc/Home) [Advanced URI Documentation](https://publish.obsidian.md/advanced-uri-doc/Home) File identifiers ================ There are multiple ways to identify a file: * [File path](https://publish.obsidian.md/advanced-uri-doc/Concepts/File+identifiers#file-path) * [File name](https://publish.obsidian.md/advanced-uri-doc/Concepts/File+identifiers#file-name) * [Daily note](https://publish.obsidian.md/advanced-uri-doc/Concepts/File+identifiers#daily-note) * [Key in frontmatter](https://publish.obsidian.md/advanced-uri-doc/Concepts/File+identifiers#key-in-frontmatter) Caution Make sure your values are properly [encoded](https://publish.obsidian.md/advanced-uri-doc/Concepts/Encoding) File path --------- * Key: `filepath` * Value: Relative path to the vault * Example: `hobbies/soccer.md` / `hobbies/soccer` * Note: You can omit the file extension `.md`. File name --------- * Key: `filename` * Value: Only the name of the file without the actual path * Example: `soccer` / `soccer.md` * Note: You can omit the file extension `.md`. It prefers just the file name, like when linking via `[[fileName]]`, causing aliases to be supported. Daily note ---------- * Key: `daily` * Value: `true` * Example: `daily=true` * Note: To use the current daily note simply set the key to `true`. If it doesn't exist already, it will be created. Key in frontmatter ------------------ * Key: `uid` * Example: `uid=d43f7a17-058c-4aea-b8dc-515ea646825a` * Use case: Some users prefer navigating to specific notes per UUID instead of the file path to be able to rename these files, but to keep the link still working. * Note: By enabling that option in the setting, every generated command with the `filepath` parameter is replaced with the `uid` parameter. The uid is either read from the frontmatter or generated and then written to the frontmatter. Info [Navigation](https://publish.obsidian.md/advanced-uri-doc/Actions/Navigation) with `uid` is always supported and doesn't need the setting to be enabled. Info By specifying `uid` and `filepath` it creates a new file, if no file with `uid` exists, at `filepath` and writes `uid` to the frontmatter. Examples -------- 1. `obsidian://adv-uri?&filepath=Inbox` This will open a note "Inbox" in your Obsidian vault even if there is no Inbox note present in your vault. 2. `obsidian://adv-uri?daily=true&heading=Inbox` This will open your daily note and place the cursor under Inbox heading if there is one. Sample image: [image](https://user-images.githubusercontent.com/95166364/205477904-dc974487-65e7-4480-a99b-d9ab0b1a2536.png) 3. Suppose you have a note called Inbox which has an alias "Brain Dumps". Now comes the use case for the `filename` parameter. Use this command `obsidian://adv-uri?filename=Brain%20Dumps` Example : [image](https://user-images.githubusercontent.com/95166364/205478454-b6949bf6-cf8c-4218-abaa-3d1bf22bfc1e.png) Links to this page [Actions](https://publish.obsidian.md/advanced-uri-doc/Actions/Actions) [Frontmatter](https://publish.obsidian.md/advanced-uri-doc/Actions/Frontmatter) [Getting started](https://publish.obsidian.md/advanced-uri-doc/Getting+started) [getting\_started](https://publish.obsidian.md/advanced-uri-doc/i18n/zh-CN/getting_started) File identifiers Not found This page does not exist Interactive graph On this page [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Frontmatter - Advanced URI Documentation - Obsidian Publish [](https://publish.obsidian.md/advanced-uri-doc/Home) [Advanced URI Documentation](https://publish.obsidian.md/advanced-uri-doc/Home) [Home](https://publish.obsidian.md/advanced-uri-doc/Home) [Installing](https://publish.obsidian.md/advanced-uri-doc/Installing) [Getting started](https://publish.obsidian.md/advanced-uri-doc/Getting+started) Concepts Actions [Actions](https://publish.obsidian.md/advanced-uri-doc/Actions/Actions) [Navigation](https://publish.obsidian.md/advanced-uri-doc/Actions/Navigation) [Writing](https://publish.obsidian.md/advanced-uri-doc/Actions/Writing) [Commands](https://publish.obsidian.md/advanced-uri-doc/Actions/Commands) [Bookmarks](https://publish.obsidian.md/advanced-uri-doc/Actions/Bookmarks) [Frontmatter](https://publish.obsidian.md/advanced-uri-doc/Actions/Frontmatter) [Search](https://publish.obsidian.md/advanced-uri-doc/Actions/Search) [Settings navigation](https://publish.obsidian.md/advanced-uri-doc/Actions/Settings+navigation) [Miscellaneous](https://publish.obsidian.md/advanced-uri-doc/Actions/Miscellaneous) [Canvas](https://publish.obsidian.md/advanced-uri-doc/Actions/Canvas) Tips External i18n [](https://publish.obsidian.md/advanced-uri-doc/Home) [Advanced URI Documentation](https://publish.obsidian.md/advanced-uri-doc/Home) Frontmatter =========== The frontmatter of a file is the metadata at the beginning of a file. It is usually written in YAML format and is enclosed by `---`. --- title: My Title tags: [tag1, tag2] --- Actions on the frontmatter are done using the `frontmatterkey` parameter. `frontmatterkey` parameter structure ------------------------------------ ### Simple Structure my_item: my_value To select the field `my_value` set the parameter `frontmatterkey=my_item`. ### Complex Structure my_item: second_item: my_value To select the field `my_value` use `frontmatterkey=[my_item,second_item]`. The value of `frontmatterkey` is the ordered list of keys to access your value to copy. Each key needs to be separated via `,`. my_item: second_item: - A - B To select `B` use `frontmatterkey=[my_item,second_item,1]`, because `B` is at index `1` in the list. Read Frontmatter ---------------- You can copy values of your frontmatter to the clipboard using a [file identifier](https://publish.obsidian.md/advanced-uri-doc/Concepts/File+identifiers) and the `frontmatterkey` paramteter. **Complete example:** obsidian://adv-uri?vault=&filepath=MyFile&frontmatterkey=[my_item,second_item,1] Write Frontmatter ----------------- You can also write to your frontmatter using the `frontmatterkey` and `data` parameter. If the key does not exist, it will be created. The `data` parameter is the value you want to write to the frontmatter field. It can be a string, a number, a boolean, a list, or any other JSON object. Use `null` for an empty value. Note For both read and write the associated file is opened by default. To prevent it from opening or control the behavior, use the `openmode` parameter. See [Navigation Parameters](https://publish.obsidian.md/advanced-uri-doc/Concepts/Navigation+Parameters) for more information. Focus Property -------------- To focus the cursor on a specific property in the frontmatter, use the values `append`, `prepend`, or `overwrite` for the `mode` parameter. E.g. to focus on the property `my_item` in the frontmatter, use the following URI: obsidian://adv-uri?vault=&filepath=MyFile&frontmatterkey=my&mode=append ### Simple Structure **Complete example:** Before: my_item: second_item: - A - B After: my_item: second_item: - A - newValue obsidian://adv-uri?vault=&filepath=MyFile&frontmatterkey=[my_item,second_item,1]&data=NewValue ### Complex Structure **Complete example:** Before: my_item: second_item: - A - B After: my_item: second_item: - A - data: - 2 - 3 obsidian://adv-uri?vault=&filepath=MyFile&frontmatterkey=[my_item,second_item,1]&data={%22data%22:[2,3]} ### Prepend/Append To List When using number as index of a list in frontmatter, you could: * Use any number less than `0` (E.g. `-1`) to prepend data to that list. * Use any number greater than the maximum index to append data to that list. Check the example below: my_item: second_item: - A - data: - 2 - 3 obsidian://adv-uri?vault=&filepath=MyFile&frontmatterkey=[my_item,second_item,-1]&data=prepended_data obsidian://adv-uri?vault=&filepath=MyFile&frontmatterkey=[my_item,second_item,3]&data=appended_data The frontmatter will be updated to the following after this operation: my_item: second_item: - prepend_data - A - data: - 1 - 2 - 3 - appended_data Frontmatter Not found This page does not exist Interactive graph On this page [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Bank Departments - roadmap - Obsidian Publish [](https://publish.obsidian.md/roadmap/) [roadmap](https://publish.obsidian.md/roadmap/) Roadmap Existing Documents Roadmap Document Target Architecture [Bank Departments](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/Bank+Departments) [BT - Data Map for Key Managerial Roles](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/BT+-+Data+Map+for+Key+Managerial+Roles) [Business Data Model - new](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/Business+Data+Model+-+new) [Business Data Model](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/Business+Data+Model) [Discutie cu Ruxandraa](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/Discutie+cu+Ruxandraa) [Logical Data Model](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/Logical+Data+Model) [RoadMap](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/RoadMap) [](https://publish.obsidian.md/roadmap/) [roadmap](https://publish.obsidian.md/roadmap/) Bank Departments ================ Okay, here's the list of common bank departments with their abbreviations, alongside the typical title and abbreviation for the head/manager of that department. Keep in mind that titles can vary between institutions. | Department | Dept. Abbr. | Manager Title | Manager Abbr. | | --- | --- | --- | --- | | Retail Banking | RB | Head of Retail Banking | HRB | | Corporate/Commercial Banking | CB | Head of Corporate Banking | HCB | | Investment Banking | IB | Head of Investment Banking | HIB | | Treasury | TSY | Treasurer / Head of Treasury | TREAS / HT | | Risk Management | RM | Chief Risk Officer | CRO | | Compliance | CMP / CPL | Chief Compliance Officer | CCO | | Operations | OPS | Head of Operations | HOO | | Information Technology | IT | Chief Technology/Information Officer | CTO / CIO | | Human Resources | HR | Chief Human Resources Officer | CHRO | | Marketing | MKT | Chief Marketing Officer | CMO | | Wealth Management/Private Bank | WM / PB | Head of Wealth Mgmt/Private Bank | HWM / HPB | | Audit (Internal) | AUD | Chief Audit Executive | CAE | | Finance | FIN | Chief Financial Officer | CFO | | Legal | LGL | General Counsel / Chief Legal Officer | GC / CLO | **Note:** * The **Chief Operating Officer (COO)** often oversees several operational departments, including Operations (OPS) and sometimes IT. * The **Chief Financial Officer (CFO)** typically oversees Treasury, Accounting, Financial Planning & Analysis (FP&A). * The overall head of the bank is the **Chief Executive Officer (CEO)**. Here's a breakdown by department, focusing on the manager's needs and the underlying data: **1\. Finance (CFO - Chief Financial Officer)** * **Key Decisions:** Profitability assessment, capital allocation, budgeting & forecasting, funding strategy, regulatory capital reporting. * **Common Reports:** * Profit & Loss (P&L) Statements (by division, product, customer segment) * Balance Sheet * Cash Flow Statements * Budget vs. Actual Analysis * Capital Adequacy Reports (e.g., Basel III/IV ratios) * Funds Transfer Pricing (FTP) Reports * Asset Liability Management (ALM) Reports * **Relevant Data Points:** * General Ledger (GL) data (account codes, balances, transaction details) * Customer account balances & transaction history * Loan portfolio details (balances, interest rates, maturity, collateral, provisions) * Deposit details (balances, rates, maturity) * Interbank lending/borrowing data * Securities portfolio data (holdings, market values, yields) * Expense data (cost centers, vendor payments) * Risk-Weighted Assets (RWAs) calculations * Off-balance sheet exposures **2\. Risk Management (CRO - Chief Risk Officer)** * **Key Decisions:** Setting risk appetite, approving credit limits/large exposures, managing market risk positions, overseeing operational risk events, stress testing scenarios, capital adequacy from a risk perspective. * **Common Reports:** * Credit Risk Exposure Reports (by counterparty, sector, geography, rating) * Portfolio Quality Reviews (NPLs, provisions, watchlists) * Market Risk Reports (Value at Risk - VaR, sensitivities, stress tests) * Liquidity Risk Reports (LCR, NSFR, gap analysis, stress tests) * Operational Risk Dashboards (incidents, losses, KRIs) * Capital Adequacy Reports (Internal Capital Adequacy Assessment Process - ICAAP) * Stress Testing Results * **Relevant Data Points:** * _Credit:_ Counterparty details (ratings, financials), loan/exposure details (amount, maturity, collateral, LTV, PD, LGD, EAD), historical default/loss data. * _Market:_ Security prices, interest rates, FX rates, volatilities, correlations, portfolio holdings, trade details. * _Liquidity:_ Cash flow projections, deposit stability data, funding sources, asset encumbrance, market liquidity indicators. * _Operational:_ Incident logs, loss data, control assessment results, process maps, IT system logs (for cyber risk). * _Model:_ Model inputs, parameters, validation results. **3\. Retail Banking (HRB - Head of Retail Banking)** Bank Departments Not found This page does not exist Interactive graph On this page [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Business Data Model - new - roadmap - Obsidian Publish [](https://publish.obsidian.md/roadmap/) [roadmap](https://publish.obsidian.md/roadmap/) Roadmap Existing Documents Roadmap Document Target Architecture [Bank Departments](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/Bank+Departments) [BT - Data Map for Key Managerial Roles](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/BT+-+Data+Map+for+Key+Managerial+Roles) [Business Data Model - new](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/Business+Data+Model+-+new) [Business Data Model](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/Business+Data+Model) [Discutie cu Ruxandraa](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/Discutie+cu+Ruxandraa) [Logical Data Model](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/Logical+Data+Model) [RoadMap](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/RoadMap) [](https://publish.obsidian.md/roadmap/) [roadmap](https://publish.obsidian.md/roadmap/) Business Data Model - new ========================= Okay, as an expert data modeler, I can translate the comprehensive data requirements we've discussed into a structured Business Data Model (BDM). This model will represent the core business concepts and their relationships at Banca Transilvania, serving as a blueprint for integrated data systems, independent of specific technologies. Below is the conceptual Business Data Model, followed by a relationship diagram illustrating the connections between key entities. Business Data Model (Conceptual) -------------------------------- This model organizes the identified data points into logical business entities and their core attributes. It focuses on _what_ data is needed from a business perspective. **I. Core Entities:** 1. **Party:** Represents any individual or organization interacting with the bank. * _Sub-types:_ Individual Customer, Corporate Customer (SME, Mid-Corp, Large Corp), Employee, Vendor/Third Party, Regulator, Correspondent Bank. * _Key Attributes:_ PartyID (Unique Identifier), Party Type, Name(s), Identification Numbers (CNP, CUI/CIF, LEI 1, Passport, Tax ID 7), Addresses, Contact Information, Relationship Start/End Dates, Status. 2. **Customer (Specialization of Party):** Represents individuals or corporates receiving banking services. * _Sub-types:_ Individual Customer, Corporate Customer. * _Key Attributes (Common):_ CustomerID (links to PartyID), Segment (Retail, Premium Retail 8, SME 8, Corporate, WM/PB), Relationship Manager ID (links to Employee), KYC/CDD Status 9, AML Risk Rating 9, GDPR Consent Records 33, Customer Lifetime Value (CLV) 40, NPS/CSAT Scores 42, Acquisition Channel/Date. * _Key Attributes (Individual):_ Date of Birth, Place of Birth, Gender, Nationality, Marital Status, Occupation.7 * _Key Attributes (Corporate):_ Legal Form, Industry Code (NACE), Turnover 51, Number of Employees, Ownership Structure, Beneficial Owner Details (links back to Party/Individual Customer).7 3. **Product:** Represents the financial offerings of the bank. * _Key Attributes:_ ProductID, ProductName, ProductType (Loan, Deposit, Card, Investment, Insurance, Advisory, Trade Finance, Cash Management, etc.), Category (Retail, Corporate, WM, etc.), Terms & Conditions, Fee Structure, Eligibility Criteria, Launch/Discontinuation Dates. 4. **Account:** Represents a specific instance of a product held by a customer. * _Key Attributes:_ AccountID, CustomerID (links to Customer), ProductID (links to Product), Account Type (Current, Savings, Loan, Investment, Card, etc.), Account Number/IBAN, Currency, Open Date, Close Date, Status (Active, Dormant, Closed), Current Balance, Maturity Date (if applicable), Interest Rate (if applicable). 5. **Transaction:** Represents a financial or non-financial event related to an account or customer interaction. * _Key Attributes:_ TransactionID, AccountID (links to Account), CustomerID (links to Customer), TransactionTimestamp, PostingDate, TransactionType (Payment, Withdrawal, Deposit, Fee, Inquiry, Login, etc.), Amount, Currency, Status (Pending, Completed, Failed, Reversed), ChannelID (links to Channel), Counterparty Information, Description/Narrative, MiFIDII Reporting Fields (if applicable) 52, SCA Exemption Data (if applicable).63 6. **Financial Instrument / Security:** Represents tradable assets. * _Key Attributes:_ InstrumentID (e.g., ISIN 52), InstrumentName, InstrumentType (Equity, Bond, Derivative, Fund Unit), IssuerID (links to Party), Currency, MaturityDate, CouponRate, CFI Code 52, MarketDataID (links to Market Data). 7. **Portfolio:** Represents a collection of financial instruments. * _Key Attributes:_ PortfolioID, PortfolioName, PortfolioType (Trading Book, Banking Book, Investment, Client Mandate), OwnerID (Bank Dept or CustomerID), Currency, Strategy/Objective, AUM (Assets Under Management). 8. **Collateral:** Represents assets pledged as security for loans. * _Key Attributes:_ CollateralID, CollateralType (Real Estate, Securities, Cash, Guarantee), Description, ValuationAmount, ValuationDate, Location, LTV (Loan-to-Value) Ratio, Link to LoanAccount. 9. **Employee (Specialization of Party):** Represents individuals working for the bank. * _Key Attributes:_ EmployeeID (links to PartyID), JobTitle, DepartmentID (links to Organizational Unit), Role, PerformanceRating, CompensationData 74, TrainingRecords, AccessRights. 10. **Organizational Unit:** Represents departments, divisions, or branches within the bank. * _Key Attributes:_ UnitID, UnitName, UnitType (Department, Division, Branch 8), ParentUnitID, Location (for branches). 11. **Channel:** Represents the means through which customers interact with the bank. * _Key Attributes:_ ChannelID, ChannelName (Branch, ATM, Web, Mobile App 44, Call Center, API), Operational Metrics (Uptime, Transaction Volume). **II. Risk & Compliance Entities:** 12. **Risk Assessment:** Represents the evaluation of various risks. * _Sub-types:_ Credit Risk Assessment, Market Risk Assessment, Operational Risk Assessment, Liquidity Risk Assessment, IRRBB/CSRBB Assessment 8, ESG Risk Assessment 9, Model Risk Assessment. * _Key Attributes:_ AssessmentID, AssessedEntityID (links to Customer, Loan, Portfolio, Process, etc.), AssessmentDate, RiskType, RiskScore/Rating, KeyMetrics (e.g., PD/LGD/EAD 2, VaR, LCR/NSFR 26, EVE/NII Sensitivity 8, PAI Indicators 82), MitigationActions, ReviewDate. 13. **Operational Risk Event:** Represents an incident causing or potentially causing loss. * _Key Attributes:_ EventID, EventDate, EventType (Internal Fraud, External Fraud, System Failure, Process Error, etc.), Description, LossAmount (Actual/Potential), RecoveryAmount, Status, RootCause, RemediationActions. 14. **Compliance Alert/Case:** Represents potential compliance breaches identified. * _Sub-types:_ AML Alert, Sanctions Hit 9, Conduct Risk Flag, Fraud Alert. * _Key Attributes:_ AlertID, AlertTimestamp, AlertType, RelatedEntityID (links to Customer, Transaction), RuleTriggered, Status (Open, Investigated, Closed, SAR Filed), InvestigationNotes, InvestigatorID (links to Employee). 15. **Regulation/Policy:** Represents internal or external rules governing bank operations. * _Key Attributes:_ RegulationID/PolicyID, Name, Type (External Regulation, Internal Policy), IssuingBody (e.g., EBA 8, NBR 74, ESMA 98, Internal Dept), EffectiveDate, Version, LinkToDocument. 16. **GDPR Data Subject Request:** Tracks requests related to data privacy rights. * _Key Attributes:_ RequestID, DataSubjectID (links to Customer/Party), RequestType (Access, Rectification, Erasure, Portability, Objection 33), DateReceived, DateDue, DateCompleted, Status, RequestDetails, ResponseDetails. **III. Financial & Operational Entities:** 17. **Financial Statement Data:** Represents aggregated financial data. * _Key Attributes:_ RecordID, ReportingPeriod, GLAccountCode, Balance, Amount, Currency, Entity (BT Standalone/Group), StatementType (Balance Sheet, P&L, Cash Flow 26). 18. **Market Data:** Represents external market information. * _Key Attributes:_ MarketDataID, DataType (Interest Rate, FX Rate, Security Price, Index Level, Volatility), Ticker/Symbol, DataSource (e.g., BVB 113, Refinitiv, Bloomberg), Timestamp, Value. 19. **Contract:** Represents legal agreements. * _Key Attributes:_ ContractID, ContractType (Vendor, Client, Lease, Loan Agreement), CounterpartyID (links to Party), EffectiveDate, ExpiryDate, KeyTerms, Status, LinkToDocument. 20. **IT Asset/System:** Represents technology components. * _Key Attributes:_ AssetID, AssetName, AssetType (Hardware, Software, Application), Status, Owner, Version, Location, PerformanceMetrics (Uptime, Response Time 82), SecurityLogs. 21. **Marketing Campaign:** Represents marketing initiatives. * _Key Attributes:_ CampaignID, CampaignName, StartDate, EndDate, TargetSegment, Channel(s), Budget, PerformanceMetrics (Reach, CTR, Conversion Rate, ROI 116). 22. **Report/Dashboard:** Represents analytical outputs for managers. * _Key Attributes:_ ReportID, ReportName, Description, TargetAudience (Manager Role/Dept), Frequency, DataSources, KeyMetricsIncluded, LinkToOutput. Business Data Model - new Not found This page does not exist Interactive graph On this page Business Data Model (Conceptual) Relationship Diagram (Conceptual - Mermaid Syntax) [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Business Data Model - roadmap - Obsidian Publish [](https://publish.obsidian.md/roadmap/) [roadmap](https://publish.obsidian.md/roadmap/) Roadmap Existing Documents Roadmap Document Target Architecture [Bank Departments](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/Bank+Departments) [BT - Data Map for Key Managerial Roles](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/BT+-+Data+Map+for+Key+Managerial+Roles) [Business Data Model - new](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/Business+Data+Model+-+new) [Business Data Model](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/Business+Data+Model) [Discutie cu Ruxandraa](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/Discutie+cu+Ruxandraa) [Logical Data Model](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/Logical+Data+Model) [RoadMap](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/RoadMap) [](https://publish.obsidian.md/roadmap/) [roadmap](https://publish.obsidian.md/roadmap/) Business Data Model =================== Here's an elaboration of possible Business Terms based on banking sector best practices - this is not the complete list but a starting point that needs to be enhanced and adapted for BT needs. **1\. Fundamental Identifiers & Timestamps** * **Customer Identifier (Unique):** The unique key assigned to identify a distinct customer entity (individual or organization). * **Account Identifier (Unique):** The unique key assigned to identify a specific financial account (e.g., savings, loan, trading). * **Product Identifier (Unique):** The unique key assigned to identify a specific banking product or service offering. * **Transaction Identifier (Unique):** The unique key assigned to identify a single financial transaction event. * **Employee Identifier (Unique):** The unique key assigned to identify an employee of the bank. * **Cost Centre Identifier:** The code identifying a specific department or unit for financial tracking and budgeting. * **Branch Identifier:** The code identifying a specific physical branch location. * **Legal Entity Identifier (LEI):** The globally standardized 20-character code identifying legal entities participating in financial transactions. * **Instrument Identifier (ISIN/CUSIP/SEDOL):** Standardized codes (e.g., ISIN, CUSIP, SEDOL) used to uniquely identify financial instruments like stocks and bonds. * **Event Timestamp:** The precise date and time an event occurred or was recorded. * **Value Date:** The date on which a transaction affects the balance of an account for interest calculation purposes. * **Posting Date:** The date on which a transaction is officially recorded in the bank's ledger (books). **2\. Customer Information** * **Customer Legal Name:** The official registered name of the customer entity. * **Customer Trading Name (Doing Business As):** The name under which a business customer operates, if different from the legal name. * **Customer Type:** Classification of the customer (e.g., Individual, Corporate, SME, Government, Financial Institution). * **Date of Birth / Incorporation Date:** The customer's date of birth (for individuals) or date of legal incorporation (for organizations). * **Tax Identification Number:** The official number assigned for tax purposes (e.g., SSN, EIN, TIN). * **Registered Address:** The official legal address of the customer. * **Contact Phone Number / Email Address:** Primary contact details for communication. * **KYC Risk Rating:** The assessed risk level of the customer based on Know Your Customer (KYC) due diligence (e.g., Low, Medium, High). * **KYC Last Review Date:** The date the customer's KYC information was last reviewed and updated. * **Customer Segment Code:** Classification based on internal segmentation models (e.g., Mass Market, Affluent, HNW, Large Corporate). * **Relationship Manager Identifier:** The Employee Identifier of the primary contact person assigned to the customer. * **Net Promoter Score (NPS):** A measure of customer loyalty and satisfaction based on survey responses. * **Customer Since Date:** The date the customer relationship officially began. * **Politically Exposed Person (PEP) Status:** Indicator if the customer or related parties meet the definition of a PEP. * **Sanctions Screening Result:** The outcome of checking the customer against official sanctions lists. * **Product Holdings per Customer:** A list or count of products/services utilized by the customer. **3\. Account & Product Details** * **Account Number:** The specific number assigned to the customer's account. * **Account Type:** Classification of the account (e.g., Current, Savings, Term Deposit, Mortgage, Credit Card). * **Account Currency Code:** The currency in which the account is denominated (e.g., USD, EUR, GBP using ISO 4217 codes). * **Account Status:** The current state of the account (e.g., Active, Dormant, Closed, Blocked). * **Account Open Date:** The date the account was officially opened. * **Account Close Date:** The date the account was officially closed. * **Current Account Balance:** The actual balance in the account at a specific point in time. * **Available Account Balance:** The portion of the current balance available for withdrawal or use. * **Accrued Interest Amount:** The amount of interest earned or charged but not yet posted to the account balance. * **Interest Rate Type:** Classification of the interest rate (e.g., Fixed, Variable, Tiered). * **Applicable Interest Rate:** The specific interest rate currently applied to the account. * **Maturity Date:** The date on which a fixed-term product (like a loan or deposit) is due. * **Fee Structure Code:** Identifier linking the account to a specific set of applicable fees. * **Product Name:** The official name of the banking product associated with the account or service. **4\. Transaction Details** * **Transaction Reference Number:** A unique identifier assigned by the system processing the transaction. * **Transaction Type Code:** Classification of the transaction (e.g., Deposit, Withdrawal, Payment, Fee, Interest). * **Transaction Amount:** The monetary value of the transaction. * **Transaction Currency Code:** The currency of the transaction amount. * **Debit Account Number:** The account from which funds are withdrawn. * **Credit Account Number:** The account to which funds are deposited. * **Transaction Channel Code:** The method or channel used to initiate the transaction (e.g., Branch, ATM, Online, Mobile, POS). * **Transaction Status Code:** The current state of the transaction processing (e.g., Pending, Completed, Failed, Reversed). * **Settlement Date:** The date on which the exchange of funds between parties is completed. * **Transaction Narrative / Description:** Textual information describing the purpose or details of the transaction. **5\. Loan & Credit Data** * **Loan Agreement Identifier:** Unique identifier for the specific loan contract. * **Borrower Customer Identifier:** The Customer Identifier of the primary party receiving the loan. * **Guarantor Customer Identifier:** The Customer Identifier of any party guaranteeing the loan. * **Facility Type Code:** Classification of the credit facility (e.g., Term Loan, Revolving Credit, Overdraft, Letter of Credit). * **Commitment Amount:** The total amount the bank has agreed to lend under the facility. * **Principal Amount Outstanding:** The current unpaid principal balance of the loan. * **Loan Purpose Code:** Classification of the reason for the loan (e.g., Mortgage, Working Capital, Acquisition). * **Loan Origination Date:** The date the loan was initially disbursed. * **Collateral Identifier:** Unique identifier for the asset pledged as security for the loan. * **Collateral Type Code:** Classification of the collateral (e.g., Real Estate, Securities, Cash, Equipment). * **Collateral Market Value:** The estimated current market value of the pledged collateral. * **Collateral Last Valuation Date:** The date the collateral was last formally valued. * **Loan-to-Value (LTV) Ratio:** The ratio of the loan amount to the appraised value of the collateral. * **Internal Credit Risk Rating:** The bank's internal assessment of the borrower's creditworthiness. * **External Credit Rating:** Credit rating assigned by an external agency (e.g., S&P, Moody's), if applicable. * **Probability of Default (PD):** The estimated likelihood that the borrower will default within a specific time horizon (e.g., 1 year). * **Loss Given Default (LGD):** The estimated percentage of the exposure that will be lost if the borrower defaults. * **Exposure at Default (EAD):** The estimated outstanding amount if the borrower defaults. * **Non-Performing Loan (NPL) Status Flag:** Indicator if the loan meets the criteria for being classified as non-performing (typically based on DPD). * **Days Past Due (DPD):** The number of days a required payment is overdue. * **Loan Provision Amount:** The amount set aside in the bank's financials to cover expected losses on the loan. * **Covenant Compliance Status:** Indicator of whether the borrower is currently meeting the agreed-upon loan covenants. **6\. Market & Securities Data** * **Security Identifier (ISIN/CUSIP):** Standard identifier for the traded security. * **Security Description:** Name or description of the security. * **Security Type Code:** Classification (e.g., Equity, Government Bond, Corporate Bond, Derivative). * **Issuer Identifier:** Identifier (often LEI) of the entity that issued the security. * **Market Price:** The current price at which the security can be traded in the market. * **Valuation Timestamp:** The date and time the market price or valuation was recorded. * **Portfolio Identifier:** Identifier for the specific portfolio (trading book, banking book, client portfolio) holding the security. * **Quantity Held:** The number of units or nominal amount of the security held. * **Market Value:** The total current value of the holding (Quantity \* Market Price). * **Interest Rate (Yield Curve Point):** Specific interest rates used for valuation or risk assessment (e.g., points on a benchmark yield curve like SOFR). * **Foreign Exchange Rate:** The rate used to convert between currencies. * **Market Volatility:** Measure of the price fluctuation of a security or market index. * **Credit Spread:** The difference in yield between a risky bond and a risk-free benchmark (e.g., government bond). **7\. Financial & Performance Data** * **General Ledger Account Code:** The specific code from the bank's Chart of Accounts. * **GL Account Balance:** The balance of a specific GL account. * **Net Interest Income (NII):** Interest income minus interest expense. * **Non-Interest Income:** Income from fees, commissions, trading, etc. * **Operating Expense:** Costs associated with running the bank (salaries, rent, IT, etc.). * **Profit Before Tax (PBT):** Total income minus total expenses before taxes. * **Return on Equity (ROE):** Net income divided by shareholders' equity. * **Return on Assets (ROA):** Net income divided by total assets. * **Cost-to-Income Ratio:** Operating expenses divided by total income (NII + Non-Interest Income). * **Risk-Weighted Assets (RWA):** Assets adjusted for their inherent credit, market, and operational risk, used in capital adequacy calculations. * **Common Equity Tier 1 (CET1) Capital Ratio:** Ratio of highest quality capital (CET1) to RWAs. * **Liquidity Coverage Ratio (LCR):** Ratio of high-quality liquid assets to net cash outflows over a 30-day stress period. * **Net Stable Funding Ratio (NSFR):** Ratio of available stable funding to required stable funding over a one-year horizon. * **Budget Amount:** Planned financial target for an account, cost center, or metric. * **Forecast Amount:** Projected future financial value. * **Funds Transfer Pricing (FTP) Rate:** Internal rate used to allocate funding costs and benefits between different units/products. **8\. Treasury & Liquidity Data** * **Nostro Account Balance:** The balance held in an account with another bank (correspondent banking). * **Cash Flow Projection Amount:** Estimated future cash inflows or outflows. * **Funding Maturity Date:** Date when a specific funding source (e.g., wholesale deposit, bond) matures. * **Asset Encumbrance Status:** Indicator if an asset is pledged as collateral and not freely available. * **Collateral Eligibility Status:** Indicator if an asset meets the criteria to be used as collateral (e.g., for central bank operations). * **Interbank Offered Rate (e.g., SOFR, LIBOR):** Benchmark rates for interbank lending. **9\. Risk Specific Data** * **Operational Risk Event ID:** Unique identifier for a specific operational risk incident. * **Operational Loss Amount:** Financial impact resulting from an operational risk event. * **Key Risk Indicator (KRI) Value:** The current value of a metric used to monitor potential risk exposures. * **Control Effectiveness Rating:** Assessment of how well an internal control is mitigating its intended risk. * **Model Identifier:** Unique identifier for a specific risk model (e.g., PD model, VaR model). * **Model Validation Date:** The date the model was last independently validated. * **Stress Test Scenario ID:** Identifier for a specific hypothetical adverse scenario used for stress testing. * **Stress Test Result Value:** The calculated impact (e.g., on capital, P&L, liquidity) under a specific stress scenario. **10\. Operational & Process Data** Business Data Model Not found This page does not exist Interactive graph On this page [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Discutie cu Ruxandraa - roadmap - Obsidian Publish [](https://publish.obsidian.md/roadmap/) [roadmap](https://publish.obsidian.md/roadmap/) Roadmap Existing Documents Roadmap Document Target Architecture [Bank Departments](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/Bank+Departments) [BT - Data Map for Key Managerial Roles](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/BT+-+Data+Map+for+Key+Managerial+Roles) [Business Data Model - new](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/Business+Data+Model+-+new) [Business Data Model](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/Business+Data+Model) [Discutie cu Ruxandraa](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/Discutie+cu+Ruxandraa) [Logical Data Model](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/Logical+Data+Model) [RoadMap](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/RoadMap) [](https://publish.obsidian.md/roadmap/) [roadmap](https://publish.obsidian.md/roadmap/) Discutie cu Ruxandraa ===================== id: Discutie cu Ruxandra aaa bbb ttt bibi are mere aliases: [] tags: [] As CDO I need to make the best Roadmap for Transylvania Bank known also as BT. For this I need to structure an MVP scope and Physical Person or PJ can be the first use case. What is useful to know is that certain initiatives are going on in BT : PJ, retail risk, finance - ODS, Integration Layer, DW, Regulatory, exploratory - Data Domains. * Data Platform in Cloud * Create an Integration Layer * Make current DataWarehouse more structured * Implement ODS within Integration Layer ? * Implement A Data Hub within Integration Layer * Implement Data Domains Platform * Implement Data Management System in Cloud as in classical DWH CTO has thought to buy DBOS for entitlement and PJ (Juridical Person) for Business SSO (Single Sign On) - used for intercross payments , offered packages , packages offered all these channels. DBOS will help also for client unification and possible also other MDM (Master Data Management) As far as I can see, the DBOS implementation will begin without Omnichannel. Scope : Create Roadmap for DWH, Integration Layer, Operational Data Store, Data Domains dwh , integration layer, ods, data domains pj, retail, cro si cfo ai arat pe ani - roadmap - 4 * * * Hi, how are you doing? because i had different convos with Iulian, Stef and Andrzej, expressing my view, putting down some words **_to help myself set the frame of DDM contribution_**  and as a suggestion view of the status quo on omnichannel storyline   It become clear to me today the following: 1. omnichannel platform (product) needs a Business Product Owner and a Tech Product Owner  2. the business PO should be Stefania, there is no better candidate on the market who knows the business, the as is process, the customer and have the capacity to control the customer  3. Irrespective to her role of Coordinator Director - she needs an official PO role, outside of EBA area  4. the tech PO can be Iulian or whomever Iulian decides  5. At this stage of understanding, from technical perspective there cannot be 1 PO - but there should be an “Assemblement of Technical POs"  6. From data perspective - I/ DDM should drive the investigation and conceptualization of data models (There will be multiple models - NOT only one), concepts, data framework - BUT I/ data framework should NOT become blocker/ stopper or driver to execution - data framework should get conceptualized in parallel and implemented once/ sync with data platform and data transformation  in the bank  7. Identity management and Entitlements are paradigms mandatory irrespective to the business strategy - this is NOT a configuration and even if this is implemented with Finshape - this is NOT representative for other channels - the speed of implementation is pure competitive advantage of Finshape for having known the context for 1 single channel   8. Reshape SCOPES by business benefits (both Cristina and Caragea killed all our statements and reduced to what is the benefit, by when, by cost, by business resources) 9. WE SHOULD START LOOKING in the details of channels: 10. LOGICAL prioritization of channels - the level achieved in the life cycle of the channel, the keeps, the kills  11. infra, stack, architecture, storage, volumes, timing 12. Processes - existing flows to be kept SIMPLE ones 1. client initiation  2. product initiation  3. product catalog 4. product life cycle and reaction 5. client life cycle and reaction 6. payment lifecycle  7. account lifecycle  8. maker - checker flows etc etc 9. eligibility flows  10. document management flows  11. standard possible operations  12. identify business use cases - obvious ones - to be solved  13. payments 14. whatever is STANDARD  and goes from your creativity 15. Subsidiaries, crms,... 13. Designed SIMPLE flows  14. align Business Flows with Designing data Model - will be multiple models  15. Design models for EVENTS States/ stages - multiple models  Business is willing but worried and biased on history: 1. misaligned tech with business  2. business resources  3. love for historical tech partners  4. total lack of trust in speed  To me it looks instrumental to find that use case which will bring a generic advantage to business - time to money  There are high level elements incorporated within Omnichannel paradigm which should be referred within the Data platform paradigm  We (Iulian and Stefania, and I m available to help) should design initially a logical roadmap of all possible business use cases we want to solve for and group by:  1. basic, 2)generic, 3) critical 3) evolved  Roadmap should design/ FORCED with dates YEARS - logical one and afterwards drive analyses and put meet on precision EA needs to contribute much more precise, material is too high level, very very high level. Details and precision we are not yet there From tech team structure perspective, I would seek to onboard for each channel a tech rep - from CORE teams to contribute with analyses - Assemble a tech team - designated for product not for service I am happy to continue with the WS org by Stef and craft the TO BE framework - but again, data concerns should not be driver or blocker of the execution of the platform implementation - but parallel Discutie cu Ruxandraa Not found This page does not exist Interactive graph On this page [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # BT - Data Map for Key Managerial Roles - roadmap - Obsidian Publish [](https://publish.obsidian.md/roadmap/) [roadmap](https://publish.obsidian.md/roadmap/) Roadmap Existing Documents Roadmap Document Target Architecture [Bank Departments](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/Bank+Departments) [BT - Data Map for Key Managerial Roles](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/BT+-+Data+Map+for+Key+Managerial+Roles) [Business Data Model - new](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/Business+Data+Model+-+new) [Business Data Model](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/Business+Data+Model) [Discutie cu Ruxandraa](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/Discutie+cu+Ruxandraa) [Logical Data Model](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/Logical+Data+Model) [RoadMap](https://publish.obsidian.md/roadmap/Clients/06-BT+Folder/Roadmap/RoadMap) [](https://publish.obsidian.md/roadmap/) [roadmap](https://publish.obsidian.md/roadmap/) BT - Data Map for Key Managerial Roles ====================================== Banca Transilvania: A Comprehensive Data Map for Key Managerial Roles ===================================================================== I. Executive Summary -------------------- This report provides the Chief Data Officer (CDO) of Banca Transilvania (BT) with a comprehensive map of critical data points required by key managers across the bank. The identification and structuring of these data needs are driven by the bank's diverse business operations, its strategic objectives including continued growth, digital transformation, and market leadership 1, and the complex, evolving Romanian (NBR) and European Union (EU) regulatory landscape.4 The objective is to create an actionable inventory that supports enhanced data governance, improves data quality, and enables more effective strategic decision-making. The scope encompasses major data domains critical to banking – Customer, Financial, Transactional, Risk, Compliance, Operations, IT, HR, Market, ESG, Third-Party, and Metadata. It addresses the specific data requirements of key C-suite and management roles, including newly identified strategic positions such as the CDO, Head of Customer Experience, and Head of ESG. The analysis integrates requirements stemming from pertinent regulations, including those from the National Bank of Romania (NBR), European Banking Authority (EBA), European Securities and Markets Authority (ESMA), General Data Protection Regulation (GDPR), Second Payment Services Directive (PSD2), Capital Requirements Regulation/Directive (CRR/CRD), Sustainable Finance Disclosure Regulation (SFDR), Corporate Sustainability Reporting Directive (CSRD), EU Taxonomy, and the Non-Performing Loans (NPL) Directive. Furthermore, the report considers essential external data sources and proposes a logical hierarchy for the identified data points. Key findings highlight the critical importance of robust data across Risk, Compliance, and increasingly, ESG domains. The interconnectedness of data needs across functional silos is evident, demanding strong governance to ensure consistency and accuracy. Upcoming regulations, such as CRR III 6 and the NPL Directive 12, will impose significant new data and reporting burdens. The bank's reliance on external data providers for credit information 13, market data 15, company verification 17, and sanctions screening 19necessitates careful management and integration. Specific challenges related to the availability, quality, and standardization of ESG data are noted 21, alongside the perennial need for rigorous Know Your Customer (KYC) and Anti-Money Laundering (AML) data management.23 Foundational data governance practices, including metadata management and quality controls 27, are paramount for achieving BT's strategic goals, such as the successful integration of OTP Bank Romania 28 and maintaining regulatory compliance. This report serves as a foundational tool for the CDO's data strategy, providing a clear roadmap for prioritizing data governance initiatives, technology investments, and organizational alignment to leverage data as a strategic asset for Banca Transilvania. II. Data Requirements by Key Manager Role ----------------------------------------- This section details the specific data requirements for key managerial roles within Banca Transilvania. For each role, an overview of responsibilities and decision-making drivers is provided, followed by examples of common reports or dashboards utilized, and a detailed inventory of necessary data points categorized by domain. These data points are linked to their purpose, regulatory drivers, and source systems where applicable. ### 1\. Chief Executive Officer (CEO) * A. Overview of Key Responsibilities & Decisions Driving Data Needs: The CEO holds ultimate responsibility for Banca Transilvania's overall strategic direction, financial performance (P&L), market positioning, and stakeholder management. Key decisions involve setting long-term goals, approving major investments and acquisitions (such as the significant OTP Bank Romania integration 28), shaping organizational culture, and ensuring the bank's profitability and sustainability in a dynamic market.3 The CEO must navigate complex regulatory environments and drive strategic initiatives like digital transformation and SME market growth.1 This necessitates a high-level, synthesized view of the bank's performance across all critical dimensions. * B. Illustrative Common Reports/Dashboards: Consolidated Group Performance Dashboard (incorporating key financial, risk, operational, market share metrics), Strategic Initiative Progress Tracker (e.g., OTP Integration Status, Digital Roadmap Milestones), Competitor Analysis Reports, Regulatory Landscape & Impact Summaries, ESG Performance Scorecard, Overall Customer Sentiment Trends. * C. Detailed Data Point Inventory: The CEO requires highly aggregated, cross-domain data focused on strategic outcomes, overall performance, and major risks. The challenge lies in ensuring the underlying data feeding these summaries is accurate, timely, and consistent across different functional silos, a complexity amplified by events like the OTP integration.28 * **Financial:** * _Key Metrics:_ Group Net Profit 29, Return on Equity (ROE) 28, Net Interest Margin (NIM) 29, Cost-to-Income Ratio 28, Revenue Growth Rates, Capital Adequacy Ratios (CAR).28 * _Supporting Data:_ Segment Profitability Summaries (Retail, Corporate/SME, WM, Treasury), Budget vs. Actual Performance Overview. * _Source:_ Aggregated from Internal Finance Systems, Regulatory Filings.28 * **Risk:** * _Key Metrics:_ Overall Risk Appetite Adherence, Group Non-Performing Loan (NPL) Ratio 29, Liquidity Coverage Ratio (LCR) / Net Stable Funding Ratio (NSFR) Summaries.29 * _Supporting Data:_ Summaries of Top Risk Exposures (Credit, Market, Operational, Compliance), High-Level Stress Test Outcomes, Overview of Major Compliance Issues or Regulatory Fines.32 * _Source:_ Aggregated from Risk Management Systems, Compliance Department Reports. * **Market:** * _Key Metrics:_ Market Share (Assets, Loans, Deposits) 2, Brand Strength Index / Reputation Scores.1 * _Supporting Data:_ Competitor Financial Performance Summaries, Key Macroeconomic Indicators (GDP Growth, Inflation Rates, NBR Policy Rate 35). * _Source:_ Internal BI Platforms, Market Research Reports, NBR Publications 36, External Data Providers. * **Customer:** * _Key Metrics:_ Overall Customer Base Growth, Net Promoter Score (NPS) Trends 37, High-Value Customer Segment Growth/Profitability. * _Source:_ Aggregated from CRM Systems, Customer Experience (CX) Platforms. * **Operations:** * _Key Metrics:_ Group-Level Operational Efficiency Trends (e.g., Cost per transaction trend 39), Overall Digital Adoption Rate Trends.39 * _Supporting Data:_ Summary of Major System Outages or Business Disruptions.41 * _Source:_ Aggregated from Operations & IT Performance Reports. * **HR:** * _Key Metrics:_ Overall Employee Engagement Scores, Senior Leadership Team Performance Summary. * _Supporting Data:_ High-Level Succession Planning Status. * _Source:_ Aggregated from HR Systems & Surveys. * **ESG:** * _Key Metrics:_ Overall Bank ESG Rating Trends (from key agencies like Sustainalytics, FTSE Russell 29), Progress Against Strategic Sustainability Goals.3 * _Supporting Data:_ Summary of Major ESG Risks and Opportunities. * _Source:_ ESG Reporting Systems, Risk Management Function. * **Regulatory:** * _Key Metrics:_ Overview of significant upcoming regulatory changes (e.g., CRR III 6, NPL Directive 12, ESG Regulations 4) and their strategic implications. * _Source:_ Summaries from Compliance, Legal, and Risk Functions. ### 2\. Chief Operating Officer (COO) * A. Overview of Key Responsibilities & Decisions Driving Data Needs: The COO is responsible for the end-to-end efficiency and effectiveness of Banca Transilvania's operations. This includes process optimization across all business lines, managing the technology infrastructure that supports operations (often in close collaboration with the CTO/CIO), controlling operational costs, ensuring high-quality service delivery through various channels (including the extensive branch network 3), maintaining business continuity, and managing large operational teams. Decisions focus on resource allocation, process re-engineering, technology investments for efficiency gains, channel strategy execution, and operational risk mitigation. * B. Illustrative Common Reports/Dashboards: Operational Efficiency Dashboard (tracking metrics like cost per transaction, process cycle times, Straight-Through Processing rates), Service Level Agreement (SLA) Compliance Dashboard 41, Branch Network Performance Scorecard, Call Center Performance Report, IT System Uptime & Performance Summary 41, Business Continuity & Disaster Recovery Test Results, Operational Risk Event Summary. * C. Detailed Data Point Inventory: The COO's data needs are heavily focused on process efficiency, cost management, and service quality across all delivery channels. A significant challenge involves integrating data from diverse operational systems (core banking, workflow engines, branch systems, call center software, digital platforms) to achieve a unified view of performance, identify bottlenecks, and optimize resource allocation. Digital adoption metrics 39 are particularly crucial for managing the shift in channel usage and associated costs. * **Operations:** * _Key Metrics:_ Process Cycle Times (e.g., loan application turnaround), Straight-Through Processing (STP) Rates (e.g., for payments), Error Rates (by process/team), Transaction Volumes (by channel, by type), Cost per Transaction 39, Service Level Agreement (SLA) Compliance Rates 41, Branch Footfall & Transaction Counts, ATM Availability & Usage Statistics, Call Center Metrics (Average Handle Time (AHT) 42, First Call Resolution (FCR) 42, Average Speed of Answer/Wait Times 42), Staff Productivity Metrics (e.g., tasks per FTE, potentially AUM/Profit per Employee linkage 43). * _Source:_ Core Banking System, Workflow Management Systems, Call Center Software, Branch Transaction Systems, ATM Monitoring Systems, HR Information System (HRIS). * **IT (Overlap w/ CTO/CIO):** * _Key Metrics:_ Critical System Uptime/Availability 41, Application Performance Metrics (affecting operational staff), Incident Resolution Times (for operational impacts) 37, Infrastructure Costs (as input to operational cost analysis). * _Source:_ IT Monitoring Systems (APM, Infrastructure Monitoring), IT Service Management (ITSM) Platforms. * **Customer:** * _Key Metrics:_ Customer Complaint Volumes & Types (related to operational processes), Channel Usage Statistics (Digital vs. Branch vs. Call Center 39), Transaction Abandonment Rates (especially in digital channels 40). * _Source:_ Customer Relationship Management (CRM) System, Digital Analytics Platforms, Call Center Logs. * **Risk:** * _Key Metrics:_ Operational Risk Event Data (Internal Losses, External Events impacting operations, Near Misses), Business Continuity Plan (BCP) Test Success Rates & Issues Identified, Operational Fraud Rates & Loss Data. * _Source:_ Operational Risk Management System, Business Continuity Management Software, Fraud Detection Systems. * **Financial:** * _Key Metrics:_ Operational Department Budgets vs. Actual Spend, Cost Allocation Data (for understanding cost drivers). * _Source:_ Financial Planning & Analysis Systems, General Ledger (GL). * **Third-Party:** * _Key Metrics:_ Key Vendor Performance Metrics (against SLAs), Outsourcing Partner Performance & Risk Assessments. * _Source:_ Vendor Management System, Contract Repository. ### 3\. Chief Financial Officer (CFO) * A. Overview of Key Responsibilities & Decisions Driving Data Needs: The CFO is the steward of Banca Transilvania's financial health, responsible for the integrity of financial reporting (statutory, regulatory under NBR/EBA rules, and internal management reporting), budgeting and forecasting processes, capital management (ensuring adequacy under CRR/CRD 6 and optimizing capital structure), liquidity management (meeting LCR/NSFR requirements), developing and executing the bank's funding strategy, tax planning and compliance, investor relations, and driving cost control and profitability analysis across the group.28 Decisions revolve around financial planning, resource allocation, capital deployment, funding mix, and communication with investors and regulators. * B. Illustrative Common Reports/Dashboards: Statutory Financial Statements (Balance Sheet, P&L, Cash Flow, Statement of Changes in Equity 28), Regulatory Reporting Packages (COREP for Capital/RWA, FINREP for Financial Information 45), Capital Adequacy Monitoring Reports (CET1, Tier 1, Total CAR 29), Liquidity Position Reports (LCR, NSFR calculations and monitoring 29), Detailed Budget vs. Actual Variance Analysis, Segment and Product Profitability Reports, Funding Composition and Cost of Funds Analysis, Investor Relations Presentations 29, Pillar 3 Disclosures (including ESG aspects 46). * C. Detailed Data Point Inventory: The CFO function demands highly accurate, auditable, and granular financial and regulatory data. The increasing complexity of regulations, such as CRR III implementation 6, specific NBR accounting rules 4, detailed IRRBB reporting 47, and ESG-related Pillar 3 disclosures 46, necessitates robust data governance, including clear data lineage, stringent quality controls, and seamless integration between Finance, Risk, and Treasury systems. Effective profitability analysis requires linking revenues and costs accurately to specific products, customer segments, and business lines. * **Financial:** * _Key Metrics:_ General Ledger (GL) Balances and Transactions, Detailed Balance Sheet Components (Assets 28, Liabilities, Equity), P&L Line Items (Net Interest Income (NII) 29, Net Fee & Commission Income (NFCI) 29, Operating Expenses 29, Loan Loss Provisions 29), Cash Flow Statement Data, Data supporting Accounting Standards (IFRS, NBR specifics 4), Segment/Product/Customer Profitability Calculations, Internal Transfer Pricing Data, Budget and Forecast Data, Tax Calculation Data. * _Source:_ General Ledger (GL), Financial Sub-ledgers (Loans, Deposits, Securities, Fixed Assets), Planning & Budgeting Systems, Treasury Management Systems (TMS), Profitability/Costing Engines. * **Regulatory Reporting:** * _Key Metrics:_ Data points required for NBR reports (e.g., Balance Sheet, P&L, Large Exposures, Securities Holdings 4), EBA COREP data (RWA calculations by risk type, Capital components, Leverage Ratio), EBA FINREP data (detailed financial statement breakdowns), Pillar 3 Disclosure data points (Quantitative & Qualitative, including ESG 4), IRRBB reporting data (as per EBA ITS 47), NPL reporting data (for NPL Directive 12). * _Source:_ Core Banking System, Risk Management Systems (Credit, Market, OpRisk), GL, Treasury/ALM Systems, Regulatory Reporting Software (e.g., BearingPoint's ABACUS used by NBR 45). * **Capital Management:** * _Key Metrics:_ Detailed breakdown of Tier 1 (CET1, AT1) and Tier 2 Capital components, Risk-Weighted Assets (RWAs) calculation details (Standardised and/or IRB approaches for Credit Risk, Market Risk, Operational Risk), Capital Ratios (CET1, Tier 1, Total CAR, Leverage Ratio 29). * _Source:_ GL, Risk Calculation Engines, Regulatory Reporting Systems. * **Liquidity Management:** * _Key Metrics:_ High-Quality Liquid Assets (HQLA) identification and valuation, Net Cash Outflow/Inflow calculation components (deposit run-off factors, drawdown rates), LCR calculation details, Available Stable Funding (ASF) components, Required Stable Funding (RSF) components, NSFR calculation details, Deposit stability analysis data, Funding concentration metrics (by counterparty, product, currency), Asset Encumbrance data. * _Source:_ GL, Treasury Management System (TMS), Asset-Liability Management (ALM) System, Core Banking System. * **Treasury/Funding:** * _Key Metrics:_ Detailed breakdown of Funding Sources (Retail Deposits by type/maturity 35, Corporate Deposits, Wholesale Funding - Bonds, CP, Interbank), Cost of Funds calculations, Asset Encumbrance levels, Debt Instrument details (ISIN, maturity, coupon, covenants), Data on Sustainable Bond issuances.29 * _Source:_ TMS, Core Banking, GL, Capital Markets Systems. * **Risk (Overlap w/ CRO):** * _Key Metrics:_ Loan Loss Provision balances and movements, Expected Credit Loss (ECL) model outputs and inputs, Impairment calculations under IFRS 9, RWA calculation results. * _Source:_ Risk Management Systems, GL, Accounting Policy Engine. * **Investor Relations:** * _Key Metrics:_ Shareholder Register Data, Dividend payment history, Earnings Per Share (EPS) calculation 29, Analyst consensus estimates, Stock price and volume data.15 * _Source:_ Share Registrar, Finance Systems, External Market Data Providers, Investor Relations Platforms. ### 4\. Chief Risk Officer (CRO) * A. Overview of Key Responsibilities & Decisions Driving Data Needs: The CRO is responsible for establishing and overseeing the bank's enterprise-wide risk management framework. This includes defining the risk appetite, monitoring adherence, and managing all material risk categories: credit risk (including NPL management 12), market risk, operational risk (including cyber risk), liquidity risk, interest rate risk in the banking book (IRRBB) 49, credit spread risk in the banking book (CSRBB) 49, compliance risk (often shared with CCO), model risk, and increasingly, ESG risks.7 The CRO oversees stress testing programs, ensures the adequacy of risk models, provides risk input for capital adequacy assessments (ICAAP), and manages regulatory risk reporting (e.g., for SREP 50). Decisions involve setting risk limits, approving large credit exposures, validating risk models, defining mitigation strategies, and advising the Board and CEO on the overall risk profile. * B. Illustrative Common Reports/Dashboards: Enterprise Risk Management (ERM) Dashboard, Risk Appetite Statement Monitoring Report, Credit Portfolio Quality Review (NPL evolution 12, concentration limits, provisioning adequacy 29), Market Risk Exposure Report (VaR, sensitivities, backtesting), Operational Risk Event Log & Loss Analysis, Liquidity Risk Dashboard (LCR, NSFR, Stress Tests 29), IRRBB/CSRBB Sensitivity Reports (EVE, NII impacts 49), Stress Testing Scenario Results, Model Validation Summary Reports, Regulatory Risk Reporting Submissions (SREP data 50). * C. Detailed Data Point Inventory: The CRO requires comprehensive, granular, and high-quality data across all significant risk types for effective measurement, modeling, monitoring, and reporting. Data quality is paramount, as it directly impacts the accuracy of risk models, regulatory capital calculations, and strategic decisions. The increasing focus on non-financial risks (Operational, Cyber, ESG 7) necessitates integrating data from diverse and sometimes new sources. Robust model risk management requires meticulous tracking of model inputs, validation results, and performance, emphasizing the need for strong data lineage and quality metrics. Specific regulations like the NPL Directive 12 and the EBA guidelines on IRRBB/CSRBB 49 impose detailed data and calculation requirements. * **Credit Risk:** * _Key Metrics:_ Borrower Identification Data (Full name, ID numbers - CNP/CUI/Passport, Address, DoB, LEI etc. 23), Loan/Exposure Details (Facility Type, Amount Granted/Outstanding, Currency, Maturity, Interest Rate, Grant Date 13), Collateral Information (Type, Valuation, Location, LTV), Payment Performance History (Days Past Due, Restructuring flags 52), Internal/External Credit Scores/Ratings (e.g., FICO from Biroul de Credit 55), Probability of Default (PD), Loss Given Default (LGD), Exposure at Default (EAD) model inputs/outputs, NPL Specific Data (Outstanding balance, Security type, Discount on sale 12), Loan Loss Provision calculations/levels 29, Portfolio Concentration Data (by Sector, Geography, Single Name), Expected Credit Loss (ECL) data under IFRS 9, Data sourced from Credit Bureaus (CCR, Biroul de Credit 13). * _Source:_ Loan Origination Systems (LOS), Core Banking System, Collateral Management System, Credit Risk Engines/Models, Data Warehouses, External Credit Bureau Feeds. * **Market Risk:** * _Key Metrics:_ Detailed Position Data (Equities, Bonds, FX, Commodities, Derivatives - by instrument, currency, maturity), Market Data Feeds (Prices, Rates, Volatilities, Correlations 15), Value-at-Risk (VaR) calculations (Historical, Parametric, Monte Carlo), Sensitivity Analysis results (Delta, Gamma, Vega, Rho, CS01), Stress Test Scenarios and Results (Market Risk specific), Backtesting Results (VaR vs. Actual P&L). * _Source:_ Trading Systems (Front/Middle Office), Market Data Systems (e.g., Refinitiv, Bloomberg), Market Risk Engines. * **Operational Risk:** * _Key Metrics:_ Internal Loss Event Data (Date, Amount, Cause, Business Line, Recovery), External Loss Event Data (relevant industry events), Key Risk Indicators (KRIs - e.g., Failed Trades, System Downtime, Staff Turnover), Control Self-Assessment Results, Scenario Analysis Inputs/Outputs, IT Risk Assessment findings, Cybersecurity Threat Intelligence Feeds, Number/Impact of Data Breaches.27 * _Source:_ Operational Risk Management Systems (GRC Platforms), IT Security Logs/Reports, Internal Audit Reports, HR Systems, Business Line reporting. * **Liquidity Risk:** * _Key Metrics:_ Detailed Cash Flow Projections (contractual and behavioural), Deposit Run-off Rate Assumptions and Analysis, Funding Concentration limits and monitoring, LCR/NSFR detailed calculation components 29, Intraday Liquidity Positions and Flows, Available Unencumbered Collateral Inventory, Liquidity Stress Test Scenarios/Inputs/Outputs. * _Source:_ Treasury Management System (TMS), ALM System, Core Banking System, Payment Systems, Collateral Management System. * **IRRBB/CSRBB:** * _Key Metrics:_ Banking Book Position Data (Loans, Deposits, Securities - with repricing characteristics, optionality), Repricing Gap Reports, Behavioral Modeling Assumptions & Validation (Non-Maturing Deposit (NMD) decay rates 47, Loan Prepayment rates, Pipeline modelling), EVE Sensitivity Calculation inputs/outputs, NII Sensitivity Calculation inputs/outputs 49, Data for Standardised/Simplified Standardised Approaches if required.56 * _Source:_ ALM System, Core Banking System, Treasury Systems, Data Warehouse. * **Model Risk:** * _Key Metrics:_ Comprehensive Model Inventory (including purpose, owner, inputs, status), Model Documentation Repository, Model Validation Reports and Findings, Ongoing Model Performance Monitoring Data (e.g., backtesting, stability tests), Model Input Data Quality Assessments, Model Change Logs. * _Source:_ Model Risk Management (MRM) System/Database, Validation Reports, Monitoring Tools. * **Compliance Risk (Overlap w/ CCO):** * _Key Metrics:_ Volume/Severity of AML Alerts and SARs filed, Sanctions Screening Hit Rates and Resolution Times 19, Number/Impact of Identified Compliance Breaches, Key Findings from Regulatory Exams/Audits related to risk areas. * _Source:_ AML Monitoring Systems, Sanctions Screening Engines, Compliance Case Management Systems, GRC Platforms. * **ESG Risk:** * _Key Metrics:_ Climate Risk Scenario Data (e.g., NGFS scenarios), Physical Risk Exposure Data (e.g., geo-location of collateral vs. hazard maps), Transition Risk Exposure Data (e.g., portfolio alignment with climate pathways, exposure to high-carbon sectors), Principal Adverse Impact (PAI) indicator data for portfolio 59, EU Taxonomy Alignment data for portfolio.60 * _Source:_ ESG Data Platforms, Internal Risk Models, Client Data/Surveys, External Climate Data Providers. * **Regulatory:** * _Key Metrics:_ Data required for Supervisory Review and Evaluation Process (SREP) submissions 50, Detailed data for regulatory Stress Testing exercises (ECB/EBA/NBR), Data inputs for all NBR/EBA risk-related reporting templates.5 * _Source:_ Aggregated/Derived from various Risk, Finance, and Core systems. **Table II.4.C: CRO Key Risk Data Summary** | | | | | | | --- | --- | --- | --- | --- | | **Risk Category** | **Key Data Point Example** | **Primary Use Case** | **Key Regulatory Driver** | **Primary Data Source System(s)** | | Credit Risk | Probability of Default (PD) Estimates | RWA Calc, Provisioning, Pricing | CRR/CRD IV, IFRS 9 | Credit Risk Engine, Core Banking | | Credit Risk | NPL Outstanding Balance & Security Type | Monitoring, Reporting, Recovery | NPL Directive 12 | Core Banking, Loan System | | Market Risk | Value-at-Risk (VaR) 99%, 1-day | Limit Monitoring, Capital Calc | CRR/CRD IV (FRTB) | Market Risk Engine, Trading System | | Op Risk | Internal Loss Event Data | Capital Calc, Risk Assessment | CRR/CRD IV | OpRisk System (GRC) | | Liquidity Risk | LCR Calculation Components | Regulatory Reporting, Monitoring | CRR/CRD IV, EBA RTS | ALM/Treasury System, Core Banking | | IRRBB | EVE Sensitivity (Parallel Up/Down Shocks) | Monitoring, Reporting, Hedging | EBA GL/RTS 49 | ALM System | | CSRBB | Fair Value Positions in Banking Book | Monitoring, Reporting | EBA GL 49 | ALM/Treasury System, Securities DB | | ESG Risk | Financed Emissions (Scope 3 Cat 15) | Reporting, Strategy, Risk Assess. | CSRD/SFDR/Pillar 3 | ESG Data Platform, Client Data | | ESG Risk | PAI Indicator: Exposure to Fossil Fuels | PAI Reporting | SFDR Annex I 59 | ESG Data Platform, Portfolio System | | Compliance | Sanctions Screening Hits | AML/CFT Compliance | AML Law 26 | Sanctions Screening Engine | | Model Risk | Model Validation Findings | Model Governance, Risk Mitigation | SR 11-7 (Implied) | MRM System, Validation Reports | ### 5\. Chief Compliance Officer (CCO) * A. Overview of Key Responsibilities & Decisions Driving Data Needs: The CCO is responsible for ensuring Banca Transilvania operates in full compliance with all applicable laws, regulations, and internal policies. Key areas include managing the Anti-Money Laundering and Counter-Terrorist Financing (AML/CFT) program 23, overseeing sanctions compliance 19, managing conduct risk, ensuring data privacy adherence under GDPR 10 and local law 32, coordinating responses to regulatory inquiries (often shared with CFO, CRO, Legal), developing and delivering compliance training, and executing compliance monitoring and testing programs. Decisions involve setting compliance policies, approving high-risk customers, investigating suspicious activity, managing regulatory relationships, and determining corrective actions for compliance breaches. * B. Illustrative Common Reports/Dashboards: AML/CFT Activity Report (Alert volumes, SARs filed trends, KYC onboarding status/backlogs), Sanctions Screening Dashboard (Hit rates, false positive analysis, list update status 26), GDPR Compliance Monitoring Report (Data Subject Access Request (DSAR) turnaround times 64, breach incident log 32), Regulatory Change Management Log & Impact Assessment, Compliance Training Completion Statistics, Conduct Risk Indicator Dashboard (Complaints trends, policy breaches), Whistleblowing Channel Report Summary. * C. Detailed Data Point Inventory: The CCO requires access to a vast and diverse range of customer, transaction, employee, and system log data to effectively monitor and enforce compliance across the organization. Key challenges include integrating data from numerous source systems for holistic surveillance (e.g., combining KYC data with transaction data for AML monitoring), ensuring the accuracy and completeness of data required for regulatory reporting (e.g., detailed MiFID II transaction reports 67), and embedding data privacy requirements 10 throughout all data processing activities. The increasing volume and complexity of regulations necessitate significant reliance on automation and specialized compliance technology (e.g., AML monitoring software, sanctions screening engines 65, GRC platforms). The emergence of regulations around new asset classes like crypto-assets also introduces new data and compliance obligations.25 * **AML/CFT:** * _Key Metrics:_ Customer Identification Program (CIP) Data (Full Name, DoB, Address, ID numbers, Nationality, Occupation, Source of Funds/Wealth 23), Beneficial Ownership Information (UBO details, ownership structure 23), Transaction Monitoring System Alerts (Rules triggered, parameters), Alert Investigation Case Files, Suspicious Activity Report (SAR)/Suspicious Transaction Report (STR) filings data, Politically Exposed Person (PEP) Identification Data and associated risk assessments 23, Customer Risk Rating scores and methodologies, Cash Transaction Records (especially >€10k equivalent 26), International Wire Transfer Data (Originator & Beneficiary details 23). * _Source:_ AML Monitoring Systems (e.g., NICE Actimize, SAS AML), KYC/CDD Utilities & Onboarding Systems, Core Banking System, SWIFT/Payment Systems Data Feeds, External Data Providers (Company info, PEP lists). * **Sanctions Compliance:** * _Key Metrics:_ Customer/Counterparty/Beneficiary Data submitted for screening, Transaction Data (payment messages, trade details) submitted for screening, Sanctions List Data Feeds (OFAC 19, EU, UN, HMT, Local NBR lists 20), Screening Results Logs (Hits, Potential Matches, False Positives, Resolution decisions and rationale). * _Source:_ Sanctions Screening Engines (e.g., Fircosoft, Pelican), Transaction Processing Systems (Payments, Trade), Customer Databases (CRM, Core Banking), List Data Providers. * **Data Privacy (GDPR):** * _Key Metrics:_ Data Subject Request Logs (Type: Access, Rectification, Erasure, Portability, Objection; Requester ID, Date Received, Date Completed, Outcome 10), Records of Customer Consent (for specific processing purposes), Data Processing Inventory (Record of Processing Activities - RoPA, detailing data types, purposes, legal basis, retention, transfers), Data Protection Impact Assessment (DPIA) register and outcomes, Personal Data Breach Register (Date, Nature, Impact, Remediation, Notification status 32), Data Protection Officer (DPO) contact details 32, Employee GDPR Training Records. * _Source:_ GDPR Management Platforms/Tools, IT System Logs (Access, Audit Trails), HR Systems, Consent Management Platforms, Data Discovery/Mapping Tools. * **Conduct Risk:** * _Key Metrics:_ Customer Complaint Data (Source, Type, Resolution, Root Cause), Sales Practices Monitoring Results (e.g., suitability assessments review), Conflicts of Interest Register & Disclosures, Gifts & Entertainment Logs/Approvals, Whistleblowing Reports & Investigation Outcomes, Employee Personal Account Dealing Records. * _Source:_ CRM/Complaint Management System, Sales Monitoring Tools, Compliance Case Management, HR Systems, Trading Surveillance Systems. * **Regulatory Compliance Management:** * _Key Metrics:_ Inventory of Applicable Laws & Regulations (NBR 4, EBA 5, ESMA 8, EU Directives/Regulations 4), Compliance Risk Assessment Results, Control Testing Outcomes, Regulatory Interaction Logs (Meetings, Inquiries, Exams), Compliance Training Curricula and Completion Rates. * _Source:_ Governance, Risk & Compliance (GRC) Platforms, Regulatory Intelligence Feeds, Internal Audit Reports, HR/LMS Systems. * **MiFID II Compliance (Overlap w/ HIB/HWM/Market Risk):** * _Key Metrics:_ Transaction Reporting Data (Accuracy/Timeliness checks against RTS 22 requirements 8), Order Record Keeping completeness checks 75, Best Execution Monitoring results (quantitative & qualitative), Product Governance records (Target Market definitions, reviews), Appropriateness & Suitability test results and documentation.76 * _Source:_ Transaction Reporting Systems (ARM/APA feeds), Order Management Systems (OMS), Trading Platforms, Compliance Monitoring Tools, CRM. * **PSD2 Compliance (Overlap w/ CTO/Digital/Fraud):** * _Key Metrics:_ Strong Customer Authentication (SCA) Success/Failure Logs 9, SCA Exemption Usage Data (by type, value, including Transaction Risk Analysis (TRA) inputs/outputs and fraud rates 77), Third-Party Provider (TPP) API Performance/Availability metrics (as per RTS 81), PSD2 Fraud Reporting Data (submitted to regulators 81), Major Incident Reporting data (submitted to regulators 81). * _Source:_ Authentication Platforms, API Gateway Logs, Fraud Monitoring Systems, Regulatory Reporting Systems, Incident Management Systems. ### 6\. Head of Operations (HOO) (Assuming focus on Back Office/Processing) BT - Data Map for Key Managerial Roles Not found This page does not exist Interactive graph On this page Banca Transilvania: A Comprehensive Data Map for Key Managerial Roles I. Executive Summary II. Data Requirements by Key Manager Role 1\. Chief Executive Officer (CEO) 2\. Chief Operating Officer (COO) 3\. Chief Financial Officer (CFO) 4\. Chief Risk Officer (CRO) 5\. Chief Compliance Officer (CCO) 6\. Head of Operations (HOO) (Assuming focus on Back Office/Processing) 7\. Chief Technology Officer / Chief Information Officer (CTO/CIO) 8\. Chief Human Resources Officer (CHRO) 9\. Chief Marketing Officer (CMO) 10\. Head of Retail Banking (HRB) 11\. Head of Corporate Banking (HCB) (Including SME & Mid-Corporate) 12\. Head of Investment Banking (HIB) 13\. Head of Wealth Management / Head of Private Banking (HWM/HPB) 14\. Treasurer / Head of Treasury (TREAS/HT) 15\. Chief Audit Executive (CAE) 16\. General Counsel / Chief Legal Officer (GC/CLO) 17\. Chief Digital Officer (CDO) (Distinct from CTO) [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Binomial coefficient - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions Basic math concepts Combinatorics [Additive principle](https://publish.obsidian.md/discretecs/Combinatorics/Additive+principle) [Binomial coefficient](https://publish.obsidian.md/discretecs/Combinatorics/Binomial+coefficient) [Dots and dividers](https://publish.obsidian.md/discretecs/Combinatorics/Dots+and+dividers) [Factorial](https://publish.obsidian.md/discretecs/Combinatorics/Factorial) [k-Permutation](https://publish.obsidian.md/discretecs/Combinatorics/k-Permutation) [Lattice paths](https://publish.obsidian.md/discretecs/Combinatorics/Lattice+paths) [License plate problem](https://publish.obsidian.md/discretecs/Combinatorics/License+plate+problem) [Multiplicative principle](https://publish.obsidian.md/discretecs/Combinatorics/Multiplicative+principle) [Permutation](https://publish.obsidian.md/discretecs/Combinatorics/Permutation) [Principle of Inclusion and Exclusion](https://publish.obsidian.md/discretecs/Combinatorics/Principle+of+Inclusion+and+Exclusion) [Weight of a bitstring](https://publish.obsidian.md/discretecs/Combinatorics/Weight+of+a+bitstring) Directed Graphs and Relations Graphs Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Binomial coefficient ==================== aliases: [binomial coefficient] [#combinatorics](https://publish.obsidian.md/discretecs/Combinatorics/Binomial+coefficient#combinatorics) Definition ---------- Definition For each [integer](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integers) n≥0 and for each integer k with 0≤k≤n, the **binomial coefficient**, denoted (nk) and pronounced "n choose k", is a number that represents the number of ways to select k objects from a group of n distinct objects. **Notes:** * Please note, (nk) is _not_ a fraction. For example (102) does not equal 5. * The binomial coefficient is sometimes notated as C(n,k). * The binomial coefficient (nk) also represents: * The number of [bitstrings](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Binary+digits+and+bitstrings) with length n and [weight](https://publish.obsidian.md/discretecs/Combinatorics/Weight+of+a+bitstring) k * The number of k\-element [subsets](https://publish.obsidian.md/discretecs/Sets+and+Functions/Subset) of an n\-element set * The coefficient on xkyn−k in the expansion of (x+y)n * The binomial coefficient (nk) can be computed [recursively](https://publish.obsidian.md/discretecs/Recursion/Recursion) when n≥1 and k≥1, using the [recurrence relation](https://publish.obsidian.md/discretecs/Recursion/Recurrence+relation) : (nk)\=(n−1k−1)+(n−1k) * The binomial coefficient (nk) can be computed directly using the [closed formula](https://publish.obsidian.md/discretecs/Recursion/Closed+formula) (nk)\=n!k!(n−k)!Here, the exclamation point in n! is the [factorial function](https://publish.obsidian.md/discretecs/Combinatorics/Factorial) . Examples -------- * Because (nk) is the number of ways to select k objects from a group of n objects, (55)\=1. There is only one way to take a group of 5 objects and select all 5. The [closed formula](https://publish.obsidian.md/discretecs/Recursion/Closed+formula) above also says this, but remember the binomial coefficient solves a counting problem. * More generally, (nn)\=1 for all n≥0. * For the same reason, (n0)\=1 for any n≥0 because there is only one way to select nothing from a group of n objects. * **How many 8-bit strings are there with exactly 5 `1` [bits](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Binary+digits+and+bitstrings) ?** This is asking, _how many 8-bit strings have [weight](https://publish.obsidian.md/discretecs/Combinatorics/Weight+of+a+bitstring) 5?_ The answer is (85)\=8!5!⋅3!\=56. * **How many ways are there to choose three letters from the alphabet A..Z without duplication if we don't care about the ordering of the letters?** This is the same question as: **How many three-element [subsets](https://publish.obsidian.md/discretecs/Sets+and+Functions/Subset) are there of a 26-element set?** The answer to both is (263)\=26!3!⋅23!\=2600. * The number of edges in Kn, the [complete graph](https://publish.obsidian.md/discretecs/Graphs/Complete+graph) on n vertices, is (n2) because in Kn, there is an [edge](https://publish.obsidian.md/discretecs/Graphs/Graph) between every pair of distinct [vertices](https://publish.obsidian.md/discretecs/Graphs/Graph) , and (n2) counts the number of such pairs that can be selected from {1,2,…,n}. Resources --------- The following videos cover the binomial coefficient from first principles. These build on each other, so each video beyond the first references all the ones before it, so watching them out of order could lead to confusion: * [Counting subsets and strings](https://vimeo.com/714228019) * [Counting k\-element subsets](https://vimeo.com/714225614) * [Counting n\-bit strings of weight k](https://vimeo.com/618985119) * [Why counting subsets and counting](https://vimeo.com/714227663) [bitstrings](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Binary+digits+and+bitstrings) are the same * [The Binomial Coefficient](https://vimeo.com/621554165) Other resources: * Tutorial: [Use the Binomial Theorem](https://courses.lumenlearning.com/waymakercollegealgebra/chapter/use-the-binomial-theorem/) Binomial coefficient Not found This page does not exist Interactive graph On this page Definition Examples Resources [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Unknown Not found! --- # Unknown Not found! --- # Unknown Not found! --- # Unknown Not found! --- # Unknown Not found! --- # Unknown Not found! --- # Unknown Not found! --- # Unknown Not found! --- # Unknown Not found! --- # Unknown Not found! --- # Unknown Not found! --- # Unknown Not found! --- # Unknown Not found! --- # Unknown Not found! --- # Unknown Not found! --- # Unknown Not found! --- # Unknown Not found! --- # Unknown Not found! --- # Unknown Not found! --- # Unknown Not found! --- # Unknown Not found! --- # Unknown Not found! --- # Unknown Not found! --- # Unknown Not found! --- # Unknown Not found! --- # Unknown Not found! --- # Unknown Not found! --- # Unknown Not found! --- # Unknown Not found! --- # Unknown Not found! --- # Unknown Not found! --- # Unknown Not found! --- # Factorial - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions Basic math concepts Combinatorics [Additive principle](https://publish.obsidian.md/discretecs/Combinatorics/Additive+principle) [Binomial coefficient](https://publish.obsidian.md/discretecs/Combinatorics/Binomial+coefficient) [Dots and dividers](https://publish.obsidian.md/discretecs/Combinatorics/Dots+and+dividers) [Factorial](https://publish.obsidian.md/discretecs/Combinatorics/Factorial) [k-Permutation](https://publish.obsidian.md/discretecs/Combinatorics/k-Permutation) [Lattice paths](https://publish.obsidian.md/discretecs/Combinatorics/Lattice+paths) [License plate problem](https://publish.obsidian.md/discretecs/Combinatorics/License+plate+problem) [Multiplicative principle](https://publish.obsidian.md/discretecs/Combinatorics/Multiplicative+principle) [Permutation](https://publish.obsidian.md/discretecs/Combinatorics/Permutation) [Principle of Inclusion and Exclusion](https://publish.obsidian.md/discretecs/Combinatorics/Principle+of+Inclusion+and+Exclusion) [Weight of a bitstring](https://publish.obsidian.md/discretecs/Combinatorics/Weight+of+a+bitstring) Directed Graphs and Relations Graphs Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Factorial ========= aliases: [factorial, factorial function] [#combinatorics](https://publish.obsidian.md/discretecs/Combinatorics/Factorial#combinatorics) Definition ---------- Definition For any [integer](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integers) n\>0, the **factorial** of n, denoted n!, is the number n!\=1⋅2⋅3⋅⋯⋅(n−1)⋅nFurthermore we define 0!\=1. **Notes**: * For our purposes, the factorial function is not defined if n<0 or if n is not an integer. * The number n! represents the number of ways to take a group of n distinct objects and rearrange them. * The previous point explains why we consider 0!\=1 and not 0: There is one and only one way to rearrange an empty group of zero objects, which is to do nothing. * The factorial can be defined [recursively](https://publish.obsidian.md/discretecs/Recursion/Recursion) : The base case is 0!\=1 and for all n\>0, define n! to be n⋅(n−1)!. * Because of the previous point, many facts about factorials and formulas that use them are proven using [mathematical induction](https://publish.obsidian.md/discretecs/Proof/Mathematical+induction) . * Python provides a `factorial` function in the `math` library. Here is an example of use: import math math.factorial(15) * You can also define it [recursively](https://publish.obsidian.md/discretecs/Recursion/Recursion) : def factorial(n): if n == 0: return 1 else: return n * factorial(n-1) Examples -------- * Here is a table with the first several values of the factorial: | n | n! | | --- | --- | | 0 | 1 (by definition) | | 1 | 1 | | 2 | 1⋅2\=2 | | 3 | 1⋅2⋅3\=6 | | 4 | 1⋅2⋅3⋅4\=24 | | 5 | 120 | | 6 | 720 | * **How many ways are there to reorder the sequence of colors** 🔴🟡🟢 ? Answer: This is a group of 3 distinct objects and we are rearranging them, so there are 3!\=6 rearrangements. Those are: 🔴🟡🟢 , 🔴🟢🟡, 🟢🔴🟡, 🟢🟡🔴, 🟡🟢🔴, and 🟡🔴🟢. Resources --------- [Screencast 4.8: Rearrangements and k-permutations](https://vimeo.com/626473882) from [Robert Talbert](https://vimeo.com/user132700952) on [Vimeo](https://vimeo.com/) . * Tutorial: [Factorials](https://www.mathsisfun.com/numbers/factorial.html) * Website: [Properties of the factorial, examples, practice exercises](https://testbook.com/maths/factorial-properties#:~:text=Differential%20Equations%20here.-,Factorials%20Properties,(n%E2%88%921)!) Factorial Not found This page does not exist Interactive graph On this page Definition Examples Resources [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Additive principle - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions Basic math concepts Combinatorics [Additive principle](https://publish.obsidian.md/discretecs/Combinatorics/Additive+principle) [Binomial coefficient](https://publish.obsidian.md/discretecs/Combinatorics/Binomial+coefficient) [Dots and dividers](https://publish.obsidian.md/discretecs/Combinatorics/Dots+and+dividers) [Factorial](https://publish.obsidian.md/discretecs/Combinatorics/Factorial) [k-Permutation](https://publish.obsidian.md/discretecs/Combinatorics/k-Permutation) [Lattice paths](https://publish.obsidian.md/discretecs/Combinatorics/Lattice+paths) [License plate problem](https://publish.obsidian.md/discretecs/Combinatorics/License+plate+problem) [Multiplicative principle](https://publish.obsidian.md/discretecs/Combinatorics/Multiplicative+principle) [Permutation](https://publish.obsidian.md/discretecs/Combinatorics/Permutation) [Principle of Inclusion and Exclusion](https://publish.obsidian.md/discretecs/Combinatorics/Principle+of+Inclusion+and+Exclusion) [Weight of a bitstring](https://publish.obsidian.md/discretecs/Combinatorics/Weight+of+a+bitstring) Directed Graphs and Relations Graphs Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Additive principle ================== aliases: [additive principle, addition principle, Addition Principle] [#combinatorics](https://publish.obsidian.md/discretecs/Combinatorics/Additive+principle#combinatorics) Definition ---------- Definition The **additive principle** of counting states that if an event A can occur in m ways, and an event B can occur in n ways, and there is no way for A and B to happen at the same time, then the event "A or B" can occur in m+n ways. Notes: * If it _is_ possible for A and B to occur at the same time, the number of ways that the event "A or B" can happen is given by the [Principle of Inclusion and Exclusion](https://publish.obsidian.md/discretecs/Combinatorics/Principle+of+Inclusion+and+Exclusion) . * The Additive Principle can be extended to more than two events.For example, if A, B, and C are events and no two of them can happen at the same time, and the number of outcomes of each are m, n, and p, then the number of ways A or B or C could occur is m+n+p. Examples and Non-Examples ------------------------- * Suppose a university's student ID number system assigns students a random five-digit number. How many ID numbers end in an [odd](https://publish.obsidian.md/discretecs/Basic+math+concepts/Even+and+odd+integers) number (1,3,5,7,9)? There are five [odd](https://publish.obsidian.md/discretecs/Basic+math+concepts/Even+and+odd+integers) numbers that could work as the ending digit, and only one can actually happen. So we can count the number of ways the ID could end in a 1, the number of ways it could end in a 3, and so on. For each possible [odd](https://publish.obsidian.md/discretecs/Basic+math+concepts/Even+and+odd+integers) ending, there are 10000 possible choices for the first four digits (for example 00001, 00011, 00021, ..., 99991). So the total number of options is 5×10000\=50,000. (Note this makes sense, because the total number of ID's possible at all is 100,000 and exactly half of those will end in an [odd](https://publish.obsidian.md/discretecs/Basic+math+concepts/Even+and+odd+integers) number.) * Using the same student ID setup, how many ID numbers either start with an [odd](https://publish.obsidian.md/discretecs/Basic+math+concepts/Even+and+odd+integers) number _or_ end in an [odd](https://publish.obsidian.md/discretecs/Basic+math+concepts/Even+and+odd+integers) number? The Additive Principle doesn't apply here, because the events are not [disjoint](https://publish.obsidian.md/discretecs/Sets+and+Functions/Intersection) ; it's possible for an ID number to both start and end in an [odd](https://publish.obsidian.md/discretecs/Basic+math+concepts/Even+and+odd+integers) number, like 58831. So we need the [Principle of Inclusion and Exclusion](https://publish.obsidian.md/discretecs/Combinatorics/Principle+of+Inclusion+and+Exclusion) for this. Resources --------- Other resources: * Wikipedia article: [Addition principle](https://en.wikipedia.org/wiki/Addition_principle) Additive principle Not found This page does not exist Interactive graph On this page Definition Examples and Non-Examples Resources [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # k-Permutation - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions Basic math concepts Combinatorics [Additive principle](https://publish.obsidian.md/discretecs/Combinatorics/Additive+principle) [Binomial coefficient](https://publish.obsidian.md/discretecs/Combinatorics/Binomial+coefficient) [Dots and dividers](https://publish.obsidian.md/discretecs/Combinatorics/Dots+and+dividers) [Factorial](https://publish.obsidian.md/discretecs/Combinatorics/Factorial) [k-Permutation](https://publish.obsidian.md/discretecs/Combinatorics/k-Permutation) [Lattice paths](https://publish.obsidian.md/discretecs/Combinatorics/Lattice+paths) [License plate problem](https://publish.obsidian.md/discretecs/Combinatorics/License+plate+problem) [Multiplicative principle](https://publish.obsidian.md/discretecs/Combinatorics/Multiplicative+principle) [Permutation](https://publish.obsidian.md/discretecs/Combinatorics/Permutation) [Principle of Inclusion and Exclusion](https://publish.obsidian.md/discretecs/Combinatorics/Principle+of+Inclusion+and+Exclusion) [Weight of a bitstring](https://publish.obsidian.md/discretecs/Combinatorics/Weight+of+a+bitstring) Directed Graphs and Relations Graphs Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) k-Permutation ============= aliases: [k-permutation, k-permutations] [#combinatorics](https://publish.obsidian.md/discretecs/Combinatorics/k-Permutation#combinatorics) Definition ---------- Definition A **k\-permutation** is a rearrangement of a group of k objects taken from a larger group of objects. The number of k\-permutations of objects taken from a group of n objects is notated P(n,k). **Notes**: * k\-permutations are similar to [permutations](https://publish.obsidian.md/discretecs/Combinatorics/Permutation) , in fact they are the same idea except k\-permutations involve selection from a larger set in addition to rearranging the selection. * If the items in the larger set are all distinct, the following formula for P(n,k) comes directly from the [Multiplicative principle](https://publish.obsidian.md/discretecs/Combinatorics/Multiplicative+principle) and its application to [license plate problems](https://publish.obsidian.md/discretecs/Combinatorics/License+plate+problem) : P(n,k)\=n!(n−k)! Example and non-example ----------------------- * **How many three-letter substrings can be made from the (six letter) word "GUITAR"?** Since all the letters in the word are different, the number is P(6,3)\=6!(6−3)!\=6!3!\=6⋅5⋅4\=120 * The formula is unnecessary for the previous problem because you can think of it as a [license plate problem](https://publish.obsidian.md/discretecs/Combinatorics/License+plate+problem) : Consider the three-character substring as three empty slots to be filled. There are 6 ways to fill the first slot, 5 to fill the second, and 4 to fill the third. Then use the [Multiplicative principle](https://publish.obsidian.md/discretecs/Combinatorics/Multiplicative+principle) to find the result. * **Non-example:** In a pizza restaurant with 10 toppings available, how many ways can you order a pizza with 4 toppings (and no double-toppings)? The answer is _not_ P(10,4)\=10!/6!\=5040 because this considers rearrangements of toppings on a pizza as completely different pizzas. For example the selection _pepperoni, sausage, mushrooms, pineapple_ would be counted differently from the selection _sausage, pineapple, pepperoni, mushrooms_ even though these are the same pizza -- so there is an overcount. In this case we are not creating _rearrangements_ of toppings, we are just selecting four toppings from a set of 10 and not caring about what order in which we make the selection. So the correct answer is given by the [binomial coefficient](https://publish.obsidian.md/discretecs/Combinatorics/Binomial+coefficient) : (104)\=10!4!⋅6!\=210 * In the non-example, you can also reason through it to say that P(10,4) overcounts by a factor equal to the number of ways to rearrange a selection of four things. Since double-toppings aren't allowed, that number is 4! and so the correct count is P(10,4)/4!\=210. Resources --------- [Screencast 4.8: Rearrangements and k-permutations](https://vimeo.com/626473882) from [Robert Talbert](https://vimeo.com/user132700952) on [Vimeo](https://vimeo.com/) . Other resources: * Tutorial: [https://zipcon.net/~swhite/docs/math/probability/counting.html](https://zipcon.net/~swhite/docs/math/probability/counting.html) See "Permutations of _k_ items taken from _n_ items". k-Permutation Not found This page does not exist Interactive graph On this page Definition Example and non-example Resources [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Permutation - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions Basic math concepts Combinatorics [Additive principle](https://publish.obsidian.md/discretecs/Combinatorics/Additive+principle) [Binomial coefficient](https://publish.obsidian.md/discretecs/Combinatorics/Binomial+coefficient) [Dots and dividers](https://publish.obsidian.md/discretecs/Combinatorics/Dots+and+dividers) [Factorial](https://publish.obsidian.md/discretecs/Combinatorics/Factorial) [k-Permutation](https://publish.obsidian.md/discretecs/Combinatorics/k-Permutation) [Lattice paths](https://publish.obsidian.md/discretecs/Combinatorics/Lattice+paths) [License plate problem](https://publish.obsidian.md/discretecs/Combinatorics/License+plate+problem) [Multiplicative principle](https://publish.obsidian.md/discretecs/Combinatorics/Multiplicative+principle) [Permutation](https://publish.obsidian.md/discretecs/Combinatorics/Permutation) [Principle of Inclusion and Exclusion](https://publish.obsidian.md/discretecs/Combinatorics/Principle+of+Inclusion+and+Exclusion) [Weight of a bitstring](https://publish.obsidian.md/discretecs/Combinatorics/Weight+of+a+bitstring) Directed Graphs and Relations Graphs Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Permutation =========== aliases: [permutation, permutations] [#combinatorics](https://publish.obsidian.md/discretecs/Combinatorics/Permutation#combinatorics) Definition ---------- Definition A **permutation** of a set of objects is a possible rearrangement of those objects. **Notes:** * The number of permutations of a set of n **distinct** objects is n! (n [factorial](https://publish.obsidian.md/discretecs/Combinatorics/Factorial) ). * The number of permutations of a set of n objects _not all of which are distinct_ is less than n! because simply computing a [factorial](https://publish.obsidian.md/discretecs/Combinatorics/Factorial) overcounts the repeated objects. * The Python library itertools contains functions for enumerating permutations of sets. More here: [https://docs.python.org/3/library/itertools.html](https://docs.python.org/3/library/itertools.html) For example the following code will print a list containing all 420 distinct permutations of the word "success": import itertools p = itertools.permutations("success") # The permutations function includes duplicate elements. # Converting the list to a set and then back to a list removes # all the duplicates. list(set(([i for i in p]))) Examples -------- * There are 6 permutations of the letters X, Y, and Z: XYZ, XZY, YXZ, YZX, ZXY, ZYX. * There are 24 permutations of the letters X, Y, Z, and T: ('x', 'y', 'z', 't'), ('x', 'y', 't', 'z'), ('x', 'z', 'y', 't'), ('x', 'z', 't', 'y'), ('x', 't', 'y', 'z'), ('x', 't', 'z', 'y'), ('y', 'x', 'z', 't'), ('y', 'x', 't', 'z'), ('y', 'z', 'x', 't'), ('y', 'z', 't', 'x'), ('y', 't', 'x', 'z'), ('y', 't', 'z', 'x'), ('z', 'x', 'y', 't'), ('z', 'x', 't', 'y'), ('z', 'y', 'x', 't'), ('z', 'y', 't', 'x'), ('z', 't', 'x', 'y'), ('z', 't', 'y', 'x'), ('t', 'x', 'y', 'z'), ('t', 'x', 'z', 'y'), ('t', 'y', 'x', 'z'), ('t', 'y', 'z', 'x'), ('t', 'z', 'x', 'y'), ('t', 'z', 'y', 'x') Resources --------- [Screencast 4.8: Rearrangements and k-permutations](https://vimeo.com/626473882) from [Robert Talbert](https://vimeo.com/user132700952) on [Vimeo](https://vimeo.com/) . Other resources: * Tutorial: [Combinations and permutations](https://www.mathsisfun.com/combinatorics/combinations-permutations.html) Permutation Not found This page does not exist Interactive graph On this page Definition Examples Resources [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # License plate problem - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions Basic math concepts Combinatorics [Additive principle](https://publish.obsidian.md/discretecs/Combinatorics/Additive+principle) [Binomial coefficient](https://publish.obsidian.md/discretecs/Combinatorics/Binomial+coefficient) [Dots and dividers](https://publish.obsidian.md/discretecs/Combinatorics/Dots+and+dividers) [Factorial](https://publish.obsidian.md/discretecs/Combinatorics/Factorial) [k-Permutation](https://publish.obsidian.md/discretecs/Combinatorics/k-Permutation) [Lattice paths](https://publish.obsidian.md/discretecs/Combinatorics/Lattice+paths) [License plate problem](https://publish.obsidian.md/discretecs/Combinatorics/License+plate+problem) [Multiplicative principle](https://publish.obsidian.md/discretecs/Combinatorics/Multiplicative+principle) [Permutation](https://publish.obsidian.md/discretecs/Combinatorics/Permutation) [Principle of Inclusion and Exclusion](https://publish.obsidian.md/discretecs/Combinatorics/Principle+of+Inclusion+and+Exclusion) [Weight of a bitstring](https://publish.obsidian.md/discretecs/Combinatorics/Weight+of+a+bitstring) Directed Graphs and Relations Graphs Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) License plate problem ===================== aliases: [license plate problems, license plate problem] [#combinatorics](https://publish.obsidian.md/discretecs/Combinatorics/License+plate+problem#combinatorics) Definition ---------- Definition The **license plate problem** is a general category of counting problems motivated by counting the number of license plates possible when given a certain way of making them. (Examples are below.) **Notes**: * The license plate problem is a typical and common use of the [Multiplicative principle](https://publish.obsidian.md/discretecs/Combinatorics/Multiplicative+principle) and of [k-permutations](https://publish.obsidian.md/discretecs/Combinatorics/k-Permutation) . Examples -------- * **A certain state makes license plates with three letters A:Z followed by three digits 0:9. How many license plates are possible?** Visualize the license plate as six empty slots: ![licenseplate.png](https://publish-01.obsidian.md/access/64d815ddc8215841f63db915c7923004/Assets/Images/licenseplate.png) There are 26 ways to fill in each of the first three slots, and 10 ways to fill in each of the last three slots. Applying the [Multiplicative principle](https://publish.obsidian.md/discretecs/Combinatorics/Multiplicative+principle) , the number of license plates is 263⋅103. * **How many 6-bit strings are there that either start on the left with `00` or end on the right with `11`?** Visualize the 6-bit string as a license plate with six slots. If we require the string to start with `00`, then the first two slots are taken and there are 2 ways to fill in the other 4, giving a total of 24 ways to start with `00`. Similarly, there are 24 ways to end in `11`. Note that these conditions are not [disjoint](https://publish.obsidian.md/discretecs/Sets+and+Functions/Intersection) because we can have a bit string that starts with `00` and ends in `11`; a string like that would leave the middle two slots open, so there are 22\=4 ways to have such a string. Therefore by the [Principle of Inclusion and Exclusion](https://publish.obsidian.md/discretecs/Combinatorics/Principle+of+Inclusion+and+Exclusion) , the number of strings that either start with `00` or end in `11` is 24+24−22\=28. Resources --------- * Tutorial: [Permutation license plate problem](https://www.beatthegmat.com/permutation-license-plate-problem-t5270.html) License plate problem Not found This page does not exist Interactive graph On this page Definition Examples Resources [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Multiplicative principle - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions Basic math concepts Combinatorics [Additive principle](https://publish.obsidian.md/discretecs/Combinatorics/Additive+principle) [Binomial coefficient](https://publish.obsidian.md/discretecs/Combinatorics/Binomial+coefficient) [Dots and dividers](https://publish.obsidian.md/discretecs/Combinatorics/Dots+and+dividers) [Factorial](https://publish.obsidian.md/discretecs/Combinatorics/Factorial) [k-Permutation](https://publish.obsidian.md/discretecs/Combinatorics/k-Permutation) [Lattice paths](https://publish.obsidian.md/discretecs/Combinatorics/Lattice+paths) [License plate problem](https://publish.obsidian.md/discretecs/Combinatorics/License+plate+problem) [Multiplicative principle](https://publish.obsidian.md/discretecs/Combinatorics/Multiplicative+principle) [Permutation](https://publish.obsidian.md/discretecs/Combinatorics/Permutation) [Principle of Inclusion and Exclusion](https://publish.obsidian.md/discretecs/Combinatorics/Principle+of+Inclusion+and+Exclusion) [Weight of a bitstring](https://publish.obsidian.md/discretecs/Combinatorics/Weight+of+a+bitstring) Directed Graphs and Relations Graphs Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Multiplicative principle ======================== aliases: [multiplicative principle, multiplication principle, Multiplication Principle] [#combinatorics](https://publish.obsidian.md/discretecs/Combinatorics/Multiplicative+principle#combinatorics) Definition ---------- Definition The **multiplicative principle** of counting states that if an event A can occur in m ways, and another event B can occur in n different ways, then the number of ways for A and B to happen simultaneously is m⋅n. Notes: * The multiplicative principle is used when counting the number of outcomes of a process where the steps in the process are independent of each other and we know the number of outcomes of each step. * The multiplicative principle can be extended to more than two events. Examples -------- * (_The "license plate" problem_) The license plate numbers in a certain state consist of three letters (A through Z) and three digits (0 through 9). How many possible license plate numbers are there? Think of choosing a license plate number as a six-step process: Choose the first letter, then the second, then the third; then choose the first digit, then the second, then the third. There are 26 ways to choose each letter (and the choice of a letter in one step doesn't influence the choice in the next step); and there are 10 ways to choose each digit. So the total number of license plate numbers is 26⋅26⋅26⋅10⋅10⋅10\=17,576,000. * What if no duplicates of either letters or digits were allowed? It's still a six-step process but the number of choices in each step will change. There are 26 choices for the first letter, now 25 for the second, and 24 for the third; likewise there are 10 choices for the first digit, now 9 for the second, and 8 for the third. The total number of license plate numbers is therefore 26⋅25⋅24⋅10⋅9⋅8\=11,232,000. * How many ways are there to have a license plate that starts with either the letter "Q" or the letter "X"? The multiplicative principle is only partially helpful here because we need to count the number of outcomes of two [disjoint](https://publish.obsidian.md/discretecs/Sets+and+Functions/Intersection) choices (starting with a Q versus starting with an X) and so we need the [Additive principle](https://publish.obsidian.md/discretecs/Combinatorics/Additive+principle) . Solution to the third example Break the problem up by counting the number of ways to start with a Q first, then count the number of ways to start with an X. Once we figure those out, use the [Additive principle](https://publish.obsidian.md/discretecs/Combinatorics/Additive+principle) . Number of ways to start with a Q: If we start with a Q then there are 26 choices for the second letter and 26 choices for the third (we are assuming duplicates are OK), then 10 choices for each digit. The multiplicative principle then says the total number of "Q" license plates is 262⋅103\=676,000. Number of ways to start with an X: It's the same reasoning as starting with a Q, so 676,000 of these. Since these two outcomes are disjoint and we are counting the ways either one could happen, the [Additive Principle](https://publish.obsidian.md/discretecs/Combinatorics/Additive+principle) applies and the total number of outcomes is 676000+676000\=1,352,000. Resources --------- [Screencast 4.2: The Multiplicative Principle](https://vimeo.com/618923433) from [Robert Talbert](https://vimeo.com/user132700952) on [Vimeo](https://vimeo.com/) . Other resources: * Tutorial: [Multiplicative principle](https://www3.nd.edu/~apilking/Math10120/Lectures/Solutions/Topic03.pdf) Multiplicative principle Not found This page does not exist Interactive graph On this page Definition Examples Resources [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Dots and dividers - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions Basic math concepts Combinatorics [Additive principle](https://publish.obsidian.md/discretecs/Combinatorics/Additive+principle) [Binomial coefficient](https://publish.obsidian.md/discretecs/Combinatorics/Binomial+coefficient) [Dots and dividers](https://publish.obsidian.md/discretecs/Combinatorics/Dots+and+dividers) [Factorial](https://publish.obsidian.md/discretecs/Combinatorics/Factorial) [k-Permutation](https://publish.obsidian.md/discretecs/Combinatorics/k-Permutation) [Lattice paths](https://publish.obsidian.md/discretecs/Combinatorics/Lattice+paths) [License plate problem](https://publish.obsidian.md/discretecs/Combinatorics/License+plate+problem) [Multiplicative principle](https://publish.obsidian.md/discretecs/Combinatorics/Multiplicative+principle) [Permutation](https://publish.obsidian.md/discretecs/Combinatorics/Permutation) [Principle of Inclusion and Exclusion](https://publish.obsidian.md/discretecs/Combinatorics/Principle+of+Inclusion+and+Exclusion) [Weight of a bitstring](https://publish.obsidian.md/discretecs/Combinatorics/Weight+of+a+bitstring) Directed Graphs and Relations Graphs Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Dots and dividers ================= aliases: [dots and dividers, stars and bars] [#combinatorics](https://publish.obsidian.md/discretecs/Combinatorics/Dots+and+dividers#combinatorics) Definition ---------- Definition The **dots and dividers** method is an approach to counting the number of ways to distribute identical objects to a group of recipients. The basic outline of the method is: 1. Represent each object being distributed as a "dot". 2. Represent the _change from one recipient to another_ as a "divider". 3. Each distribution is now representable as a sequence of dots and dividers, which can be translated into [bitstrings](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Binary+digits+and+bitstrings) in which each dot is a `0` and each divider is a `1`. 4. The number of those [bitstrings](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Binary+digits+and+bitstrings) , and hence the number distributions, can then be counted with the [binomial coefficient](https://publish.obsidian.md/discretecs/Combinatorics/Binomial+coefficient) . **Notes:** * This method goes by other names including _stars and bars_; _balls and bars_; _sticks and stones_; and _balls and urns_. Examples -------- Example **Problem:** How many ways are there to distribute ten identical 20-dollar bills to three children? **Solution:** Model each distribution using dots and dividers with each bill represented by a dot, and each change between children as a divider. For example, giving the first child 2 bills, the second child 5 bills, and the third child 3 bills would be represented as: `**|*****|***`. Likewise the diagram `****||******` represents a distribution where the first child gets 4 bills, the second child gets none, and the third child gets 6. Each diagram corresponds to a 12-bit [bitstring](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Binary+digits+and+bitstrings) that has [weight](https://publish.obsidian.md/discretecs/Combinatorics/Weight+of+a+bitstring) 2 because there are always 2 dividers no matter what the distribution. There are \\binom{12}{2} = 66 of these. Example **Problem**: How many nonnegative integer solutions are there to the equation x + y + z + w = 15? **Solution**: This is the same problem as distributing 15 identical objects to four different people, so we can model each solution as a dots-and-dividers diagram. For example x = 1, y = 4, z = 8, w = 2 is a solution and can be represented by the diagram `*|****|********|**`. There are 15 dots and 3 dividers, so each diagram can be thought of as an 18-bit string with weight 3. There are \\binom{18}{3} = 816 of these. Resources --------- Other resources: * Video: [Stars and bars counting](https://www.youtube.com/watch?v=epY_8lcKxCU) * Tutorial: [Ball-and-urn](https://artofproblemsolving.com/wiki/index.php/Ball-and-urn) Dots and dividers Not found This page does not exist Interactive graph On this page Definition Examples Resources [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Lattice paths - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions Basic math concepts Combinatorics [Additive principle](https://publish.obsidian.md/discretecs/Combinatorics/Additive+principle) [Binomial coefficient](https://publish.obsidian.md/discretecs/Combinatorics/Binomial+coefficient) [Dots and dividers](https://publish.obsidian.md/discretecs/Combinatorics/Dots+and+dividers) [Factorial](https://publish.obsidian.md/discretecs/Combinatorics/Factorial) [k-Permutation](https://publish.obsidian.md/discretecs/Combinatorics/k-Permutation) [Lattice paths](https://publish.obsidian.md/discretecs/Combinatorics/Lattice+paths) [License plate problem](https://publish.obsidian.md/discretecs/Combinatorics/License+plate+problem) [Multiplicative principle](https://publish.obsidian.md/discretecs/Combinatorics/Multiplicative+principle) [Permutation](https://publish.obsidian.md/discretecs/Combinatorics/Permutation) [Principle of Inclusion and Exclusion](https://publish.obsidian.md/discretecs/Combinatorics/Principle+of+Inclusion+and+Exclusion) [Weight of a bitstring](https://publish.obsidian.md/discretecs/Combinatorics/Weight+of+a+bitstring) Directed Graphs and Relations Graphs Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Lattice paths ============= aliases: - lattice paths - lattice path - grid path tags: combinatorics created: 2026-03-01 updated: 2026-03-01 * * * Definition ---------- Definition A **lattice path** from (0,0) to (m,n) is a path on the [integer](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integers) grid that starts at the origin, ends at the point (m,n), and at each step moves either **one unit to the right** (R) or **one unit up** (U). The total number of such paths is (m+nm). Picture the integer grid — the set of all points (x,y) where x and y are non-negative integers. A lattice path from (0,0) to (m,n) must take exactly m steps to the right and exactly n steps upward, in some order. Since every path consists of exactly m+n steps total, and we need to choose which m of those steps are "right" steps (the rest being "up" steps), the count follows directly from the [binomial coefficient](https://publish.obsidian.md/discretecs/Combinatorics/Binomial+coefficient) . Lattice paths are a powerful combinatorial tool because many counting problems can be recast as counting lattice paths — sometimes with additional constraints (like "never cross a diagonal"). They also provide natural [combinatorial proofs](https://publish.obsidian.md/discretecs/Proof/Combinatorial+proof) of [binomial coefficient](https://publish.obsidian.md/discretecs/Combinatorics/Binomial+coefficient) identities. **Why (m+nm):** Every lattice path from (0,0) to (m,n) corresponds to a sequence of m+n moves, exactly m of which are R and n of which are U. Choosing which m positions in the sequence are R (and the remaining n are U) uniquely determines the path, so there are (m+nm) paths. Examples and Non-Examples ------------------------- **Example — paths from (0,0) to (2,2):** Each path takes 4 steps, 2 of which are R and 2 are U. The (42)\=6 paths are: * RRUU * RURU * RUUR * UURR * URUR * URRU You can verify these by drawing the 2×2 grid and tracing each route. **Example — paths from (0,0) to (3,1):** Each path takes 4 steps, 3 R and 1 U. There are (41)\=4 paths: RRRU, RRUR, RURR, URRR. **Example — [combinatorial proof](https://publish.obsidian.md/discretecs/Proof/Combinatorial+proof) connection:** The Pascal's triangle identity (nk)\=(n−1k−1)+(n−1k) has a natural lattice path proof. Every path from (0,0) to (k,n−k) either passes through (k−1,n−k) (the step just before the last R) or through (k,n−k−1) (the step just before the last U). Counting paths through each intermediate point gives (n−1k−1)+(n−1k), which equals (nk). **Non-example — diagonal moves:** If a path is allowed to move diagonally (e.g., up-right in a single step), it is no longer a lattice path in the standard sense. The count (m+nm) applies only when moves are restricted to single steps right or up. **Non-example — unrestricted grid walks:** A random walk on the integer grid that allows left and down moves, or moves in all four directions, is not a lattice path in this sense. Lattice paths are strictly monotone — they never move left or down. Resources --------- Video: See course video playlist for the lecture on combinatorics and the binomial coefficient. Other resources: * Course Vault: [Binomial coefficient](https://publish.obsidian.md/discretecs/Combinatorics/Binomial+coefficient) * Course Vault: [Combinatorial proof](https://publish.obsidian.md/discretecs/Proof/Combinatorial+proof) * Oscar Levin, _Discrete Mathematics: An Open Introduction_, Section 1.2: [https://discrete.openmathbooks.org/dmoi4.html](https://discrete.openmathbooks.org/dmoi4.html) Practice -------- 1. How many lattice paths are there from (0,0) to (4,3)? List the moves in two of them explicitly. 2. How many lattice paths from (0,0) to (5,5) pass through the point (2,3)? (Hint: count paths from (0,0) to (2,3) and from (2,3) to (5,5) separately, then apply the [Multiplicative Principle](https://publish.obsidian.md/discretecs/Combinatorics/Multiplicative+principle) .) 3. Give a [combinatorial proof](https://publish.obsidian.md/discretecs/Proof/Combinatorial+proof) of the identity (nk)\=(nn−k) using lattice paths. (Hint: describe a bijection between paths from (0,0) to (k,n−k) and paths from (0,0) to (n−k,k).) 4. How many lattice paths from (0,0) to (n,n) stay on or below the main diagonal (i.e., never have more U steps than R steps at any point along the path)? (This is the Catalan number Cn\=1n+1(2nn) — you do not need to prove this formula, but try to count for small values of n and verify.) Lattice paths Not found This page does not exist Interactive graph On this page Definition Examples and Non-Examples Resources Practice [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Recurrence relation - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions Basic math concepts Combinatorics Directed Graphs and Relations Graphs Proof Recursion [Arithmetic sequence](https://publish.obsidian.md/discretecs/Recursion/Arithmetic+sequence) [Characteristic root method](https://publish.obsidian.md/discretecs/Recursion/Characteristic+root+method) [Closed formula](https://publish.obsidian.md/discretecs/Recursion/Closed+formula) [Fibonacci sequence](https://publish.obsidian.md/discretecs/Recursion/Fibonacci+sequence) [Geometric sequence](https://publish.obsidian.md/discretecs/Recursion/Geometric+sequence) [Homogeneous recurrence relation](https://publish.obsidian.md/discretecs/Recursion/Homogeneous+recurrence+relation) [Linear recurrence relation](https://publish.obsidian.md/discretecs/Recursion/Linear+recurrence+relation) [Recurrence relation](https://publish.obsidian.md/discretecs/Recursion/Recurrence+relation) [Recursion](https://publish.obsidian.md/discretecs/Recursion/Recursion) [Sequence](https://publish.obsidian.md/discretecs/Recursion/Sequence) [Solution to a recurrence relation](https://publish.obsidian.md/discretecs/Recursion/Solution+to+a+recurrence+relation) Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Recurrence relation =================== aliases: [recurrence relation, recurrence relations] [#recursion-induction](https://publish.obsidian.md/discretecs/Recursion/Recurrence+relation#recursion-induction) Definition ---------- Definition A **recurrence relation** is a formula that defines a [sequence](https://publish.obsidian.md/discretecs/Recursion/Sequence) using a rule that gives the next term of the sequence terms of previously-computed terms of the sequence. The **order** of the recurrence relation refers to the number of steps backward needed to define the next term. Notes: * A [recursive](https://publish.obsidian.md/discretecs/Recursion/Recursion) definition of a sequence consists of two parts: A set of _initial conditions_ that explicitly give early terms of the sequence, and a recurrence relation used to build later terms of the sequence from the initial ones. * A **solution** to a recurrence relation is a [closed formula](https://publish.obsidian.md/discretecs/Recursion/Closed+formula) that gives all the terms of the sequence without using [recursion](https://publish.obsidian.md/discretecs/Recursion/Recursion) . Examples -------- * The [Fibonacci sequence](https://publish.obsidian.md/discretecs/Recursion/Fibonacci+sequence) uses the recurrence relation F\_n = F\_{n-1} + F\_{n-2} which, in English, says that each term of the sequence is the sum of the previous two. Because it requires going back two steps, this is a _second-order_ recurrence relation. To compute the [Fibonacci sequence](https://publish.obsidian.md/discretecs/Recursion/Fibonacci+sequence) terms, we also need initial conditions, in this case F\_0 = 1 and F\_1 = 1. * The number of circles in step n of the visual pattern below can be expressed with the recurrence relation T\_n = T\_{n-1} + n if we start the index at n=1. In words, the number of circles in the next step is equal to the number of circles from the previous step, plus the actual number of the step. (For example in Step 5, 15 circles, the number of circles is the number of circles from Step 4 plus the number 5. In Step 6, there would be 15 + 6 = 21 circles, and so on.) This is a _first-order_ recurrence relation because it only requires one backward step. ![triangular-visual.png](https://publish-01.obsidian.md/access/64d815ddc8215841f63db915c7923004/Assets/Images/triangular-visual.png) * A [closed formula](https://publish.obsidian.md/discretecs/Recursion/Closed+formula) for the recurrence relation in the previous point, is f(n) = \\dfrac{n(n+1)}{2}. * Suppose the sequence a\_n is given [recursively](https://publish.obsidian.md/discretecs/Recursion/Recursion) by the initial condition a\_0 = 3 and the first-order recurrence relation a\_n = 2a\_{n-1} for n > 0. Then a\_1 = 2a\_0 = 6. Then a\_2 = 2a\_1 = 12. Then a\_3 = 2a\_2 = 24. Continuing this way we get the [geometric sequence](https://publish.obsidian.md/discretecs/Recursion/Geometric+sequence) 3, 6, 12, 24, 48, 96, \\dots. A [closed formula](https://publish.obsidian.md/discretecs/Recursion/Closed+formula) for this recurrence relation is f(n) = 3 \\cdot 2^n. Resources --------- Recurrence relation Not found This page does not exist Interactive graph On this page Definition Examples Resources [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Recursion - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions Basic math concepts Combinatorics Directed Graphs and Relations Graphs Proof Recursion [Arithmetic sequence](https://publish.obsidian.md/discretecs/Recursion/Arithmetic+sequence) [Characteristic root method](https://publish.obsidian.md/discretecs/Recursion/Characteristic+root+method) [Closed formula](https://publish.obsidian.md/discretecs/Recursion/Closed+formula) [Fibonacci sequence](https://publish.obsidian.md/discretecs/Recursion/Fibonacci+sequence) [Geometric sequence](https://publish.obsidian.md/discretecs/Recursion/Geometric+sequence) [Homogeneous recurrence relation](https://publish.obsidian.md/discretecs/Recursion/Homogeneous+recurrence+relation) [Linear recurrence relation](https://publish.obsidian.md/discretecs/Recursion/Linear+recurrence+relation) [Recurrence relation](https://publish.obsidian.md/discretecs/Recursion/Recurrence+relation) [Recursion](https://publish.obsidian.md/discretecs/Recursion/Recursion) [Sequence](https://publish.obsidian.md/discretecs/Recursion/Sequence) [Solution to a recurrence relation](https://publish.obsidian.md/discretecs/Recursion/Solution+to+a+recurrence+relation) Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Recursion ========= aliases: [recursion, recursively, recursive] [#recursion-induction](https://publish.obsidian.md/discretecs/Recursion/Recursion#recursion-induction) Definition ---------- Definition **Recursion** is the process of computing or constructing an object using simpler versions of itself. A process that exhibits recursion is called _recursive_. A recursive process needs two parts to be fully specified: 1. A _base case_ (or base cases) that gives the computation or construction directly without recursion, and 2. A _recursive step_ consisting of a set of rules for computing or building all other cases out of simpler cases, eventually terminating in the base case. Notes: * Without the base case, a recursive process would enter an [infinite regress](https://en.wikipedia.org/wiki/Infinite_regress) where computations would continue but never end. Examples -------- ### The [Fibonacci sequence](https://publish.obsidian.md/discretecs/Recursion/Fibonacci+sequence) The _[Fibonacci sequence](https://publish.obsidian.md/discretecs/Recursion/Fibonacci+sequence) _ is a [sequence](https://publish.obsidian.md/discretecs/Recursion/Sequence) of [integers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integers) defined recursively as follows: * Base case: The first two Fibonacci numbers, F\_0 and F\_1 are defined directly: We declare F\_0 =1 and also F\_1 = 1. * Recursive step: All other Fibonacci numbers are computed as _the sum of the previous two Fibonacci numbers_. That is, for n \\geq 2, F\_n = F\_{n-1} + F\_{n-2}. The Fibonacci sequence therefore starts with F\_0 = 1 and F\_1 = 1. Then F\_2 = F\_1 + F\_0 = 1 + 1 = 2. Then F\_3 = F\_2 + F\_1 = 2 + 1 = 3. Then F\_4 = F\_3 + F\_2 = 3 + 2 = 5. And so on. The first 20 numbers in the sequence are: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, \\dots Here is a recursive Python function for computing the nth Fibonacci number: def fib(n): if n == 1 or n == 2: return 1 else: return fib(n-1) + fib(n-2) (Warning, this function is extremely slow for inputs above 20.) ### Summing a list of numbers Suppose `L` is a list of numbers. We can define the sum of the list, `sum(L)`, recursively using the length of the list: * Base case: If the length of `L` is 0 then `sum(L)` is defined to be 0. If the length of `L` is 1, then `sum(L)` is defined to be just the single number in the list. * Recursive step: If the list has length 2 or greater, then select the first element in the list and call it `a`. Then, `sum(L)` is `a`, plus the `sum` of the list consisting of `L` with `a` removed. Thus, for example, `sum([8,6,7,5])` would be computed like this: \\begin{align\*} \\text{sum}(\[8,6,7,5\]) &= 8 + \\text{sum}(\[6,7,5\]) \\\\ &= 8 + (6 + \\text{sum}(\[7,5\])) \\\\ &= 8 + (6 + (7 + \\text{sum}(\[5\]))) \\\\ &= 8 + 6 + 7 + 5 \\\\ &= 26 \\end{align\*} Here is a recursive Python function that does this: def sum_rec(L): if len(L) == 0: return 0 elif len(L) == 1: return L[0] else: return L[0] + sum_rec(L[1:]) ### Other examples Many other examples of recursion are found throughout mathematics and computing, including the [binomial coefficient](https://publish.obsidian.md/discretecs/Combinatorics/Binomial+coefficient) . Resources --------- Other resources: * Video: [Recursion simply explained with code examples](https://www.youtube.com/watch?v=m1Fjdnj_Mds) * Video: [Learn recursion in 8 minutes](https://www.youtube.com/watch?v=u8Xam9EsqXQ) * Video : [5 simple steps for solving any recursive problem](https://www.youtube.com/watch?v=ngCos392W4w) Recursion Not found This page does not exist Interactive graph On this page Definition Examples The Fibonacci sequence Summing a list of numbers Other examples Resources [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Principle of Inclusion and Exclusion - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions Basic math concepts Combinatorics [Additive principle](https://publish.obsidian.md/discretecs/Combinatorics/Additive+principle) [Binomial coefficient](https://publish.obsidian.md/discretecs/Combinatorics/Binomial+coefficient) [Dots and dividers](https://publish.obsidian.md/discretecs/Combinatorics/Dots+and+dividers) [Factorial](https://publish.obsidian.md/discretecs/Combinatorics/Factorial) [k-Permutation](https://publish.obsidian.md/discretecs/Combinatorics/k-Permutation) [Lattice paths](https://publish.obsidian.md/discretecs/Combinatorics/Lattice+paths) [License plate problem](https://publish.obsidian.md/discretecs/Combinatorics/License+plate+problem) [Multiplicative principle](https://publish.obsidian.md/discretecs/Combinatorics/Multiplicative+principle) [Permutation](https://publish.obsidian.md/discretecs/Combinatorics/Permutation) [Principle of Inclusion and Exclusion](https://publish.obsidian.md/discretecs/Combinatorics/Principle+of+Inclusion+and+Exclusion) [Weight of a bitstring](https://publish.obsidian.md/discretecs/Combinatorics/Weight+of+a+bitstring) Directed Graphs and Relations Graphs Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Principle of Inclusion and Exclusion ==================================== aliases: [Inclusion-Exclusion Principle, Inclusion-Exclusion, PIE] [#combinatorics](https://publish.obsidian.md/discretecs/Combinatorics/Principle+of+Inclusion+and+Exclusion#combinatorics) Definition ---------- Definition The Principle of Inclusion and Exclusion states that if an event A can occur in m ways, and an event B can occur in n ways, and there are p ways for both A and B to happen at the same time, then the number of ways for the event "A or B" to happen is m+n−p. Notes: * Informally the Principle of Inclusion and Exclusion says that the number of ways for either A or B to happen equals the number of ways A can happen, plus the number of ways B can happen, **minus the number of ways A and B can happen**. * The subtraction is due to the fact that outcomes where A and B happen simultaneously are counted twice if we just add the outcomes of A to the outcomes of B. * The Principle of Inclusion and Exclusion can be phrased in terms of [sets](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set) : If A and B are any two sets, then |A∪B|\=|A|+|B|−|A∩B|. (The vertical bars indicate [cardinality](https://publish.obsidian.md/discretecs/Sets+and+Functions/Cardinality) ; the symbol ∪ is the [union](https://publish.obsidian.md/discretecs/Sets+and+Functions/Union) ; the symbol ∩ is [intersection](https://publish.obsidian.md/discretecs/Sets+and+Functions/Intersection) .) * The [Additive principle](https://publish.obsidian.md/discretecs/Combinatorics/Additive+principle) is really just a special case of the Principle of Inclusion and Exclusion, where the two events are disjoint; in this case you'd just be subtracting off zero, since the [intersection](https://publish.obsidian.md/discretecs/Sets+and+Functions/Intersection) of disjoint sets is empty. * The Principle of Inclusion and Exclusion can be extended to three or more events, but the formula gets progressively more complicated. [Go here to learn more](https://artofproblemsolving.com/wiki/index.php/Principle_of_Inclusion-Exclusion#Three_Set_Examples) . Example ------- * **How many [natural numbers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Natural+numbers) between 1 and 1000 (including 1 and 1000) are either even, or are multiples of 3?** First, note that the [Additive principle](https://publish.obsidian.md/discretecs/Combinatorics/Additive+principle) doesn't apply directly here since being even and being a multiple of 3 are not [disjoint](https://publish.obsidian.md/discretecs/Sets+and+Functions/Intersection) events: It's possible for a number to be both even and a multiple of 3, for example the numbers 6 or 30. So the answer to the question is: > (The count of even numbers from 1 to 1000) + (The count of multiples of 3 from 1 to 1000) - (The count of numbers that are both even and multiples of 3 from 1 to 1000) Exactly half of the numbers from 1 to 1000 are even, so there are 500 of those. The number of multiples of 3 in this range is ⌊1000/3⌋\=333 (divide 1000 by 3 and round down; or just do a direct count using a Python script). In order to be both even and a multiple of 3, a number has to be a multiple of 6; there are ⌊1000/6⌋\=166 of those in this range. Therefore there are 500+333−166\=667 [natural numbers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Natural+numbers) from 1 to 1000 that are either even or multiples of 3. The following Python script will verify that count: len([n for n in range(1,1001) if n % 2 == 0 or n % 3 == 0]) Resources --------- [Screencast 4.1: The \[\[Additive Principle\]\] and Principle of Inclusion-Exclusion](https://vimeo.com/618309204) from [Robert Talbert](https://vimeo.com/user132700952) on [Vimeo](https://vimeo.com/) . Other resources: * Tutorial: [Principle of Inclusion-Exclusion](https://artofproblemsolving.com/wiki/index.php/Principle_of_Inclusion-Exclusion) Principle of Inclusion and Exclusion Not found This page does not exist Interactive graph On this page Definition Example Resources [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Binary digits and bitstrings - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic [Addition in binary](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Addition+in+binary) [Base 2 representation](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+2+representation) [Base 8 representation](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+8+representation) [Base 10 representation](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+10+representation) [Base 16 representation](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+16+representation) [Base conversion algorithm](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+conversion+algorithm) [Binary digits and bitstrings](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Binary+digits+and+bitstrings) [Converting to base 10](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Converting+to+base+10) [Division in binary](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Division+in+binary) [Integer congruence](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integer+congruence) [Integer division](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integer+division) [Integers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integers) [Multiplication in binary](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Multiplication+in+binary) [Natural numbers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Natural+numbers) [Subtraction in binary](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Subtraction+in+binary) [The division algorithm](https://publish.obsidian.md/discretecs/Computer+Arithmetic/The+division+algorithm) [The modulus operator](https://publish.obsidian.md/discretecs/Computer+Arithmetic/The+modulus+operator) [Two's complement](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Two's+complement) Logic Sets and Functions Basic math concepts Combinatorics Directed Graphs and Relations Graphs Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Binary digits and bitstrings ============================ aliases: [binary digits, bits, bitstring, bitstrings] [#computer-arithmetic](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Binary+digits+and+bitstrings#computer-arithmetic) Definition ---------- Definition A **binary digit** or "**bit**" is either the number 0 or the number 1. A **bitstring** is a sequence of one or more bits. Notes: * When a positive [integer](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integers) is written in [binary representation](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+2+representation) , it has the form of a bitstring where each bit represents a power of 2. * The length of the bitstring is the number of bits it has in all. * The weight of the bitstring is the number of 1 bits it has. * The number of bit strings of length n and weight k is given by the [binomial coefficient](https://publish.obsidian.md/discretecs/Combinatorics/Binomial+coefficient) \\displaystyle{\\binom{n}{k}}. Examples -------- The [base 2 representation](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+2+representation) of the positive ([base 10](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+10+representation) ) [integer](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integers) 214, is 11010110. This is a bitstring of length 8 and [weight](https://publish.obsidian.md/discretecs/Combinatorics/Weight+of+a+bitstring) 5. Binary digits and bitstrings Not found This page does not exist Interactive graph On this page Definition Examples [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Subset - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions [Bijective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Bijective) [Cardinality](https://publish.obsidian.md/discretecs/Sets+and+Functions/Cardinality) [Cartesian product](https://publish.obsidian.md/discretecs/Sets+and+Functions/Cartesian+product) [Codomain](https://publish.obsidian.md/discretecs/Sets+and+Functions/Codomain) [Complement](https://publish.obsidian.md/discretecs/Sets+and+Functions/Complement) [Domain](https://publish.obsidian.md/discretecs/Sets+and+Functions/Domain) [Empty set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Empty+set) [Function](https://publish.obsidian.md/discretecs/Sets+and+Functions/Function) [Injective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Injective) [Intersection](https://publish.obsidian.md/discretecs/Sets+and+Functions/Intersection) [Power set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Power+set) [Range](https://publish.obsidian.md/discretecs/Sets+and+Functions/Range) [Roster notation](https://publish.obsidian.md/discretecs/Sets+and+Functions/Roster+notation) [Set difference](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set+difference) [Set-builder notation](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set-builder+notation) [Set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set) [Subset](https://publish.obsidian.md/discretecs/Sets+and+Functions/Subset) [Surjective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Surjective) [Symmetric difference](https://publish.obsidian.md/discretecs/Sets+and+Functions/Symmetric+difference) [Union](https://publish.obsidian.md/discretecs/Sets+and+Functions/Union) [Universal set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Universal+set) Basic math concepts Combinatorics Directed Graphs and Relations Graphs Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Subset ====== aliases: [subset, subsets] [#sets-functions](https://publish.obsidian.md/discretecs/Sets+and+Functions/Subset#sets-functions) Definition ---------- Definition A set B is a **subset** of another set A, if every element of B is also an element of A. If B is a subset of A, this relationship is denoted B \\subseteq A. If B \\subseteq A but B \\neq A, we say that B is a **proper subset** of A and write B \\subset A. A visual representation of the relationship B \\subseteq A is this Venn diagram: ![Pasted image 20230718094622.png](https://publish-01.obsidian.md/access/64d815ddc8215841f63db915c7923004/Assets/Images/Pasted%20image%2020230718094622.png) (This is actually showing that B is a _proper_ subset of A since the two are not shown as being equal.) In terms of logical propositions, B is a subset of A if the following [conditional statement](https://publish.obsidian.md/discretecs/Logic/Conditional+statements) is true: > For every x, if x \\in B then x \\in A. Examples and Non-Examples ------------------------- Examples: * The [natural numbers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Natural+numbers) are a (proper) subset of the [integers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integers) . (That is, \\mathbb{N} \\subseteq \\mathbb{Z}.) * The set \\{0,1,2,3\\} is a (proper) subset of \\mathbb{N}. * The set \\{0,2,4\\} is a (proper) subset of the set \\{0,2,4,6,8\\}. The empty is a subset of every set The [empty set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Empty+set) \\emptyset is a subset of every set. To see this, use the [conditional statement](https://publish.obsidian.md/discretecs/Logic/Conditional+statements) that defines the subset relationship: _For all x, if x \\in B then x \\in A._ Let B be the [empty set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Empty+set) and let A be any set at all. Then the [hypothesis](https://publish.obsidian.md/discretecs/Logic/Conditional+statements) of this statement, x \\in \\emptyset, is always false because nothing is "in" the [empty set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Empty+set) . Therefore the [conditional statement](https://publish.obsidian.md/discretecs/Logic/Conditional+statements) is always true. Non-examples: * The set of [integers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integers) is not a subset of the set of [natural numbers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Natural+numbers) , because there are elements of the integers that don't belong to the [natural numbers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Natural+numbers) , such as \-3. * The set \\{1,2,3\\} is not a subset of \\{2,3,4\\} because although these sets have elements in common (i.e. the [intersection](https://publish.obsidian.md/discretecs/Sets+and+Functions/Intersection) is not the [empty set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Empty+set) ), the number 1 is not an element of the set \\{2,3,4\\}. Resources --------- Practice -------- Subset Not found This page does not exist Interactive graph On this page Definition Examples and Non-Examples Resources Practice [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Complete graph - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions Basic math concepts Combinatorics Directed Graphs and Relations Graphs [Adjacent](https://publish.obsidian.md/discretecs/Graphs/Adjacent) [Bipartite graph](https://publish.obsidian.md/discretecs/Graphs/Bipartite+graph) [Brooks' Theorem](https://publish.obsidian.md/discretecs/Graphs/Brooks'+Theorem) [Chromatic index](https://publish.obsidian.md/discretecs/Graphs/Chromatic+index) [Chromatic number](https://publish.obsidian.md/discretecs/Graphs/Chromatic+number) [Clique number](https://publish.obsidian.md/discretecs/Graphs/Clique+number) [Complete graph](https://publish.obsidian.md/discretecs/Graphs/Complete+graph) [Connected graph](https://publish.obsidian.md/discretecs/Graphs/Connected+graph) [Cycle graph](https://publish.obsidian.md/discretecs/Graphs/Cycle+graph) [Degree](https://publish.obsidian.md/discretecs/Graphs/Degree) [Dijkstra's Algorithm](https://publish.obsidian.md/discretecs/Graphs/Dijkstra's+Algorithm) [Dirac's Theorem](https://publish.obsidian.md/discretecs/Graphs/Dirac's+Theorem) [Distance](https://publish.obsidian.md/discretecs/Graphs/Distance) [Eccentricity](https://publish.obsidian.md/discretecs/Graphs/Eccentricity) [Edge coloring](https://publish.obsidian.md/discretecs/Graphs/Edge+coloring) [Eulerian trail and circuit](https://publish.obsidian.md/discretecs/Graphs/Eulerian+trail+and+circuit) [Four Color Theorem](https://publish.obsidian.md/discretecs/Graphs/Four+Color+Theorem) [Graph](https://publish.obsidian.md/discretecs/Graphs/Graph) [Greedy coloring algorithm](https://publish.obsidian.md/discretecs/Graphs/Greedy+coloring+algorithm) [Hamiltonian path and circuit](https://publish.obsidian.md/discretecs/Graphs/Hamiltonian+path+and+circuit) [Handshake Lemma](https://publish.obsidian.md/discretecs/Graphs/Handshake+Lemma) [Isomorphism invariant](https://publish.obsidian.md/discretecs/Graphs/Isomorphism+invariant) [Isomorphism](https://publish.obsidian.md/discretecs/Graphs/Isomorphism) [Kuratowski's Theorem](https://publish.obsidian.md/discretecs/Graphs/Kuratowski's+Theorem) [Multigraph](https://publish.obsidian.md/discretecs/Graphs/Multigraph) [Ore's Theorem](https://publish.obsidian.md/discretecs/Graphs/Ore's+Theorem) [Path graph](https://publish.obsidian.md/discretecs/Graphs/Path+graph) [Paths](https://publish.obsidian.md/discretecs/Graphs/Paths) [Planar graph](https://publish.obsidian.md/discretecs/Graphs/Planar+graph) [Representations of graphs](https://publish.obsidian.md/discretecs/Graphs/Representations+of+graphs) [Spanning tree](https://publish.obsidian.md/discretecs/Graphs/Spanning+tree) [Subdivision](https://publish.obsidian.md/discretecs/Graphs/Subdivision) [Subgraph](https://publish.obsidian.md/discretecs/Graphs/Subgraph) [Vertex coloring](https://publish.obsidian.md/discretecs/Graphs/Vertex+coloring) [Vizing's Theorem](https://publish.obsidian.md/discretecs/Graphs/Vizing's+Theorem) [Weighted graph](https://publish.obsidian.md/discretecs/Graphs/Weighted+graph) Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Complete graph ============== aliases: - complete graph tags: - graphs created: 2024-07-05 updated: * * * Definition ---------- Definition The **complete graph on n vertices** is denoted K\_n and consists of: * The [vertex](https://publish.obsidian.md/discretecs/Graphs/Graph) set is V = \\{1,2,\\dots, n\\} * The [edge](https://publish.obsidian.md/discretecs/Graphs/Graph) set is the set of all two-element [subsets](https://publish.obsidian.md/discretecs/Sets+and+Functions/Subset) of V. In other words, K\_n is the [graph](https://publish.obsidian.md/discretecs/Graphs/Graph) with n vertices in which there is an edge between every possible pair of distinct vertices. Notes: * The number of vertices in K\_n is n, and the number of edges is \\binom{n}{2} where the notation here is the [binomial coefficient](https://publish.obsidian.md/discretecs/Combinatorics/Binomial+coefficient) . It follows from the [closed formula](https://publish.obsidian.md/discretecs/Recursion/Closed+formula) for the [binomial coefficient](https://publish.obsidian.md/discretecs/Combinatorics/Binomial+coefficient) that there are \\dfrac{n(n-1)}{2} edges in K\_n. Examples -------- Here are visualizations of K\_1 through K\_6: ![Pasted image 20240705121105.png](https://publish-01.obsidian.md/access/64d815ddc8215841f63db915c7923004/Assets/Images/Pasted%20image%2020240705121105.png) Complete graph Not found This page does not exist Interactive graph On this page Definition Examples [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Graph - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions Basic math concepts Combinatorics Directed Graphs and Relations Graphs [Adjacent](https://publish.obsidian.md/discretecs/Graphs/Adjacent) [Bipartite graph](https://publish.obsidian.md/discretecs/Graphs/Bipartite+graph) [Brooks' Theorem](https://publish.obsidian.md/discretecs/Graphs/Brooks'+Theorem) [Chromatic index](https://publish.obsidian.md/discretecs/Graphs/Chromatic+index) [Chromatic number](https://publish.obsidian.md/discretecs/Graphs/Chromatic+number) [Clique number](https://publish.obsidian.md/discretecs/Graphs/Clique+number) [Complete graph](https://publish.obsidian.md/discretecs/Graphs/Complete+graph) [Connected graph](https://publish.obsidian.md/discretecs/Graphs/Connected+graph) [Cycle graph](https://publish.obsidian.md/discretecs/Graphs/Cycle+graph) [Degree](https://publish.obsidian.md/discretecs/Graphs/Degree) [Dijkstra's Algorithm](https://publish.obsidian.md/discretecs/Graphs/Dijkstra's+Algorithm) [Dirac's Theorem](https://publish.obsidian.md/discretecs/Graphs/Dirac's+Theorem) [Distance](https://publish.obsidian.md/discretecs/Graphs/Distance) [Eccentricity](https://publish.obsidian.md/discretecs/Graphs/Eccentricity) [Edge coloring](https://publish.obsidian.md/discretecs/Graphs/Edge+coloring) [Eulerian trail and circuit](https://publish.obsidian.md/discretecs/Graphs/Eulerian+trail+and+circuit) [Four Color Theorem](https://publish.obsidian.md/discretecs/Graphs/Four+Color+Theorem) [Graph](https://publish.obsidian.md/discretecs/Graphs/Graph) [Greedy coloring algorithm](https://publish.obsidian.md/discretecs/Graphs/Greedy+coloring+algorithm) [Hamiltonian path and circuit](https://publish.obsidian.md/discretecs/Graphs/Hamiltonian+path+and+circuit) [Handshake Lemma](https://publish.obsidian.md/discretecs/Graphs/Handshake+Lemma) [Isomorphism invariant](https://publish.obsidian.md/discretecs/Graphs/Isomorphism+invariant) [Isomorphism](https://publish.obsidian.md/discretecs/Graphs/Isomorphism) [Kuratowski's Theorem](https://publish.obsidian.md/discretecs/Graphs/Kuratowski's+Theorem) [Multigraph](https://publish.obsidian.md/discretecs/Graphs/Multigraph) [Ore's Theorem](https://publish.obsidian.md/discretecs/Graphs/Ore's+Theorem) [Path graph](https://publish.obsidian.md/discretecs/Graphs/Path+graph) [Paths](https://publish.obsidian.md/discretecs/Graphs/Paths) [Planar graph](https://publish.obsidian.md/discretecs/Graphs/Planar+graph) [Representations of graphs](https://publish.obsidian.md/discretecs/Graphs/Representations+of+graphs) [Spanning tree](https://publish.obsidian.md/discretecs/Graphs/Spanning+tree) [Subdivision](https://publish.obsidian.md/discretecs/Graphs/Subdivision) [Subgraph](https://publish.obsidian.md/discretecs/Graphs/Subgraph) [Vertex coloring](https://publish.obsidian.md/discretecs/Graphs/Vertex+coloring) [Vizing's Theorem](https://publish.obsidian.md/discretecs/Graphs/Vizing's+Theorem) [Weighted graph](https://publish.obsidian.md/discretecs/Graphs/Weighted+graph) Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Graph ===== aliases: - graph - graphs - edge - edges - vertex - vertices - node - nodes - Graphs - Edge - Vertex - Node - Edges - Vertices - Nodes - endpoint tags: - graphs created: 2024-07-01 updated: 2024-08-07 * * * Definition ---------- Definition A **graph** is a pair of [sets](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set) : 1. A nonempty [set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set) called the **vertex set**, whose elements we call **vertices** or **nodes**. 2. A (possibly empty) set called the **edge set**, whose elements we call **edges**, where each edge is a [subset](https://publish.obsidian.md/discretecs/Sets+and+Functions/Subset) of the vertex set that contains exactly two elements, called the **endpoints** of the edge. If two vertices are endpoints of an edge, we say that they are **adjacent** vertices. We often use G = (V,E) to denote a graph whose name is G, whose vertex set is V, and whose edge set is E. Notes: * The definition of a graph is rather abstract because we want room to represent graphs in different ways: both visually, and as pure data structures in several different forms. See [Representations of graphs](https://publish.obsidian.md/discretecs/Graphs/Representations+of+graphs) for more. * Note that the edge set of a graph is a set, whose [elements](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set) are also sets -- namely, two-element [subsets](https://publish.obsidian.md/discretecs/Sets+and+Functions/Subset) of the vertices. The edge \\{u,v\\} and the edge \\{v,u\\} are the same, since they are equal [sets](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set) . Examples -------- * Consider the graph G = (\\{a,b,c,d\\}, \\{\\{a,c\\}, \\{a,d\\}, \\{d,c\\}, \\{a,b\\}\\}). Note that this is a pair of sets, enclosed in parentheses. The first element of the pair is the set \\{a,b,c,d\\}, and these are the vertices. The second element is \\{\\{a,c\\}, \\{a,d\\}, \\{d,c\\}, \\{a,b\\}\\} and these are the edges. There are four edges: One with endpoints a and c; one with endpoints a and d; a third with endpoints d and c; and a fourth with endpoints a and b. Note that because the edges are given as sets, not as ordered pairs, each edge is the same no matter what order we list the endpoints in. A visualization of the graph G is: ![Pasted image 20240701115858.png](https://publish-01.obsidian.md/access/64d815ddc8215841f63db915c7923004/Assets/Images/Pasted%20image%2020240701115858.png) * When visualized in this way -- with each vertex shown as a point and each edge shown as a line segment between its endpoints -- graphs are representations of _networks_. * Consider the following visualization of a graph: ![Pasted image 20240701120930.png](https://publish-01.obsidian.md/access/64d815ddc8215841f63db915c7923004/Assets/Images/Pasted%20image%2020240701120930.png) Note that there are five vertices and 10 edges, one edge between every pair of different vertices. In notation, this graph is G = (V,E) where V = \\{1,2,3,4,5\\} (the vertices) and E = \\{\\{1,2\\}, \\{1,3\\}, \\{1,4\\}, \\{1,5\\}. \\{2,3\\}, \\{2,4\\}, \\{2,5\\}, \\{3,4\\}, \\{3,5\\}, \\{4,5\\}\\}. (This graph is called the [Complete graph](https://publish.obsidian.md/discretecs/Graphs/Complete+graph) on five vertices.) * Not every vertex in a graph needs to be the endpoint of an edge. Consider G = (\\{1,2,3\\}, \\{1,2\\}) for example which has three vertices but only one edge, whose endpoints are 1 and 2. ![Pasted image 20240701121143.png](https://publish-01.obsidian.md/access/64d815ddc8215841f63db915c7923004/Assets/Images/Pasted%20image%2020240701121143.png) * While every graph must have at least one vertex according to the definition, the edge set can be empty. For example G= (\\{1,2,3\\}, \\emptyset) has three vertices but no edges. Its visualization would just be three dots with no line segments. * There can only be at most one edge between any two distinct vertices in a graph; two different vertices cannot be connected by two or more edges. (Graph-like structures that allow for multiple edges between the same two vertices are called [multigraphs](https://publish.obsidian.md/discretecs/multigraphs) .) This is because in the definition, the edges are a set of two-element sets, and the same two-element set cannot happen twice. * An edge cannot connect a vertex to itself, forming a loop. This because each edge is actually a two-element [subset](https://publish.obsidian.md/discretecs/Sets+and+Functions/Subset) of the vertices, and the same vertex cannot appear twice. Resources --------- Graph Not found This page does not exist Interactive graph On this page Definition Examples Resources [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Mathematical induction - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions Basic math concepts Combinatorics Directed Graphs and Relations Graphs Proof [Combinatorial proof](https://publish.obsidian.md/discretecs/Proof/Combinatorial+proof) [Direct proof](https://publish.obsidian.md/discretecs/Proof/Direct+proof) [Indirect proof](https://publish.obsidian.md/discretecs/Proof/Indirect+proof) [Mathematical induction](https://publish.obsidian.md/discretecs/Proof/Mathematical+induction) [Proof by contraposition](https://publish.obsidian.md/discretecs/Proof/Proof+by+contraposition) [Proof](https://publish.obsidian.md/discretecs/Proof/Proof) [Strong induction](https://publish.obsidian.md/discretecs/Proof/Strong+induction) [Structural induction](https://publish.obsidian.md/discretecs/Proof/Structural+induction) Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Mathematical induction ====================== aliases: [induction, mathematical induction, Induction, inductive hypothesis] [#recursion-induction](https://publish.obsidian.md/discretecs/Proof/Mathematical+induction#recursion-induction) Definition ---------- Definition **Mathematical induction** is a [Proof](https://publish.obsidian.md/discretecs/Proof/Proof) technique used when proving that a [predicate](https://publish.obsidian.md/discretecs/Logic/Predicate) P(n) (whose [domain](https://publish.obsidian.md/discretecs/Sets+and+Functions/Domain) is the set of all [natural numbers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Natural+numbers) ) is true for all [natural numbers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Natural+numbers) or for some specified [subset](https://publish.obsidian.md/discretecs/Sets+and+Functions/Subset) . It is especially applicable if the [predicate](https://publish.obsidian.md/discretecs/Logic/Predicate) involves [recursion](https://publish.obsidian.md/discretecs/Recursion/Recursion) . Induction proofs follow a three-step **framework**: 1. (_Base case_) Establish, by direct computation or demonstration, that P(n) is true for the smallest value of n for which it is claimed to be true. That is, establish that the base case leads to a true statement. 2. (_Inductive hypothesis_) Assume that P(k) is true for some random, undisclosed value of k. 3. (_Inductive step_) Prove that P(k+1) is true, using a combination of the inductive hypothesis, the [recursion](https://publish.obsidian.md/discretecs/Recursion/Recursion) involved in the predicate, previously-proven results, and so on. **Notes**: * This general framework is sometimes known as _weak induction_. Other forms of induction are possible, including [strong induction](https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-fall-2010/resources/lecture-3-strong-induction/) , [structural induction](https://www.cs.umd.edu/class/summer2016/cmsc250/files/slides/structuralInduction.pdf) , and [transfinite induction](https://mathworld.wolfram.com/TransfiniteInduction.html) . * The base case is often n = 0 but not always. Check the statement being proven for the smallest case. Examples -------- Consider the Python function def f(n): if n == 0: return 3 else: return 2*f(n-1) By playing with examples, we see this function returns the [sequence](https://publish.obsidian.md/discretecs/Recursion/Sequence) 3, 6, 12, 24, 48, \\dots. So we might conjecture that **For all [natural numbers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Natural+numbers) n, f(n) = 3 \\cdot 2^n.** Mathematical induction Not found This page does not exist Interactive graph On this page Definition Examples Resources [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Intersection - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions [Bijective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Bijective) [Cardinality](https://publish.obsidian.md/discretecs/Sets+and+Functions/Cardinality) [Cartesian product](https://publish.obsidian.md/discretecs/Sets+and+Functions/Cartesian+product) [Codomain](https://publish.obsidian.md/discretecs/Sets+and+Functions/Codomain) [Complement](https://publish.obsidian.md/discretecs/Sets+and+Functions/Complement) [Domain](https://publish.obsidian.md/discretecs/Sets+and+Functions/Domain) [Empty set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Empty+set) [Function](https://publish.obsidian.md/discretecs/Sets+and+Functions/Function) [Injective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Injective) [Intersection](https://publish.obsidian.md/discretecs/Sets+and+Functions/Intersection) [Power set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Power+set) [Range](https://publish.obsidian.md/discretecs/Sets+and+Functions/Range) [Roster notation](https://publish.obsidian.md/discretecs/Sets+and+Functions/Roster+notation) [Set difference](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set+difference) [Set-builder notation](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set-builder+notation) [Set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set) [Subset](https://publish.obsidian.md/discretecs/Sets+and+Functions/Subset) [Surjective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Surjective) [Symmetric difference](https://publish.obsidian.md/discretecs/Sets+and+Functions/Symmetric+difference) [Union](https://publish.obsidian.md/discretecs/Sets+and+Functions/Union) [Universal set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Universal+set) Basic math concepts Combinatorics Directed Graphs and Relations Graphs Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Intersection ============ aliases: [intersection, disjoint] [#sets-functions](https://publish.obsidian.md/discretecs/Sets+and+Functions/Intersection#sets-functions) Definition ---------- Definition The **intersection** of two [sets](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set) A and B is the set consisting of [elements](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set) that are in both A and B. The notation for the intersection of A and B is A \\cap B. In [set-builder notation](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set-builder+notation) , A \\cap B = \\{x \\, : \\, x \\in A \\ \\text{and} \\ x \\in B\\}. A visual representation of A \\cap B is this Venn diagram: ![intersection.png](https://publish-01.obsidian.md/access/64d815ddc8215841f63db915c7923004/Assets/Images/intersection.png) **Notes:** * If A and B have no elements in common, then A \\cap B = \\emptyset (the [empty set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Empty+set) ) and we say A and B are **disjoint**. Examples -------- * If A = \\{1,2,3,4\\} and B = \\{1,3,5,7,9\\} then A \\cap B = \\{3\\}. * If A = \\{n \\in \\mathbb{N} \\, : \\, n \\ \\text{is a multiple of 3}\\} and B = \\{n \\in \\mathbb{N} \\, : \\, n \\ \\text{is a multiple of 2}\\} then A \\cup B = \\{0, 6, 12, 18, 24, \\dots\\} -- in other words all the [natural numbers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Natural+numbers) that are multiples of both 3 and 2 (which makes them multiples of 6). Resources --------- [Screencast 3.6: Set operations](https://vimeo.com/606600971) from [Robert Talbert](https://vimeo.com/user132700952) on [Vimeo](https://vimeo.com/) . Other resources: * Video: [Sets and set operations](https://www.youtube.com/watch?v=QiOfsWm3peE&list=PL2419488168AE7001&index=64&pp=iAQB) * Tutorial: [Intersection of sets](https://www.cuemath.com/algebra/intersection-of-sets/) Intersection Not found This page does not exist Interactive graph On this page Definition Examples Resources [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Characteristic root method - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions Basic math concepts Combinatorics Directed Graphs and Relations Graphs Proof Recursion [Arithmetic sequence](https://publish.obsidian.md/discretecs/Recursion/Arithmetic+sequence) [Characteristic root method](https://publish.obsidian.md/discretecs/Recursion/Characteristic+root+method) [Closed formula](https://publish.obsidian.md/discretecs/Recursion/Closed+formula) [Fibonacci sequence](https://publish.obsidian.md/discretecs/Recursion/Fibonacci+sequence) [Geometric sequence](https://publish.obsidian.md/discretecs/Recursion/Geometric+sequence) [Homogeneous recurrence relation](https://publish.obsidian.md/discretecs/Recursion/Homogeneous+recurrence+relation) [Linear recurrence relation](https://publish.obsidian.md/discretecs/Recursion/Linear+recurrence+relation) [Recurrence relation](https://publish.obsidian.md/discretecs/Recursion/Recurrence+relation) [Recursion](https://publish.obsidian.md/discretecs/Recursion/Recursion) [Sequence](https://publish.obsidian.md/discretecs/Recursion/Sequence) [Solution to a recurrence relation](https://publish.obsidian.md/discretecs/Recursion/Solution+to+a+recurrence+relation) Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Characteristic root method ========================== aliases: [characteristic root method, characteristic root technique, characteristic equation, characteristic root] [#recursion-induction](https://publish.obsidian.md/discretecs/Recursion/Characteristic+root+method#recursion-induction) Definition ---------- Definition The **characteristic root method** is a technique for deriving a [solution](https://publish.obsidian.md/discretecs/Recursion/Solution+to+a+recurrence+relation) to a [linear](https://publish.obsidian.md/discretecs/Recursion/Linear+recurrence+relation) [homogeneous](https://publish.obsidian.md/discretecs/Recursion/Homogeneous+recurrence+relation) recurrence relation. The general method is as follows: 1. Put the recurrence relation in "standard form" with the new term on the left side of the equals sign and all other objects on the right side. 2. Replace a\_{n} with x^n, a\_{n-1} with x^{n-1}, and so on until all sequence terms are replaced with powers of x. 3. Divide both sides by the smallest power of x to arrive at a polynomial equation. (This equation is known as the _characteristic equation_ for the recurrence relation.) 4. Solve the polynomial equation using basic algebra techniques. The resulting value(s) of x are called the _characteristic roots_ of the recurrence relation. 5. If x\_1, x\_2, \\dots, x\_k are the characteristic roots, the general form of the [solution](https://publish.obsidian.md/discretecs/Recursion/Solution+to+a+recurrence+relation) to the recurrence relation is a(n) = \\alpha\_1 x\_1^n + \\alpha\_2 x\_2^n + \\cdots + \\alpha\_k x\_k^n where \\alpha\_1, \\alpha\_2, \\dots, \\alpha\_k are unknown constants. 6. Use the initial conditions of the recurrence relation to find the values of \\alpha\_1, \\alpha\_2, \\dots, \\alpha\_k. This involves solving a [system of linear equations](https://www.mathsisfun.com/algebra/systems-linear-equations.html) . Notes: * This method requires that the recurrence relation be [linear](https://publish.obsidian.md/discretecs/Recursion/Linear+recurrence+relation) and [homogeneous](https://publish.obsidian.md/discretecs/Recursion/Homogeneous+recurrence+relation) otherwise the steps do not all apply. * This description of the method only deals with the simple case where none the characteristic roots are zero, and none are repeated. If one of those is the case, the general form of the solution in step 5 above is different. Example ------- Consider the second-[order](https://publish.obsidian.md/discretecs/Recursion/Recurrence+relation) [linear](https://publish.obsidian.md/discretecs/Recursion/Linear+recurrence+relation) [homogeneous](https://publish.obsidian.md/discretecs/Recursion/Homogeneous+recurrence+relation) recurrence relation: a\_0 = 1, a\_1 = 2; and for n > 1, a\_n = 5a\_{n-1} - 6a\_{n-2}. This recurrence relation is already in "standard form" with the highest term isolated on the left. Replace a\_n with x^n and similarly for the other terms to get: x^n = 5x^{n-1} - 6x^{n-2} Divide off by the smallest power of x, which in this case is x^{n-2} to get: x^2 = 5x - 6This is the same as x^2 - 5x + 6 = 0. Factor this to get: (x-3)(x-2) = 0Therefore the characteristic roots are x = 3 and x = 2. Set up the solution to the recurrence relation: a(n) = \\alpha\_1 3^n + \\alpha\_2 2^nNow we will use the initial conditions to find the two constants. Those conditions were a\_0 = 1 and a\_1 = 2. Plugging in n = 0 gives a(0) on the left which equals 1, and it gives \\alpha\_1 3^0 + \\alpha\_2 2^0 on the right which equals \\alpha\_1 + \\alpha\_2. Therefore \\alpha\_1 + \\alpha\_2 = 1. Similarly, plugging in 1 for n gives the equation 3\\alpha\_1 + 2\\alpha\_2 = 2. Solving this system of equations (for example through [substitution](https://www.varsitytutors.com/hotmath/hotmath_help/topics/solving-systems-of-linear-equations-using-substitution) or [elimination](https://www.mathplanet.com/education/algebra-1/systems-of-linear-equations-and-inequalities/the-elimination-method-for-solving-linear-systems) ) gives \\alpha\_1 = 0 and \\alpha\_2 = 1. Therefore the solution to the recurrence relation is: a(n) = 0 \\cdot 3^n + 1 \\cdot 2^n = 2^{n}We can reality check this by computing a few terms of the sequence using both the recurrence relation and this [closed formula](https://publish.obsidian.md/discretecs/Recursion/Closed+formula) . Running this Python code will give the first 10 terms of the sequence: def a(n): if n == 0: return 1 elif n == 1: return 2 else: return 5*a(n-1) - 6*a(n-2) [a(n) for n in range(10)] This gives `[1, 2, 4, 8, 16, 32, 64, 128, 256, 512]`. The following code will find the first ten terms using the closed formula: Characteristic root method Not found This page does not exist Interactive graph On this page Definition Example Resources [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Addition in binary - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic [Addition in binary](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Addition+in+binary) [Base 2 representation](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+2+representation) [Base 8 representation](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+8+representation) [Base 10 representation](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+10+representation) [Base 16 representation](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+16+representation) [Base conversion algorithm](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+conversion+algorithm) [Binary digits and bitstrings](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Binary+digits+and+bitstrings) [Converting to base 10](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Converting+to+base+10) [Division in binary](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Division+in+binary) [Integer congruence](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integer+congruence) [Integer division](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integer+division) [Integers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integers) [Multiplication in binary](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Multiplication+in+binary) [Natural numbers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Natural+numbers) [Subtraction in binary](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Subtraction+in+binary) [The division algorithm](https://publish.obsidian.md/discretecs/Computer+Arithmetic/The+division+algorithm) [The modulus operator](https://publish.obsidian.md/discretecs/Computer+Arithmetic/The+modulus+operator) [Two's complement](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Two's+complement) Logic Sets and Functions Basic math concepts Combinatorics Directed Graphs and Relations Graphs Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Addition in binary ================== aliases: [binary addition, base 2 addition, addition in binary] [#computer-arithmetic](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Addition+in+binary#computer-arithmetic) Process ------- Process First note that if we are just adding two [bits](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Binary+digits+and+bitstrings) together, there are four possible ways to do this: `0+0`, `1+0`, `0+1`, and `1+1`. The sum `0+0` equals `0`. The sums `0+1` and `1+0` both equal `1`. The sum `1+1` equals `10` (that is, 2, written in [base 2](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+2+representation) ). Now if we want to add two positive [integers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integers) in [base 2](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+2+representation) without [converting to base 10](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Converting+to+base+10) first: 1. Add the two [bits](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Binary+digits+and+bitstrings) in the "ones" place (that is, the 2^0 digit). If the two [bits](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Binary+digits+and+bitstrings) are anything other than `1` and `1`, record the resulting sum and move on to the "twos" place (that is, the 2^1 digit). If the two [bits](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Binary+digits+and+bitstrings) are both `1`, the sum in the 2^0 place is `0`, and carry a `1` over to the 2^1 digit. 2. Add the two [bits](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Binary+digits+and+bitstrings) in the "twos" place (that is, the 2^1 digit) along with the `1` that was carried from the previous step, if applicable. The result will be one of the following: `0`, `1`, `10`, or `11`. If it's `0` or `1`, record this in the 2^1 and move on to the "fours" place (that is, the 2^2 digit). Otherwise record the lowest bit (either `0` or `1` ) and carry the `1` over to the the 2^2 digit. 3. Repeat this process of adding either 2 or 3 [bits](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Binary+digits+and+bitstrings) (depending on whether a `1` was carried or not) until you reach the leftmost end of the numbers you are adding. Examples -------- Add the [base 2](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+2+representation) integers 1011 and 1010. 1. Add the ones digits: `1+0 = 1`. Record the `1` as the result. There's no carried `1` here so move on. 2. Add the twos digits: `1+1 = 10`. Record `0` as the result and carry the `1`. 3. Add the fours digits and the carried `1`: `1 + 0 + 0 = 1`. There's no carried `1` so move on. 4. Add the eights digits: `1 + 1 = 10`. Record the `0` and carry the 1. 5. There's no sixteens digits to add, so the carried `1` is the leftmost bit of the result. In other words, 1011 + 1010 = 10101. Notice this checks out because 1011\_2 = 11\_{10} and 1010 = 10\_{10}, and in [base 10](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+10+representation) we know that 11 + 10 = 21. And converting the result 10101\_2 back to [base 10](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+10+representation) gives 21 as it should. Resources --------- Other resources: * [Binary arithmetic calculator](https://www.calculator.net/binary-calculator.html) * [Khan Academy video on binary addition](https://www.youtube.com/watch?v=RgklPQ8rbkg&pp=ygUPYmluYXJ5IGFkZGl0aW9u) * [Video on addition (and subtraction) of binary integers](https://www.youtube.com/watch?v=C5EkxfNEMjE) * [Yet another video on addition and subtraction of binary integers](https://www.youtube.com/watch?v=AE-27BSbkJ4) Practice -------- To practice this concept: Just make up pairs of random positive integers and convert to binary (or make up pairs of random [bitstrings](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Binary+digits+and+bitstrings) ). Then add them. Then check your work by either using the [binary arithmetic calculator](https://www.calculator.net/binary-calculator.html) or by converting the answer to [base 10](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+10+representation) and seeing if it matches what you should get if you added the original integers together in [base 10](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+10+representation) . Addition in binary Not found This page does not exist Interactive graph On this page Process Examples Resources Practice [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Sequence - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions Basic math concepts Combinatorics Directed Graphs and Relations Graphs Proof Recursion [Arithmetic sequence](https://publish.obsidian.md/discretecs/Recursion/Arithmetic+sequence) [Characteristic root method](https://publish.obsidian.md/discretecs/Recursion/Characteristic+root+method) [Closed formula](https://publish.obsidian.md/discretecs/Recursion/Closed+formula) [Fibonacci sequence](https://publish.obsidian.md/discretecs/Recursion/Fibonacci+sequence) [Geometric sequence](https://publish.obsidian.md/discretecs/Recursion/Geometric+sequence) [Homogeneous recurrence relation](https://publish.obsidian.md/discretecs/Recursion/Homogeneous+recurrence+relation) [Linear recurrence relation](https://publish.obsidian.md/discretecs/Recursion/Linear+recurrence+relation) [Recurrence relation](https://publish.obsidian.md/discretecs/Recursion/Recurrence+relation) [Recursion](https://publish.obsidian.md/discretecs/Recursion/Recursion) [Sequence](https://publish.obsidian.md/discretecs/Recursion/Sequence) [Solution to a recurrence relation](https://publish.obsidian.md/discretecs/Recursion/Solution+to+a+recurrence+relation) Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Sequence ======== aliases: [sequence, sequences] [#recursion-induction](https://publish.obsidian.md/discretecs/Recursion/Sequence#recursion-induction) Definition ---------- Definition A **sequence** is an ordered list of numbers. Notes: * The main difference between a sequence and a [set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set) is that sequences are ordered while sets aren't. * Sequences can also contain duplicate elements while [sets](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set) cannot. For example 1, 2, 1, 2, 1, 2, \\dots is an acceptable sequence. * Sequences typically have a _first_ element, followed by a second, third, fourth, etc. elements. Typically we [zero-index](https://stringfestanalytics.com/seen-zero-based-indexing/) a sequence, meaning we refer to the first item in the sequence as having "position 0". * If we use variables to represent terms in a sequence, we write a\_0, a\_1, a\_2, a\_3, \\dots (The letter a can be replaced with other letters; but notice the index of the term appears as a subscript.) * Sequences can be expressed as explicit lists, [recursively](https://publish.obsidian.md/discretecs/Recursion/Recursion) , or as [closed formulas](https://publish.obsidian.md/discretecs/Recursion/Closed+formula) . See below for examples. Examples and Non-Examples ------------------------- Here are some sequences: * 1, 1, 2, 3, 5, 8, 13, 21, 34, \\dots is the [Fibonacci sequence](https://publish.obsidian.md/discretecs/Recursion/Fibonacci+sequence) . * 1, 3, 6, 10, 15, 21, \\dots is the sequence of triangular numbers. * 3, 1, 4, 1, 5, 9, \\dots is the sequence of digits of \\pi. * The sequence 2, 3, 5, 9, 17, 33, \\dots can also be given as a [closed formula](https://publish.obsidian.md/discretecs/Recursion/Closed+formula) : f(n) = 1 + 2^n where n \\geq 0. * The sequence 2, 4, 10, 22, 52, 118, \\dots can be expressed [recursively](https://publish.obsidian.md/discretecs/Recursion/Recursion) as follows: a\_0 = 2, a\_1 = 4, and if n \\geq 2 then a\_n = 3a\_{n-2} + a\_{n-1}. This is an example of a [recurrence relation](https://publish.obsidian.md/discretecs/Recursion/Recurrence+relation) . Resources --------- Sequence Not found This page does not exist Interactive graph On this page Definition Examples and Non-Examples Resources [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Solution to a recurrence relation - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions Basic math concepts Combinatorics Directed Graphs and Relations Graphs Proof Recursion [Arithmetic sequence](https://publish.obsidian.md/discretecs/Recursion/Arithmetic+sequence) [Characteristic root method](https://publish.obsidian.md/discretecs/Recursion/Characteristic+root+method) [Closed formula](https://publish.obsidian.md/discretecs/Recursion/Closed+formula) [Fibonacci sequence](https://publish.obsidian.md/discretecs/Recursion/Fibonacci+sequence) [Geometric sequence](https://publish.obsidian.md/discretecs/Recursion/Geometric+sequence) [Homogeneous recurrence relation](https://publish.obsidian.md/discretecs/Recursion/Homogeneous+recurrence+relation) [Linear recurrence relation](https://publish.obsidian.md/discretecs/Recursion/Linear+recurrence+relation) [Recurrence relation](https://publish.obsidian.md/discretecs/Recursion/Recurrence+relation) [Recursion](https://publish.obsidian.md/discretecs/Recursion/Recursion) [Sequence](https://publish.obsidian.md/discretecs/Recursion/Sequence) [Solution to a recurrence relation](https://publish.obsidian.md/discretecs/Recursion/Solution+to+a+recurrence+relation) Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Solution to a recurrence relation ================================= aliases: [solution to a recurrence relation] [#recursion-induction](https://publish.obsidian.md/discretecs/Recursion/Solution+to+a+recurrence+relation#recursion-induction) Definition ---------- Definition A **solution** to a [recurrence relation](https://publish.obsidian.md/discretecs/Recursion/Recurrence+relation) is a [closed formula](https://publish.obsidian.md/discretecs/Recursion/Closed+formula) that produces the same sequence of objects that the [recurrence relation](https://publish.obsidian.md/discretecs/Recursion/Recurrence+relation) produces. Notes: * Whereas a recurrence relation produces objects in a sequence [recursively](https://publish.obsidian.md/discretecs/Recursion/Recursion) , a solution to the recurrence relation produces them directly. * Solutions to recurrence relations are useful for making computations but are not always preferable to [recursion](https://publish.obsidian.md/discretecs/Recursion/Recursion) , since they can hide key insights on the structure of the objects in the sequence. * There are numerous methods for finding solutions to recurrence relations, including the [characteristic root method](https://publish.obsidian.md/discretecs/Recursion/Characteristic+root+method) if the recurrence relation is [linear](https://publish.obsidian.md/discretecs/Recursion/Linear+recurrence+relation) and [homogeneous](https://publish.obsidian.md/discretecs/Recursion/Homogeneous+recurrence+relation) , as well as the basic methods for finding solutions if the sequence is an [arithmetic](https://publish.obsidian.md/discretecs/Recursion/Arithmetic+sequence) or [geometric](https://publish.obsidian.md/discretecs/Recursion/Geometric+sequence) sequence of numbers. * Taking a given [closed formula](https://publish.obsidian.md/discretecs/Recursion/Closed+formula) and checking that it is indeed a solution to a recurrence relation, involves a [proof](https://publish.obsidian.md/discretecs/Proof/Proof) using [mathematical induction](https://publish.obsidian.md/discretecs/Proof/Mathematical+induction) . Examples and Non-Examples ------------------------- * The recurrence relation a\_0 = 3 and a\_n = 2a\_{n-1} when n > 0 produces the sequence 3, 6, 12, 24, 48, \\dots. This is a [geometric sequence](https://publish.obsidian.md/discretecs/Recursion/Geometric+sequence) that has the solution a(n) = 3 \\cdot 2^n. * The sequence 1, 3, 6, 10, 15, \\dots given by the recurrence relation T\_1 = 1 and T\_n = T\_{n-1} + n when n > 1, has a solution given by T(n) = \\dfrac{n(n+1)}{2}. * The [Fibonacci sequence](https://publish.obsidian.md/discretecs/Recursion/Fibonacci+sequence) 1, 1, 2, 3, 5, 8, 13, 21, \\dots given by the recurrence relation F\_1 = 1, F\_2 = 1 and F\_n = F\_{n-1} + F\_{n-2} when n > 2 has the solution: F\_n = \\frac{\\left(\\frac{1+\\sqrt{5}}{2}\\right)^n - \\left(\\frac{1-\\sqrt{5}}{2}\\right)^n}{\\sqrt{5}} * **Non-example:** Consider the recurrence relation: a\_0 = 2, a\_1=5, and for n > 1, a\_n = 3a\_{n-1} - 2a\_{n-2}. This produces the sequence 2, 5, 11, 23, 47, 95, ... The [function](https://publish.obsidian.md/discretecs/Sets+and+Functions/Function) a(n) = 1.5n^2 + 1.5n + 2 is _not_ a solution to this recurrence relation. It produces the first three terms correctly: a(0) = 2, a(1) = 5, a(2) = 11. But then whereas the fourth term (n=3) of the sequence is 23, the formula instead gives a(3) = 1.5 \\cdot 3^2 1.5 \\cdot 3 + 2 = 20. Examples are not proofs Just because a formula produces the first few terms of a recurrence relation correctly, it is not necessarily a solution to the recurrence relation. Giving examples where the formula "works" is not sufficient to prove that it's a solution. Instead this requires using a method of coming up with the formula that is known to produce correct solutions, or checking that the formula is a solution via a proof by [mathematical induction](https://publish.obsidian.md/discretecs/Proof/Mathematical+induction) . Resources --------- Solution to a recurrence relation Not found This page does not exist Interactive graph On this page Definition Examples and Non-Examples Resources [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Base 10 representation - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic [Addition in binary](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Addition+in+binary) [Base 2 representation](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+2+representation) [Base 8 representation](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+8+representation) [Base 10 representation](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+10+representation) [Base 16 representation](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+16+representation) [Base conversion algorithm](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+conversion+algorithm) [Binary digits and bitstrings](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Binary+digits+and+bitstrings) [Converting to base 10](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Converting+to+base+10) [Division in binary](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Division+in+binary) [Integer congruence](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integer+congruence) [Integer division](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integer+division) [Integers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integers) [Multiplication in binary](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Multiplication+in+binary) [Natural numbers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Natural+numbers) [Subtraction in binary](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Subtraction+in+binary) [The division algorithm](https://publish.obsidian.md/discretecs/Computer+Arithmetic/The+division+algorithm) [The modulus operator](https://publish.obsidian.md/discretecs/Computer+Arithmetic/The+modulus+operator) [Two's complement](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Two's+complement) Logic Sets and Functions Basic math concepts Combinatorics Directed Graphs and Relations Graphs Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Base 10 representation ====================== aliases: [decimal, base 10] [#computer-arithmetic](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+10+representation#computer-arithmetic) Definition ---------- Definition An [integer](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integers) is written in **base 10** or **decimal** format if it consists of a string of digits, all between 0 and 9, that represent groupings of power of 10. Examples -------- Base 10 is the standard way of writing positive [integers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integers) we learn in school. The digits represent place value. For example the [integer](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integers) 267 has 7 in the "ones place", 6 in the "tens place", and 2 in the "hundreds place". This means that this number consists of 2 copies or groups of 100, 6 copies of 10, and 7 copies of 1. We can write this fact as: 267 = 2 \\times 100 + 6 \\times 10 + 7 \\times 1Each of the groups is represented by a power of 10, so we can also write this as: 267 = 2 \\times 10^2 + 6 \\times 10^1 + 7 \\times 10^0 **Another example:** The number 90125, written in base 10, can be written as 90125 = 9 \\times 10^4 + 0 \\times 10^3 + 1 \\times 10^2 + 2 \\times 10^1 + 5 \\times 10^0The digit attached to each grouping of 10 must be a [natural number](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Natural+numbers) between 0 and 9. If a digit were greater than 9, it would just create a new place value. Resources --------- The first three minutes of this video covers more on base 10 representation: Base 10 representation Not found This page does not exist Interactive graph On this page Definition Examples Resources [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Base 16 representation - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic [Addition in binary](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Addition+in+binary) [Base 2 representation](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+2+representation) [Base 8 representation](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+8+representation) [Base 10 representation](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+10+representation) [Base 16 representation](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+16+representation) [Base conversion algorithm](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+conversion+algorithm) [Binary digits and bitstrings](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Binary+digits+and+bitstrings) [Converting to base 10](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Converting+to+base+10) [Division in binary](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Division+in+binary) [Integer congruence](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integer+congruence) [Integer division](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integer+division) [Integers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integers) [Multiplication in binary](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Multiplication+in+binary) [Natural numbers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Natural+numbers) [Subtraction in binary](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Subtraction+in+binary) [The division algorithm](https://publish.obsidian.md/discretecs/Computer+Arithmetic/The+division+algorithm) [The modulus operator](https://publish.obsidian.md/discretecs/Computer+Arithmetic/The+modulus+operator) [Two's complement](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Two's+complement) Logic Sets and Functions Basic math concepts Combinatorics Directed Graphs and Relations Graphs Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Base 16 representation ====================== aliases: [hexadecimal, hexadecimal representation, base 16, base 16 representation] [#computer-arithmetic](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+16+representation#computer-arithmetic) Definition ---------- Definition An [integer](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integers) is written in **base 16** or **hexadecimal** format if it consists of a string of the numbers 0 through 9 and letters A through F that represent groupings of powers of 16. Notes: * In hexadecimal, the letter A represents the [base 10](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+10+representation) number 10; B represents 11; C represents 12; D represents 13; E represents 14; and F represents 15. * The alphabetical digits are needed to have more than ten copies of a power of 16. * The first few powers of 16 are: 16^0 = 1, 16^1 = 16, 16^2 = 256, 16^3 = 4096. These are all powers of 2 as well, since 16= 2^4. Examples -------- The number 2670 can be written as a sum of powers of 16 as follows: 2670 = 10 \\times 256 + 6 \\times 16 + 14 \\times 1 = 10 \\times 16^2 + 6 \\times 16^1 + 14 \\times 16^0Using the multipliers in front of the powers of 16 and replacing 10 and 14 with A and E respectively, we get 2670 \\ \\text{base 10} = A6E \\ \\text{base 16}A subscript is often used to indicate which base we mean: 2670\_{10} = A6E\_{16}. Likewise, the number 2561 is 10 \\times 256 + 0 \\times 16 + 1 \\times 1so 2561\_{10} = A01\_{16}. Resources --------- Base 16 representation Not found This page does not exist Interactive graph On this page Definition Examples Resources Practice [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Base conversion algorithm - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic [Addition in binary](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Addition+in+binary) [Base 2 representation](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+2+representation) [Base 8 representation](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+8+representation) [Base 10 representation](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+10+representation) [Base 16 representation](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+16+representation) [Base conversion algorithm](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+conversion+algorithm) [Binary digits and bitstrings](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Binary+digits+and+bitstrings) [Converting to base 10](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Converting+to+base+10) [Division in binary](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Division+in+binary) [Integer congruence](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integer+congruence) [Integer division](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integer+division) [Integers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integers) [Multiplication in binary](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Multiplication+in+binary) [Natural numbers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Natural+numbers) [Subtraction in binary](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Subtraction+in+binary) [The division algorithm](https://publish.obsidian.md/discretecs/Computer+Arithmetic/The+division+algorithm) [The modulus operator](https://publish.obsidian.md/discretecs/Computer+Arithmetic/The+modulus+operator) [Two's complement](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Two's+complement) Logic Sets and Functions Basic math concepts Combinatorics Directed Graphs and Relations Graphs Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Base conversion algorithm ========================= aliases: [base conversion algorithm] [#computer-arithmetic](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+conversion+algorithm#computer-arithmetic) Process ------- To convert a positive [integer](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integers) _from_ [base 10](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+10+representation) _to_ base b where b is any other number base: Let n be the integer in base 10 that you want to convert to base b. 1. Divide n by b. Let q\_1 be the quotient (how many times b goes into n) and let r\_1 be the remainder. 2. Now replace n with q\_1. Divide q\_1 by b, and let q\_2 be the new quotient and r\_2 be the new remainder. 3. Replace q\_1 with q\_2. Divide q\_2 by b, and let q\_3 be the new quotient and r\_3 be the new remainder. 4. Continue these steps (divide the previous quotient by b and keeping the new quotient and new remainder) until the new quotient is 0. In the final step where the new quotient is 0, go ahead and keep the. new remainder (which will just be the number you divided into). 5. The base b representation of the original integer n, is **the sequence of remainders written in reverse order**. So, if there were k steps in all, the base b representation is r\_k r\_{k-1} r\_{k-2} \\cdots r\_3 r\_2 r\_1. Notes: * The algorithm here always terminates because the quotients are [nonnegative integers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Natural+numbers) , and at each step must get strictly smaller, and therefore they will always converge to zero. * Here is Python code for this algorithm if the base is between 2 and 10. It terminates immediately if the base is larger than 10, because to convert to a larger base you would need alphabetical replacements for the numbers 10 and above, as in [hexadecimal](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+16+representation) . You could modify this code, though, to work for larger bases if you introduced some additional data structures to represent 10, 11, 12, etc. Also, notice this returns a string, not a number. def convert_to_base(number, base): if base < 2 or base > 10: raise ValueError("Invalid base: %d" % base) digits = [] while number: # Loop exists once "number" equals 0 digit = number % base #Divide by the base and keep the remainder digits.append(chr(ord('0') + digit)) number //= base # Replace "number" with the previous quotient digits.reverse() return ''.join(digits) Examples -------- Converting the [base 10](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+10+representation) integer 42 to [binary](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+2+representation) ([base 2](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+2+representation) ): 1. Divide 42 by 2 and keep the quotient and remainder: q\_1 = 21, r\_1 = 0 2. Divide q\_1 by 2 and keep the quotient and remainder: q\_2 = 10, r\_2 = 1 3. Divide q\_2 by 2 and keep the quotient and remainder: q\_3 = 5, r\_3 = 0 4. Divide q\_3 by 2 and keep the quotient and remainder: q\_4 = 2, r\_4 = 1 5. Divide q\_4 by 2 and keep the quotient and remainder: q\_5 = 1, r\_1 = 0 6. Divide q\_5 by 2 and keep the quotient and remainder: q\_6 = 0, r\_1 = 1. This is because 2 goes into 1 zero times, with a remainder of 1. 7. The quotient equalled zero, so stop and return the remainders in reverse order: 101010. That is, 42\_{10} = 101010\_2. Base conversion algorithm Not found This page does not exist Interactive graph On this page Process Examples Resources Practice [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Cardinality - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions [Bijective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Bijective) [Cardinality](https://publish.obsidian.md/discretecs/Sets+and+Functions/Cardinality) [Cartesian product](https://publish.obsidian.md/discretecs/Sets+and+Functions/Cartesian+product) [Codomain](https://publish.obsidian.md/discretecs/Sets+and+Functions/Codomain) [Complement](https://publish.obsidian.md/discretecs/Sets+and+Functions/Complement) [Domain](https://publish.obsidian.md/discretecs/Sets+and+Functions/Domain) [Empty set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Empty+set) [Function](https://publish.obsidian.md/discretecs/Sets+and+Functions/Function) [Injective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Injective) [Intersection](https://publish.obsidian.md/discretecs/Sets+and+Functions/Intersection) [Power set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Power+set) [Range](https://publish.obsidian.md/discretecs/Sets+and+Functions/Range) [Roster notation](https://publish.obsidian.md/discretecs/Sets+and+Functions/Roster+notation) [Set difference](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set+difference) [Set-builder notation](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set-builder+notation) [Set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set) [Subset](https://publish.obsidian.md/discretecs/Sets+and+Functions/Subset) [Surjective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Surjective) [Symmetric difference](https://publish.obsidian.md/discretecs/Sets+and+Functions/Symmetric+difference) [Union](https://publish.obsidian.md/discretecs/Sets+and+Functions/Union) [Universal set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Universal+set) Basic math concepts Combinatorics Directed Graphs and Relations Graphs Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Cardinality =========== aliases: [cardinality] [#sets-functions](https://publish.obsidian.md/discretecs/Sets+and+Functions/Cardinality#sets-functions) Definition ---------- Definition The **cardinality** of a [set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set) is the set's size. If the set is finite, its cardinality is simply the number of elements it contains. If the set is infinite, we just say that the set "has infinite cardinality". If A is a set, its cardinality is denoted |A|. Notes: * For infinite sets, the concept of "the number of elements in the set" does not make semantic sense because there is no number that describes the cardinality. Again, we just say that infinite sets have infinite cardinalities. * It is possible to distinguish between different types of infinite cardinalities; for example the cardinality of the set of real numbers has a "larger" cardinality than the set of integers. But this is beyond the scope of this course. Examples -------- * The cardinality of the set \\{10, x, 4/5\\} is 3. * The cardinality of the set \\{\\emptyset, \\{1,2,3\\}, 4, \\{5,6\\}\\} is 4. * The cardinality of \\{n \\in \\mathbb{N} \\, : \\, 24 \\, \\% \\, n = 0 \\} is 8. That's because this set that is given in [set-builder notation](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set-builder+notation) would, in [roster notation](https://publish.obsidian.md/discretecs/Sets+and+Functions/Roster+notation) , be \\{1, 2, 3, 4, 6, 8, 12, 24\\}. * The cardinality of \\{x^2 \\, : \\, x \\in \\mathbb{N}\\} is infinite. Resources --------- Cardinality Not found This page does not exist Interactive graph On this page Definition Examples Resources [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Cartesian product - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions [Bijective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Bijective) [Cardinality](https://publish.obsidian.md/discretecs/Sets+and+Functions/Cardinality) [Cartesian product](https://publish.obsidian.md/discretecs/Sets+and+Functions/Cartesian+product) [Codomain](https://publish.obsidian.md/discretecs/Sets+and+Functions/Codomain) [Complement](https://publish.obsidian.md/discretecs/Sets+and+Functions/Complement) [Domain](https://publish.obsidian.md/discretecs/Sets+and+Functions/Domain) [Empty set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Empty+set) [Function](https://publish.obsidian.md/discretecs/Sets+and+Functions/Function) [Injective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Injective) [Intersection](https://publish.obsidian.md/discretecs/Sets+and+Functions/Intersection) [Power set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Power+set) [Range](https://publish.obsidian.md/discretecs/Sets+and+Functions/Range) [Roster notation](https://publish.obsidian.md/discretecs/Sets+and+Functions/Roster+notation) [Set difference](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set+difference) [Set-builder notation](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set-builder+notation) [Set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set) [Subset](https://publish.obsidian.md/discretecs/Sets+and+Functions/Subset) [Surjective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Surjective) [Symmetric difference](https://publish.obsidian.md/discretecs/Sets+and+Functions/Symmetric+difference) [Union](https://publish.obsidian.md/discretecs/Sets+and+Functions/Union) [Universal set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Universal+set) Basic math concepts Combinatorics Directed Graphs and Relations Graphs Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Cartesian product ================= aliases: - cartesian product - ordered pair tags: - sets-functions created: updated: 2024-08-07 * * * [#sets-functions](https://publish.obsidian.md/discretecs/Sets+and+Functions/Cartesian+product#sets-functions) Definition ---------- Definition If A and B are [sets](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set) , the **Cartesian product** of A and B is the set of all ordered pairs whose first coordinate is an [element](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set) of A and whose second coordinate is an element of B. In notation, the Cartesian product of A and B is written A \\times B. In [set-builder notation](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set-builder+notation) , A \\times B = \\{ (x,y) \\, : \\, x \\in A \\ \\text{and} \\ y \\in B\\} **Notes:** * The symbol \\times does _not_ mean "multiplication" in this context. * The order of sets in a Cartesian product matters: A \\times B is not the same set as B \\times A because the pairs in the Cartesian product are _ordered_ pairs -- switching coordinates does not keep the ordered pairs equal. * In Python terminology, the elements of a Cartesian product are [tuples](https://www.w3schools.com/python/python_tuples.asp) with two elements. * It is possible to similarly define the Cartesian product of more than two sets, using tuples that have more than two elements. For example A \\times B \\times C would be the set of all three-element tuples with the first coordinate in A, the second in B, and the third in C. * If A is a finite set with [cardinality](https://publish.obsidian.md/discretecs/Sets+and+Functions/Cardinality) equal to N, and B is finite with [cardinality](https://publish.obsidian.md/discretecs/Sets+and+Functions/Cardinality) M, then A \\times B has [cardinality](https://publish.obsidian.md/discretecs/Sets+and+Functions/Cardinality) N \\cdot M since A \\times B contains all the combinations of elements from A and B. Examples -------- * Let A = \\{0,1,2\\} and B = \\{s,t\\}. Then A \\times B = \\{(0,s), (0,t), (1,s), (1,t), (2,s), (2,t)\\}. * Let S = \\{x,y,z\\}. Then S \\times S is the set of all ordered pairs whose coordinates from from S: \\{(x,x), (x,y), (x,z), (y,x), (y,y), (y,z), (z,x), (z,y), (z,z)\\}. * We can also find the Cartesian product of infinite sets. For example, if S = \\{x,y,z\\} and \\mathbb{N} is the set of all [natural numbers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Natural+numbers) , then S \\times \\mathbb{N} = \\{(x,0), (y,0), (z,0), (x,1), (y,1), (z,1), (x,2), (y,2), (z,2), \\dots\\} Resources --------- Cartesian product Not found This page does not exist Interactive graph On this page Definition Examples Resources Practice [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Function - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions [Bijective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Bijective) [Cardinality](https://publish.obsidian.md/discretecs/Sets+and+Functions/Cardinality) [Cartesian product](https://publish.obsidian.md/discretecs/Sets+and+Functions/Cartesian+product) [Codomain](https://publish.obsidian.md/discretecs/Sets+and+Functions/Codomain) [Complement](https://publish.obsidian.md/discretecs/Sets+and+Functions/Complement) [Domain](https://publish.obsidian.md/discretecs/Sets+and+Functions/Domain) [Empty set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Empty+set) [Function](https://publish.obsidian.md/discretecs/Sets+and+Functions/Function) [Injective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Injective) [Intersection](https://publish.obsidian.md/discretecs/Sets+and+Functions/Intersection) [Power set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Power+set) [Range](https://publish.obsidian.md/discretecs/Sets+and+Functions/Range) [Roster notation](https://publish.obsidian.md/discretecs/Sets+and+Functions/Roster+notation) [Set difference](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set+difference) [Set-builder notation](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set-builder+notation) [Set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set) [Subset](https://publish.obsidian.md/discretecs/Sets+and+Functions/Subset) [Surjective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Surjective) [Symmetric difference](https://publish.obsidian.md/discretecs/Sets+and+Functions/Symmetric+difference) [Union](https://publish.obsidian.md/discretecs/Sets+and+Functions/Union) [Universal set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Universal+set) Basic math concepts Combinatorics Directed Graphs and Relations Graphs Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Function ======== aliases: [functions, function] [#sets-functions](https://publish.obsidian.md/discretecs/Sets+and+Functions/Function#sets-functions) Definition ---------- Definition A **function** is a rule that accepts input from one [set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set) and produces output in another set, so that every input is assigned to one and only one output. If the inputs come from from the set A and the outputs come from the set B, and the name of the function is f, then we write f: A \\rightarrow B. Notes: * In the notation above (f: A \\rightarrow B) the set A is the [domain](https://publish.obsidian.md/discretecs/Sets+and+Functions/Domain) of the function and the set B is the [Codomain](https://publish.obsidian.md/discretecs/Sets+and+Functions/Codomain) . * If x \\in A, then the output that is assigned to x by the function f is notated f(x) ("f of x"). This is sometimes called the _image_ of x. * Functions can take on different forms or representations. Common forms are: * _Formulas_. For example f: \\mathbb{Z} \\rightarrow \\mathbb{Z} defined by f(n) = 2n is a function that assigns each [integer](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integers) input n to its double. * _Tables or lists_. For example g: \\{0,1,2\\} \\rightarrow \\{a,b,c\\} defined by g(0) = c, g(1) = a, g(2) = b is a function, defined by explicitly listing the outputs assigned to each input. * _Verbal descriptions._ For example, define the function p: \\mathbb{N} \\rightarrow \\mathbb{N} by assigning n to the nth digit of \\pi. So p(0) = 3, p(1) = 1, p(2) = 4, p(3) = 1, etc. * _Graphs or diagrams_. For example the diagram below defines a function from A = \\{-2,0,3,5\\} to B = \\{-4,-3,4\\}: ![simple-function-diagram.png](https://publish-01.obsidian.md/access/64d815ddc8215841f63db915c7923004/Assets/Images/simple-function-diagram.png) ([Source](https://mathbooks.unl.edu/PreCalculus/Intro-to-Functions.html) ) * In order for a rule of assignment to be a valid function according to this definition, two things must happen: * Every point in A (the [domain](https://publish.obsidian.md/discretecs/Sets+and+Functions/Domain) of f) must actually have an output; that is, there can be no [elements](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set) of A that are unassigned or uncomputable. * No point in A can be sent to two different outputs. * However notice in the examples above, and below, that **it is within the definition for two different inputs to be sent to the same output** (a "collision"). We just cannot send _one_ input to _two or more_ outputs ("splitting"). Examples and Non-Examples ------------------------- Some examples are shown above; here are a few more. * The function ceil: \\mathbb{R} \\rightarrow \\mathbb{Z} takes a real number (floating point number) as input, and the output assigned is the integer you get when you round the input up. For example ceil(9.22) = 10. This is a function because every input does receive an output, and no input gets more than one. (However there are lots of collisions, where different inputs are sent to the same output; for example every number greater than 9 and less than or equal to 10 will be sent to 10.) * The function f: \\mathbb{R} \\rightarrow \\mathbb{R} defined as the formula f(x) = x^2 is a function, since every number can be squared and no number has more than one square. (Again however there are collisions, since f(1) = f(-1).) Some examples of assignments or mappings that are _not_ functions: Function Not found This page does not exist Interactive graph On this page Definition Examples and Non-Examples Resources [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Base 2 representation - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic [Addition in binary](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Addition+in+binary) [Base 2 representation](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+2+representation) [Base 8 representation](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+8+representation) [Base 10 representation](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+10+representation) [Base 16 representation](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+16+representation) [Base conversion algorithm](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+conversion+algorithm) [Binary digits and bitstrings](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Binary+digits+and+bitstrings) [Converting to base 10](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Converting+to+base+10) [Division in binary](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Division+in+binary) [Integer congruence](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integer+congruence) [Integer division](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integer+division) [Integers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integers) [Multiplication in binary](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Multiplication+in+binary) [Natural numbers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Natural+numbers) [Subtraction in binary](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Subtraction+in+binary) [The division algorithm](https://publish.obsidian.md/discretecs/Computer+Arithmetic/The+division+algorithm) [The modulus operator](https://publish.obsidian.md/discretecs/Computer+Arithmetic/The+modulus+operator) [Two's complement](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Two's+complement) Logic Sets and Functions Basic math concepts Combinatorics Directed Graphs and Relations Graphs Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Base 2 representation ===================== aliases: [binary, binary representation, base 2, base 2 representation] [#computer-arithmetic](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Base+2+representation#computer-arithmetic) Definition ---------- Definition An [integer](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integers) is written in **base 2** or **binary** format if it consists of a string of the numbers 0 and 1, called **[binary digits](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Binary+digits+and+bitstrings) ** or "**[bits](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Binary+digits+and+bitstrings) **", that represent groupings of powers of 2. Notes: * A group of 8 [bits](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Binary+digits+and+bitstrings) is known as a **byte**. * Every positive integer can in fact be written as a sum of powers of 2 and in only one way. This fact can be proven using [Logic/Mathematical induction](https://publish.obsidian.md/discretecs/Logic/Mathematical+induction) . Examples -------- The number 267 can be written as a sum of powers of 2 as follows: 267 = 256 + 8 + 2 + 1 = 2^8 + 2^3 + 2^1 + 2^0Using 0 to pad this sum with groups that are not used and 1 multiplied to groups that are use, this becomes: 267 = 256 + 8 + 2 + 1 = 1 \\cdot 2^8 + 0 \\cdot 2^7 + 0 \\cdot 2^6 + 0 \\cdot 2^5 + 0 \\cdot 2^4 + 1 \\cdot 2^3 + + 0 \\cdot 2^2 + 1 \\cdot 2^1 + 1 \\cdot 2^0The resulting string of 0's and 1's, read left-to-right, is the binary representation of 267: 267 \\ \\text{base 10} = 100001011 \\ \\text{base 2}A subscript is often used to indicate which base we mean: 267\_{10} = 100001011\_{2}. Likewise, the number 24 is 24 = 16 + 8 = 1 \\cdot 2^4 + 1 \\cdot 2^3 + 0 \\cdot 2^2 + 0 \\cdot 2^1 + 0 \\cdot 2^0. Therefore 24\_{10} = 11000\_2. Resources --------- Base 2 representation Not found This page does not exist Interactive graph On this page Definition Examples Resources Practice [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Set - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions [Bijective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Bijective) [Cardinality](https://publish.obsidian.md/discretecs/Sets+and+Functions/Cardinality) [Cartesian product](https://publish.obsidian.md/discretecs/Sets+and+Functions/Cartesian+product) [Codomain](https://publish.obsidian.md/discretecs/Sets+and+Functions/Codomain) [Complement](https://publish.obsidian.md/discretecs/Sets+and+Functions/Complement) [Domain](https://publish.obsidian.md/discretecs/Sets+and+Functions/Domain) [Empty set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Empty+set) [Function](https://publish.obsidian.md/discretecs/Sets+and+Functions/Function) [Injective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Injective) [Intersection](https://publish.obsidian.md/discretecs/Sets+and+Functions/Intersection) [Power set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Power+set) [Range](https://publish.obsidian.md/discretecs/Sets+and+Functions/Range) [Roster notation](https://publish.obsidian.md/discretecs/Sets+and+Functions/Roster+notation) [Set difference](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set+difference) [Set-builder notation](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set-builder+notation) [Set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set) [Subset](https://publish.obsidian.md/discretecs/Sets+and+Functions/Subset) [Surjective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Surjective) [Symmetric difference](https://publish.obsidian.md/discretecs/Sets+and+Functions/Symmetric+difference) [Union](https://publish.obsidian.md/discretecs/Sets+and+Functions/Union) [Universal set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Universal+set) Basic math concepts Combinatorics Directed Graphs and Relations Graphs Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Set === aliases: [sets, set, element, elements] [#sets-functions](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set#sets-functions) Definition ---------- Definition A **set** is an unordered collection of distinct objects. An item that belongs to a set is said to be an **element** of the set. If x is an element of the set A, we denote this by x \\in A ("x is an element of A"). If x is not an element of the set A, we denote this by x \\not \\in A. Notes * Sets can be described in a few different ways: * In words, for example "the set of all current MTH 225 students at Grand Valley State University" * As a symbol, usually a capital letter (A, X, etc.) * For some commonly-used sets we use a special letter -- for example \\mathbb{N} denotes the set of all [Natural numbers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Natural+numbers) and \\mathbb{Z} denotes the set of all [Integers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integers) . * In **[roster notation](https://publish.obsidian.md/discretecs/Sets+and+Functions/Roster+notation) **, where we list the items of the set explicitly within curly braces, for example \\{0, 2, 4, 6\\}. * In [set-builder notation](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set-builder+notation) , where we describe the set using rules for deciding what its elements are, for example \\{n \\in \\mathbb{N} \\, : \\, n \\ \\text{is even and} \\ 0 \\leq n < 7\\}. This set is equal to \\{0,2,4,6\\} * The word "distinct" in the definition indicates that **sets cannot contain duplicate items**. For example \\{2,2,2,2,2\\} is not a properly-written set. This set is the same as \\{2\\} and should be written this way, without duplicates. Examples and Non-Examples ------------------------- * The set of all letters in the word "valley" could be written as \\{v,a,l,e,y\\}. The ordering of the elements doesn't matter; but again we do not allow duplicate items. * There is no restriction on the types of objects allowed in a set. For example, \\{1, x, \\{10,11\\}, \\emptyset\\} is a set with four elements: The number 1, the letter x, a two-element set, and the [empty set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Empty+set) . * Sets can be either finite or infinite. Finite sets, if they are small, are often just written in [roster notation](https://publish.obsidian.md/discretecs/Sets+and+Functions/Roster+notation) . * If the elements of a set have a pattern, we usually use dots (\\dots) to indicate this. For example \\{3, 6, 9, 12, \\dots, 96, 99\\} is the set of all positive [integers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integers) less than 100 that are multiples of 3. You could also write this set in [set-builder notation](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set-builder+notation) as \\{a \\in \\mathbb{N} \\, : \\, 0 < a < 100 \\ \\text{and} \\ a \\% 3 = 0\\}. * Infinite sets that continue a pattern forever in the positive or negative \\infty direction also use dots. For example the set of all integer multiples of 10 is \\{\\dots, -30, -20, -10, 0, 10, 20, 30, \\dots\\} Resources --------- Set Not found This page does not exist Interactive graph On this page Definition Examples and Non-Examples Resources Practice [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Codomain - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions [Bijective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Bijective) [Cardinality](https://publish.obsidian.md/discretecs/Sets+and+Functions/Cardinality) [Cartesian product](https://publish.obsidian.md/discretecs/Sets+and+Functions/Cartesian+product) [Codomain](https://publish.obsidian.md/discretecs/Sets+and+Functions/Codomain) [Complement](https://publish.obsidian.md/discretecs/Sets+and+Functions/Complement) [Domain](https://publish.obsidian.md/discretecs/Sets+and+Functions/Domain) [Empty set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Empty+set) [Function](https://publish.obsidian.md/discretecs/Sets+and+Functions/Function) [Injective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Injective) [Intersection](https://publish.obsidian.md/discretecs/Sets+and+Functions/Intersection) [Power set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Power+set) [Range](https://publish.obsidian.md/discretecs/Sets+and+Functions/Range) [Roster notation](https://publish.obsidian.md/discretecs/Sets+and+Functions/Roster+notation) [Set difference](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set+difference) [Set-builder notation](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set-builder+notation) [Set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set) [Subset](https://publish.obsidian.md/discretecs/Sets+and+Functions/Subset) [Surjective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Surjective) [Symmetric difference](https://publish.obsidian.md/discretecs/Sets+and+Functions/Symmetric+difference) [Union](https://publish.obsidian.md/discretecs/Sets+and+Functions/Union) [Universal set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Universal+set) Basic math concepts Combinatorics Directed Graphs and Relations Graphs Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Codomain ======== aliases: [codomain] [#sets-functions](https://publish.obsidian.md/discretecs/Sets+and+Functions/Codomain#sets-functions) Definition ---------- Definition The **codomain** of a [function](https://publish.obsidian.md/discretecs/Sets+and+Functions/Function) is the [set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set) consisting of all allowable outputs of that function. In standard function notation, if f: A \\rightarrow B is a function then the set B is the codomain. Notes: * The codomain of f contains the [range](https://publish.obsidian.md/discretecs/Sets+and+Functions/Range) of the function as a [subset](https://publish.obsidian.md/discretecs/Sets+and+Functions/Subset) , but the two are not necessarily equal. See examples below. * Informally we can think of the codomain as specifying the "data type" of the outputs. For example the [ceiling function](https://publish.obsidian.md/discretecs/Basic+math+concepts/Floor+and+ceiling+functions) ceil: \\mathbb{R} \\rightarrow \\mathbb{Z} that takes a real number and rounds it up, has a codomain of \\mathbb{Z} which indicates that the outputs are of "type integer". Examples -------- * The function f: \\mathbb{R} \\rightarrow \\mathbb{R} defined as the formula f(x) = x^2 has codomain equal to \\mathbb{R}, the set of all real numbers. (This is also its [domain](https://publish.obsidian.md/discretecs/Sets+and+Functions/Domain) .) * The function p: \\mathbb{N} \\rightarrow \\mathbb{N} defined by assigning n to the nth digit of \\pi. So p(0) = 3, p(1) = 1, p(2) = 4, p(3) = 1, etc. has codomain equal to the [natural numbers](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Natural+numbers) (same as its [domain](https://publish.obsidian.md/discretecs/Sets+and+Functions/Domain) ). * The function from A = \\{-2,0,3,5\\} to B = \\{-4,-3,4\\} shown in the diagram below has a codomain of \\{-4,-3,4\\}: ![simple-function-diagram.png](https://publish-01.obsidian.md/access/64d815ddc8215841f63db915c7923004/Assets/Images/simple-function-diagram.png) * The (Python) function shown below takes a positive integer and returns a list of all of its positive divisors. For example `divisors(18) = [1,2,3,6,9,18]`. The [domain](https://publish.obsidian.md/discretecs/Sets+and+Functions/Domain) in this case is the set of all positive integers, and the codomain is the set of all _lists of_ positive integers. (That is, the outputs have a "data type" of lists containing positive integers.) def divisors(n): return [i for i in range(1,n+1) if n % i == 0] Resources --------- Codomain Not found This page does not exist Interactive graph On this page Definition Examples Resources [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Bijective - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions [Bijective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Bijective) [Cardinality](https://publish.obsidian.md/discretecs/Sets+and+Functions/Cardinality) [Cartesian product](https://publish.obsidian.md/discretecs/Sets+and+Functions/Cartesian+product) [Codomain](https://publish.obsidian.md/discretecs/Sets+and+Functions/Codomain) [Complement](https://publish.obsidian.md/discretecs/Sets+and+Functions/Complement) [Domain](https://publish.obsidian.md/discretecs/Sets+and+Functions/Domain) [Empty set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Empty+set) [Function](https://publish.obsidian.md/discretecs/Sets+and+Functions/Function) [Injective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Injective) [Intersection](https://publish.obsidian.md/discretecs/Sets+and+Functions/Intersection) [Power set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Power+set) [Range](https://publish.obsidian.md/discretecs/Sets+and+Functions/Range) [Roster notation](https://publish.obsidian.md/discretecs/Sets+and+Functions/Roster+notation) [Set difference](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set+difference) [Set-builder notation](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set-builder+notation) [Set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set) [Subset](https://publish.obsidian.md/discretecs/Sets+and+Functions/Subset) [Surjective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Surjective) [Symmetric difference](https://publish.obsidian.md/discretecs/Sets+and+Functions/Symmetric+difference) [Union](https://publish.obsidian.md/discretecs/Sets+and+Functions/Union) [Universal set](https://publish.obsidian.md/discretecs/Sets+and+Functions/Universal+set) Basic math concepts Combinatorics Directed Graphs and Relations Graphs Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Bijective ========= aliases: [bijective, bijection] [#sets-functions](https://publish.obsidian.md/discretecs/Sets+and+Functions/Bijective#sets-functions) Definition ---------- Definition A [function](https://publish.obsidian.md/discretecs/Sets+and+Functions/Function) f: A \\rightarrow B is **bijective** if it is both [injective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Injective) and [surjective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Surjective) . **Notes:** * If a function is bijective it informally means two things: * There are no "collisions" (because the function is [injective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Injective) ) * There are no points in the [codomain](https://publish.obsidian.md/discretecs/Sets+and+Functions/Codomain) that are "left out" (because the function is [surjective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Surjective) ) * If there is a bijection between A and B, then those two [sets](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set) have the same [cardinality](https://publish.obsidian.md/discretecs/Sets+and+Functions/Cardinality) . The [converse](https://publish.obsidian.md/discretecs/Logic/Converse) is also true for finite sets: If A and B are finite and have the same number of elements, then it's possible to create a bijection between them. Examples and Non-Examples ------------------------- * The function f: A \\rightarrow B shown in the diagram below is a bijection: ![injective1.png](https://publish-01.obsidian.md/access/64d815ddc8215841f63db915c7923004/Assets/Images/injective1.png) ([Image source](https://www.google.com/url?sa=i&url=https%3A%2F%2Fcollegedunia.com%2Fexams%2Fbijective-function-mathematics-articleid-5395&psig=AOvVaw3bIRWsNf8Mn9zace0S4B8A&ust=1696082301870000&source=images&cd=vfe&opi=89978449&ved=0CBIQjhxqFwoTCLj4zor9z4EDFQAAAAAdAAAAABAE) ) * The function g: \\mathbb{Z} \\rightarrow \\mathbb{Z} given by the formula g(n) = n + 1 is a bijection. * Let A be the set of all 8\-bit strings that have exactly two `1` [bits](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Binary+digits+and+bitstrings) (for example `10100000`) and B the set of all 8\-bit strings that have exactly six `1` [bits](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Binary+digits+and+bitstrings) (like `00111111`). Then the function f: A \\rightarrow B that flips all `0` [bits](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Binary+digits+and+bitstrings) in the input to `1`s and vice versa, is a bijection. (Therefore there are exactly the same number of 8-bit strings with 2 `1` [bits](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Binary+digits+and+bitstrings) , as there are 8-bit strings with 6 `1` [bits](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Binary+digits+and+bitstrings) .) * Let S be any finite set with n elements, written as S = \\{a\_1, a\_2, a\_3, \\dots, a\_n\\}. If A \\in \\cal{P}(S) (meaning that A is a [subset](https://publish.obsidian.md/discretecs/Sets+and+Functions/Subset) of S) then let f(A) be the n\-bit string defined as follows: For each i from 1 to n, set the ith bit of the string equal to 0 if a\_i \\not \\in A and set it equal to 1 if a\_i \\in A. (For example if S = \\{a\_1, a\_2, a\_3, a\_4\\} then f(\\{a\_2, a\_3\\}) is `0110`.) This function is a bijection, and it tells us that the number of subsets of S is exactly the same as the number of n\-bit strings if S has n elements. Here are some non-examples: * The function shown below is not a bijection because it is not [injective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Injective) (although it is [surjective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Surjective) ): ![surj-not-inj.png](https://publish-01.obsidian.md/access/64d815ddc8215841f63db915c7923004/Assets/Images/surj-not-inj.png) * The function g: \\mathbb{Z} \\rightarrow \\mathbb{Z} given by the formula g(n) = 2n + 1 is _not_ a bijection because the function is not [surjective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Surjective) : There is no integer in the [domain](https://publish.obsidian.md/discretecs/Sets+and+Functions/Domain) that maps onto the number 2, for example. (That number would have to be n=1/2 but this is not in the [domain](https://publish.obsidian.md/discretecs/Sets+and+Functions/Domain) .) A bijection between sets does not always mean the sets have the same number of elements For _finite_ sets, if there is a bijection between the sets, then the sets have "the same number of elements". But if the sets are _infinite_, this need not be the case. Consider this example: Let f: \\mathbb{N} \\rightarrow \\mathbb{Z} be the function defined by the following rules: 1. If n is [odd](https://publish.obsidian.md/discretecs/Basic+math+concepts/Even+and+odd+integers) , then f(n) = n. 2. If n is [even](https://publish.obsidian.md/discretecs/Basic+math+concepts/Even+and+odd+integers) , then f(n) = -n/2. So f(0) = 0, f(1) = 1, f(2) = -1, f(3) = 3, f(4) = -3, and so on. This mapping is a bijective function because the function is [injective](https://publish.obsidian.md/discretecs/Sets+and+Functions/Injective) (no two inputs map to the same output) and because the function is surjective (given y \\in \\mathbb{Z}, if y is positive then y \\in \\mathbb{N} maps onto it; if y is negative then \-2y \\in \\mathbb{N} maps onto it). However clearly \\mathbb{N} and \\mathbb{Z} do not have "the same number of elements", since \\mathbb{N} is a proper [subset](https://publish.obsidian.md/discretecs/Sets+and+Functions/Subset) of \\mathbb{Z}. The notion of "the number of elements" in a set breaks down if the sets are infinite. Resources --------- [Screencast 3.11: Bijective functions](https://vimeo.com/614541763) from [Robert Talbert](https://vimeo.com/user132700952) on [Vimeo](https://vimeo.com/) . * Tutorial: [Bijective functions](https://byjus.com/maths/bijective-function) Bijective Not found This page does not exist Interactive graph On this page Definition Examples and Non-Examples Resources [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Adjacent - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions Basic math concepts Combinatorics Directed Graphs and Relations Graphs [Adjacent](https://publish.obsidian.md/discretecs/Graphs/Adjacent) [Bipartite graph](https://publish.obsidian.md/discretecs/Graphs/Bipartite+graph) [Brooks' Theorem](https://publish.obsidian.md/discretecs/Graphs/Brooks'+Theorem) [Chromatic index](https://publish.obsidian.md/discretecs/Graphs/Chromatic+index) [Chromatic number](https://publish.obsidian.md/discretecs/Graphs/Chromatic+number) [Clique number](https://publish.obsidian.md/discretecs/Graphs/Clique+number) [Complete graph](https://publish.obsidian.md/discretecs/Graphs/Complete+graph) [Connected graph](https://publish.obsidian.md/discretecs/Graphs/Connected+graph) [Cycle graph](https://publish.obsidian.md/discretecs/Graphs/Cycle+graph) [Degree](https://publish.obsidian.md/discretecs/Graphs/Degree) [Dijkstra's Algorithm](https://publish.obsidian.md/discretecs/Graphs/Dijkstra's+Algorithm) [Dirac's Theorem](https://publish.obsidian.md/discretecs/Graphs/Dirac's+Theorem) [Distance](https://publish.obsidian.md/discretecs/Graphs/Distance) [Eccentricity](https://publish.obsidian.md/discretecs/Graphs/Eccentricity) [Edge coloring](https://publish.obsidian.md/discretecs/Graphs/Edge+coloring) [Eulerian trail and circuit](https://publish.obsidian.md/discretecs/Graphs/Eulerian+trail+and+circuit) [Four Color Theorem](https://publish.obsidian.md/discretecs/Graphs/Four+Color+Theorem) [Graph](https://publish.obsidian.md/discretecs/Graphs/Graph) [Greedy coloring algorithm](https://publish.obsidian.md/discretecs/Graphs/Greedy+coloring+algorithm) [Hamiltonian path and circuit](https://publish.obsidian.md/discretecs/Graphs/Hamiltonian+path+and+circuit) [Handshake Lemma](https://publish.obsidian.md/discretecs/Graphs/Handshake+Lemma) [Isomorphism invariant](https://publish.obsidian.md/discretecs/Graphs/Isomorphism+invariant) [Isomorphism](https://publish.obsidian.md/discretecs/Graphs/Isomorphism) [Kuratowski's Theorem](https://publish.obsidian.md/discretecs/Graphs/Kuratowski's+Theorem) [Multigraph](https://publish.obsidian.md/discretecs/Graphs/Multigraph) [Ore's Theorem](https://publish.obsidian.md/discretecs/Graphs/Ore's+Theorem) [Path graph](https://publish.obsidian.md/discretecs/Graphs/Path+graph) [Paths](https://publish.obsidian.md/discretecs/Graphs/Paths) [Planar graph](https://publish.obsidian.md/discretecs/Graphs/Planar+graph) [Representations of graphs](https://publish.obsidian.md/discretecs/Graphs/Representations+of+graphs) [Spanning tree](https://publish.obsidian.md/discretecs/Graphs/Spanning+tree) [Subdivision](https://publish.obsidian.md/discretecs/Graphs/Subdivision) [Subgraph](https://publish.obsidian.md/discretecs/Graphs/Subgraph) [Vertex coloring](https://publish.obsidian.md/discretecs/Graphs/Vertex+coloring) [Vizing's Theorem](https://publish.obsidian.md/discretecs/Graphs/Vizing's+Theorem) [Weighted graph](https://publish.obsidian.md/discretecs/Graphs/Weighted+graph) Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Adjacent ======== aliases: - adjacent - incident - neighbor - neighbors tags: created: 2024-07-05 updated: * * * Definition ---------- Definition Two [vertices](https://publish.obsidian.md/discretecs/Graphs/Graph) v and w in a [graph](https://publish.obsidian.md/discretecs/Graphs/Graph) are said to be **adjacent** if they are the endpoints of an [edge](https://publish.obsidian.md/discretecs/Graphs/Graph) . We also say that v and w are **neighbors**. An [edge](https://publish.obsidian.md/discretecs/Graphs/Graph) in a [graph](https://publish.obsidian.md/discretecs/Graphs/Graph) is **incident** to a vertex if that vertex is one of its endpoints. Two edges are said to be **incident** to each other if they have an endpoint in common. Notes: * The word "incident" has two different uses: One to describe the relationship of an edge to a vertex, and another to describe the relationship between two edges. Be sure to be clear on the context when using that term. Examples and Non-Examples ------------------------- Consider this graph: ![degree-graph-example.png](https://publish-01.obsidian.md/access/64d815ddc8215841f63db915c7923004/Assets/Images/degree-graph-example.png) In this graph: * Vertices 1 and 2 are adjacent. So are vertices 2 and 6. But vertex 1 is _not_ adjacent to vertex 6. * The complete list of neighbors of vertex 3 is: 1,2,4,5. Vertex 3 is adjacent to all of these. But it is not adjacent to vertex 6. * The edge \\{2,5\\} is incident to vertices 2 and 5. In fact every edge is incident to its two endpoints -- and to no other vertices. * The edges \\{2,5\\} and \\{5,6\\} are incident with each other. But \\{2,5\\} is not incident with \\{1,3\\}. Adjacent Not found This page does not exist Interactive graph On this page Definition Examples and Non-Examples [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Clique number - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions Basic math concepts Combinatorics Directed Graphs and Relations Graphs [Adjacent](https://publish.obsidian.md/discretecs/Graphs/Adjacent) [Bipartite graph](https://publish.obsidian.md/discretecs/Graphs/Bipartite+graph) [Brooks' Theorem](https://publish.obsidian.md/discretecs/Graphs/Brooks'+Theorem) [Chromatic index](https://publish.obsidian.md/discretecs/Graphs/Chromatic+index) [Chromatic number](https://publish.obsidian.md/discretecs/Graphs/Chromatic+number) [Clique number](https://publish.obsidian.md/discretecs/Graphs/Clique+number) [Complete graph](https://publish.obsidian.md/discretecs/Graphs/Complete+graph) [Connected graph](https://publish.obsidian.md/discretecs/Graphs/Connected+graph) [Cycle graph](https://publish.obsidian.md/discretecs/Graphs/Cycle+graph) [Degree](https://publish.obsidian.md/discretecs/Graphs/Degree) [Dijkstra's Algorithm](https://publish.obsidian.md/discretecs/Graphs/Dijkstra's+Algorithm) [Dirac's Theorem](https://publish.obsidian.md/discretecs/Graphs/Dirac's+Theorem) [Distance](https://publish.obsidian.md/discretecs/Graphs/Distance) [Eccentricity](https://publish.obsidian.md/discretecs/Graphs/Eccentricity) [Edge coloring](https://publish.obsidian.md/discretecs/Graphs/Edge+coloring) [Eulerian trail and circuit](https://publish.obsidian.md/discretecs/Graphs/Eulerian+trail+and+circuit) [Four Color Theorem](https://publish.obsidian.md/discretecs/Graphs/Four+Color+Theorem) [Graph](https://publish.obsidian.md/discretecs/Graphs/Graph) [Greedy coloring algorithm](https://publish.obsidian.md/discretecs/Graphs/Greedy+coloring+algorithm) [Hamiltonian path and circuit](https://publish.obsidian.md/discretecs/Graphs/Hamiltonian+path+and+circuit) [Handshake Lemma](https://publish.obsidian.md/discretecs/Graphs/Handshake+Lemma) [Isomorphism invariant](https://publish.obsidian.md/discretecs/Graphs/Isomorphism+invariant) [Isomorphism](https://publish.obsidian.md/discretecs/Graphs/Isomorphism) [Kuratowski's Theorem](https://publish.obsidian.md/discretecs/Graphs/Kuratowski's+Theorem) [Multigraph](https://publish.obsidian.md/discretecs/Graphs/Multigraph) [Ore's Theorem](https://publish.obsidian.md/discretecs/Graphs/Ore's+Theorem) [Path graph](https://publish.obsidian.md/discretecs/Graphs/Path+graph) [Paths](https://publish.obsidian.md/discretecs/Graphs/Paths) [Planar graph](https://publish.obsidian.md/discretecs/Graphs/Planar+graph) [Representations of graphs](https://publish.obsidian.md/discretecs/Graphs/Representations+of+graphs) [Spanning tree](https://publish.obsidian.md/discretecs/Graphs/Spanning+tree) [Subdivision](https://publish.obsidian.md/discretecs/Graphs/Subdivision) [Subgraph](https://publish.obsidian.md/discretecs/Graphs/Subgraph) [Vertex coloring](https://publish.obsidian.md/discretecs/Graphs/Vertex+coloring) [Vizing's Theorem](https://publish.obsidian.md/discretecs/Graphs/Vizing's+Theorem) [Weighted graph](https://publish.obsidian.md/discretecs/Graphs/Weighted+graph) Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Clique number ============= aliases: - clique - Clique - clique number tags: - graphs created: 2024-09-23 updated: * * * Definition ---------- Definition A **clique** in a [graph](https://publish.obsidian.md/discretecs/Graphs/Graph) is a set of vertices which are all pairwise [adjacent](https://publish.obsidian.md/discretecs/Graphs/Adjacent) ; that is, it is a [subgraph](https://publish.obsidian.md/discretecs/Graphs/Subgraph) of the graph that is a copy of the [complete graph](https://publish.obsidian.md/discretecs/Graphs/Complete+graph) K\_n. The **clique number** of a graph is the largest n for which there is a clique of size n in the graph. Notes: * "Clique" is pronounced "CLEEK". * The common use of the term "clique" refers to a subgroup of people within a large group, and everyone in the subgroup knows everyone else in the subgroup. That is the same sense as what's meant in a graph. * A clique of size n is just a triangle. So, any graph that contains a triangle has a clique number at least (if not bigger than) 3. * The [chromatic number](https://publish.obsidian.md/discretecs/Graphs/Chromatic+number) of a graph must be greater than or equal to its clique number. Examples -------- The graph below has a clique of size 4 (consisting of of vertices 1, 6, 3, and 4) and several cliques of size 3 (for example, vertices 1, 3, and 4). ![clique4.png](https://publish-01.obsidian.md/access/64d815ddc8215841f63db915c7923004/Assets/Images/clique4.png) This graph does not have a clique of size 5, because in such a clique, each of the five vertices in the clique would have to have a [degree](https://publish.obsidian.md/discretecs/Graphs/Degree) at least 4 (since each vertex in the clique would be adjacent to all the other vertices in the clique and possibly others outside the clique). But, this graph has just three vertices of degree 4. Similarly there are no cliques of size 6, 7, 8, etc. Therefore the largest clique present has size 4, hence the graph's clique number is 4. Resources --------- Clique number Not found This page does not exist Interactive graph On this page Definition Examples Resources [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Chromatic index - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions Basic math concepts Combinatorics Directed Graphs and Relations Graphs [Adjacent](https://publish.obsidian.md/discretecs/Graphs/Adjacent) [Bipartite graph](https://publish.obsidian.md/discretecs/Graphs/Bipartite+graph) [Brooks' Theorem](https://publish.obsidian.md/discretecs/Graphs/Brooks'+Theorem) [Chromatic index](https://publish.obsidian.md/discretecs/Graphs/Chromatic+index) [Chromatic number](https://publish.obsidian.md/discretecs/Graphs/Chromatic+number) [Clique number](https://publish.obsidian.md/discretecs/Graphs/Clique+number) [Complete graph](https://publish.obsidian.md/discretecs/Graphs/Complete+graph) [Connected graph](https://publish.obsidian.md/discretecs/Graphs/Connected+graph) [Cycle graph](https://publish.obsidian.md/discretecs/Graphs/Cycle+graph) [Degree](https://publish.obsidian.md/discretecs/Graphs/Degree) [Dijkstra's Algorithm](https://publish.obsidian.md/discretecs/Graphs/Dijkstra's+Algorithm) [Dirac's Theorem](https://publish.obsidian.md/discretecs/Graphs/Dirac's+Theorem) [Distance](https://publish.obsidian.md/discretecs/Graphs/Distance) [Eccentricity](https://publish.obsidian.md/discretecs/Graphs/Eccentricity) [Edge coloring](https://publish.obsidian.md/discretecs/Graphs/Edge+coloring) [Eulerian trail and circuit](https://publish.obsidian.md/discretecs/Graphs/Eulerian+trail+and+circuit) [Four Color Theorem](https://publish.obsidian.md/discretecs/Graphs/Four+Color+Theorem) [Graph](https://publish.obsidian.md/discretecs/Graphs/Graph) [Greedy coloring algorithm](https://publish.obsidian.md/discretecs/Graphs/Greedy+coloring+algorithm) [Hamiltonian path and circuit](https://publish.obsidian.md/discretecs/Graphs/Hamiltonian+path+and+circuit) [Handshake Lemma](https://publish.obsidian.md/discretecs/Graphs/Handshake+Lemma) [Isomorphism invariant](https://publish.obsidian.md/discretecs/Graphs/Isomorphism+invariant) [Isomorphism](https://publish.obsidian.md/discretecs/Graphs/Isomorphism) [Kuratowski's Theorem](https://publish.obsidian.md/discretecs/Graphs/Kuratowski's+Theorem) [Multigraph](https://publish.obsidian.md/discretecs/Graphs/Multigraph) [Ore's Theorem](https://publish.obsidian.md/discretecs/Graphs/Ore's+Theorem) [Path graph](https://publish.obsidian.md/discretecs/Graphs/Path+graph) [Paths](https://publish.obsidian.md/discretecs/Graphs/Paths) [Planar graph](https://publish.obsidian.md/discretecs/Graphs/Planar+graph) [Representations of graphs](https://publish.obsidian.md/discretecs/Graphs/Representations+of+graphs) [Spanning tree](https://publish.obsidian.md/discretecs/Graphs/Spanning+tree) [Subdivision](https://publish.obsidian.md/discretecs/Graphs/Subdivision) [Subgraph](https://publish.obsidian.md/discretecs/Graphs/Subgraph) [Vertex coloring](https://publish.obsidian.md/discretecs/Graphs/Vertex+coloring) [Vizing's Theorem](https://publish.obsidian.md/discretecs/Graphs/Vizing's+Theorem) [Weighted graph](https://publish.obsidian.md/discretecs/Graphs/Weighted+graph) Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Chromatic index =============== aliases: - chromatic index tags: - graphs created: 2024-07-24 updated: * * * Definition ---------- Definition Given a [graph](https://publish.obsidian.md/discretecs/Graphs/Graph) G, the **chromatic index** of G is the minimum number of colors in any proper [edge coloring](https://publish.obsidian.md/discretecs/Graphs/Edge+coloring) of G. We denote the chromatic index of G by \\chi'(G). Notes: * \\chi is the Greek letter "chi", pronounced "Kie" (rhymes with "pie"). The symbol ' next to the \\chi is pronounced "prime". * The notation for chromatic index is similar to that of the [chromatic number](https://publish.obsidian.md/discretecs/Graphs/Chromatic+number) , which is the minimum number of colors in any [vertex coloring](https://publish.obsidian.md/discretecs/Graphs/Vertex+coloring) of G. Examples and Non-Examples ------------------------- For the [complete graph](https://publish.obsidian.md/discretecs/Graphs/Complete+graph) K\_4, the chromatic index is \\chi'(K\_4) = 3. Here is an [edge coloring](https://publish.obsidian.md/discretecs/Graphs/Edge+coloring) with 3 colors that implements this: ![k4-edge-color-3.png](https://publish-01.obsidian.md/access/64d815ddc8215841f63db915c7923004/Assets/Images/k4-edge-color-3.png) This example proves only that the chromatic index is _at most_ 3; by itself it does not rule out an [edge coloring](https://publish.obsidian.md/discretecs/Graphs/Edge+coloring) with fewer than three colors. However, in fact, an [edge coloring](https://publish.obsidian.md/discretecs/Graphs/Edge+coloring) of K\_4 with fewer than three colors is impossible, since each vertex has three edges [incident](https://publish.obsidian.md/discretecs/Graphs/Adjacent) with it, and each edge must receive a different color. Therefore the chromatic index is exactly 3. The chromatic index of C\_n, the [cycle graph](https://publish.obsidian.md/discretecs/Graphs/Cycle+graph) on n vertices, is 2 if n is [even](https://publish.obsidian.md/discretecs/Basic+math+concepts/Even+and+odd+integers) because we can just alternate colors as we go around the cycle. If n is odd, there is an extra edge in the cycle and therefore 3 colors are needed. Resources --------- Chromatic index Not found This page does not exist Interactive graph On this page Definition Examples and Non-Examples Resources Practice [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Chromatic number - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions Basic math concepts Combinatorics Directed Graphs and Relations Graphs [Adjacent](https://publish.obsidian.md/discretecs/Graphs/Adjacent) [Bipartite graph](https://publish.obsidian.md/discretecs/Graphs/Bipartite+graph) [Brooks' Theorem](https://publish.obsidian.md/discretecs/Graphs/Brooks'+Theorem) [Chromatic index](https://publish.obsidian.md/discretecs/Graphs/Chromatic+index) [Chromatic number](https://publish.obsidian.md/discretecs/Graphs/Chromatic+number) [Clique number](https://publish.obsidian.md/discretecs/Graphs/Clique+number) [Complete graph](https://publish.obsidian.md/discretecs/Graphs/Complete+graph) [Connected graph](https://publish.obsidian.md/discretecs/Graphs/Connected+graph) [Cycle graph](https://publish.obsidian.md/discretecs/Graphs/Cycle+graph) [Degree](https://publish.obsidian.md/discretecs/Graphs/Degree) [Dijkstra's Algorithm](https://publish.obsidian.md/discretecs/Graphs/Dijkstra's+Algorithm) [Dirac's Theorem](https://publish.obsidian.md/discretecs/Graphs/Dirac's+Theorem) [Distance](https://publish.obsidian.md/discretecs/Graphs/Distance) [Eccentricity](https://publish.obsidian.md/discretecs/Graphs/Eccentricity) [Edge coloring](https://publish.obsidian.md/discretecs/Graphs/Edge+coloring) [Eulerian trail and circuit](https://publish.obsidian.md/discretecs/Graphs/Eulerian+trail+and+circuit) [Four Color Theorem](https://publish.obsidian.md/discretecs/Graphs/Four+Color+Theorem) [Graph](https://publish.obsidian.md/discretecs/Graphs/Graph) [Greedy coloring algorithm](https://publish.obsidian.md/discretecs/Graphs/Greedy+coloring+algorithm) [Hamiltonian path and circuit](https://publish.obsidian.md/discretecs/Graphs/Hamiltonian+path+and+circuit) [Handshake Lemma](https://publish.obsidian.md/discretecs/Graphs/Handshake+Lemma) [Isomorphism invariant](https://publish.obsidian.md/discretecs/Graphs/Isomorphism+invariant) [Isomorphism](https://publish.obsidian.md/discretecs/Graphs/Isomorphism) [Kuratowski's Theorem](https://publish.obsidian.md/discretecs/Graphs/Kuratowski's+Theorem) [Multigraph](https://publish.obsidian.md/discretecs/Graphs/Multigraph) [Ore's Theorem](https://publish.obsidian.md/discretecs/Graphs/Ore's+Theorem) [Path graph](https://publish.obsidian.md/discretecs/Graphs/Path+graph) [Paths](https://publish.obsidian.md/discretecs/Graphs/Paths) [Planar graph](https://publish.obsidian.md/discretecs/Graphs/Planar+graph) [Representations of graphs](https://publish.obsidian.md/discretecs/Graphs/Representations+of+graphs) [Spanning tree](https://publish.obsidian.md/discretecs/Graphs/Spanning+tree) [Subdivision](https://publish.obsidian.md/discretecs/Graphs/Subdivision) [Subgraph](https://publish.obsidian.md/discretecs/Graphs/Subgraph) [Vertex coloring](https://publish.obsidian.md/discretecs/Graphs/Vertex+coloring) [Vizing's Theorem](https://publish.obsidian.md/discretecs/Graphs/Vizing's+Theorem) [Weighted graph](https://publish.obsidian.md/discretecs/Graphs/Weighted+graph) Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Chromatic number ================ aliases: - chromatic number tags: - graphs created: 2024-07-24 updated: * * * Definition ---------- Definition The **chromatic number** of a [graph](https://publish.obsidian.md/discretecs/Graphs/Graph) G is the minimum number of colors in any proper [vertex coloring](https://publish.obsidian.md/discretecs/Graphs/Vertex+coloring) of G. The chromatic number of G is denoted \\chi(G). Notes * \\chi is the Greek letter "chi", pronounced "Kie" (rhymes with "pie"). * A given graph can have many different possible proper [colorings](https://publish.obsidian.md/discretecs/Graphs/Vertex+coloring) ; for example we can just assign a different color to each vertex. But there is only one minimum number of colors needed for a proper coloring, and that number is \\chi(G). * The [greedy graph coloring](https://publish.obsidian.md/discretecs/Graphs/Greedy+coloring+algorithm) algorithm can, but does not always produce the minimum coloring. Examples -------- **Example 1 -- Complete graphs** The chromatic number of K\_3, the [complete graph](https://publish.obsidian.md/discretecs/Graphs/Complete+graph) on three vertices, is 3. Since each vertex is [adjacent](https://publish.obsidian.md/discretecs/Graphs/Adjacent) to the other two, three colors are necessary for a proper coloring, and two colors are not enough: ![colored-k3.png](https://publish-01.obsidian.md/access/64d815ddc8215841f63db915c7923004/Assets/Images/colored-k3.png) By extension, \\chi(K\_n) = n (where K\_n is the [complete graph](https://publish.obsidian.md/discretecs/Graphs/Complete+graph) on n vertices) for every positive [integer](https://publish.obsidian.md/discretecs/Computer+Arithmetic/Integers) n, since each vertex is [adjacent](https://publish.obsidian.md/discretecs/Graphs/Adjacent) to the remaining n-1 vertices. Chromatic number Not found This page does not exist Interactive graph On this page Definition Examples Resources Practice [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Bipartite graph - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions Basic math concepts Combinatorics Directed Graphs and Relations Graphs [Adjacent](https://publish.obsidian.md/discretecs/Graphs/Adjacent) [Bipartite graph](https://publish.obsidian.md/discretecs/Graphs/Bipartite+graph) [Brooks' Theorem](https://publish.obsidian.md/discretecs/Graphs/Brooks'+Theorem) [Chromatic index](https://publish.obsidian.md/discretecs/Graphs/Chromatic+index) [Chromatic number](https://publish.obsidian.md/discretecs/Graphs/Chromatic+number) [Clique number](https://publish.obsidian.md/discretecs/Graphs/Clique+number) [Complete graph](https://publish.obsidian.md/discretecs/Graphs/Complete+graph) [Connected graph](https://publish.obsidian.md/discretecs/Graphs/Connected+graph) [Cycle graph](https://publish.obsidian.md/discretecs/Graphs/Cycle+graph) [Degree](https://publish.obsidian.md/discretecs/Graphs/Degree) [Dijkstra's Algorithm](https://publish.obsidian.md/discretecs/Graphs/Dijkstra's+Algorithm) [Dirac's Theorem](https://publish.obsidian.md/discretecs/Graphs/Dirac's+Theorem) [Distance](https://publish.obsidian.md/discretecs/Graphs/Distance) [Eccentricity](https://publish.obsidian.md/discretecs/Graphs/Eccentricity) [Edge coloring](https://publish.obsidian.md/discretecs/Graphs/Edge+coloring) [Eulerian trail and circuit](https://publish.obsidian.md/discretecs/Graphs/Eulerian+trail+and+circuit) [Four Color Theorem](https://publish.obsidian.md/discretecs/Graphs/Four+Color+Theorem) [Graph](https://publish.obsidian.md/discretecs/Graphs/Graph) [Greedy coloring algorithm](https://publish.obsidian.md/discretecs/Graphs/Greedy+coloring+algorithm) [Hamiltonian path and circuit](https://publish.obsidian.md/discretecs/Graphs/Hamiltonian+path+and+circuit) [Handshake Lemma](https://publish.obsidian.md/discretecs/Graphs/Handshake+Lemma) [Isomorphism invariant](https://publish.obsidian.md/discretecs/Graphs/Isomorphism+invariant) [Isomorphism](https://publish.obsidian.md/discretecs/Graphs/Isomorphism) [Kuratowski's Theorem](https://publish.obsidian.md/discretecs/Graphs/Kuratowski's+Theorem) [Multigraph](https://publish.obsidian.md/discretecs/Graphs/Multigraph) [Ore's Theorem](https://publish.obsidian.md/discretecs/Graphs/Ore's+Theorem) [Path graph](https://publish.obsidian.md/discretecs/Graphs/Path+graph) [Paths](https://publish.obsidian.md/discretecs/Graphs/Paths) [Planar graph](https://publish.obsidian.md/discretecs/Graphs/Planar+graph) [Representations of graphs](https://publish.obsidian.md/discretecs/Graphs/Representations+of+graphs) [Spanning tree](https://publish.obsidian.md/discretecs/Graphs/Spanning+tree) [Subdivision](https://publish.obsidian.md/discretecs/Graphs/Subdivision) [Subgraph](https://publish.obsidian.md/discretecs/Graphs/Subgraph) [Vertex coloring](https://publish.obsidian.md/discretecs/Graphs/Vertex+coloring) [Vizing's Theorem](https://publish.obsidian.md/discretecs/Graphs/Vizing's+Theorem) [Weighted graph](https://publish.obsidian.md/discretecs/Graphs/Weighted+graph) Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Bipartite graph =============== aliases: - bipartite - Bipartite - bipartite graph - complete bipartite graph - complete bipartite - Complete bipartite tags: - graphs created: 2024-07-24 updated: * * * Definition ---------- Definition A [graph](https://publish.obsidian.md/discretecs/Graphs/Graph) G = (V,E) is **bipartite** if we can partition the [vertex](https://publish.obsidian.md/discretecs/Graphs/Graph) set V into two nonempty, [disjoint](https://publish.obsidian.md/discretecs/Sets+and+Functions/Intersection) [sets](https://publish.obsidian.md/discretecs/Sets+and+Functions/Set) , say X and Y, such that every [edge](https://publish.obsidian.md/discretecs/Graphs/Graph) of the graph has exactly one [endpoint](https://publish.obsidian.md/discretecs/Graphs/Graph) in X and one endpoint in Y. A bipartite graph in which each vertex in one of the partitions is [adjacent](https://publish.obsidian.md/discretecs/Graphs/Adjacent) to _every_ vertex in the other partition, is called a **complete bipartite graph**. For a complete bipartite graph, if one of the partitions has n vertices and the other has m, we denote it K\_{n,m}. Examples -------- The graph below is bipartite, with the partitions separated into red/numbers and blue/letters: ![bipartite1.png](https://publish-01.obsidian.md/access/64d815ddc8215841f63db915c7923004/Assets/Images/bipartite1.png) It is bipartite because every edge has one endpoint in one of the partitions and the other endpoint in the other partition. However it is not a _complete_ bipartite graph because there are vertices in one partition that are not [adjacent](https://publish.obsidian.md/discretecs/Graphs/Adjacent) to every vertex in the other. For example vertex 1 is not [adjacent](https://publish.obsidian.md/discretecs/Graphs/Adjacent) to vertex B. In fact, none of the vertices in the red/upper partition is connected to _all_ vertices in the blue/lower one. The complete bipartite version of the graph above is denoted K\_{4,5} since there are 4 vertices in one partition and 5 in the other, and it looks like this (the vertices are relabeled and the graph is "sideways" but it is [isomorphic](https://publish.obsidian.md/discretecs/Graphs/Isomorphism) to the first one): ![bipartite2.png](https://publish-01.obsidian.md/access/64d815ddc8215841f63db915c7923004/Assets/Images/bipartite2.png) The complete bipartite graph K\_{3,3} is frequently encountered in discrete mathematics as an example or [counterexample](https://publish.obsidian.md/discretecs/Logic/Counterexample) of different properties: ![k33-colored.png](https://publish-01.obsidian.md/access/64d815ddc8215841f63db915c7923004/Assets/Images/k33-colored.png) For example, K\_{3,3} is one of the simplest examples of a non-[planar](https://publish.obsidian.md/discretecs/Graphs/Planar+graph) graph. Bipartite graph Not found This page does not exist Interactive graph On this page Definition Examples Resources [Powered by Obsidian Publish](https://publish.obsidian.md/) --- # Brooks' Theorem - Discrete Structures for Computer Science - Obsidian Publish [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) [START HERE](https://publish.obsidian.md/discretecs/START+HERE) Computer Arithmetic Logic Sets and Functions Basic math concepts Combinatorics Directed Graphs and Relations Graphs [Adjacent](https://publish.obsidian.md/discretecs/Graphs/Adjacent) [Bipartite graph](https://publish.obsidian.md/discretecs/Graphs/Bipartite+graph) [Brooks' Theorem](https://publish.obsidian.md/discretecs/Graphs/Brooks'+Theorem) [Chromatic index](https://publish.obsidian.md/discretecs/Graphs/Chromatic+index) [Chromatic number](https://publish.obsidian.md/discretecs/Graphs/Chromatic+number) [Clique number](https://publish.obsidian.md/discretecs/Graphs/Clique+number) [Complete graph](https://publish.obsidian.md/discretecs/Graphs/Complete+graph) [Connected graph](https://publish.obsidian.md/discretecs/Graphs/Connected+graph) [Cycle graph](https://publish.obsidian.md/discretecs/Graphs/Cycle+graph) [Degree](https://publish.obsidian.md/discretecs/Graphs/Degree) [Dijkstra's Algorithm](https://publish.obsidian.md/discretecs/Graphs/Dijkstra's+Algorithm) [Dirac's Theorem](https://publish.obsidian.md/discretecs/Graphs/Dirac's+Theorem) [Distance](https://publish.obsidian.md/discretecs/Graphs/Distance) [Eccentricity](https://publish.obsidian.md/discretecs/Graphs/Eccentricity) [Edge coloring](https://publish.obsidian.md/discretecs/Graphs/Edge+coloring) [Eulerian trail and circuit](https://publish.obsidian.md/discretecs/Graphs/Eulerian+trail+and+circuit) [Four Color Theorem](https://publish.obsidian.md/discretecs/Graphs/Four+Color+Theorem) [Graph](https://publish.obsidian.md/discretecs/Graphs/Graph) [Greedy coloring algorithm](https://publish.obsidian.md/discretecs/Graphs/Greedy+coloring+algorithm) [Hamiltonian path and circuit](https://publish.obsidian.md/discretecs/Graphs/Hamiltonian+path+and+circuit) [Handshake Lemma](https://publish.obsidian.md/discretecs/Graphs/Handshake+Lemma) [Isomorphism invariant](https://publish.obsidian.md/discretecs/Graphs/Isomorphism+invariant) [Isomorphism](https://publish.obsidian.md/discretecs/Graphs/Isomorphism) [Kuratowski's Theorem](https://publish.obsidian.md/discretecs/Graphs/Kuratowski's+Theorem) [Multigraph](https://publish.obsidian.md/discretecs/Graphs/Multigraph) [Ore's Theorem](https://publish.obsidian.md/discretecs/Graphs/Ore's+Theorem) [Path graph](https://publish.obsidian.md/discretecs/Graphs/Path+graph) [Paths](https://publish.obsidian.md/discretecs/Graphs/Paths) [Planar graph](https://publish.obsidian.md/discretecs/Graphs/Planar+graph) [Representations of graphs](https://publish.obsidian.md/discretecs/Graphs/Representations+of+graphs) [Spanning tree](https://publish.obsidian.md/discretecs/Graphs/Spanning+tree) [Subdivision](https://publish.obsidian.md/discretecs/Graphs/Subdivision) [Subgraph](https://publish.obsidian.md/discretecs/Graphs/Subgraph) [Vertex coloring](https://publish.obsidian.md/discretecs/Graphs/Vertex+coloring) [Vizing's Theorem](https://publish.obsidian.md/discretecs/Graphs/Vizing's+Theorem) [Weighted graph](https://publish.obsidian.md/discretecs/Graphs/Weighted+graph) Proof Recursion Trees [](https://publish.obsidian.md/discretecs/START+HERE) [Discrete Structures for Computer Science](https://publish.obsidian.md/discretecs/START+HERE) Brooks' Theorem =============== aliases: tags: - graphs created: 2024-07-24 updated: * * * Definition ---------- Definition **Brooks' Theorem** states that any [graph](https://publish.obsidian.md/discretecs/Graphs/Graph) G satisfies the inequality \\chi(G) \\leq \\Delta(G) where \\chi(G) is the graph's [chromatic number](https://publish.obsidian.md/discretecs/Graphs/Chromatic+number) and \\Delta(G) is its [maximum degree](https://publish.obsidian.md/discretecs/Graphs/Degree) , unless G is a [complete graph](https://publish.obsidian.md/discretecs/Graphs/Complete+graph) or an [odd](https://publish.obsidian.md/discretecs/Basic+math+concepts/Even+and+odd+integers) [cycle](https://publish.obsidian.md/discretecs/Graphs/Paths) , in which case \\chi(G) = \\Delta(G) + 1. Notes: * Brooks' Theorem is useful as a way to place an upper bound on the [chromatic number](https://publish.obsidian.md/discretecs/Graphs/Chromatic+number) of a graph, or in the case of a [complete graph](https://publish.obsidian.md/discretecs/Graphs/Complete+graph) or [odd](https://publish.obsidian.md/discretecs/Basic+math+concepts/Even+and+odd+integers) [cycle](https://publish.obsidian.md/discretecs/Graphs/Paths) to compute the [chromatic number](https://publish.obsidian.md/discretecs/Graphs/Chromatic+number) outright. * Brooks' Theorem is similar to but different than [Vizing's Theorem](https://publish.obsidian.md/discretecs/Graphs/Vizing's+Theorem) which is a [theorem](https://publish.obsidian.md/discretecs/Logic/Theorem) about [edge coloring](https://publish.obsidian.md/discretecs/Graphs/Edge+coloring) . Examples -------- Consider this graph G with 10 [vertices](https://publish.obsidian.md/discretecs/Graphs/Graph) and 15 [edges](https://publish.obsidian.md/discretecs/Graphs/Graph) : ![random-graph-723.png](https://publish-01.obsidian.md/access/64d815ddc8215841f63db915c7923004/Assets/Images/random-graph-723.png) By visual inspection, \\Delta(G) = 6. Brooks' Theorem would say that \\chi(G) \\leq 6 since this graph is clearly not a [complete graph](https://publish.obsidian.md/discretecs/Graphs/Complete+graph) or an [odd](https://publish.obsidian.md/discretecs/Basic+math+concepts/Even+and+odd+integers) [cycle](https://publish.obsidian.md/discretecs/Graphs/Paths) . Also note that the [chromatic number](https://publish.obsidian.md/discretecs/Graphs/Chromatic+number) must be _at least_ 3, since there are copies of K\_3 (a triangle) in the graph and at least three different colors are needed to color each copy. Therefore we know from this information alone that 3 \\leq \\chi(G) \\leq 6. In fact the actual [chromatic number](https://publish.obsidian.md/discretecs/Graphs/Chromatic+number) is exactly 3, as seen directly from this 3-[coloring](https://publish.obsidian.md/discretecs/Graphs/Vertex+coloring) : ![random-graph723-color.png](https://publish-01.obsidian.md/access/64d815ddc8215841f63db915c7923004/Assets/Images/random-graph723-color.png) Resources --------- Brooks' Theorem Not found This page does not exist Interactive graph On this page Definition Examples Resources [Powered by Obsidian Publish](https://publish.obsidian.md/) ---