This tag is for basic questions about the study of finite or countable discrete structures — specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions. ...

learn more… | top users | synonyms (5)

0
votes
2answers
22 views

Find a probability of $L_\sigma(A) = F_\sigma(B)$

We are given set $\{1, 2, \dots n\}$ and some random permutation $\sigma$ of that set. Sets $A, B \subseteq \{1, 2, \dots n\}$ and |$A \cap B| = 1$ and $|A| = |B| = k$ We define $L_\sigma(A)$ as the ...
1
vote
1answer
42 views

Maximal number of colours in a palette that allows for fewer than 500 mixtures

An artist is planning on mixing together any number of different colours from her palette. A mixture results as long as the artist combines at least two colours. If the number of possible mixtures is ...
2
votes
2answers
732 views

Puzzle, Permutation and Combination problem?

I have a puzzle here: There are five colored balls: 2 green, 2 blue and 1 yellow Rule 1: All balls of the same color must be adjacent to each other. I wrote a program to find all the ...
0
votes
2answers
29 views

Combinatorics (discrete math course) help

problem 1: you have 4 balls with different weights and 6 drawers stacked on top of each other. how many ways are there to organize the balls such that the top drawer will have exactly 1 ball and the ...
0
votes
0answers
24 views

Number of sock combinations with limited information

Suppose in your sock drawer of 14 socks there are 5 different colors and 3 different lengths present. One day, you decide you want to wear two socks that have both different colors and different ...
0
votes
0answers
28 views

questions related to derangement

Six cards and six envelopes are numbered 1, 2, 3, 4, 5, 6 and cards are to be placed in envelopes so that each envelope contains exactly one card and no card is placed in the envelope bearing the same ...
-1
votes
2answers
23 views

How many groups consisting of 4 members can be made with b,c,d if they can be repeated?

How many groups of b,c and d can I make if they can be repeated? Eg. {bbcd},{bbcc},{cdcc},{cccc} etc. Pls specify the no.of b's in a specific kind of group such as {bbdc} has two b's
0
votes
1answer
25 views

How prove this $n$ smaller cubes ( length is $1,2,3,\cdots,n$) can't Mosaic a big cube

Question: Show that: for any postive integer $n(n\ge 2)$, there are $n$ cubes ( length is $1,2,3,\cdots,n$) can't Mosaic a big cube This is answer it is clear when $n=2,3$. .But I can't ...
0
votes
1answer
17 views

Please help. (SDR) [on hold]

Let A=(A1,A2,......,An) be a family of sets with an SDR. Let x be an element of A1. Prove that there is an SDR containing x, but show by example that it may not be possible to find an SDR in which x ...
0
votes
2answers
40 views

How to find sum of $n$ terms of $3C_1+7C_2+11C_3+\cdots$

let $n\in \mathbb N$ be fixed and let $0\leq k\leq n$ Let $C_k$ denote number of ways of choosing $k$ objects from n distinct objects. How to find sum of $n$ terms of $$3C_1+7C_2+11C_3+\cdots$$ I ...
0
votes
1answer
22 views

How to determine whether the following sets are countable:

How to determine whether the following sets are countable: i.collection of all finite subsets of $\mathbb N$ ii.the collection of all functions from $\mathbb N$ to $\mathbb R$ iii.collection of all ...
1
vote
2answers
39 views

Combinations of fruits and their “nutrients”

As a computer scientist and not a mathematician, I know not some of the formal language to describe my problem, so I'll present it in a word problem form. Maybe someone can help me hone my search and ...
2
votes
0answers
22 views

Split Question: Bergelson Multiplicative Density of “Even-like” sets

This post splits the post: Questions about Bergelson multiplicative upper density into one more concentrated series of questions. It is largely copied directly. Let $\mathbb{P} \subset \mathbb{N}$ ...
1
vote
0answers
28 views

is configuration space an H-space?

Let $X$ be a manifold. Let $F(X,n)$ be the configuration space of order $n$. Let $B(X,n)=F(X,n)/\Sigma_n$ be the unordered configuration space of order $n$. Is $B(X,n)$ an H-space? Under what ...
2
votes
2answers
46 views

Number of 8 character passwords including numbers and letters without repetition

A password must be created with 8 characters. It can use number or letters, but they cannot be repeated (and letters are not case sensitive so we have only 36 characters). How many passwords are ...
1
vote
2answers
34 views

Select four teams of 9 from 36

I am struggling to understand a type of combinatorics problem where we are dealing with multiple groupings. Through applying another example, I've come up with the following but I don't fully ...
0
votes
2answers
17 views

Permutation Question Help

