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
43 views

combinatorics & probability problem

There are numbered cards 1 to 13 each of colour red, green, yellow and white. And four players have been distributed 4 each of these cards randomly. What is the probability that each player gets ...
3
votes
1answer
43 views

How can I show the cardinality of the set $A_m=\{\alpha\in\mathbb N_0^n: |\alpha|\leq m\}$ is $\#A_m=\binom{m+n}{m}$?

Let $\mathbb N_0=\mathbb N\cup \{0\}$. An element of $\mathbb N_0^n$ is called a multi-index. In $\mathbb N_0^n$ consider the set $$A_m=\{\alpha\in\mathbb N_0^n: |\alpha|\leq m\},$$ where ...
2
votes
2answers
75 views

Combination small challenge problem

How many ways can 3 different Scientific Groups be formed using 5 students such that Each student is at least be a member of one committee and each two committee has exactly 2 students in common? I ...
1
vote
1answer
36 views

Iterate through n coins flipping these obtaining all possible combinations.

If I have let say n coins all facing the same way. Is there an iterative method for turning these coins, one at a time, until all possible combinations have occurred one and only one time? This is ...
0
votes
2answers
161 views

number of combinations of ordered sequences of N integers

suppose a N-tuple of N integers, such that every element in the tuple is bigger than or equal to the last one and each element in the sequence ranges from 1 to K. Is there any closed formula for the ...
1
vote
0answers
69 views

Need help with these recurrence relations

I had received some challenging recurrence last week, I did most of them except this and also one of its kind. It states Given $a_0=0$ and $a_1=1$, solve these recurrence relations: ...
4
votes
2answers
74 views

How to evaluate the sum $\sum_{k = 0}^{n}2^k {{n}\choose {k}}$ [duplicate]

How do I evaluate the sum: $$\sum_{k = 0}^{n}2^k {{n}\choose {k}}$$ I know that $2^k = {n \choose 0} + {n \choose 1} + {n \choose 2} + {n \choose 3}... {n \choose k}$, but I don't know how to proceed ...
1
vote
1answer
21 views

Block walking and Pascal's Triangle

This is quoted text from a math book: The key to block walking is to imagine taking a walk on Pascal's Triangle. Starting at $0\choose0$, we proceed strictly downward along the lines drawn in the ...
1
vote
1answer
16 views

Proving an identity involving binomial coefficients and fractions

I've been trying to prove the following formula (for $n > 1$ natural, $a, b$ non-zero reals), but I don't know where to start. $$\sum_{j=1}^n \binom{n-1}{j-1} \left( \frac{a-j+1}{b-n+1} \right) ...
0
votes
1answer
35 views

Estimating number of customers

I'm trying to analyze a simple model for businesses. I'm not sure if the problem I'm having is with notation. There seems to be some discrete structure I don't understand how to write down or ...
1
vote
1answer
46 views

Combinatorics problem with repetition…

Ten different people walk into a delicatessen to buy a sandwich. Four always order tuna fish, two always order chicken, two always order roast beef, and two order any of the three types of ...
2
votes
3answers
54 views

Proving $k\binom{n}{k} = n\binom{n-1}{k-1}$

