For 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 (4)

7
votes
1answer
622 views

Number of binary $M\times N$ matrices with even row sums, even col sums and $K$ ones, $K$ even

A combinatorial problem arising with certain checksums: When sending messages, the user data are protected by adding a parity bit for bit positions $1\dots8$ and a parity bit for each byte. So, the ...
1
vote
1answer
144 views

Combinatorics of the coupon collector's problem

I have a set of N numbers. How many possible M-combinations - with M > N - of the N numbers are there which contain every number at least once? Example: Numbers {1,2} and hence N = 2 and M be 3. ...
1
vote
1answer
42 views

Constructing function for set enumeration

Let $X$ be a set of non-negative integers. Let $X^i$ denote $i$-th cartesian power of set $X$. Let $X^* = \bigcup\limits_{i=1}^\inf X^i$, i.e. all possible combinations of $X$'s elements. Let ...
1
vote
3answers
5k views

A bowl contains 10 red balls and 10 blue balls, A women selects ball at random without looking?

How can we solve this question ? A bowl contains $10$ red balls and $10$ blue balls, and a women picks up balls from the bowl, at random, without looking. A) How many balls must she pickup in ...
1
vote
1answer
110 views

Is there a Pigeon hole principle proof

Let $a_i$, $1 \leq i \leq 5$ denote five positive real numbers such that $\sum_{i =1}^{5}a_i = 100$. Show that there exist a pair $a_i,a_j$ such that $|a_i-a_j|\leq 10$. Is there a proof using pigeon ...
2
votes
4answers
79 views

Combination question?

I have question it is a practise question for my textbook. You are given $5$ books and $7$ bookshelves. How many ways are there to place these books on the shelves? (Order matters). I checked the ...
0
votes
0answers
56 views

Using Binomial Theorem to show that (-1)^k C(n,k) [duplicate]

I came across this question on my text book and i didn't know how to prove it. Use the Binomial Theorem to show that $$ 0=\sum_{k=0}^n \ (-1)^ {k} C(n,k)$$
2
votes
4answers
932 views

How to tell if two matrices are equal up to a permutation

