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)

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
762 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
172 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
263 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
86 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
601 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
598 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
164 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
302 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 ...
0
votes
2answers
91 views

Prove the identity $\sum_{{{\underset{k-even}{k=0}}}}^{n}{n \choose k}2^{k}=\frac{3^{n}+(-1)^{n}}{2}$

I need to prove the following identity: $\sum_{{{\underset{k-even}{k=0}}}}^{n}{n \choose k}2^{k}=\frac{3^{n}+(-1)^{n}}{2}$ I know that - $\sum_{k=0}^{n}{n \choose k}2^{k}=3^{n}$ but don't know ...
2
votes
1answer
38 views

Little combinatorics excersise

If $n$ is an odd number, determine the number of numerical palindromes of $n$ digits that contains at least two zeros. Then I considered: $(a,b,a) \rightarrow 10$ possibilities $(a,b,c,b,a) ...
0
votes
2answers
59 views

Calculating of the sum

I'm trying to found this sum:$\sum_{i=0}^m\left(\begin{array}{cccc}m\\i\end{array}\right)\cdot (-1)^i\cdot i^m$. I calculated this sum for small value of $m$ and realized that it's equal to ...
1
vote
1answer
24 views

Little equivalence-relation problem

If $U=\{1,2,\ldots,1000\}$ and $A = \mathbb P(U) - \{ \emptyset \}$, the following relation $R$ is defined in $A$ $$XRY \Leftrightarrow (\min X = \min Y) \wedge (\max X = \max Y)$$ Calculate ...
2
votes
3answers
58 views

Relations and Combinatorics exercise

Be $A=\{1,2,3,\ldots,10\}$ Determine how many equivalence relations can be defined in $A$ with exactly two equivalence classes. Determine how many equivalence relations can be defined in $A$ with ...
1
vote
2answers
252 views

Formulating a simple combinatorics problem in a 3x3 grid

I have a 3x3 grid, and I want to move from a point A in the left corner below, to a point B in the right corner above. I can move 2 times horizontally, and 2 times vertically. The number of paths that ...
2
votes
3answers
94 views

Is there only one counter example in $K_5$ for $R(3,3)$?

Title says it all. And the one that I know is below. (image from wikipedia) My question is: Is there only one counter example in $K_5$ for $R(3,3)$ where $K_5$ is a complete graph of 5 points and ...
1
vote
1answer
26 views

How to compute the number of n-element combinations of non-negative integers with a given sum?

The title has the general form of the problem, but I'd also welcome insight into the following specific case: how many sets of five non-negative integers exist having a sum of 20? I've tried breaking ...
1
vote
1answer
115 views

Game Of Strings

There are two strings A and B. Initially, some strings A’ and B’ are written on the sheet of paper. A’ is always a substring of A and B’ is always a substring of B. A move consists of appending a ...
0
votes
1answer
85 views

Covering a $8\times 8$ chessboard with dominoes without placing any domino over another.

In how many ways can $8\times 8$ chessboard be with dominoes without placing any domino over another. I have this problem in my mind since I read colouring proofs. This question has been ...
3
votes
2answers
326 views

Combinatorics: binomial coefficient with negative fractions

We've been asked to prove an identity using binomial coefficients, but there's a negative fraction involved and I'm not sure what to do. Prove that $${-1/2 \choose n} = (-1/4)^n {2n \choose n}$$ I ...
1
vote
1answer
65 views

Finding generating function for product of two sequences [duplicate]

If I know generating funcions for sequences $$A: a_0, a_1, a_2, a_3, a_4, \dots$$ and $$B: b_0, b_1, b_2, b_3, b_4, \dots$$ and I want to find a new generating function for $$C: a_0b_0, a_1b_1, ...
1
vote
2answers
38 views

Partioning/Enumeration

How many ways can one distribute A) 15 Balls into 3 bags. Both bag and balls are distinct (labelled) and each bag must contain at least one ball. B) 10 balls into 3 bags. again both bag and balls ...