Hexadecimal numbers are made using the sixteen digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. They are denoted by the subscript 16. For example, 9A2D$_{16}$ and BC54$_{16}$ are ...
1
vote
2answers
255 views

Probability of picking specific balls

Suppose I have $20$ red balls in one box and $20$ blue balls in another box. There $12$ red balls and $7$ blue balls have stars on them. I randomly take out one red ball and one blue ball at each ...
13
votes
3answers
934 views

Baby Shower Problem. Too hard for 1st grader but got parents thinking

So our six year old son comes home from 1st grade with the following math puzzle. Your Aunt is having a baby. You have created a party game for a baby shower. It is called pick the gender. You ...
8
votes
1answer
288 views

Bipartite graph: how many closed walk with given properties

Let be $G=(U,V,E)$ a bipartite graph where $U$ has $K$ possible vertices and $V$ has $N$ possible vertices. We focus on closed walks of length $2L$. Such walks can be described by the sequence of ...
1
vote
0answers
20 views

Prove that if there are $2n$ points and $n^2+1$ straight lines connecting them, then there are at least $n$ triangles in this shape.

Proof by induction. For $n=2$, it says that if we have $2(2)=4$ points and $2^2+1=5$ lines connecting them to each other, then there are at least 2 triangles in this shape. Which is true (shown ...
0
votes
1answer
286 views

I need a formula for how many ways I can choose k balls (two balls each time from the same box) from n boxes?

We have n (can take any value 1,2,3,...) boxes each has the same number of distinct marbles, say b marbles, so the total number of marbles S=n*b. we can choose marbles from boxes with the following ...
1
vote
2answers
28 views

Probability that this stamp is one that you haven't seen before

Suppose you have 4 stamps with probabilities 0.2, 0.4, 0.3, and 0.1, respectively. Each time you pick a stamp is independent of every other pick. Suppose you pick your 10th stamp. What is the ...
1
vote
1answer
27 views

Do complete graphs maximize the number of triangles?

Let $G$ be a graph with $a\choose 2$ edges (and an arbitrary number of vertices). Is it true that it has at most $a\choose 3$ triangles? Context: this continues the question Number of triangles in a ...
1
vote
2answers
55 views

number of ways you can partition a string into substrings of certain length

Hi I am trying to teach myself combinatorics, and cannot figure out an expression number of ways you can partition a string of length $n$ into sub-strings of length at most $r$. Any help would be ...
1
vote
3answers
53 views

Counting and Probability Problem

The question I am having trouble with is how many permutations of six letters{A,B,C,D,E,F} are there that contains neither "BAD" nor "DEF" patterns. My plan for solving this would be to find the ...
0
votes
1answer
23 views

what is the probability that the real estate agent can get into specific home ???

A real estate agent has 8 master keys to open several new home. Only 1 master key will open any given house. If 40% of the homes are usually left unlocked what is the probability that the real estate ...
1
vote
0answers
34 views

Trying to understand a strange regularity found for a ratio of repeated products

I was considering an alternate simplification of $\binom {2 n} {n} $ by pairing the components of one of the denominator factorials with the even terms in the numerator and pairing the other ...
0
votes
1answer
26 views

How many different ways can a student check off one answer to each question?

If a multiple-choice test consists of 6 questions each with 4 possible answers of which only 1 is correct, In how many different ways can a student check off one answer to each question ?
1
vote
2answers
39 views

Finding the generating function of a series with a binomial coefficient and a exponential coefficient

So I am given this series $$2^8, 2^7 \binom{8}{1}, 2^6 \binom{8}{2}, 2^5 \binom{8}{3}, 2^4 \binom{8}{4}, 2^3 \binom{8}{5}, 2^2 \binom{8}{6}, 2^1 \binom{8}{7}, \binom{8}{8}, 0, 0, 0, 0, ...$$ which I ...
1
vote
1answer
45 views

Elementary combinatorics problem: which answer is the right one?

In how many ways can the sequence of the natural numbers from 1 to 10 be ordered if: 1) each sequence starts with $ 1 $ 2) the absolute value of the difference of two successive terms in the ...
0
votes
0answers
26 views

why Petersen graph has exactly six perfect matching? [on hold]

Must I find all six matching and show, that there cannot be more? I know, that all cubic graphs have at least 5 matching.
0
votes
0answers
31 views

How many 4 digits prime numbers can be formed from 0,1,…,9 without repeated digits?

I'm just curious about the prime numbers in combinatorics. Can we use the combinatorics rule to find the number of prime number from given number, for example from the above condition? My attempt: I ...
1
vote
3answers
352 views

