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

0
votes
1answer
20 views

Counting number of two pair hands in poker (not standard)

I was doing number counting problem and wanted to check if my result was correct. Problem description: From a standard deck of cards(52 cards, 4 suits, 13 numbers in each suit) there are 5 cards ...
0
votes
1answer
21 views

show existence of subsequence $\{a_{i_b}\}_b^{n+1}$

Suppose $\{a_n\}_{n=1}^{m^2+1}$ is a strictly increasing sequence of $n^2+1$ positive integers, show that there exist a subsequence $\{a_{i_b}\}_b^{n+1}$ of length $n+1$ such that $a_{i_k}$ is ...
0
votes
1answer
66 views

Please explain this explanation to me; Discrete Math: Counting

This is a counting solution to which selections of object which are not all distinct. The basic premise is that the number of non-negative integer solutions to $x_1+x_2+x_3+...+x_k = n$ is equal to ...
0
votes
1answer
18 views

Number of ways for a k-letter word to have no repeat letters.

Assuming a standard English 26-letter alphabet, and $k<26$, what's the number of $k$-letter words where the letters don't repeat? So for example 'house' has no repeat letters, while 'rolls' has a ...
0
votes
2answers
29 views

Understanding a combinatorial relation.

I would like some insight as to why the following expression is true. $$\sum_{i=0}^n {{n}\choose{i}} 2^{n-i} = 3^n $$ I arrived at this relation in solving a subset problem, and I understand the ...
0
votes
0answers
12 views

What is a combinatorial structure?

I keep seeing the phrase used but unlike with algebra, topology, measure, etc., it's not obvious what sort of "structure" allows combinatorics to be performed on a set.
0
votes
1answer
36 views

Where did I go wrong in this combanitorics question?

The question is as follows: A fancy bed and breakfast inn has $5$ rooms, each with a distinctive color-coded decor. One day $5$ friends arrive to spend the night. There are no other guests that ...
1
vote
1answer
51 views

Find $a_{n}$ from a convolution formula

Suppose that $c_{n}$ satisfies the recurrence formula below: $c_2=\alpha$, and $$c_{2n}+c_{2n-2}=\frac{(\alpha)_n}{n!},n\geq2.$$ were $(\alpha)_n = \alpha(\alpha-1)·\cdots·(\alpha-n+1)$ and $\alpha$ ...
0
votes
0answers
25 views

How to denote combinations of differences?