Given two real rectangular matrices A, B how can I tell if they are equal up to a permutation of their rows/column without trying all possible permutations? (This is closely related to the question I ...
2
votes
2answers
83 views

Placing $4$ numbers on (-1,1) following some conditions!

I want to place 4 numbers, call them $A,B,C$ and $D$ on (-1,1) subject to the following conditions: (1) $A>B>0>C>D$ i.e. $A$ and $B$ are positive (with $A>B$) while $C$ and $D$ are ...
1
vote
1answer
75 views

How can you show that $\binom {n}{7}=\sum_{k=7}^n \binom {k-1} {6}$? [duplicate]

How can you show that $\binom {n}{7}=\sum_{k=7}^n \binom {k-1} {6}$? This counts the number of subsets from $\{1,2,3,\dots,n\}$ having size $7$. To me, the summation part counts subsets of size ...
1
vote
1answer
92 views

About antichain proof

Given that the set S which has odd number of elements, is there any special way to prove that there are exactly two antichains length of $\binom{n}{\lfloor n/2 \rfloor}$? For example, for ...
1
vote
2answers
52 views

Mary needs to go to work [duplicate]

This was on my combinatorics exam. I definitely didn't answer it correctly, but I'll explain what I did. Mary has to go to work or some bs. She needs to travel 6 blocks east and 7 blocks north. How ...
1
vote
1answer
47 views

Distributing Fruit Counting

There are 6 indistinguishable oranges, and 4 unique apples. There are 7 people. How many ways can each person get 1 piece of fruit? Then, say Person A requires an apple, how many ways can this be done ...
0
votes
3answers
42 views

Figuring out the steps in a Recursive Function

I have the following recursive function: $f(0) = 7$ $f(n+1) = f(n) + 6n + 1$ for all integers $n => 0 $ I know the answer is $f(n) = 3n^2 + 2n + 7$ I would like to know the steps to get to this ...
0
votes
2answers
171 views

Counting and probability questions

I am working on some practice midterm problems. The solutions have been given, but I am a bit confused for a couple of them. I would really appreciate any help. Thanks in advance. Note: answers are in ...
2
votes
3answers
759 views

Give a combinatorial argument to show that C(n,k) = C(n,n-k)

What is combinatorial argument and how can i prove this equation ? As far i understand i think we have to apply the Chu-Vandermonde identity but i am not sure if thats right or not. ...
1
vote
2answers
8k views

In how many ways can 20 identical balls be distributed into 4 distinct boxes subject?

I was practicing math exercises on text book and i got stuck in this question ? ...
4
votes
1answer
171 views

How many answers to this combinatorial puzzle?

Take a square. How many ways are there to draw or not draw a line from the center to each of its sides? 16, of course. Here are all the different squares: Now, how many ways are there to put ...
4
votes
1answer
266 views

Issue concerning enumerating vertices in a prism (number of two adjacent vertices can only differ by a certain amount)

There are 100 vertices in a prism with a 50-gon as its base. Those vertices are assigned integers 1 to 100 (inclusive) in a random order. Each number can only be assigned once. The objective is to ...
0
votes
1answer
260 views

Partition a set into 2 subsets

I was dealing with this problem: Consider the set $S=\{1,2,3,\dots,100\}$. We construct two subsets $A$ and $B$ with $10$ elements each, such that the elements of $A$ are all smaller than the ...
0
votes
1answer
20 views

Basic Combinatorics and Counting

I'm thinking that the number of ways to seat 5 people in 8 chairs is the same as the number of ways to seat 8 people in 5 chairs. For 5 people in 8 chairs: ${8\choose{5}}5!$ ways. Choose the 5 ...
2
votes
2answers
370 views

Distribute n distinct objects groups to distinct recepeints

Formula for distributing n distinct objects to $r$ distinct recipients: $n^r$ Formula for distributing n identical objects to $r$ distinct recipients: $\binom{n+r-1}{r-1}$ What is the formula for ...
0
votes
1answer
25 views

What is the probability of getting three “top cards” in the same suit and two cards in another suit (but both in the same suit)?

Jack, Queen, King and Ace are the top cards. What is the probability of getting three top cards in the same suit and two cards in another suit (but both in the same suit)? This has stumped me for ...
1
vote
2answers
62 views

Number of distinct decompositions

Given an integer $m$ as a product of integers $a_1,a_2,\ldots a_n$ I need to find the number of distinct decompositions of number $m$ into the product of $n$ ordered positive integers. Example: If ...
0
votes
1answer
91 views

combinatorics :: selecting from variety of groups

in how many ways one or more than one fruit can be selected from 6 varieties of fruits given that there are 5 fruits of each variety? MY TRY : i dont have any clue so i am giving my thoughts MY ...
1
vote
4answers
85 views

issues with probability

a man has $4$ children, given that atleast one of whom is a girl.Find the probability that he has $3$ girls and $1$ boy. MY TRY : probability of girl=$1/4$ and probability of boy=$3/4$ (my doubt is ...
0
votes
1answer
307 views

Suppose you choose 5 cards from a standard 52 card deck

How many different choices of cards are possible if all $5$ cards must be diamonds?
2
votes
0answers
46 views

Least amount of people such that two are neither friends nor have any common friends

In a group of $m$ people each person is friends with exactly $n$ other persons, $m \gt n$. $k$ people are arbitarily chosen. What is the lowest possible value of $k$ such that we can be completely ...
1
vote
0answers
204 views

Card combinatorics problem

Suppose we have a standart deck of cards. It is fixed and can have maximally 52 cards, but may be less. Also we have several subsets of this deck, each subset consist either of all cards of the same ...
0
votes
0answers
60 views

Summing a particular product of binomial coefficients

I expect this is elementary, but I can't find a closed form. Let $a_i$, $i=1,...,m$, be a sequence of natural numbers and $n>\sum a_i$. What is the value of the sum: ...
0
votes
1answer
34 views

Is the “or” in Ramsey Theory exclusive?

The Ramsey number, $R(n,m)$ is defined to be the order(number of vertices) of the smallest complete graph $G$ such that for any red-blue colouring of $G$ there is a red $K_n$ \emph{or} a blue $K_m$; ...
0
votes
1answer
38 views

Arranging numbers

First things first, this is my first post and I might not add the right tags and the title might not help me very much, please feel free to add tags or change the title if mod thinks this is too ...
0
votes
1answer
55 views

Expected number of events using a multiset

Consider events A, B, C, and D with probabilities of $1/6$, $1/2$, $1/12$, and $1/4$ respectively. A, B, C, and D are independent and mutually exclusive. I am looking at sequences involving A ...
0
votes
2answers
25 views

Counting the number of numbers that can be formed

How many ways can I arrange the digits 1,2,3,4,5 in such way that I can form 10 digit numbers? number can be repeated: 1111111111 is allowed 2222233321 is allowed too. I know how to do it if it is ...
3
votes
3answers
597 views

Pigeonhole Principle to Prove a Hamiltonian Graph

I am trying to figure out if a graph can be assumed Hamiltonian or not, or if it's indeterminable with minimal information: A graph has 17 vertices and 129 edges. ...
1
vote
1answer
27 views

Partioning Mystery

Who has the wisdom to answer the following: 9 distinct marbles distrubted into 4 distinct bags with each bag receiving at least 1 marble,how many ways can this be done? Thankyou for contributing! ...
2
votes
2answers
92 views

How do I calculate permutations where some values are restricted?

I am curious about the formula for determining the number of combinations there are in a given set where some values are restricted to a certain range. For example, if I have a 10 character, ...
0
votes
3answers
56 views

Combinatorics: negative binomial coefficent

We've been asked to prove an identity using binomial coefficients, but there's a negative fraction and im not sure how to solve it. I saw a similar post that helped and I wanted to know what you would ...
0
votes
0answers
82 views

Summing the product of combinations of matrix elements

I have a situation where I have an $NxN$ matrix $A$ where each element $a_{i,j}\in\mathbb{R}_{\leq 0}$. I would like to consider the set of all collections of elements such that each collection of $N$ ...
0
votes
1answer
68 views

Effcient Box packing algorithm

I have 10 boxes, and each box can hold items. I also have 5 different types of objects. Each item can hold 2 objects. No box can hold more then 1 of the same object, but it is possible for it to hold ...
1
vote
5answers
3k views

Proof of a binomial identity $\sum_{k=0}^n {n \choose k}^{\!2} = {2n \choose n}.$

Prove that $$\sum_{k=0}^n {n \choose k}^{\!2} = {2n \choose n}.$$ The exercise provides the following hint: $\,\,\displaystyle{n \choose k}={n\choose n-k}$. Any help?
3
votes
1answer
594 views

Distributing $n$ different things among $r$ persons

How can $10$ different pencils be distributed among $3$ students? MY TRY $1$ total ways $= 3^{10}$ MY TRY $2$ $10 \times 9 \times 8 =720$ Which one is correct? If both are wrong what is correct ...
0
votes
2answers
73 views

Permutation Homework

There are two teams.Two games were played.There are three possible outcomes which are win, lose or draw. how many permutations are there?
1
vote
1answer
28 views

Proxy optimisation problem

Suppose we have a set of participants $p$ who should attend $e$ number of events and everyone of them must declare his presence with signature. Each can however sign for $s$ number of other ...
0
votes
2answers
80 views

Combinatorial Inequality

For any integer $n>1$ prove that, $$\large 2^n < {2n \choose n} < \frac{2^n}{\prod^{i=n-1}_{i=0}(1-\frac{i}{n})}$$ Now proving that the first term is smaller than the third term is ...
0
votes
2answers
163 views

Prove Stirling's Formula: $n!=\kappa n^{n+1/2}\exp\bigg(-n+\dfrac{\theta(n)}{12n}\bigg)$

Prove Stirling's Formula, i.e. $n!=\kappa n^{n+1/2}\exp\bigg(-n+\dfrac{\theta(n)}{12n}\bigg),$ where $1-\dfrac{1}{12n+1}\le\theta(n)\le 1$ and $\kappa=\sqrt{2\pi}$. I tried to do it by ...
1
vote
1answer
53 views

identity proof by using combinatorics method

How can i prove that $\sum_{k=0}^p \binom{m-(k+1)}{p-k}= \binom{m}{p} $? Of course I can use induction here but it's not very nice solution. Right hand side of equality is choosing $p$ people from set ...
0
votes
1answer
95 views

Given a random bit string with length 15. Let event A be an even number of 1's and B be no consecutive 1's?

How do I find the probability of this? I'm completely lost... I just need P(A) and P(B)
0
votes
3answers
301 views

In a bit string of length 11, how do you find the probability of even number of zeros?

I thought about doing the complement but I wasn't sure if that was correct. Or add up the different cases that there is an even number of 0's as the probability?
0
votes
2answers
6k views

Outcome possibilities with three teams and three outcomes for each game

So there are six teams (let's say: 1,2,3,4,5,6), and they pair up to face each other, (so three games in total). In each game, one team either wins or their is a tie. Let's set up the teams and their ...