Prove that $$k\binom{n}{k} = n\binom{n-1}{k-1}$$ is true for all integers $n, k$ with $0 \leq k \leq n$. Would this be enough to prove this? $$\binom nk=\frac{n!}{k! ...
1
vote
2answers
38 views

Generating function satisfying a second degree equation

I got this problem in an exercise list: Let $G(x)$ be the generating function of the numeric sequence $(C_n; n \geq 0)$ satisfying the recurrence equation: $$C_n = \sum_{k=0}^{n-1}C_kC_{n-k-1}, ...
2
votes
1answer
26 views

Binomial thereom to figure out coefficents

Use the binomial theorem to find the coefficient of $x^8y^5$ in $(x + y)^{15}$ My textbook shows how to do this looking at the coefficents of Pascal's triangle but, I know theres another way using ...
2
votes
1answer
17 views

Splitting 2 different objects across 3 people with additional properties

Sorry for somewhat vague title, but I really couldn't explain it any further in the title alone.. Here goes the problem: Joe, Bob and Smith need to split pencils and erasers. In how many ways Joe, ...
2
votes
3answers
19 views

Solution check for counting in a list

This problem involves lists made from the letters T,H,E,O,R,Y, with repetition allowed. How many 4-letter lists are there that don’t begin with T, or don’t end in Y ? Just want to make sure my ...
0
votes
0answers
36 views

two correlated process

I apologize if this question is not placed in the right place. But I am having a hard time to figure it out. It would be greatly appreciated if some one could help me out. Assume that there are two ...
-1
votes
1answer
53 views

Intermediate Counting Question

Two Americans, two Canadians, two Mexicans, and two Jamaicans are seated around a round table. People from the same country are distinguishable. In how many ways can all eight people be seated such ...
1
vote
0answers
36 views

Variations of M,n,k-games

I just read about M,n,k-games and wondered if the following variation (with fixed $k$) has been studied as well and if there exists a name for it: Two players consecutively mark elements of ${\bf Z}$ ...
0
votes
1answer
15 views

Differnce between circuits in graphs

Given a full undirected graph with 3 vertices: $v1, v2, v3$ and $3$ edges. Is there any differnce between those 2 cycles: $C1: v1-{(e1)}-v2-{(e2)}-v3-{(e3)}-v1$ $C2: ...
0
votes
0answers
52 views

Probability with dice sum K

Alice rolls a N faced die M times. she adds all the numbers she gets on all throws. What is the probability that she has a sum of K. A N faced die has all numbers from 1 to N written on it and each ...
1
vote
1answer
70 views

Count pairs with odd XOR

Given an array A1,A2...AN. We have to tell how many pairs (i, j) exist such that 1 ≤ i < j ≤ N and Ai XOR Aj is odd. Example : If N=3 and array is [1 2 3] then here answer is 2 as 1 XOR 2 is 3 ...
1
vote
3answers
79 views

4 heads in 8 tosses

If someone asked me the odds of getting 4 heads in 8 flips of a fair coin. I would initially think to do something like this: $\dfrac{2^8 - \left( \binom{8}{0} + \binom{8}{1} + \binom{8}{2} + ...
0
votes
1answer
28 views

Multiset questions requested

I am in need of more multiset questions. Would anyone have any combinatiorics questions that deal with multisets? I've been look around on Google, but haven't really found any.
2
votes
1answer
35 views

Partitioning into groups with maximal mixing

Suppose I have a class of 30 students and I want to give them 8 assignments to do in groups of 3. As far as possible I'd like the students to work with as many different students as possible. Ideally ...
2
votes
0answers
31 views

Probability that half the nodes has more than half out-degree

This is something I just wondered about, and I don't know whether there is a closed-form answer or not. I've tried but without making progress, so any idea would be helpful. Consider a complete graph ...
6
votes
1answer
140 views

My fun conjecture about linearly independence

In the $\mathbb{R}^n$ vector space, there are distinct $m$ vectors $v_i$'s ($1< i\leq m)$ such that each component has value 0 or 1. Let $A_i$ be the set of $j$'s where $j$-th component of $v_i$ ...
1
vote
0answers
25 views

resilience of graphs question

The following is a definition of the resilience of a graph w.r.t to a property $\mathcal{P}$ (Local resilience) A property $\mathcal{P}$ is said to be monotone if the property is preserved under ...
3
votes
1answer
59 views

What is the joint probability distribution of number of balls after $n$ draws?

The following problem came into my mind when I am studying the Polya Urn Model. At the beginning, from a bin containing $c_1$ balls labeled $1$, $c_2$ balls labeled $2$, … , $c_m$ balls labeled $m$, ...
0
votes
3answers
64 views

Inclusion-Exclusion Principle for basic combinatorics problem…

How many ways are there to pick five people for a committee if there are six (different) men and eight (different) women and the selection must include at least one man and one woman? I know ...
2
votes
0answers
41 views

Number of queries required to find the function.

this is a slight variation to question $3$ of the Nordic mathematical olympiad of 2010.(in short that one deals with bijections and this one deals with any kind of function).We have 2010 buttons and ...
0
votes
2answers
46 views

SAT Math probability and repeats

A ball's area is divided into two sections. If each section is to be painted using one of 5 different colors, how many differently painted designs are possible? I know that the first area has 5 ...
0
votes
1answer
32 views

Distance Transitive Graph Property

Asked this over in math overflow and have refined the question a bit. I'm working on trying to show this, but can't seem to get a proof methodology worked out. No guarantees that it is true, but ...
0
votes
0answers
57 views

2 player team knowing maximum moves

Given a list of N players who are to play a game. Each of them are either well versed in a move or they are not. Find out the maximum number of moves a 2-player team can know. And also find out how ...
0
votes
1answer
23 views

Number of particular terms in a product

I hope this question is not too stupid, but I know very little about combinatorics and i can't find an answer.. So fix $r\in \mathbb{N}$. Let $x_1,\ldots, x_r$ be variables, let the product between ...
1
vote
1answer
53 views

52-card deck probability…

If 13 players are each dealt four cards from a 52-card deck, what is the probability that each player gets one card of each suit? So I chose to do the situation where we have no repetition (i.e ...
2
votes
2answers
56 views

Equivalent definitions for a coloop?

From wikipedia, in a matroid, An element that belongs to no circuit is called a coloop. Equivalently, an element is a coloop if it belongs to every basis. I wonder why the equivalence? From ...
1
vote
3answers
50 views

Missing Numbers in Roulette, Dice, and Other Gambling Devices

Case 1: I roll a die N times. What is the probability that one of the 6 numbers never comes up? The probability that K of the 6 numbers never comes up? Case 2: Same idea, but with a Las Vegas ...
0
votes
1answer
31 views

Counting of the elements in a set

I have an algorithm returning a set of groups from a time series. Be $X$ this time series, made of $n$ points $x_1$ to $x_n$. My algorithm returns from the time series a set of groups G, containig ...
2
votes
3answers
225 views

Combinatorial optimization - Bijections between duplicated numbers

English is not my native language: sorry for my mistakes. Thank you in advance for your answers. Two Bijections and an Array... Here is a 2D array (in this particular example: rows: 1 to 4; ...
0
votes
0answers
23 views

Finding integer vectors in the column space of a matrix

Consider a given set $S \subset Z$. $S$ is a finite set. Matrix $A \in S^{N \times M}$ is also given. Does there exist an algorithm to find all the vectors belonging to the space Col$(A)\cap S^N$ ...
3
votes
0answers
52 views

number of Lattice paths from origin to diagonal after removing vertices

i am stuck with the following problem: consider the quarter plane $\mathbb{N}_0^2$ with vertices $(i,j)\in\mathbb{N}_0^d$ and edges from each vertex $(i,j)$ to $(i+1,j)$ and $(i,j+1)$, i.e. one ...
0
votes
2answers
93 views

Advanced Counting Puzzle

Suppose we have a house in which every room has an even number of doors. Prove that the number of doors from the house to the outside world is also even.
0
votes
1answer
17 views

How do the dependent sets of a matroid characterize the matroid?

Wikipedia says: The dependent sets of a matroid characterize the matroid completely. The collection of dependent sets has simple properties that may be taken as axioms for a matroid. So I ...
1
vote
0answers
28 views

Name for variations of elements from several sets

Consider the set $S=\{1,2,3\}$. As is well known, $(1,1), (1,2), (1,3), (2,1), (2,3), \ldots, (3,3)$ are the variations with repetition of elements of $S$ taken two at a time. We can similarly ...
1
vote
1answer
63 views

Divide and Conquer (recurrence relation problem)…

The problem: (a) Use a divide-and-conquer approach to devise a procedure to find the largest and next-to-largest numbers in a set of n distinct integers. (b) Give a recurrence relation for ...
3
votes
0answers
58 views

A function on sets which is constant for all permutations

Let $U=\{1, 2,\ldots, 2014\}$. For positive integers $a$, $b$, $c$ we denote by $f(a, b, c)$ the number of ordered 6-tuples of sets $(X_1,X_2,X_3,Y_1,Y_2,Y_3)$ satisfying the following conditions: ...
0
votes
2answers
355 views

Finding Coprime triplets

Given a sequence a1, a2, ..., aN. Count the number of triples (i, j, k) such that 1 ≤ i < j < k ≤ N and GCD(ai, aj, ak) = 1. Here GCD stands for the Greatest Common Divisor. Example : Let N=4 ...
3
votes
1answer
60 views

How many orientations are there for pawns (for a single player) on a chess board?

How many orientations are there for pawns on a chess board? Pawns can only move forward or diagonally forward. No two pawns may exist on the same square. Pawns start on the second row, and ...
5
votes
1answer
81 views

Binomial Congruence

How can we show that $\dbinom{pm}{pn}\equiv\dbinom{m}{n}\pmod {p^3}$ for positive integers m and n and p a prime greater than 5? I can do it for mod p^2 but Im stuck here.