Let $ \mathcal{A} $, $ \mathcal{B} $ and $ \mathcal{C} $ be sets defined by $ \mathcal{A} = \{ A_k \} $, $ \mathcal{B} = \{ B_k \} $ and $ \mathcal{C} = \{ C_k \} $ where $ k \in \{1 , 2 , \ldots , ...
0
votes
2answers
62 views

Proving $\phi(m)|\phi(n)$ whenever m|n

Show that $\varphi(m)|\varphi(n) $ whenever m|n. I am stuck after writing the formula. I know that if m divides n, that means one of the prime factors of n would include m or a multiple of m. ...
1
vote
1answer
24 views

Number of possible sequences with at most 2 repetitions and entry $a_i \in\{1,2,3,\dots,i\}$

We denote the first $k$ natural numbers (not including 0) by $N_k = \{1,2,3,4,\dots, k\}$. Consider a length $n$ sequence, $S=(s_1,s_2,s_3,\dots,s_n)$ such that $s_1 \in N_1$, $s_2 \in N_2$ and more ...
1
vote
2answers
24 views

Alternating sum of a part of a row of Pascal's triangle

$\displaystyle \sum_{r=0}^m(-1)^r{n \choose r}=(-1)^m{n-1 \choose m}$ if $m$ is less than $n$. This question actually consists of two part that is when $m$ is less than $n$ and when $m$ is equal to ...
0
votes
1answer
32 views

The number of $p$-subsets of an $n$-set is $n$ choose $p$

I want to show that the number of subsets of cardinality $p$ of a set $E$ of cardinality $n$ is ${n \choose p}$. I've read a proof that I couldn't understand it basically says that for any injection ...
1
vote
2answers
23 views

How many ways are there to place 24 people into two treatment groups?

How many ways are there to place 48 people into two treatment groups? I thought the answer was (48 choose 24) because two treatment groups means that there will be 24 people in each group. However, ...
1
vote
0answers
23 views

Estimate for the co-volume of discs centered at lattice points in the plane?

Suppose I have a unimodular lattice $\Lambda = A \mathbb{Z^2}$ ($A\in SL(2,\mathbb{R})$) in the plane. I place a disc of fixed radius, $r$, around each point of $\Lambda$, so that I have a union of ...
2
votes
1answer
32 views

Forming a sequence from a given set

28 random draws are made from the set {1,2,3,4,5,6,7,8,9,A,B,C,D,J,K,L,U,X,Y,Z} containing 20 elements. In each draw, one element from the set is drawn with replacement. What is the probability that ...
1
vote
1answer
34 views

How many dice do you have to roll to get your odds of seeing each face at least once equal to 0.5?

In a pub the owner is throwing a number of dice simultaneously. "I am trying to get one of each of the six faces", he says, "But it hasn't happened yet". "No", I said "You need at least four more dice ...
5
votes
1answer
20 views

counting combinations of {+1, -1} with constraints

I'm trying to count the number of ways of arranging a sequence of length $N+2L$ made of "$+1$" and "$-1$", with the following two conditions: 1) the total has to sum to $N$ 2) no partial sum is ...
1
vote
1answer
15 views

estimates for the largest disc not intersecting a unimodular lattice?

Are there any nice estimates for the size of the largest disc (centered anywhere) not intersecting a unimodular (i.e. covolume = 1) lattice in the plane? Maybe estimates in terms of the shortest ...
1
vote
1answer
81 views

Divide N Hot dogs among M persons

There are N hot dogs and M people and we need to divide the hot dogs equally. Now we need to calculate the minimum number of cuts required to distribute the hot dogs equally. In order to divide the ...
1
vote
4answers
48 views

Number of pizza topping combinations

It seems there are lots of pizza questions but I'm not sure how to apply the answers to my problem. Obviously I'm not a mathematician. Essentially I'm trying to determine how many different ...
1
vote
1answer
49 views

Count ways to form isosceles triangles

Their are N persons sitting on a table with N vertices.We need to count the number of isosceles triangles formed such that each vertex of the triangle is a vertex of the table and all persons seating ...
1
vote
3answers
45 views

Is there a closed form for a sum $nPk +(n-1)Pk + (n-2)Pk + … + kPk$?

I would like to know if there is some closed form to solve for a sum in the form: $nPk +(n-1)Pk + (n-2)Pk + ... + kPk$ For instance, if $n=7$ and $k=2$: $7P2 + 6P2 + 5P2 + ... + 2P2$ = ...
1
vote
3answers
42 views

Race Problem counting

In a race there are n horses.In the race more than one horse may get the same position. For example, 2 horses can finish in 3 ways. Both first horse1 first and horse2 second horse2 first and horse1 ...
0
votes
2answers
31 views

All solution of some equation [duplicate]

Let $A=\{(m,n)\in\mathbb{N\times N}:m\neq n \text{ and } m^n=n^m\}$. It is clear that $(2,4),(4,2)\in A$. What is the solution of this equation ?
-4
votes
0answers
42 views

Prove $ {n \choose k} = {n! \over k!(n-k)! } $ by Pascal fourmla [on hold]

Let $\ {n\choose k}=1$ for $k=0$ or $k = n$ , and $${n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}\ for\ n \geq 1 $$ Prove that $$ {n \choose k} = {n! \over (k!)(n-k)!}\ \text{for} \ n \geq 1\ ...
5
votes
1answer
47 views

Two sequences $a_{2n}=a_n+1, a_{2n+1}=a_{n}+2$ and $b_{3n}=b_n+1, b_{3n+1}=b_n+2, b_{3n+2}=b_n+3$

Let us consider two sequences $$a_{2n}=a_n+1, a_{2n+1}=a_{n}+2, a_1=1,a_2=2$$ and $$b_{3n}=b_n+1, b_{3n+1}=b_n+2, b_{3n+2}=b_n+3, b_1=1,b_2=2,b_3=2.$$ Prove that $a_{2^n} < b_{2^n}$ for ...
0
votes
1answer
23 views

Counting — Placing 5 balls into 3 boxes

Five balls are numbered 1 to 5. Three boxes are numbered 1 to 3. How many distinct ways can the balls be put in the boxes if two boxes have two balls each and the other box has the remaining ball? ...
1
vote
1answer
130 views

Is there software I can use to draw this graph?

So, I have this particular graph to consider. It has the vertex set $\{1,...,17\}$ and edge set $\{(i,j)|i+j ~\mbox{is prime}\}$. Define a cost function $c:E(G)\mapsto \mathbb{R}$ by setting ...
3
votes
1answer
31 views

Explaining the coefficients of matching polynomials

Matching polynomials are generating functions that tells us the number of $k$-matching (meaning choosing of $k$ independent/non-adjacent edges) in the graph say $G$. Farrell et al., "On matching ...
-1
votes
1answer
17 views

How many matches in a 5-team tournament? [closed]

There will be 5 teams playing in the National Table Tennis Tournament. Each team plays against every other team once. How many matches are scheduled for the tournament?
1
vote
1answer
42 views

Number of derangements where first m numbers are fixed points

Let $m,n \in \mathbb N$ with $m<n$. Find, in terms of $D_{k}$'s the number of derangements $a_{1},a_{2},...a_{n}$ of $\mathbb N_{n}$ such that {$a_{1},a_{2},...a_{m}$} = {$1,2,...,m$}. My ...
1
vote
1answer
46 views

Numbers fulfilling a certain condition in a range of numbers [on hold]

A year is a leap year if it is either (i) a multiple of 4 but not a multiple of 100, or (ii) a multiple of 400. For example, 1600 and 1924 were leap years while 2200 will not be. Find the number ...
0
votes
1answer
91 views

Combinatorics: ways to place books

So we're trying to partition {1..n} into m ordered sets. I would do this by first scrambling {1..n} into one of n! orderings. After having done that we can partition that into m non-empty sets in ...
2
votes
1answer
65 views

Solving a Binomial Recurrence

Related to this problem: Expected Homogenization Time When calculating the expected number of iterations for that problem, in terms of $N$, I get the recurrence ...
1
vote
1answer
30 views

Random distribution of colored balls into boxes.

This is an abstraction of a real problem I have: I have a large number of balls that are either Red or Blue ($n = 9*10^7$) and a bunch of containers ($c = 3*10^7$). I've calculated that the ...
1
vote
1answer
10 views

Expected Homogenization Time

Assume we have $N$ boxes, and each box contains one red sock and one blue sock. We can then perform the following process: randomly take one sock from each box and replace it with a red sock. What is ...
1
vote
0answers
23 views

Sampling from Cartesian product without replacement, but with balanced totals

I am struggling with a combinatorial task that I cannot reduce to any procedure I know: Given two sets $F, G$, I want to sample from $F \times G$ without replacement, but subject to the condition that ...
5
votes
0answers
63 views

Double factorial as a sum

I believe the following equality to hold for all integer $l\geq 1$ $$(2l+1)!2^l\sum_{k=0}^l\frac{(-1)^k(l-k)!}{k!(2l-2k+1)!4^k}=(-1)^l(2l-1)!!$$ (it's correct for at least $l=1,2,3,4$), but cannot ...
0
votes
0answers
19 views

Combinatorics Summation Simplification [duplicate]

I am at a loss for how to approach simplifying the following combinatorics summation. I assume some method using summation formulas and combinatorial identities is required. $$\sum_{c = ...
0
votes
1answer
53 views

Conditions for equality of two binomial sums

Let $k,r,n$ be integers such that $0<k,r<n$. Let $$K=\sum^n_{i=k}k^{n-i}\binom{n-k}{i-k}^2k!(i-k)! \,\text{ and }\, R=\sum^n_{i=r}r^{n-i}\binom{n-r}{i-r}^2r!(i-r)!.$$ How to show that ...
0
votes
2answers
46 views

Combinations and Permutations: Number of ways of taking out 1 $ bills

Can A has N 1 $ bills. Can B is empty. At each step you can either take a bill from can A or put a bill you already have into can B. You can choose to keep some bills in your hand and take some more ...
0
votes
5answers
48 views

Combinatorial argument for the sum of the first $n$ integers.

Can someone give a combinatorial argument (at least for $\binom{n+1}{2}$) for why $\binom{n+1}{2}=(n^2+n)/2$?
1
vote
1answer
29 views

Finding minimum value of a trigonometric expression

If $A+B+C=\pi$ then what is the minimal value of $$\tan^{2}A/2+\tan^{2}B/2+\tan^{2}C/2$$
2
votes
0answers
30 views

What happens to the number of maximal cliques (and their size) as you delete one edge at a time from a complete graph?

Say one has a complete graph with 1 giant clique. As we delete an edge from it at a time, the number of maximal cliques might increase or at least, the size of the maximal clique has to decrease by ...
1
vote
2answers
73 views

multiplication rule questions - 7 people attending a concert

7 people are attending a concert. (a) In how many different ways can they be seated in a row? (b) Two attendees are Alice and Bob. What is the probability that Alice sits next to Bob? (c) Bob ...
0
votes
0answers
30 views

Probability of a number of weighted items being allocated to the same bin

I have the following (probably classic) combinatorics problem: There are $n$ bins that can hold $k$ items each, and a total of $r = n\,k$ items. The items have weights $w_1 > w_2 > \dots ...
2
votes
1answer
36 views

Finding number of 10 digit numbers

A ten-digit number is to be made using the digits from the set $\{0,1,2,3,4\}$ such that the difference between any two consecutive digits is either $1$ or $-1$. How many such numbers can be made?
0
votes
1answer
22 views

How many ways to choose at least one piece of fruit from 9 apples and 6 oranges

I am wondering if someone can explain the reasoning behind the solution my book gives me to the following problem: How many ways are there to pick some pieces of fruit from 9 oranges and 6 apples if ...
1
vote
1answer
29 views

Combinatorics problem involving multinomial theorem

here is my problem: 4 digits are picked randomly (from 0 to 9), in how many combinations can you have only 2 different digits? Meaning that I would have let us say 2,2,4,4 or 5,5,5,8. So the ...