Pigeonhole Principle Question - Group of 6 people, do 3 either know each other or not?

Prove that in any group of 6 people there are always at least 3 people who either all know one-another or all are strangers to one-another. Hint: Use the pigeonhole principle. I don't see how this ...
4
votes
1answer
316 views

What is the number of ways to divide a rectangle into $n$ smaller rectangles line by line?

The original problem was to consider how many ways to make a wiring diagram out of $n$ resistors. When I thought about this I realized that if you can only connect in series and shunt. - Then this is ...
2
votes
1answer
48 views

Show that $\sum_{i=1}^{r} i^2 = \binom{r+1}{3} + \binom{r+2}{3}$ by finding generating function

Find the generating function for the sequence $c_r$ where $c_0 = 0$ and $ c_r = \sum_{i=1}^{r} i^2 $ for $r \in \mathbb N$. Hence show that $\sum_{i=1}^{r} i^2 = \binom{r+1}{3} + \binom{r+2}{3}$ ...
1
vote
1answer
64 views

Is this probabilistic balls-and-bins problem well-defined and is my solution correct?

Problem definition: There are $n$ bins, labeled with $1, 2, \ldots, n$. Let $X_i$ be a random variable denoting the number of balls contained in the $i$-th bin. The collection of random variables ...
0
votes
1answer
32 views

Monochromatic Solutions

I recently came across this paper: http://borisalexeev.com/pdf/foxgraham.pdf "On Minimal Colorings Without Monochromatic Solutions To a Linear Equation" Can someone explain in clearer terms what ...
0
votes
0answers
30 views

How many first neighbors does a node whose degree is known in an undirected graph have?

Consider a graph $\mathcal{G} = \left(V,E\right)$ with vertices (nodes) $V$ and undirected connections between them $E$. If I know the degree of the $i$th node, $d\left(i\right) = k$, and the ...
1
vote
3answers
124 views

A common problem in Combinatorial Analysis

Please help me prove the fact below: $$ \sum_{n=1}^N \frac{N!}{n!(N-n)!}\frac{(-1)^{n-1}n}{n+x} = \frac{N!}{\prod_{n=1}^N (n+x)}. $$ I think this problem is common, but it is really hard for me to ...
1
vote
1answer
15 views

How are inclusion-wise maximal and minimal sets defined?

I have tried to find them over the internet, but am lacking a resource that rigorously defines these two terms.
0
votes
2answers
17 views

Counting number of ways in poker game

What is the total number of ways in which the poker hand is full of house that is you have to pick 5 cards out of 52 cards such that it contains exactly 3 cards with the same value. Example a card ...
2
votes
1answer
274 views

Probability question involving sets of cards

I have an infinite deck built out of sets of 10 cards (in other words 10*n cards). The sets are identical so one '2' is identical to another '2'. A player draws 6 cards. If he draws: any '1' AND a ...
0
votes
1answer
41 views

Can you find the number of people at this party?

At a party everyone was shaking hands with others. In all, there were 66 handshakes. Now find the number of people at this party. Note:- You may choose to read the solution below.
-2
votes
0answers
18 views

Identities involving binomial coeffcient [duplicate]

Show that $\binom{k}{k}+\binom{k+1}{k}+\binom{k+2}{k}+ \cdots +\binom{n}{k}=\binom{n+1}{k+1}$ for all natural numbers $k\leq n$.
3
votes
3answers
128 views

Number of ways to get a total of 14 when tossing a die 3 times

Each of the 3 boys tosses a die once. Find the number of ways for them to get a total of 14. I'm trying to solve it by forming this equation, $$x_1 + x_2 + x_3 = 14$$ where $1\leq x_i\leq 6$ for ...
-3
votes
1answer
28 views

Permutations and image of numbers [closed]

How can I solve this? How many is permutations of the numbers 1,...,10 in which no even number maps to itself. Thanks
0
votes
0answers
22 views

Find a closed form for the expression [closed]

Let $B$ be a finite set. I need to find a closed form for $\sum_{A \subseteq B} \alpha^{|A|}$
-2
votes
1answer
22 views

An urn contains 15 balls ,8 pf which are red and 7 are blue .in how many ways 7 balls are to be choosen so that atleast 5 are red

An urn contains 15 balls ,8 pf which are red and 7 are blue .in how many ways 7 balls are to be choosen so that atleast 5 are red. please solve this question on combinations
0
votes
1answer
42 views

What is $\Gamma(a)$?

I'm reading Van Lint's Course in Combinatorics: He mentions $\Gamma(a)$ in this text but I'm not really sure of what it means and I'm also afraid of assume something wrong, at first thought I ...